leveldb源代码分析系列1.2:skiplist实现

skiplist的实现介绍

leveldb中的 SkipList 是一个模板类,其模板参数的类型分别是存储的 Key 类型和 Comparator 类型。

虽然名字是Key类型,但其实存储了整个entry,只不过 Comparator 只比较了entry的internal_key部分。这份跳表实现不提供删除存储项操作。因为leveldb中的删除操作只是一种特别的插入操作罢了。

和模板类 SkipList 紧密相关的两个辅助类为:作为列表中一项的 Node 类和遍历skiplist的 Iterator 类。

SkipList 采用的是单向列表,因此查找某一项的前一项时会进行一次搜索。

SkipList 有如下成员:

其中 Random 类是产生随机数的实现,用来插入新节点时选择height。其余的成员类型都在之前介绍过,此处不再赘述。

接下来介绍几个非常重要的成员函数, NodeIterator 的很多实现都是对这些函数的封装。

1. FindGreaterOrEqual(const Key& key,Node** prev) const

在各个level寻找key的前一个Node,并将其放入prev[level]中,返回值为大于等于key的第一个Node。

2. Insert(const Key& key)

首先调用 FindGreatorOrEqual 函数,获取各个level上key的前一个Node和大于等于key的第一个Node(实际上由于sequence的唯一性,存储的Node没有相等的)然后通过 NewNode 初始化一个Node x,在各个level插入x。

Node的NoBarrier系列函数是和原子操作相关的函数,此处暂且先不考虑,仅将其作为普通的next指针即可。

3. FindLessThan(const Key& key)

找到key的前一个Node,实现方式类似FindGreaterOrEqual。

Node类中有如下几个成员:

这里的next_只分配了一个元素,这利用了c语言中的一个技巧:通过数组成员实现结构的扩展,在c99标准中叫做柔性数组。详情见链接: https://blog.csdn.net/imxiang... 在SkipList的成员函数NewNode中,根据随机分配的height动态申请内存,最终使得next_拥有动态长度。

Iterator类提供了 Next,Prev,Seek,SeekToFirst,SeekToLast 等函数用来遍历 SkipList 。(Seek:Advance to the first entry with a key >= target)

这个类的实现非常简单,直接阅读源代码即可。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章