目录

  1. 概述
  2. 跳表与红黑树的抉择
    1. Redis Zset 为什么使用跳表而不使用红黑树
    2. HashMap 为什么使用红黑树而不使用跳表
  3. 为什么有序集合需要同时使用跳表和字典来实现？
  4. 附录

概述

zset 的底层数据结构是跳表，不由得产生了这样一个想法：为什么 redis 的 zset 底层选择使用跳表而不是用红黑树来进行存储，毕竟 HashMap 的底层最终使用的就是红黑树

跳表与红黑树的抉择

Redis 只在两个地方用到了跳跃表，一个是实现有序集合键(zset)，另一个是在集群节点中用作内部数据结构，除此之外，跳表在 Redis 里面没有其他用途。但是为什么底层使用的是跳表而不是红黑树？

Redis Zset 为什么使用跳表而不使用红黑树

Redis 只在两个地方用到了跳跃表，一个是实现有序集合键(zset)，另一个是在集群节点中用作内部数据结构，除此之外，跳表在 Redis 里面没有其他用途

❓ 为什么 Redis 选择使用跳表而不是使用红黑树尼？

  1. 从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含 2 个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数 p 的大小。如果像 Redis 里的实现一样，取p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势
  2. 跳表在范围查询的时候效率是高于红黑树的，因为跳表是从上层向下层查找的，上层的区域范围更广，可以快速定位到查询到范围
  3. 平衡树的插入和删除操作 kennel 引发子树的调整、逻辑复杂、而跳表只需要维护相邻节点即可
  4. 从算法实现难度上来比较，skiplist 比平衡树要简单得多

HashMap 为什么使用红黑树而不使用跳表

  1. 跳表需要维护额外的多层链表，是空间换时间的做法，红黑树不用占用多余的空间
  2. HashMap 的 Entry 并没有内在的排序关系，所以也无法使用跳表，因为跳表本身要求要存在排序关系

为什么有序集合需要同时使用跳表和字典来实现？

在理论上，有序集合可以单独使用字典或跳表的其中一种数据结构来实现，但无论单独使用字典还是跳跃表，在性能上对比起同时使用字典和跳跃表都会有所降低。

举个例子，如果我们只使用字典来实现有序集合，那么虽然能够以 O(1) 复杂度查找成员的分值这一特性会被保留，但是，因为字典以无需的方式来保存集合元素，所以每次在执行范围型操作——比如：ZRANK、ZRANGE 等命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序需要至少 O(NlogN)时间复杂度，以及额外的 O(N)内存空间（因为要创建一个数组来保存排序后的元素）

另一方面，如果只是使用跳跃表实现有序集合，那么跳跃表执行范围型操作的所有优点都会被保留，但因为没有来字典，所以根据成员查找分值这一操作的复杂度将从 O(1) 上升到 O(logN)。因为以上原因，为了让有序集合的查找和范围型操作都尽可能快地执行，Redis 选择了同时使用字典和跳表两种数据结构来实现有序集合

redis设计与实现

附录

HashMap 为什么用红黑树而不用跳表？redis 的 zset 为什么用跳表而不用红黑树？
redis 为什么选择了跳跃表而不是红黑树