在我阅读 Redis 底层实现中跳表的部分的时候，不由得想起 b+ 树系列。它们有类似性，比如都是通过多层结构实现快速跳转查找。但是跳表中的层数完全随机，即便是在统计意义上的平均时间复杂度也是和 b+ 树相近。好像跳表从各个方面都不太比得上 b+ 树，那为什么 Redis 的作者却更偏向使用跳表来实现呢？ (3.0版本之后的 Redis 更喜欢将 sdlist 与 skiplist 一起使用，并称之为 quicklist )
如下即是一个典型的跳表[1]:
关于跳表的细节可以参考 WilliamPugh 关于跳表的论文 《Skip Lists: A Probabilistic Alternative to Balanced Trees》[0]
Include: 跳表的粗浅理解, Redis 作者给出的理由
跳表理解
关于跳表的每个结点层高，不妨带入以下算法计算：
· 首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。
· 如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。
· 节点最大的层数不允许超过一个最大值，记为MaxLevel。
在 Redis 的 Skiplist 实现中，这两个参数分别为:
p = 1/4, MaxLevel = 32
查找
从头部的最高节点出发，一旦指针所指的结点超过目标结点，则回溯查找下一层。如下图所示：
插入
如下是插入的示意图：
正序来看也许比较抽象，倒不如从插入点反过来看[2]。从插入点开始回溯：
现在假设我们从一个层数为i的节点x出发，需要向左向上攀爬k层。这时我们有两种可能：
· 如果节点x有第(i+1)层指针，那么我们需要向上走。这种情况概率为p。
· 如果节点x没有第(i+1)层指针，那么我们需要向左走。这种情况概率为(1-p)。
那么显而易见，从统计上来说，每当我们爬升一个层级，所需要的步数为 1/p 步。而我们总共需要攀爬的层数等于 Skiplist 的总层数 -1。
那么接下来我们需要分析一下当skiplist中有n个节点的时候，它的总层数的概率均值是多少。这个问题直观上比较好理解。根据节点的层数随机算法，容易得出：
- 第1层链表固定有n个节点；
- 第2层链表平均有n*p个节点；
- 第3层链表平均有n*p2个节点；
- …
所以，从第1层到最高层，各层链表的平均节点数是一个指数递减的等比数列。容易推算出，总层数的均值为log1/pn，而最高层的平均节点数为1/p。
综上，粗略来计算的话，平均查找长度约等于：
C(log1/pn-1)=(log1/pn-1)/p
即，平均时间复杂度为O(log n)。
删除
移除结点的示意图如下:
移除节点则要简单很多，可以总结为：
- 查找到指定节点，否则返回
- 调整指针指向
- 释放节点空间
从之前对 skiplist 的分析中已经不难看出为什么用 skiplist 的原因了。
Redis 的作者在论坛 Hacker News 中给出了他使用跳表的一些理由[3]：
There are a few reasons:
１) They are not very memory intensive. It’s up to you basically.
Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
注：跳表的一个缺点是耗内存（因为要重复分层存节点），但是作者也说了，可以调参数来降低内存消耗，和那些平衡树结构达到差不多。
２) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list.
With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
注：redis经查有范围操作，这样利用跳表里面的双向链表，可以方便地操作。另外还有缓存区域化（cache locality）不会比平衡树差。
３) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch
(already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
注：实现简单。zrank操作能够到O(log N).
About the Append Only durability & speed, I don’t think it is a good idea to optimize Redis at cost of more code
and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command).
Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.
About threads: our experience shows that Redis is mostly I/O bound. I’m using threads to serve things from Virtual Memory.
The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core,
is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores),
and using the “Redis Cluster” solution that I plan to develop in the future.