Redis数据结构之跳表

目录

简介

应用场景

数据结构

zskiplistNode

---

 

简介

跳跃表(skiplist)是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的
指针，从而达到快速访问节点的目的。
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找，还可以通过顺序性操作来批
量处理节点。

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树
要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。

跳跃表类似于多级的单向链表：

应用场景

和链表、字典等数据结构被广泛地应用在Redis内部不同，Redis只在两个地方用到了
跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在Redis里面没有其他用途。

数据结构

Redis的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成，其中zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度)，而zskiplistNode则用于表示跳跃表节点。每个跳跃表节点的层高都是1至32之间的随机数。在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。

跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

书中所画的跳表结构如下：

也可以这样话，大致意思是一样的：

zskiplistNode

 
跳跃表节点的Ievel 数组可以包含多个元素，每个元素都包含一个指向其他节点的指
针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他
节点的速度就越快。
每次创建一个新跳跃表节点的时候，程序都根据幂次定律（power law,越大的数出现
的概率越小）随机生成一个介于1和32之间的值作为 level 数组的大小，这个大小就是
层的“高度”。
下图分别展示了三个高度为1层、3层和5层的节点，因为C语言的数组索引总是从
0开始的，所以节点的第一层是level [0],而第二层是level [1],以此类推。