跳表skiplist
目录
面试题：为什么Redis要用跳表来实现有序集合，为什么不用红黑树
为什么会出现跳表
跳表可以说是平衡树的一种替代品。它也是为了解决元素随机插入后快速定位的的问题。那这个问题，hash 表解决的很好，插入和查找都是 O(1) 的时间复杂度。但若想要有序呢？这个时候 hash 表就不行了，二叉查找树可以解决这个问题。
但是由于二叉查找树在按大小顺序进行插入的时候，就会退化为链表。所以又出现了平衡二叉树，而根据算法不同，又分为AVL树、B-Tree、B+Tree、红黑树等。（先不用管这些数据结构的实现，其是复杂的）。
而跳表的出现就是为了解决平衡二叉树复杂的问题，它以一种较为简单的方式实现了平衡二叉树的功能。
跳表(skiplist、跳跃表) 是一个类似链表的数据结构。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。
其结构特点在名称能很好的体现出来，会跳，即是可以跳过多个元素来快速找到目标，如下图。
跳表源码结构
Redis中没有把该结构放置在当个文件中，而是放置在src/server.c内。由注释可知的，在 Redis 中，目前使用到跳表的只有 有序集合(zset)。
/* ZSETs use a specialized version of Skiplists */
/* ZSETs use a specialized version of Skiplists */
//跳表节点
typedef struct zskiplistNode {
sds ele; //成员对象，value
double score; //分值，是作为索引
struct zskiplistNode *backward; //后退指针
//节点层结构， 其是个数组
struct zskiplistLevel {
struct zskiplistNode *forward; //前进指针
unsigned long span; //x.level[i].span 表示节点x在第i层到其下一个节点需跳过的节点数。注：两个相邻节点span为1
} level[];
} zskiplistNode;
//跳表结构体
typedef struct zskiplist {
struct zskiplistNode *header, *tail; //跳表的头/尾节点，头节点是不保存元素的
unsigned long length; //节点的个数，也不包括头节点的
int level; //最大层数，因为头节点不保存元素，所以最大层数是不包括头节点的最大层数的
} zskiplist;
//有序集合 zset的实现
typedef struct zset {
dict *dict; //哈希表
zskiplist *zsl; //跳表，本文的重点
} zset;可能不能很好理解结构体zskiplistNode中的level[]的用途。看看Redis的跳表结构图。
跳表结构图
该图中最高层数是2，然后每个层级的节点都通过指针连接起来：
- level1层的节点有：元素分别是1,2,3,4,5,6的节点
- level2层的节点有:元素分别是1,3,5的节点
从上图可知，跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的 zskiplistLevel 结构体类型的 level 数组。
level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。zskiplistLevel 结构体里定义了指向同一层的下一个节点的指针和跨度，跨度是用来记录两个节点之间的距离。
看到跨度，可能会想到是和遍历操作有关，实际上并没有关系，遍历操作只需要用前向指针（struct zskiplistNode *forward）就可以完成了。
跨度实际上是为了计算这个节点在跳表中的排位。
具体怎么做的呢？跳表中的节点都是按序排列的，那么计算某个节点排位的时候，从头节点点到该结点的查询路径上，将沿途访问过的所有层的跨度累加起来，其结果就是目标节点在跳表中的排位。
比如，查找图中元素3 在跳表中的排位，从最高层(level2)头节点开始查找节点 3，查找的过程中，找到元素1，这时跨度是1，接着找到了目标元素3，这个跨度是2,，所以元素3 在跳表中的排位是 2+1=3。
跳表节点的层数的设置
前面知道了跳表是个带有层级关系的链表。那每个节点就有可能有多个层级。那是如何计算出每个节点是多少层级的呢？
为达到二分查找的效果，每一层的结点数需要是相邻下一层结点数的二分之一最好，其查找复杂度可以降低到 O(logN)。
那该如何维持这个比例呢？
在添加元素的时候，就需要设置新增节点的层数，要是通过调整跳表节点以维持比例的方法的话，会带来额外的开销。
所以Redis没有这样做，其是在创建节点的时候，随机生成每个节点的层数，所以是并没有严格维持相邻两层的节点数量比例为 2 : 1 。
具体的做法是，跳表在创建节点时候，会生成值范围为uint32的一个随机数，如果(随机数&0xFFFF)<(0.25*0xFFF)，那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果不符合条件，最终确定该节点的层数。
由于ZSKIPLIST_P=0.25，所以相当于0xFFFF右移2位变为0x3FFF，假设random()比较均匀，在进行0xFFFF高16位清零之后，低16位取值就落在0x0000-0xFFFF之间。
这样while为真的概率只有1/4，更一般地说为真的概率为ZSKIPLIST_P
这样相当于每增加一层的概率不超过 25%，层数越高，概率越低。
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#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;
}
//没有找到random()函数的实现，这个也不是c语言库的函数。
//不过从zslRandomLevel的逻辑来看，其返回的随机数应该是值为uint32的整数，不会是范围为[0,1]的小数跳表的API
源码中都会更新节点的每层的span，看源码时候可以先抛弃关于span部分，这样会更好理解主体部分。要查看某元素在所有元素的排名，这个时候就会使用上span。
1.创建跳表
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl = zmalloc(sizeof(*zsl));
zsl->level = 1; //刚创建的层数是1
zsl->length = 0; //节点个数是0
//创建头节点，头节点是不保存元素的
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
//头节点需要有足够的指针域，用来满足构造最大层数的需求，而尾结点是不需要指针域的
//对节点的level[]数组进行构造
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}
//创建节点
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
}2.插入元素
主要思路:从跳表的最高层开始比较查找，当前节点的下一节点的同一层的score<待插入的score，就继续往前查找。找到合适的位置创建节点。
这里要特意说明下两个数组：
- update:用来记录查找过程中，每次能达到的最右节点，下图的黄色框的就是每层的update[i]
- rank:用来记录每层节点在最底层的的位置，下图一共有4层,第三层的2的位置是2，则rank[2]=2，第2层的4的位置是4，则rank[1]=4。
用前面的图来说明下面源码中的update数组
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x; //update数组表示要插入元素的前面的节点
unsigned int rank[ZSKIPLIST_MAXLEVEL];//排名数组，某节点在每一层中排名
int i, level;
serverAssert(!isnan(score));
x = zsl->header; //获取跳跃表头结点地址，从头节点开始一层一层遍历
for (i = zsl->level-1; i >= 0; i--) {//遍历头节点的每个level，从下标最大层遍历到0层
/* store rank that is crossed to reach the insert position */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];//更新rank[i]为i+1层所跨越的节点数
//这个while循环是查找的过程，沿着x指针遍历跳跃表，满足以下条件则要继续在当层往前走
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
//当前层的前进指针不为空 &&(当前待插入的score>当前层的score ||(他们score相等&&当前层的元素ele<插入的ele))
rank[i] += x->level[i].span; //记录该层一共跨越了多少节点 加上 上一层遍历所跨越的节点数
x = x->level[i].forward; 指向同层的下一节点
}
//while循环跳出时，用update[i]记录第i层所遍历到的最后一个节点，遍历到i=0时，就要在该节点后要插入节点
update[i] = x;
}
level = zslRandomLevel();//获得一个随机的层数
//新增节点的层数高于当前最大层数，就需要更新
if (level > zsl->level) {
for (i = zsl->level; i < level; i++) {
rank[i] = 0; //将>=原zsl->level层以上的rank[]设置为0
update[i] = zsl->header; //将>=原来zsl->level层以上update[i]指向头结点
update[i]->level[i].span = zsl->length;//update[i]已经指向头结点，将第i层的跨度设置为length,length是跳表的节点个数
}
zsl->level = level; //更新最大层数
}
x = zslCreateNode(level,score,ele); //根据level层数创建节点
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
/* update span covered by update[i] as x is inserted here */
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);//更新插入节点的跨度值
update[i]->level[i].span = (rank[0] - rank[i]) + 1;//更新插入节点前一个节点的跨度值
}
/* increment span for untouched levels */
for (i = level; i < zsl->level; i++) {//如果插入节点的level小于原来的zsl->level才会执行
update[i]->level[i].span++; //因为高度没有达到这些层，所以只需将查找时每层最后一个节点的值的跨度加1，因为是添加了一个节点
}
//设置插入节点的后退指针，就是查找时最下层的最后一个节点，该节点的地址记录在update[0]中
//如果插入在第二个节点，也就是头结点后的位置就将后退指针设置为NULL
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)//如果x节点不是最尾部的节点
x->level[0].forward->backward = x;//就将x节点后面的节点的后退节点设置成为x地址
else
zsl->tail = x;//否则更新表头的tail指针，指向最尾部的节点x
zsl->length++;
return x;
}3.删除元素
- 和插入元素一样，先要找到待删除元素的位置，即是找到待删除元素位置的前一节点，然后把前一节点的每层都存储到updat数组。
- 然后判断找到的节点是否是待删除的节点，若是就调用zslDeleteNode来删除该节点
int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
x = zsl->header;
//遍历所有层，记录被删除节点的每层需要被修改的节点到update数组
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;
}
//现在判断x是否是待删除的节点，若是，调用zslDeleteNode进行删除节点
x = x->level[0].forward;
if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
zslDeleteNode(zsl, x, update);
if (!node)
zslFreeNode(x);
else
*node = x;
return 1;
}
return 0; /* not found */ //没有找到待删除的节点，返回0
}
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = 0; i < zsl->level; i++) {
//若该层的update的forward是待删除的节点
if (update[i]->level[i].forward == x) {
update[i]->level[i].span += x->level[i].span - 1; //更新其span
update[i]->level[i].forward = x->level[i].forward; //要删除节点x,所以该层的update的forward就不是节点x,是节点x的forward
} else {
update[i]->level[i].span -= 1;
}
}
if (x->level[0].forward) { //forward不为null,表明待删除节点x不是尾结点
x->level[0].forward->backward = x->backward; //x是待删除节点，更新x前后节点的backward指向
} else {
zsl->tail = x->backward;
}
//更新层数
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--;
}4.计算节点的排位 zslGetRank
跳表本身是有序的，Redis在跳表的forward指针上进行了优化，给每个forward指针添加了spans属性，用来表示从上一节点沿着当前层的forward指针调到当前这个节点中间会跳过多少个接节点。Redis在插入和删除操作时候会仔细地更行每层的span值。
所以，可以沿着每层查找，把span值进行累加就可能酸菜当前元素的最终排名。
通过上图可以加深理解。源码如下:
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x;
unsigned long rank = 0;
int i;
x = zsl->header;
//从最高层开始查找
for (i = zsl->level-1; i >= 0; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) <= 0))) {
rank += x->level[i].span; //累加每一次的span
x = x->level[i].forward;
}
/* x might be equal to zsl->header, so test if obj is non-NULL */
if (x->ele && sdscmp(x->ele,ele) == 0) {
return rank;
}
}
return 0;
}面试题：为什么Redis要用跳表来实现有序集合，为什么不用红黑树
-
从内存占用上来比较，跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针，而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。Redis 取 p=1/4(即是ZSKIPLIST_P），那么平均每个节点包含 1.33 个指针，比平衡树更有优势。(1/(1-p)是计算跳表结点的平均层数得到的，过程比较复杂，可自行去查看)
-
在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对最低层链表进行若干步的遍历就可以实现。
-
从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作相对简单又快速。
Mysql的innodb索引为什么使用B+树而不使用跳表？
B+树是多叉树结构，每个结点都是一个16k的数据页，能存放较多索引信息。三层左右就可以存储2kw左右的数据。也就是说查询一次数据，如果这些数据页都在磁盘里，那么最多需要查询三次磁盘IO。
跳表是链表结构，一条数据一个结点，如果最底层要存放2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在左右 ，即是跳表高度在24层左右。最坏情况下，这24层数据会分散在不同的数据页里，也即是查一次数据会经历24次磁盘IO。
因此存放同样量级的数据，B+树的高度比跳表的要少。对于mysql数据库上来说，磁盘IO次数更少，因此B+树查询更快。
而针对写操作，B+树需要拆分合并索引数据页，跳表则独立插入，并根据随机函数确定层数，没有旋转和维持平衡的开销，因此跳表的写入性能会比B+树要好。
那为什么现在还在使用红黑树这些二叉平衡树?
因为红黑树出现的更早，已经在多个领域大量使用，很多编程语言的map都是用红黑树来实现的。
现在的编程语言没有实现跳表，要想使用跳表，还需要自己来实现。
原文地址：https://blog.csdn.net/m0_57408211/article/details/137639921
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！