面试题：Redis有序集合对象排序算法的基础理解

Question

简述Redis有序集合对象排序算法所依赖的数据结构，以及在添加元素时如何维持排序的一致性。

Answer 1

数据结构

1. 跳跃表（Skip List）：
   • Redis 有序集合在实现上使用跳跃表来进行排序。跳跃表是一种随机化的数据结构，它基于链表，通过在每个节点中维持多个指向其他节点的指针，来达到快速访问节点的目的。
   • 跳跃表的节点包含多个层（level），每个层都有一个指向后续节点的指针。层数是随机生成的，这使得跳跃表在平均情况下能够达到接近平衡树的查找效率（O(log n)），而其实现相对平衡树更为简单。
   • 跳跃表的节点结构除了多个层的指针外，还包含元素的分值（score）和成员（member），分值用于排序，成员是集合中的实际数据。
2. 字典（Hash Table）：
   • Redis 有序集合同时还使用字典来存储成员到分值的映射。字典提供了 O(1) 的查找效率，使得可以快速根据成员找到其对应的分值，这在很多操作（如查询成员分值、判断成员是否存在等）中非常有用。

添加元素时维持排序一致性的方式

1. 跳跃表插入：
   • 当向有序集合中添加一个新元素时，首先要确定该元素在跳跃表中的插入位置。这通过在跳跃表中进行查找来实现，从跳跃表的最高层开始，比较当前节点和下一个节点的分值。
   • 如果下一个节点的分值大于要插入元素的分值，或者下一个节点为 NULL，则确定当前位置为插入点。然后在每一层都找到对应的插入位置，并插入新节点。
   • 为了维持跳跃表的随机性，新节点的层数是随机生成的。生成过程通常是通过一个随机函数，以一定的概率决定新节点是否增加一层。
2. 字典更新：
   • 在跳跃表插入新元素后，同时要更新字典，将新添加的成员和其对应的分值插入到字典中，以保证字典中成员到分值映射的完整性。这样，下次查询成员分值时，通过字典可以快速获取，同时也维持了整个有序集合数据结构的一致性。