跳跃表深入理解

1、认识跳跃表

redis 中 zset 是一个有序非线性的数据结构，它底层核心的数据结构是跳表。跳表（skiplist）是一个特俗的链表，相比一般的链表，有更高的查找效率，其效率可比拟于二叉查找树。

一张关于跳表和跳表搜索过程如下图：

在图中，需要寻找 68，在给出的查找过程中，利用跳表数据结构优势，只比较了3次，横箭头不比较，竖箭头比较。由此可见，跳表预先间隔地保存了有序链表中的节点，从而在查找过程中能达到类似于二分搜索的效果，而二分搜索思想就是通过比较中点数据放弃另一半的查找，从而节省一半的查找时间。缺点即浪费了空间，自古空间和时间两难全。

红黑树在空间和时间效率上略胜跳跃表一筹，但跳跃表实现上相对简单，颇得程序猿们的青睐。redis和leveldb中都有采用跳表。

2、跳跃表的提出

跳表首先由William Pugh在其1990年的论文《Skip lists: A probabilistic alternative to balanced trees》中提出。由该论文的题目可以知道两点：

1. 跳表是概率型数据结构。
2. 跳表是用来替代平衡树的数据结构。准确来说，是用来替代自平衡二叉查找树（self-balancing BST）的结构。

比如有个在有序序列中查找某个特定元素的场景：如果序列采用支持随机访问的线性结构（数组）存储，那么很容易地用二分查找来做。但是考虑到增删效率和内存扩展性，很多时候要用不支持随机访问的线性结构（链表）存储，就只能从头遍历、逐个比对。 于是折衷考虑下，如果用二叉树结构（BST）存储，就可以不靠随机访问特性进行二分查找了。 但是普通BST对于插入元素越有序效率就越低，最坏情况会退化回链表。因此提出了自平衡BST结构，保证任何情况下的增删查操作都保持O(logn)的时间复杂度。自平衡BST的代表有AVL树、2-3树及其衍生出来的红黑树。推广不限于二叉树的话，耳熟能详的B树和B+树也属于此类，常用于文件系统和数据库。这样子来看，自平衡BST真香啊，很适合我们的场景，但也存在不爽的点：树的自平衡过程比较复杂，实现起来超级麻烦，在高并发的情况下，加锁也会带来非常可观的损耗。比如AVL树需要LL、LR、RL、RR四种旋转操作来保持平衡，红黑树则需要左旋、右旋和变色三种操作。 那么有没有实现起来简单、和自平衡BST效率想近的实现方法呢？答案就是跳表，并且简单很多。

3、设计思想

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。跳跃表在 Redis 里没有其它用途。

跳表就是如下图的链表集合：

跳表具有的性质：

• 由很多层组成，最底层为第1层，以此类推。层数不会超过一个固定的最大值MAX。
• 每层都是一个由头节点的有序链表，第1层的链表包含跳表中的所有元素。
• 如果某个元素在第K层出现，那么在1～K-1层也必定会出现。

很显然这是一种空间换时间的思路，和索引异曲同工。第K层可以认为是第K-1层的索引，用来加速查找。为了避免占用过多空间，第1层之上都不存储实际数据，只有指针。

当查找元素时，会从最顶层链表的头节点开始遍历。如当前节点的下一个节点包含的值比目标元素值小，则继续向右查找。如果下一个节点的值比目标值大，就转到当前层的下一层去查找。重复向右和向下的操作，直到找到与目标值相等的元素为止。下图中的蓝色箭头标记出了查找元素21的步骤。

通过图示查找过程，可以更加明白跳表的含义，因为查找过程确实是跳跃的，比线性查找省时。当数据量越来越大的时候，这种结构的优势就更加明显了。

2.1、插入元素的概率性

前面说过，跳表第K层的元素会按一定的概率出现在K+1层，这种概率是在插入过程中实现的。当按照上述查找流程找到新元素的插入位置上，将其插入第1层。然后通过随机方法来决定是否继续插入第2、3、4、5....层。

int randomizeLevel(double p, int lmax) {  
int level = 1;   
Random random = new Random();    
while (random.nextDouble() < p && level < lmax) {
 level++; 
 } 
 return level; 
 } 

由逻辑可知，随着层树的增加，元素被插入到上层的概率会指数级的下降。这种随机方法也被称为“抛硬币”算法。

相对于插入来说，删除操作没有那么多的逻辑，跟正常的单链表删除一致。

3、为啥Redis不用平衡搜索树来实现？

至于为什么Redis不用平衡搜索树来做，结合Redis作者的话可以认为这么做挺好的，确实在保证底线（最差）的情况下在某些时候还有亮点。

1. 内存占用更少，自定义参数化决定使用多少内存
2. 有序集合很多时候用zrange 或者zrevrange 。性能至少不比平衡树差
3. 简单更容易实现和维护

一句话总结什么是跳表：跳表就是在有序链表的基础上通过增加额外的指针节点来解决查询效率，通过随机插入来提高变更效率的一种数据结构。

4、参考：

《Redis 为什么用跳表而不用平衡树？》

《为什么Redis一定要用跳表来实现有序集合？》