Redis数据库跳跃表大概介绍

Redis skiplist 跳跃表 笔记

跳跃表简介

  • skiplist 是一种有序数据结构, 通过在每个节点维持多个指向其它节点的指针,达到快速访问节点的目的。
  • skiplist 支持平均O(logN)、最坏O(N)复杂度的节点查找。大部分情况下和平衡树相媲美,并且比平衡树实现简单。
  • redis使用skiplist做为有序集合键的底层实现之一。

跳跃表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef struct zskiplistNode {  //跳跃表节点
robj *obj; //所保存的成员对象 在同一个跳跃表中,各个节点保存的成员对象
//必须是唯一的,但各个节点保存的分值却可以是相同的,分值相同
//的节点按成员对象在字典序中的大小来进行排序。
double score; //分值 跳跃表中,节点按各自所保存的分值从小到大排列
struct zskiplistNode *backward; //后退指针,指向位于当前节点的前一个节点。
//后退指针在程序从表尾向表头遍历时使用
struct zskiplistLevel {
struct zskiplistNode *forward; //前进指针, 用于从表头向表尾方向访问节点。
unsigned int span; //跨度, 用于记录两个节点之间的距离。两个节点之间的跨
//度越大,他们相聚得就越远。指向NULL的所有前进指针的
//跨度都为0, 因为它们没有连向任何节点。跨度用于计算
//排位,在查找某个节点的过程中,将沿途访问过的所有曾
//的跨度累计起来,得到的结果就是目标节点在跳跃表中的排名。
} level[]; //层 包含多个元素,每个元素包含一个指向其它节点的指针,
//程序可以通过这些层加快访问其它节点的速度, 一般来说,层
//的数量越多,访问其它节点的速度就越快。每次创建新跳跃表
//节点的时候,程序根据幂次定律随机生成一个介于1到32之间的值
//做为levle数组的大小,这个大小就是层的"高度"
} zskiplistNode;

typedef struct zskiplist { //跳跃表节点相关信息
struct zskiplistNode *header, *tail; //指向跳跃表表头节点和表尾节点
unsigned long length; //跳跃表的长度,即跳跃表目前包含节点的数量
int level; //记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)
} zskiplist;