redis 基础-数据结构-跳跃表

跳跃表定义:

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

跳跃表使用场景:

Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现,
和链表、字典等数据结构被广泛地应用在Redis内部不同，Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在Redis里面没有其他用途。

跳跃表构成:

Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义。

zskiplistNode结构用于表示跳跃表节点:

• 层（level）：节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。

每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。

• 后退（backward）指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。

• 分值（score）：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中，节点按各自所保存的分值从小到大排列。

• 成员对象（obj）：各个节点中的o1、o2和o3是节点所保存的成员对象。

zskiplist结构:用于保存跳跃表节点的相关信息，比如节点的数量，以及指向表头节点和表尾节点的指针等等。

• header：指向跳跃表的表头节点。

• tail：指向跳跃表的表尾节点

• level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）

• length：记录跳跃表的长度，也即是，跳跃表目前包含节点的数量（表头节点不计算在内

跳跃表展示图:

image

zskiplistNod 结构详细介绍：

• 结构定义：

image

跳跃表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其他节点的速度就越快

image

查询遍历过程：

• 1）迭代程序首先访问跳跃表的第一个节点（表头），然后从第四层的前进指针移动到表中的第二个节点。

• 2）在第二个节点时，程序沿着第二层的前进指针移动到表中的第三个节点。

• 3）在第三个节点时，程序同样沿着第二层的前进指针移动到表中的第四个节点。

• 4）当程序再次沿着第四个节点的前进指针移动时，它碰到一个NULL，程序知道这时已经到达了跳跃表的表尾，于是结束这次遍历。

举个查询例子：

假如要查询 数值为3.0的位置，从头节点出发遍历到3.0, 沿途经历的层：查找的过程只经过了一个层，并且层的跨度为3，所以目标节点在跳跃表中的位置为3。是不是很快！

zskiplist 结构详细介绍：

• 结构定义：

image

通过使用一个zskiplist结构来持有这些节点，程序可以更方便地对整个跳跃表进行处理，比如快速访问跳跃表的表头节点和表尾节点，或者快速地获取跳跃表节点的数量（也即是跳跃表的长度）等信息

跳跃表常见api

image

总结

• 跳跃表是有序集合的底层实现之一。

• Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。

• 每个跳跃表节点的层高都是1至32之间的随机数。

• 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。❑跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。