Redis数据结构 skiplist

### 基本概念
跳表是可以实现二分查找的有序链表。

![](/media/202108/redis11_1629418572.png)
### 跳表的插入
插入数据看起来也很简单，跳表的原始链表需要保持有序，所以我们会向查找元素一样，找到元素应该插入的位置，然后再将数据插入。整个时间复杂度为查找元素的时间复杂度 O(logn)。

假如一直往跳表中添加数据，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况，跳表退化为单链表，从而使得查找效率从 O(logn) 退化为 O(n)。那这种问题该怎么解决呢？我们需要在插入数据的时候，索引节点也需要相应的增加、或者重建索引，来避免查找效率的退化。那我们该如何去维护这个索引呢？

比较容易理解的做法就是完全重建索引，我们每次插入数据后，都把这个跳表的索引删掉全部重建，重建索引的时间复杂度是多少呢？因为索引的空间复杂度是 O(n)，即：索引节点的个数是 O(n) 级别，每次完全重新建一个 O(n) 级别的索引，时间复杂度也是 O(n) 。造成的后果是：为了维护索引，导致每次插入数据的时间复杂度变成了 O(n)。

那有没有其他效率比较高的方式来维护索引呢？
> 假如跳表每一层的晋升概率是 1/2，最理想的索引就是在原始链表中每隔一个元素抽取一个元素做为一级索引。换种说法，我们在原始链表中随机的选 n/2 个元素做为一级索引是不是也能通过索引提高查找的效率呢？ 当然可以了，因为一般随机选的元素相对来说都是比较均匀的。随机选择了n/2 个元素做为一级索引，虽然不是每隔一个元素抽取一个，但是对于查找效率来讲，影响不大。当原始链表中元素数量足够大，且抽取足够随机的话，我们得到的索引是均匀的。我们要清楚设计良好的数据结构都是为了应对大数据量的场景，如果原始链表只有 5 个元素，那么依次遍历 5 个元素也没有关系，因为数据量太少了。

所以，我们可以维护一个这样的索引：
```
随机选 n/2 个元素做为一级索引；
随机选 n/4 个元素做为二级索引；
随机选 n/8 个元素做为三级索引；
依次类推，一直到最顶层索引;
```
> 每层索引的元素个数已经确定，且每层索引元素选取的足够随机，所以可以通过索引来提升跳表的查找效率。

那代码该如何实现，才能使跳表满足上述这个样子呢？
可以在每次新插入元素的时候，尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引，以此类推，就能满足我们上面的条件。现在我们就需要一个概率算法帮我们把控这个 1/2、1/4、1/8 ... ，当每次有数据要插入时，先通过概率算法告诉我们这个元素需要插入到几级索引中，然后开始维护索引并把数据插入到原始链表中。下面开始讲解这个概率算法代码如何实现
```
跳表的概率算法：
我们可以实现一个 randomLevel() 方法，该方法会随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），且该方法有 1/2 的概率返回 0、1/4 的概率返回 1、1/8的概率返回 2，以此类推。
randomLevel() 方法返回 0 表示当前插入的该元素不需要建索引，只需要存储数据到原始链表即可（概率 1/2）
randomLevel() 方法返回 1 表示当前插入的该元素需要建一级索引（概率 1/4）
randomLevel() 方法返回 2 表示当前插入的该元素需要建二级索引（概率 1/8）
randomLevel() 方法返回 3 表示当前插入的该元素需要建三级索引（概率 1/16）
。。。以此类推
```
之前我们说过，要让元素有1/2的概率建立一级索引，为什么这里是1/4的概率呢？
因为建立索引时我们发现了一个特点：
```
建立二级索引时，同时也会建立一级索引；
建立三级索引时，同时也会建立一级、二级索引；
```
所以我们可以得到：
```
一级索引中元素的个数 = [ 原始链表元素个数 ] * [ randomLevel() > 0 的概率 ]
二级索引中元素的个数 = [ 原始链表元素个数 ] * [ randomLevel() > 1 的概率 ]
。。。以此类推
```
我们来看一下randomLevel 的实现：
```
import random

MAX_LEVEL = 3  	# 跳表的最大层级
SKIPLIST_P = 0.5   # 晋升概率
def randomLevel():
    level = 1
    while random.random() < SKIPLIST_P and level < MAX_LEVEL:
        level += 1
    return level
```
### 总结

> 1. 跳表是可以实现二分查找的有序链表；
2. 每个元素插入时随机生成它的level；
3. 最底层包含所有的元素；
4. 如果一个元素出现在level(x)，那么它肯定出现在x以下的level中；
5. 每个索引节点包含两个指针，一个向下，一个向右；（笔记目前看过的各种跳表源码实现包括Redis 的zset 都没有向下的指针，那怎么从二级索引跳到一级索引呢？留个悬念，看源码吧，文末有跳表实现源码）
6. 跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近；

### 问答
Redis为什么使用跳表而不是红黑树来实现有序集合？
跳表和红黑树（红黑树是平衡二叉搜索树）的时间复杂度都是logn，而且红黑树有空间优势，但是对于区间的查找，红黑树的查找效率没有跳表高。

### 参考
> [Skip List--跳表](https://www.jianshu.com/p/9d8296562806 "Skip List--跳表")
[Redis 数据结构 skiplist](https://wiki.jikexueyuan.com/project/redis/skiplist.html "Redis 数据结构 skiplist")
[Python Skip List 实现](https://github.com/wangzheng0822/algo/blob/master/python/17_skiplist/skip_list.py "Python Skip List 实现")