redis跳表

zset

zset是可排序的set。与hash的实现方式类似&＃xff0c;如果元素个数不多且不大&＃xff0c;就使用压缩列表ziplist来存储。不过由于zset包含了score的排序信息&＃xff0c;所以在ziplist内部&＃xff0c;是按照score排序递增来存储的。意味着每次插入数据都要移动之后的数据。

跳表

跳表&＃xff08;skiplist&＃xff09;是另一种实现dict的数据结构。跳表是对链表的一个增强。我们在使用链表的时候&＃xff0c;即使元素的有序排列的&＃xff0c;但如果要查找一个元素&＃xff0c;也需要从头一个个查找下去&＃xff0c;时间复杂度是O(N)。而跳表顾名思义&＃xff0c;就是跳跃了一些元素&＃xff0c;可以抽象多层。

如下图所示&＃xff0c;比如我们要查找8&＃xff0c;先在最上层L2查找&＃xff0c;发现在1和9之间&＃xff1b;然后去L1层查找&＃xff0c;发现在5和9之间&＃xff1b;然后去L0查找&＃xff0c;发现在7和9之间&＃xff0c;然后找到8。

当元素比较多时&＃xff0c;使用跳表可以显著减少查找的次数。

同list类似&＃xff0c;Redis内部也不是直接使用的跳表&＃xff0c;而是使用了一个自定义的数据结构来持有跳表。下图左边蓝色部分是skiplist&＃xff0c;右边是4个zskiplistNode。zskiplistNode内部有很多层L1、L2等&＃xff0c;指针指向这一层的下一个结点。BW是回退指针&＃xff08;backward&＃xff09;&＃xff0c;用于查找的时候回退。然后下面是score和对象本身object。


可以看到一个是dict结构&＃xff0c;主要key是其集合元素&＃xff0c;而value就是对应分值&＃xff0c;而zkiplist作为跳跃表&＃xff0c;按照分值排序&＃xff0c;方便定位成员


zskiplistNode中的robj指针指向具体元素&＃xff0c;注意这个指针和dict中key指针指向同一个元素&＃xff0c;其中backward后腿指针便于回溯

复杂度

第一层索引节点n/2,第二层索引节点n/4,第三层索引节点n/8,以此类推第n层节点n 得到h&＃61;logn - 1。
由上图可以知道&＃xff0c;当我们要找到8号这个节点的时候&＃xff0c;我们在k级索引发现5<8<9&＃xff0c;故我们要到k-1索引下找&＃xff0c;但是发现7<8<9,故我们要到原始链表找&＃xff0c;且k索引层最多遍历1&＃xff0c;5&＃xff0c;9三个节点&＃xff0c;k-1最多遍历5&＃xff0c;7&＃xff0c;9三个节点&＃xff0c;故跳表的时间复杂度为O(3logn)&＃61;O(logn),索引节点总数为&＃xff1a;n/2 &＃43; n/4 &＃43; n/8 &＃43; … &＃43; 8 &＃43; 4 &＃43; 2 &＃61;n&＃xff0c;故空间复杂度为O(n)

为什么选择了跳跃表而不是红黑树

1. 在做范围查找的时候&＃xff0c;平衡树比skiplist操作要复杂。在平衡树上&＃xff0c;我们找到指定范围的小值之后&＃xff0c;还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造&＃xff0c;这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单&＃xff0c;只需要在找到小值之后&＃xff0c;对第1层链表进行若干步的遍历就可以实现。
2. 平衡树的插入和删除操作可能引发子树的调整&＃xff0c;逻辑复杂&＃xff0c;而skiplist的插入和删除只需要修改相邻节点的指针&＃xff0c;操作简单又快速。
3. 从内存占用上来说&＃xff0c;skiplist比平衡树更灵活一些。一般来说&＃xff0c;平衡树每个节点包含2个指针&＃xff08;分别指向左右子树&＃xff09;&＃xff0c;而skiplist每个节点包含的指针数目平均为1/(1-p)&＃xff0c;具体取决于参数p的大小。如果像Redis里的实现一样&＃xff0c;取p&＃61;1/4&＃xff0c;那么平均每个节点包含1.33个指针&＃xff0c;比平衡树更有优势。
4. 查找单个key&＃xff0c;skiplist和平衡树的时间复杂度都为O(log n)&＃xff0c;大体相当&＃xff1b;而哈希表在保持较低的哈希值冲突概率的前提下&＃xff0c;查找时间复杂度接近O(1)&＃xff0c;性能更高一些。所以我们平常使用的各种Map或dictionary结构&＃xff0c;大都是基于哈希表实现的。
5. 从算法实现难度上来比较&＃xff0c;skiplist比平衡树要简单得多。

参考
https://blog.csdn.net/qq_38286618/article/details/102530020
https://blog.csdn.net/weixin_39030846/article/details/112433527
https://www.cnblogs.com/cjjjj/p/12751487.html (redis为什么选择了跳跃表而不是红黑树)