菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
53
0

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

原创
05/13 14:22
阅读数 1183

skiplist的实现介绍
leveldb中的SkipList是一个模板类,其模板参数的类型分别是存储的Key类型和Comparator类型。
虽然名字是Key类型,但其实存储了整个entry,只不过Comparator只比较了entry的internal_key部分。这份跳表实现不提供删除存储项操作。因为leveldb中的删除操作只是一种特别的插入操作罢了。
和模板类SkipList紧密相关的两个辅助类为:作为列表中一项的Node类和遍历skiplist的Iterator类。
SkipList采用的是单向列表,因此查找某一项的前一项时会进行一次搜索。
SkipList有如下成员:
image.png
其中Random类是产生随机数的实现,用来插入新节点时选择height。其余的成员类型都在之前介绍过,此处不再赘述。
接下来介绍几个非常重要的成员函数,NodeIterator的很多实现都是对这些函数的封装。
1.FindGreaterOrEqual(const Key& key,Node** prev) const
在各个level寻找key的前一个Node,并将其放入prev[level]中,返回值为大于等于key的level为0的第一个Node。
image.png
2.Insert(const Key& key)
首先调用FindGreatorOrEqual函数,获取各个level上key的前一个Node和大于等于key的第一个Node(实际上由于sequence的唯一性,存储的Node没有相等的)然后通过NewNode初始化一个Node x,在各个level插入x。
image.png
Node的NoBarrier系列函数是和原子操作相关的函数,此处暂且先不考虑,仅将其作为普通的next指针即可。
3.FindLessThan(const Key& key)
找到key的前一个Node,实现方式类似FindGreaterOrEqual。
image.png

Node类中有如下几个成员:

Key const key;
std::atomic<Node*> next_[1];

这里的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)
这个类的实现非常简单,直接阅读源代码即可。

发表评论

0/200
53 点赞
0 评论
收藏