0%

Redis跳表

跳表skiplist是一种有序数据结构,在每个节点维持指向其他节点的指针,可以达到快速访问节点的目的。可以认为跳表在原有的有序链表上增加了多级索引,通过索引就可以快速查找。跳表的查找、插入、删除事件复杂度都是O(log n),还可以实现区间查找。

Redis的有序集合的底层实现使用了跳表。

Redis为什么使用跳表而不使用红黑树

  • 在查找、插入、删除、有序输出元素,跳表和红黑树都可以完成,并且时间复杂度都是O(long n)。
  • 查找区间内的元素红黑树效率没有跳表高。跳表只需要定位两个端点在最低层级的位置,然后遍历元素;红黑树定位到端点后,需要每次从首位置开始查找元素。
  • 红黑树实现也很复杂,跳表实现简单。

跳表的实现

Redis跳表由两个结构组成:zskiplistNode表示跳表节点、zskiplist保存跳表节点相关信息:

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
27
28
29
30
31
struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;

// 表中节点的数量
unsigned long length;

// 表中层数最大的节点的层数
int level;
}

struct zskiplistNode {
// level数组,层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;

// 跨度
unsigned int span;
} level[];

// 后退指针
struct zskiplistNode *backward;

// 分值
double score;

// 成员对象
robj *obj;

}

zskiplist:

  • header指向跳表头节点
  • tail指向跳表尾节点
  • level表示跳表内层数最大的节点层数,表头节点层数不计算在内
  • length表示跳表长度、包含节点的数量,不包含表头节点

zskiplistNode:

  • level,层,每个层有两个属性:前进指针和跨度,前进指针指向表尾方向的其他的节点;跨度记录了前进至真所指向节点和当前结点的距离
  • backward,指向当前节点的前一个节点,用于从表尾向表头遍历时使用
  • score,分值,各个结点的分值从小到大排列
  • obj,成员对象。
坚持原创技术分享,您的支持将鼓励我继续创作!
Fork me on GitHub