面试官：讲讲redis的zset原理

在 Redis 中，zset（有序集合）是一种既能保存元素的唯一性，又能通过分数进行排序的数据结构。zset 的内部实现基于两种数据结构的组合：跳表（skiplist）和 哈希表（hash table），这两者结合实现了高效的数据存储和快速的排名操作。

1. 跳表（skiplist）

• 跳表是一种层级化的链表结构，可以理解为多个“平行的链表”，每一层都有不同的跨度。每一层都链接一部分节点，最底层的链表会完整地链接所有节点。
• 当进行查找或插入操作时，跳表会通过跳过一些中间节点来加速搜索，尤其适合用于排序的快速查找。
• 在 Redis 的 zset 中，跳表结构按照每个元素的分数（score）排序，允许 Redis 高效地进行范围查找（比如“查找分数在一定范围内的元素”）和顺序操作（比如“取前 N 个元素”）。

2. 哈希表（hash table）

• Redis 使用哈希表来存储元素的唯一性和快速定位。
• 每个元素的成员名（member）作为哈希表的 key，分数作为值，这样我们可以通过哈希表快速地检查一个成员是否存在，并且在 O(1) 的时间复杂度下读取或更新其分数。

3. 两者结合

• zset 中，每个元素的分数会存储在跳表中来保证排序，同时在哈希表中存储用于快速访问。
• 这种结合使得 zset 可以在 O(log N) 的时间内完成插入、删除、更新等操作，且还能维持元素的唯一性和排序。

为什么使用跳表？

跳表的基本思想

假设我们有一个链表来存储一系列排序好的数据。通常情况下，如果你要在链表中查找某个数据，你只能一个个节点往后走，效率较低（O(n)）。而跳表通过增加额外的“跳跃”层级来实现更快的查找。

跳表的结构

跳表可以看成是一层一层的链表：

• 底层：是完整的链表，包含所有的数据节点。
• 上层：是每隔几个节点抽取一个的链表，只包含部分数据节点。
• 每一层的节点可以跳跃更多节点，逐层往上，节点数会越来越少。

就像上图那样。比如要找42，那么先找到L3 的14，往下走，到L2，还是14，往下走，找到L1 的34，往下走，找到42.

每一层选择的数字都是随机的，但是遵循的概率为1/2，1/4....

为什么Redis选择使用跳表而不是红黑树来实现有序集合？

Redis 中的有序集合(zset) 支持的操作：

1. 插入，删除，查找，有序输出一个元素

2. 按照范围区间查找元素（比如查找值在 [1, 100] 之间的数据）

其中，第一条红黑树也可以完成，且时间复杂度跟跳表相同。但第二条查找数据这个操作，跳表更方便，因为找到以后往后遍历就可以了，很高效。