临时或永久地禁用SELinux

跳跃表的实现(源码分析)

redis关于跳跃表的API都定义在t_zset.c文件中。

千万不要看到源码分析就跑开了，一定要看哦。

创建跳跃表

创建空的跳跃表，其实就是创建表头和管理所有的节点的level数组。首先，定义一些变量，尝试分配内存空间。其次是初始化表头的level和length，分别赋值1和0。接着创建管理所有节点的Level的数组，是调用zslCreateNode函数，输入参数为数组大小宏常量ZSKIPLIST_MAXLEVEL(32)，分数为0，对象值为NULL。(此为跳跃表得以实现重点)。再接着就是为此数组每个元素的前指针forword和跨度span初始化。最后初始化尾指针并返回值。

可以参照下面的图解和源码：


 

上图主要分为3大块：(这边大致看下就行，下面将对各模块进行代码详细解释)

表头

主要包括四个属性，分别是头指针header,尾指针tail,节点长度length,所有节点的最大level。

header：指向跳跃表的表头节点，通过这个指针地址可以直接找到表头，时间复杂度为O(1)。

tail：指向跳跃表的表尾节点，通过这个指针可以直接找到表尾，时间复杂度为O(1)。

length：记录跳跃表的长度，即不包含表头节点，整个跳跃表中有多少个元素。

level：记录当前跳跃表内，所有节点层数最大的level(排除表头节点)。

管理所有节点层数level的数组

其对象值为空，level数组为32层，目的是为了管理真正的数据节点。关于具体的level有哪些属性放在数据节点来说。

数据节点

主要包括四个属性对象值obj，分数score，后退指针backward和level数组。每个数据的Level数组有多少层，是随机产生的，这跟上面说过的跳跃表是一样的。

成员对象obj：真正的实际数据，每个节点的数据都是唯一的，但是节点的分数可能相同。两个相同分数的节点是按照成员对象在字典中的大小进行排序的，成员对象较小的节点会排在前面，成员对象较大的节点会排在后面。

分数score:各个节点中的数字是节点所保存的分数，在跳跃表中，节点按各自所保存的分数从小到大排列。

后退指针backward:用于从表尾向表头遍历，每个节点只有一个后退指针，即每次只能后退一步。

层级level：节点中用1，2，3等字样标记节点的各个层，L1代表第一层，L2代表第二层，L3代表第三层，并以此类推。

跳跃表的定义

表头结构zskiplist

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!