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

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

Image placeholder
LoveCode
未设置
  53人点赞

没有讨论,发表一下自己的看法吧

推荐文章
leveldb源代码分析系列1:MemTable的实现

MemTable及其实现这是一个第零层的主题,预计扩展如下第一层主题:1.1comparator介绍1.2skiplist实现介绍1.3数据压缩相关介绍1.4Put流程1.5Get流程leveldb中

leveldb源代码分析系列1.1:memtable中comparator的实现

leveldb中memtable封装了一个skiplist用来存储真正的数据,跳跃列表的实现一定需要定义存储项的序关系,而在leveldb中这个序关系通过comparator相关类来实现。leveld

Gradle Builds Everything —— Task 实例

上文讲述了Gradle中关于任务的基础概念,本文开始讲述下Task是如何定义的。为了方便,我们的语境分不开Gradle和AndroidGradlePlugin,因此此处不脱离Android环境来介绍G

TPC-C解析系列03_TPC-C基准测试之SQL优化

TPC-C是一个非常严苛的基准测试模型,考验的是一个完备的关系数据库系统全链路的能力。这也是为什么在TPC-C的榜单前列,出现的永远只是大家熟知的那几家在业界有着几十年积累、从关系数据库理论开始发展就

TPC-C解析系列05_TPC-C基准测试之存储优化

TPC-C规范要求被测数据库的性能(tpmC)与数据量成正比。TPC-C的基本数据单元是仓库(warehouse),每个仓库的数据量通常在70MB左右(与具体实现有关)。TPC-C规定每个仓库所获得的

Nebula 架构剖析系列(二)图数据库的查询引擎设计

摘要上文(存储篇)说到数据库重要的两部分为存储和计算,本篇内容为你解读图数据库Nebula在查询引擎QueryEngine方面的设计实践。在Nebula中,QueryEngine是用来处理Nebula

TPC-C解析系列01_TPC-C benchmark测试介绍

作者:阳振坤2019.10导语:自从蚂蚁金服自研数据库OceanBase获得TPC-C测试第一名后,引起了行业内外大量关注,我们衷心的感谢大家对OceanBase的支持与厚爱,也虚心听取外界的意见和建

TPC-C解析系列02_OceanBase如何做TPC-C测试

导语:蚂蚁金服自研数据库OceanBase登顶TPC-C引起业内广泛关注,为了更清楚的展示其中的技术细节,我们特意邀请OceanBase核心研发人员对本次测试进行技术解读,共包括五篇:1)TPC-C基

TPC-C解析系列04_TPC-C基准测试之数据库事务引擎的挑战

OceanBase这次TPC-C测试与榜单上Oracle和DB2等其他数据库在硬件使用上有非常大的不同,OceanBase的数据库服务器使用的是204+3台型号是ecs.i2.16xlarge阿里云E

使用BCC工具分析系统性能

系统管理员可以通过利用BCC(BPFCompilerCollection)库的工具来分析操作系统性能和获取操作系统信息。BCC介绍BCC工具全称BPFCompilerCollection(BCC),是

笨办法学 Linux Bash:Shell、`.profile`、`.bashrc`、`.bash_history`

Bash:Shell、.profile、.bashrc、.bash_history。 当使用CLI(命令行界面)来使用Linux时,你正在与一个名为shell的程序进行交互。所有你输入的都传递给she

Python可视化 | Seaborn5分钟入门(二)——barplot&countplot&pointplot

微信公众号:「Python读财」如有问题或建议,请公众号留言Seaborn是基于matplotlib的Python可视化库。它提供了一个高级界面来绘制有吸引力的统计图形。Seaborn其实是在matp

Requests源码分析

Requests源码分析最近python学习到了瓶颈了,这次准备从KennethReitz大神的requests入手分析源码,看大神的代码是一种学习的好方法,让我从中学到很多以前不知道的知识reque

即使站在风口也未必能飞:SaaS公司生存指南

Salesforce市值突破1000亿美元,Slack的估值超过70亿美元,这似乎让人觉得SaaS成为风口,任何人只要站在这个风口上,就能获得成功,虽然这么说并不能说不对,尤其是在风险投资盛行的美

即使站在风口也未必能飞:SaaS公司生存指南

Salesforce市值突破1000亿美元,Slack的估值超过70亿美元,这似乎让人觉得SaaS成为风口,任何人只要站在这个风口上,就能获得成功,虽然这么说并不能说不对,尤其是在风险投资盛行的美国。

源码分析 | 咋嘞?你的IDEA过期了吧!加个Jar包就破解了,为什么?

微信公众号:bugstack虫洞栈|博客:https://bugstack.cn沉淀、分享、成长,专注于原创专题案例,以最易学习编程的方式分享知识,让自己和他人都能有所收获。目前已完成的专题有;Net

程序员垃圾代码分类指南

上一篇文章《程序员垃圾分类图鉴》和大家聊了聊程序员的垃圾分类,有的程序员直呼太真实,有的程序员觉得太讽刺,不应该给程序员进行这样的分类。其实每个行业都会存在各种各样糟糕的情况,娱乐性的分类会将问题放大

DBA职业发展之路:去“IOE”等挑战之下,DBA将何去何从?

开篇随着近些年来,开源、自动化、云化的兴起,DBA职业也正悄然发生一些变化。经常有朋友咨询我,职业发展规划;特别是近期Oracle的大幅裁员之后,针对DBA这一职业未来该如何发展?本文是个人对此问题的

GoldenDB ,一个已经全面支撑银行核心系统的国产数据库

摘要:沿用、并存还是替代,一直是银行核心系统数据库转型重点思考的问题。四大行目前主要采用的是沿用与并存的数据库产品战略,在确保稳定的大前提下对新兴数据库技术进行探索研究和实践。相对而言,股份制银行在这

陆天炜: GoldenDB事务一致性处理机制优化历程

前言:GoldenDB是中兴通讯推出的一款自研的金融级交易型分布式数据。针对金融行业关注的数据库事务一致性问题,中兴通讯GoldenDB分布式数据库架构师陆天炜,在DTCC2019数据库大会上做了干货

五年磨一剑 中兴GoldenDB数据库出征

国产软件经过几十年的探索已经有了不错的发展,甚至在移动支付等某些领域引领全球。但是在基础技术领域比如操作系统、数据库、芯片等方面还有很多不足。随着新技术、新的业态的发展带来了新的机遇与挑战。提起中兴通

Python可视化 | Seaborn5分钟入门(一)——kdeplot和distplot

微信公众号:「Python读财」如有问题或建议,请公众号留言Seaborn是基于matplotlib的Python可视化库。它提供了一个高级界面来绘制有吸引力的统计图形。Seaborn其实是在matp

Python可视化 | Seaborn5分钟入门(四)——stripplot和swarmplot

微信公众号:「Python读财」如有问题或建议,请公众号留言Seaborn是基于matplotlib的Python可视化库。它提供了一个高级界面来绘制有吸引力的统计图形。Seaborn其实是在matp

慢查询分析调优工具~mysqldumpslow

在日常的业务开发中,MySQL出现慢查询是很常见的,要么说明你家产品的增长性很好,要么就是你的SQL写的太烂了。所以对慢查询SQL进行分析和优化很重要,其中mysqldumpslow是MySQL服务自

Hyperf 发布 Session、极简 DB、zk 配置中心组件和支持 Twig/Plates 视图引擎支持

更新内容 本周更新主要新增极简DB组件,Zookeeper配置中心,和Session组件,以及为视图组件增加了Twig和Plates视图引擎的支持,同时为计划任务组件增加了集群执行的支持。极简DB组件