Redis04-Redis的数据结构之跳表
前言
上一篇文章我们介绍了字典这个数据结构，这一篇文章我们接着来学习下另外一个数据结构，跳表。那么什么是跳表呢？
跳表的基本概念
跳表是一种有序的数据结构，它通过在每个节点中维持多个指向其他的节点指针，从而达到快速访问队尾的目的。
这么说是不是感觉有点云里雾里呢？那么我们详细解释下这个概念。
想象一下，对于一个单链表，如果我们要查找单链表中的某个结点，我们该怎么做呢？是不是必须要从链头开始向链尾遍历直到找到我们想要找的那个元素。其时间复杂度在O(n)。如下图所示，如果我们需要查找6这个结点，我需要把前面的结点遍历完。
那么我们可以怎么优化这个查找效率呢？优化的思路就是尽量少的去遍历结点个数。该怎么做到这一点呢？这时候我们可以想到索引。增加索引减少需要遍历的结点个数。如下图所示：
其中我们通过索引层结点的 down 指针，下降到原始链表这一层。例如我们需要查找6这个结点，原来我们需要遍历6个结点，现在我们只需要遍历5个节点就可以了。我们不需要从链头对结点一个个的去遍历，只需要从链表的索引层开始查找。单链表越长，索引层越多查询的效率差别越明显。
像这种单链表+索引的结构就是跳表。
跳表的时间复杂度
介绍完了跳表的基本概念，接下来我们来了解下跳表的时间复杂度。我们分别分析下查询，插入以及删除的时间复杂度。
查询的时间复杂度
如上图：我们每两个结点抽出一个结点作为上一级索引的结点，那第一级索引的结点个数大约就是n/2，第二级索引的结点个数大约就是n/4，依次类推，也就是说，第K级索引的结点个数是第k-1级索引结点个数的1/2，那么第k级索引结点的个数就是n/(2^k)。
假设索引有h级，*的索引有2个结点，通过上面的公司，我们可以得到n/(2^h)=2,从而求得h=log2n-1,如果包含原始链表这一层的话，整个跳表的高度就是log2n。我们在跳表中查询某个数据的时候，如果每一层都要遍历m个结点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。
那么整个m的值是多少呢？按照前面的这种索引结构，我们每一级索引都最多只需要遍历3个节点，也就是说m=3，假设我们查找的数据是x（45），在第k级索引中，我们遍历到y（40）结点之后，发现x（45）大于y（40）,小于后面的节点z（50）,所以我们通过y（40）的down指针，从第k级索引下降到第k-1级索引。在第k-1级索引中，y（40）和z（50）之间只有3个结点（包含y和z）。所以，我们在k-1级索引中最多只需要遍历3个结点，依次类推，每一级都最多只需要遍历3个结点。通过上面的分析，我们得到m=3,所以在跳表中查询任意数据的时间复杂度就是O(logn)。例如我们需要查找45。
对于链表而言，只要定位到了要操作的结点，进行插入或者删除是很快的，所以，其时间复杂度是很低的就是O(1),但是，这里为了保证原始链表的有序性，我们需要先找到要插入的位置，这个查找操作就会比较耗时。跳表支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是O(logn)。图中中标黄的是插入的结点24，插入过程如下图所示：
删除操作跟插入操作类似。在此就不在赘述了。
但是如果我们不停地往跳表中插入数据，而不去更新索引，就有可能出现某2个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。如下图所示: 20和30这两个索引节点直接有太多的结点了。
那么如何处理这种情况呢？我们可以在往跳表插入数据的时候，选择同时将这个数据插入到部分索引层中，如何选择加入哪些索引层呢？
我们通过一个随机函数，来决定将这个结点插入到哪几个索引中，比如随机函数生成的值k，那么我们就将这个结点添加到第一级到第k级这k级索引中。如下图所示：
Redis中的跳表的实现
Redis使用跳表作为有序集合的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳表来作为有序集合键的底层实现。Redis的跳表由zskiplistNode和skiplist两个结构定义，其中zskiplistNode结构用于表示跳表节点，而zskiplist结构则用于保存跳表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等。如图所示：
zskiplist
typedef struct zskiplist {
// 头节点，尾节点
struct zskiplistNode *header, *tail;
// 节点数量
unsigned long length;
// 目前表内节点的最大层数
int level;
} zskiplist;
zskiplist结构的属性描述如下：
- header：指向跳跃表的表头节点，通过这个指针程序定位表头节点的时间复杂度为O(1)。
- tail: 指向跳跃表的表尾节点，通过这个指针程序定位表尾节点的时间复杂度就为O(1)。
- level: 记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）,通过这个属性可以获取层高最高的节点的层数。
- length: 记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内），通过这个属性，程序可以在O(1)的时间复杂度内返回跳跃表的长度。
zskiplistNode
typedef struct zskiplistNode {
// member 对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 这个层跨越的节点数量
unsigned int span;
} level[];
} zskiplistNode;
zskiplistNode结构内的属性说明如下：
1. level（层）
节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。
每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离（跨度越大、距离越远）。在上图中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着前进指针进行。
层高
节点的层高最小值为1，最大值是ZSKIPLIST_MAXLEVEL，Redis中节点层高的值为32。
#define ZSKIPLIST_MAXLEVEL 32 //最大层数
zslRandomLevel函数
每次创建一个新跳跃表节点的时候，程序都会根据幂次定律（zslRandomLevel,越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”。 节点层高确定之后便不会在修改，生成随机层高的代码如下。
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
上述代码中，level的初始值为1，通过while循环，每次生成一个随机值，取这个值的低16位作为x，当x小于0.25倍的0xFFFF时，level的值加1；否则退出while循环。最终返回level和ZSKIPLIST_MAXLEVEL两者中的最小值。下面计算节点的期望层高，假设p=ZSKIPLIST_P
- 节点层高为1的概率为(1-p)。
- 节点层高为2的概率为p(1-p)。
- 节点层高为3的概率为p^2(1-p)。
- 。。。。。。。
- 节点层高为n的概率为
p^(n-1)*(1-p)
所以节点的期望层高为
E＝1×(1-p)＋2×p(1-p)＋3×p2(1-p)＋…
＝(1-p)∑+∞i=1ipi-1
＝1/(1-p)
当p=0.25时，跳跃表节点的期望层高为 1/(1-0.25)=1.33。
2. 后退（backward）指针：
节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。与前进指针所不同的是每个节点只有一个后退指针，因此每次只能后退一个节点。
3. 分值（score）
各个节点中的1，11和21是节点所保存的分值，在跳跃表中，节点按各自所保存的分值从小到大排列。
4. 成员对象（ele）
各个节点中的ele是节点所保存的成员对象。在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的，分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）。
总结
本文介绍了跳跃表这种稍陌生的数据结构，跳表是基于单链表加索引的方式实现的，它是以空间换时间的方式来提升查找速度。Redis有序集合在节点元素较大或者元素数量较多时使用跳表实现，它是由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点，表尾节点，长度），zskiplistNode则用于表示跳跃表节点。Redis每个跳跃表节点的层高都是1至32之间的随机数。在同一个跳跃表中，多个节点可以包含相同的分值，但是每个节点的成员对象必须是唯一，跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
参考
Redis数据结构-跳跃表
跳跃表
《Redis的设计与实现》
带你读《Redis 5设计与源码分析》之三：跳 跃 表
17 -跳表：为什么Redis一定要用跳表来实现有序集合？