当前位置:首页 > 芯闻号 > 充电吧
[导读]LevelDB中的skiplist实现方式基本上和中的实现方式类似。它向外暴露接口非常简单,如下:public:   // Create a new SkipList object that will

LevelDB中的skiplist实现方式基本上和中的实现方式类似。它向外暴露接口非常简单,如下:

public:
  // Create a new SkipList object that will use "cmp" for comparing keys,
  // and will allocate memory using "*arena".  Objects allocated in the arena
  // must remain allocated for the lifetime of the skiplist object.
  explicit SkipList(Comparator cmp, Arena* arena);

  // Insert key into the list.
  // REQUIRES: nothing that compares equal to key is currently in the list.
  void Insert(const Key& key);

  // Returns true iff an entry that compares equal to key is in the list.
  bool Contains(const Key& key) const

private成员变量:


private:
  enum { kMaxHeight = 12 };

  // Immutable after construction
  Comparator const compare_;
  Arena* const arena_;    // Arena used for allocations of nodes

  Node* const head_;

  // Modified only by Insert().  Read racily by readers, but stale
  // values are ok.
  port::AtomicPointer max_height_;   

  // Read/written only by Insert().
  Random rnd_;

一.构造函数

templateSkipList::SkipList(Comparator cmp, Arena* arena)
    : compare_(cmp),
      arena_(arena),
      head_(NewNode(0 /* any key will do */, kMaxHeight)),
      max_height_(reinterpret_cast(1)),
      rnd_(0xdeadbeef) {
  for (int i = 0; i < kMaxHeight; i++) {
    head_->SetNext(i, NULL);
  }
}

重点注意下head_和rnd_的初始化,NewNode方法如下。

templatetypename SkipList::Node*
SkipList::NewNode(const Key& key, int height) {
  char* mem = arena_->AllocateAligned(
      sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
  return new (mem) Node(key);
}

这里为什么是“height-1”详见:LevelDb源码分析之五:skiplist(1)。


new (mem) Node(key)使用了placement new技巧,详见:C++中使用placement new

rnd_是一个Random类型的变量,使用0xdeadbeef进行初始化,Random详见LevelDB源码分析之七:Random

二.插入函数


templatevoid SkipList::Insert(const Key& key) {
  // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
  // here since Insert() is externally synchronized.
  // prev记录的是查询路径,下面需要使用prev来修改新生成结点的指针  
  // prev相当于LevelDb源码分析之五:skiplist(1)中的update
  // 整个流程与LevelDb源码分析之五:skiplist(1)相似,这里不再详细解释
  Node* prev[kMaxHeight];
  // 返回大于等于key的结点或者NULL,原因详见FindGreaterOrEqual的分析
  Node* x = FindGreaterOrEqual(key, prev);

  // Our data structure does not allow duplicate insertion
  // 不允许插入重复的值  
  assert(x == NULL || !Equal(key, x->key));
  // 产生一个随机层数height
  int height = RandomHeight();
  // 如果height大于原最大层数,则更新prev,并更新最大层数
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    //fprintf(stderr, "Change height from %d to %dn", max_height_, height);

    // It is ok to mutate max_height_ without any synchronization
    // with concurrent readers.  A concurrent reader that observes
    // the new value of max_height_ will see either the old value of
    // new level pointers from head_ (NULL), or a new value set in
    // the loop below.  In the former case the reader will
    // immediately drop to the next level since NULL sorts after all
    // keys.  In the latter case the reader will use the new node.
    max_height_.NoBarrier_Store(reinterpret_cast(height));
  }
  // 创建一个待插入的结点x,从低到高一层层插入
  x = NewNode(key, height);
  // 逐层更新结点的指针,和普通链表插入一样 
  for (int i = 0; i < height; i++) {
    // NoBarrier_SetNext() suffices since we will add a barrier when
    // we publish a pointer to "x" in prev[i].
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

插入函数里调用了私有函数FindGreaterOrEqual。FindGreaterOrEqual中完成查询操作,就是向下(level控制)和向右(x控制)移动过程,并不断将经过路径保存到参数prev中。



templatetypename SkipList::Node* SkipList::FindGreaterOrEqual(const Key& key, Node** prev)
    const {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  // 从最高层往下,每层都查找插入位置,当遍历到该层的尾部(x->next[level]==NULL)  
  // 也没有找到比key大的结点时,将该层的最后一个结点的指针放到prev[level]中。  
  // 如果在某层中找到了比key大或等于key的结点时,将该结点之前的那个比key小的结点的指针  
  // 放到prev[level]中。  
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      // Keep searching in this list
      x = next;
    } else {
      if (prev != NULL) prev[level] = x;
	  // 当查到第一层时,有两种情况:
	  // 1.第一层中有满足要求的结点,此时next刚好是不小于key的那个结点
	  // 2.第一层中没有满足要求的结点,此时实际上到了尾部,next=NULL
      if (level == 0) {
        return next;
      } else {
        // Switch to next list
        level--;
      }
    }
  }
}

三.查找函数


查找操作基本上就是调用函数上面的函数FindGreaterOrEqual实现。


templatebool SkipList::Contains(const Key& key) const {
  Node* x = FindGreaterOrEqual(key, NULL);
  if (x != NULL && Equal(key, x->key)) {
    return true;
  } else {
    return false;
  }
}

需要注意的是,LevelDB中没有提供显式的删除节点操作,但实际上是可以删除的,因为当我们插入数据时,key的形式为key:value,当删除数据时,则插入key:deleted类似删除的标记,等到Compaction再删除。


本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

9月2日消息,不造车的华为或将催生出更大的独角兽公司,随着阿维塔和赛力斯的入局,华为引望愈发显得引人瞩目。

关键字: 阿维塔 塞力斯 华为

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布,该公司与Amazon Web Services (AWS)签订了...

关键字: AWS AN BSP 数字化

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V,这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具,可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字: 汽车 人工智能 智能驱动 BSP

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行,同时企业却面临越来越多业务中断的风险,如企业系统复杂性的增加,频繁的功能更新和发布等。如何确保业务连续性,提升韧性,成...

关键字: 亚马逊 解密 控制平面 BSP

8月30日消息,据媒体报道,腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字: 腾讯 编码器 CPU

8月28日消息,今天上午,2024中国国际大数据产业博览会开幕式在贵阳举行,华为董事、质量流程IT总裁陶景文发表了演讲。

关键字: 华为 12nm EDA 半导体

8月28日消息,在2024中国国际大数据产业博览会上,华为常务董事、华为云CEO张平安发表演讲称,数字世界的话语权最终是由生态的繁荣决定的。

关键字: 华为 12nm 手机 卫星通信

要点: 有效应对环境变化,经营业绩稳中有升 落实提质增效举措,毛利润率延续升势 战略布局成效显著,战新业务引领增长 以科技创新为引领,提升企业核心竞争力 坚持高质量发展策略,塑强核心竞争优势...

关键字: 通信 BSP 电信运营商 数字经济

北京2024年8月27日 /美通社/ -- 8月21日,由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字: VI 传输协议 音频 BSP

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上,软通动力信息技术(集团)股份有限公司(以下简称"软通动力")与长三角投资(上海)有限...

关键字: BSP 信息技术
关闭
关闭