本文耗时60分钟，阅读需要5分钟。

---

今天给大家介绍一下跳跃链表。

跳跃列表由 William Pugh 发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。参见 引用并下载文档。

引用发明者的话：

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。

在计算机科学领域，跳跃链表是一种数据结构，允许快速查询一个有序连续元素的数据链表。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。 

基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。

基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表，因此得名。所有操作都以对数随机化的时间进行。

跳跃列表是按层建造的。底层是一个普通的有序链表。每个更高层都充当下面列表的“快速跑道”，这里在层 i 中的元素按某个固定的概率 p (通常为0.5或0.25)出现在层 i+1 中。平均起来，每个元素都在 1/(1-p) 个列表中出现，而最高层的元素（通常是在跳跃列表前端的一个特殊的头元素）在 O(log1/p n) 个列表中出现。

本文耗时10分钟，阅读需要5分钟。 RocksDB介绍：一个比LevelDB更彪悍的引擎 RocksDB实际上是在LevelDB之上做的改进。本

本文耗时60分钟，阅读需要20分钟。

---

leveldb 介绍

LevelDB 是 Google 开源的持久化KV单机数据库，具有很高的随机写，顺序读/写性能，但是随机读的性能很一般，也就是说，LevelDB很适合应用在查询较少，而写很多的场景。 LevelDB 应用了LSM (Log Structured Merge) 策略，lsm_tree 对索引变更进行延迟及批量处理，并通过一种类似于归并排序的方式高效地将更新迁移到磁盘，降低索引插入开销，关于LSM，本文在后面也会简单提及。

根据Leveldb官方网站的描述，LevelDB的特点和限制如下：

特点： 1、key和value都是任意长度的字节数组； 2、entry（即一条K-V记录）默认是按照key的字典顺序存储的，当然开发者也可以重载这个排序函数； 3、提供的基本操作接口：Put()、Delete()、Get()、Batch()； 4、支持批量操作以原子操作进行； 5、可以创建数据全景的snapshot(快照)，并允许在快照中查找数据； 6、可以通过前向（或后向）迭代器遍历数据（迭代器会隐含的创建一个snapshot）； 7、自动使用Snappy压缩数据； 8、可移植性；

限制： 1、非关系型数据模型（NoSQL），不支持sql语句，也不支持索引； 2、一次只允许一个进程访问一个特定的数据库； 3、没有内置的C/S架构，但开发者可以使用LevelDB库自己封装一个server；

LevelDB本身只是一个lib库，在源码目录make编译即可，然后在我们的应用程序里面可以直接include leveldb/include/db.h头文件，该头文件有几个基本的数据库操作接口。

存储流程简述

存储流程如下所示：

• 当插入一条key-value数据时,leveldb先将数据插入到log文件(追加)中，成功后写入memtable中，既保证了高效写入,也保证了数据的稳定性
• 当memtable插入的数据到了一个界限之后，会转为Immutable memtable, 由新的memtable支持写入操作.同时，leveldb在后台会通过调度程序将 Immutable memtable dump到磁盘上的sstable文件中。
• sstable内部的数据是key有序的。由Immutable memtable不断dump出来的 sstable文件越来越多，会进行compact操作，形成新的level的sstable文 件。

本文耗时60分钟，阅读需要5分钟。 认知，突破，成长 《欢乐颂2》：为什么越是出身底层，越追求稳定 在第一季《欢乐颂》中，曲筱绡说过一句话：什么叫

本文耗时120分钟，阅读需要15分钟。 互联网产品动不动就搞一个活动，虽然现在搞多了，用户活跃度降低了很多，但是依然会在短时间内带来巨大的流量

本文耗时60分钟，阅读需要5分钟。 30天习惯养成记完成已经有一两周了，最近个人工作上做了一些调整，所以博文更新也停滞了。 现在，我重新开始制定

本文耗时60分钟，阅读需要5分钟。 近况 最近我有在使用小米手环2，他不仅有计步的功能，还提供睡眠检测，以及睡眠质量的检测，主要检测“深睡眠”和

本文耗时60分钟，阅读需要5分钟。 思考总是存在的，我们一定要持续思考。 茶歇驿站 一个让你可以在茶歇之余，停下来看一看，里面的内容或许对你有一些

本文耗时60分钟，阅读需要5分钟。

本文耗时10分钟，阅读需要2分钟。