Redis 的有序集合为什么选跳表而不是红黑树
翻开 Redis 的源码，
Redis 作者 antirez 本人在邮件列表里解释过这个选择。他的理由有三层。第一，跳表的实现比红黑树简单太多。红黑树的插入删除要处理旋转、变色、兄弟侄子关系，调试起来像在解魔方；跳表就是多层链表，插入靠随机抛硬币决定层数，删除直接摘节点，代码量差了一截。第二，跳表的范围查询天然友好。
跳表的核心思路其实很直觉：一条单链表查找是 O(N)，如果在每隔一个节点上加一层"快线"，查找就近似二分了；再加一层更快线，继续递推。层数由抛硬币（概率 1/2 升层）决定，期望层数 log₂N，所以查找、插入、删除都是期望 O(log N)。它用随机的概率一致性替代了红黑树严格的旋转不变量。
!skip list structure
看源码还有一个细节容易漏掉：Redis 的跳表每个节点最多 32 层（
所以这个选择本质上是工程判断：在理论复杂度相同的前提下，选可读性更强、范围操作更顺手的数据结构。
#CS
翻开 Redis 的源码，
t_zset.c 里有序集合（ZSET）的底层实现有两个：元素少时用 ziplist，元素多时切换到 skiplist。跳表这个词很多人听过，但未必想过一个更深层的问题——为什么不是红黑树？Redis 作者 antirez 本人在邮件列表里解释过这个选择。他的理由有三层。第一，跳表的实现比红黑树简单太多。红黑树的插入删除要处理旋转、变色、兄弟侄子关系，调试起来像在解魔方；跳表就是多层链表，插入靠随机抛硬币决定层数，删除直接摘节点，代码量差了一截。第二，跳表的范围查询天然友好。
ZRANGEBYSCORE 这种操作在跳表里就是从底层定位起点后沿链表遍历，O(log N + M) 一路走完；红黑树做范围查询要先定位起点，再中序遍历，实现路径更曲折。第三，跳表每个节点有回退指针（backward pointer），可以高效做 ZREVRANGE，而红黑树反向遍历需要额外处理。跳表的核心思路其实很直觉：一条单链表查找是 O(N)，如果在每隔一个节点上加一层"快线"，查找就近似二分了；再加一层更快线，继续递推。层数由抛硬币（概率 1/2 升层）决定，期望层数 log₂N，所以查找、插入、删除都是期望 O(log N)。它用随机的概率一致性替代了红黑树严格的旋转不变量。
!skip list structure
看源码还有一个细节容易漏掉：Redis 的跳表每个节点最多 32 层（
ZSKIPLIST_MAXLEVEL 宏），概率用的是 1/4 而非经典的 1/2，这让平均层数从 log₂N 降到 log₄N，空间更省，代价只是常数因子的差异。所以这个选择本质上是工程判断：在理论复杂度相同的前提下，选可读性更强、范围操作更顺手的数据结构。
#CS
