先声明下,图都是别的地方薅来的,别人画的挺认真的,多看图有助于理解.很多博客说的都很好,我记录了一下我学习的过程:
跳表
先从下面这张动图开始:
元素添加到跳表
说到底,链表是个线性结构,一次只能到指向的下一个节点上,双向的无非也就是两个.想查个啥只能是O(n)查.
跳表在于"跳".多整点指针,能去的远点,节点多一点.这也是需要代价的,因为你得记点东西支持他去不是?一种典型的空间换时间的优化思路.不得不说,很巧妙.
最后整个弄下来,细一看,跟一个树结构长得差不多,当然平均的时间复杂度也就变成了O(logN)了.
总结: 跳表理论上在最底层是一条双端链表，然后基于此建立了多层索引节点以实现的.能做到这些,核心是两个东西,一个是分治算法(我理解就是二分找),一个是随机算法(概率学).
上面的这些就是调表的,redis的跳跃表的实现了.
redis跳跃表
先来个跳跃表的定义:
typedef struct zskiplist {
struct zskiplistNode *header, *tail; //指向头尾节点
unsigned long length;
int level;
} zskiplist;
节点的定义:
typedef struct zskiplistNode {
sds ele; // 数据
double score; //分数 按此值进行排序的
struct zskiplistNode *backward; // 前指针(从后往前)
struct zskiplistLevel {
struct zskiplistNode *forward; //前向指针
unsigned int span;
} level[];//level数组
} zskiplistNode;
level数组是最关键的,每个元素都是zskiplistLevel结构,这个结构包括一个forward前向指针,一个span跨度.
一个节点有几层,也就是说level数组有几个元素,是由一个随机算法算出来的,这就是开头说的概率问题.幂次定律(越大的数出现的概率越小)
真去建立索引层是不好实现的,redis的实现:每个节点除了存储节点自身的数据外，还通过 level 数组保存了该节点在整个跳表各个索引层的节点引用.那变成了下图这个样子:
节点长这样
那整个跳表就变成了这个样子:
跳表长这样
有了上面的两个结构体,加上上面的图的描绘,我们就能初始化一个redis的跳表了.
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;
}
/* Create a new skiplist. */
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
//分配内存空间
zsl = zmalloc(sizeof(*zsl));
//默认只有一层索引
zsl->level = 1;
//0 个节点
zsl->length = 0;
//1、创建一个 node 节点，这是个哨兵节点
//2、为 level 数组分配 ZSKIPLIST_MAXLEVEL=32 内存大小
//3、也即 redis 中支持索引最大 32 层
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;
}
逻辑上说,先来个哨兵节点(更像个哨楼),有了这个再把节点的level数组初始化了,因为是头节点,那redis规定最高32层,那它就应该是32层(不这么高,一会玩不下去了)
插入一个元素
开始之前,先来几个名词解释:
1 跨度:此索引层这个节点到下个节点中间相隔几个节点
2 update数组: 用于记录新节点在每一层索引的目标插入位置
3 rank数组:记录目标节点每一层的排名
4 节点的排名(实际就是第几个节点):等于查找该节点时,之前所遍历过的节点的层跨度之和(最底层链表的第几个元素当然==之前跨度的和)
对照上面的图,加上下面的逻辑段:
1 从最高索引层开始遍历，根据 score 找到它的前驱节点，用 update 数组进行保存,rank数组记录前驱节点的排名.
2 生成随机的层数level
3 创建新节点
4 更新新节点的及其前驱节点的跨度span
5 维护双链表结构.更新新节点的backward理解下面的插入源码:
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
//update数组将用于记录新节点在每一层索引的目标插入位置
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
//rank数组记录目标节点每一层的排名
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
//指向哨兵节点
x = zsl->header;
//这一段就是遍历每一层索引，找到最后一个小于当前给定score值的节点
//从高层索引向底层索引遍历
for (i = zsl->level-1; i >= 0; i--) {
//rank记录的是节点的排名，正常情况下给它初始值等于上一层目标节点的排名
//如果当前正在遍历最高层索引，那么这个初始值暂时给0
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
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)))
{
//我们说过level结构中，span表示的是与后面一个节点的跨度
//rank[i]最终会得到我们要找的目标节点的排名，也就是它前面有多少个节点
rank[i] += x->level[i].span;
//挪动指针
x = x->level[i].forward;
}
update[i] = x;
}
//至此，update数组中已经记录好，每一层最后一个小于给定score值的节点
//我们的新节点只需要插在他们后即可
//random算法获取一个平衡跳表的level值，标志着我们的新节点将要在哪些索引出现
//具体算法这里不做分析，你也可以私下找我讨论
level = zslRandomLevel();
//如果产生值大于当前跳表最高索引
if (level > zsl->level) {
//为高出来的索引层赋初始值，update[i]指向哨兵节点
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
//根据score和ele创建节点
x = zslCreateNode(level,score,ele);
//每一索引层得进行新节点插入，建议对照我之前给出的跳表示意图
for (i = 0; i < level; i++) {
//断开指针，插入新节点
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
//rank[0]等于新节点再最底层链表的排名，就是它前面有多少个节点
//update[i]->level[i].span记录的是目标节点与后一个索引节点之间的跨度，即跨越了多少个节点
//得到新插入节点与后一个索引节点之间的跨度
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
//修改目标节点的span值
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
//如果上面产生的平衡level大于跳表最高使用索引，我们上面说会为高出部分做初始化
//这里是自增他们的span值，因为新插入了一个节点，跨度自然要增加
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
//修改 backward 指针与 tail 指针
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
到这,应该基本都理解了,剩下的不管是删除,修改,查询都需要先找到位置,再做一些大同小异的操作.
还有一些命令与API都是基于其中维护的一些字段的特性,做的处理.
参考:
https://blog.csdn.net/gqtcgq/article/details/50613896
https://www.cnblogs.com/yangming1996/p/11663810.html
