Skip to main content

Redis的跳表是什么？

作者：程序员马丁

在线博客：https://open8gu.com

note

大话面试，技术同学面试必备的八股文小册，以精彩回答应对深度问题，助力你在面试中拿个offer。

回答话术​

跳表是 ZSet 的底层实现之一，它是一种包含多级链表的数据结构，它允许通过额外的索引层来实现快速查找，实现 O(logN) 的平均复杂度。

Redis 的跳表节点里面保存了 score 和 member，所有的节点都按照 score 排序，而当 score 相同时，会再按照 member 的字典顺序进行排序。

虽然理想情况下，跳表的相邻两层之间的节点数量比是 2:1 ，但是这样做会导致在操作时付出额外的代价重建索引，因此 Redis 的使用了一种随机算法来生成索引：生成一个 0 到 1 之间的随机数，然后判断是不是小于 0.25，如果是就加一层，然后继续重复这个动作，直到随机数大于 0.25 或者到了最大层高为止。

这个策略保证了高层节点相对较少而底层节点相对较多，进而保证了索引的节点密度会随着层级从底层往上逐渐减少。

相比起具有同样查找效率的二叉树，它占用的内存更小，对范围操作的支持更好，并且修改的代价更小，实现也更简单。

问题详解​

1. 什么是跳表？​

跳表在传统链表的基础上，额外添加了多层的索引表，每一层索引表都是原始原始链表的子集，它们只包含原始链表的一部分元素元素。

当查找时，从顶层链表开始，逐层向下跳跃，直到找到元素或者找到一个接近目标元素的位置，然后再在底层链表中线性查找。

Skip_list_add_element-en.gif

以上图为例，现有 30 到 90 共六个元素，我们分别为其建立三级索引，每一级索引包含的原始数量从上到下依次增加。当我们插入一个元素 80 的时候：

  1. 检查第四层链表，找到离 80 最接近的 30；
  2. 从 30 向下进入第三层链表，找到离 80 最近的 50；
  3. 从 50 向下进入第二层链表，找到离 80 最近的 70；
  4. 从 70 进入第一层链表，发现 70 以后就是 90，于是直接插入 80；

查询的流程也是一样的。当节点数量比较多时，跳表能够大幅度的提高查询效率。

2. 数据结构？​

跳表具有四个属性：

  • header：指向头节点的指针。
  • tail：指向尾节点的指针。
  • level：跳表的最大层数。
  • length：跳表的长度。

而跳表中的节点则具有四个属性：

  • level：节点的层，该结构体包含两个属性：
    • forward：指向下一节点的前进指针。
    • span：下一节点与当前节点之间的跨度。
  • backward：指向前一个节点的指针，用于逆向遍历。
  • score：即 ZSet 中的分数 score，通过比较分数可以确定节点之间的先后顺序。
  • obj：指向成员 member 的指针。

image.png

3. 数据的保存方式​

跳表使用 obj 指针来指向 member，使用 socre 保存分值，同时又使用了字典来保存成员 member 和 score 之间的映射关系，两者共享相同的 member 对象，因此即使同时使用了两种数据结构，也只占用一份内存。

正因如此，实际上有序集合 ZSet 的底层实现其实同时包括三种数据结构：字典、跳表和压缩列表。

当使用压缩列表时，score 和 member 都保存在列表的节点中。而当使用跳表时，除了在跳表的节点中记录 score 和 member（的指针）外，还额外在字典值记录的 member 与 score 的映射关系。

4. score 相同怎么办？​

image.png

在跳表中，如果出现多个具有相同 score 的 member，即 score 相同的情况，Redis 将根据 member 的字典顺序来确定它们在跳表中的位置顺序。

比如，如果向一个 ZSet 同时添加了三个 score 为 4 的字符串 "b"，"a"，"c"，那么在跳表中会有三个 score 为 4 的节点。然后，根据 member 的字典排序结果，最终它们在跳表中的顺序会是 "a"，"b"，"c"。

在跳表中，节点的顺序实际上就是排位，当执行诸如 ZRANK 等排位相关命令时，会按照这个顺序来操作。

关于字典排序的顺序，可以简单理解为按照 ASCII 码进行排序，首先是 0-9，然后是 A-Z，最后是 a-z。

具体参见官方文档：Redis ZADD 官方文档 sourl.cn/UQRuUa

5. 如何建立索引？​

理想情况下，我们会希望每一层索引中的节点数量都是下一层的一半，即相邻两层节点数量之比为 2:1。这样就可以保证查找的复杂度为 O(logN)，相当于二分查找。

不过，如果想要实现这一点，必然会导致需要额外的开销来频繁更新索引。因此，Redis 选择通过一种随机算法在创建节点时生成层数：

  1. 生成一个介于 0 到 1 之间的随机数，如果该随机数小于 0.25，就加一层；
  2. 重复上述步骤，直到随机数大于 0.25 ，或者当前层数已经达到最大值为止（最新版本最大层数为 32）；

这种策略的巧妙之处在于，随着次数的增加，连续掷出小于 0.25 的概率会越来越小，因此高层节点会相对较少，而底层节点会相对较多，从而保证了索引的节点密度会随着层级从底层往上逐渐减少。

为了便于理解，我们可以简单粗暴的认为，层高为 2 的节点出现的概率是 0.25，而层高为 3 的节点出现的概率为 0.25 * 0.25……以此类推。当然，实际上概率肯定不是这么算的，不过当层数越高，则此类节点出现的概率越低，这一点的没错的。

6. 为什么不用平衡树？​

  • 节省内存：跳表相比于树占用的内存较少，而且还可以通过调整层级生成的随机数来平衡索引效率和内存占用。
  • 对范围操作支持友好：ZSet 经常需要进行诸如 ZRANGE 或 ZREVRANGE 这种范围操作，跳表在这方面操作的效率不比平衡树差。
  • 修改操作的代价小：平衡树在修改后需要重新平衡，而跳表的效率更高。
  • 实现简单：跳表相比树的实现更为简单。

具体可以参见作者在下面这个问题的回答：关于平衡树 sourl.cn/7WP2cn

Table of Contents