跳表和红黑树这类平衡树有什么区别？为什么 Redis 常用跳表？
简化版
跳表用多级链表和随机层数实现近似平衡，查询、插入、删除期望 O(log n)。红黑树靠旋转和颜色保证最坏 O(log n)。跳表实现简单、范围遍历方便、并发改造友好，所以 Redis 有序集合底层使用跳表加哈希表。
详细版
跳表不是树，但常被拿来和平衡树比较，因为它也支持有序集合操作：
- 查找：从最高层向右走，走不动就下层；
- 插入：随机生成节点层数，更新多层前驱指针；
- 删除：移除各层中的该节点。
与红黑树相比：
- 跳表是概率平衡，期望 O(log n)，极端情况下理论上可能退化；
- 红黑树是确定性平衡，最坏 O(log n)；
- 跳表范围遍历从底层链表顺序走很自然；
- 红黑树实现旋转和删除修复更复杂。
Redis 的 zset 使用 dict + skiplist：dict 负责按 member O(1) 查分数，skiplist 负责按 score 排序和范围查询。
完整版教学
一、为什么跳表能和平衡树放在一起比较
跳表本质是有序链表的加速版。普通有序链表查找要 O(n)，因为只能一格一格走。跳表在链表上方增加多级索引，高层跳得远，低层走得细，效果类似平衡树从根到叶逐步缩小范围。
所以跳表和红黑树解决的是同一类问题：动态有序集合。它们都支持查找、插入、删除、范围遍历，只是平衡方式完全不同。
记忆钩子：红黑树靠旋转修树形，跳表靠随机搭电梯；目标都是少走路。
二、跳表查询怎么走
查询从最高层头节点开始。若右侧下一个节点的 key 小于目标，就向右；否则向下一层。这样不断右移和下沉，最后在底层找到目标或确定不存在。
Level 3: head --------> 30
Level 2: head --> 10 -> 30
Level 1: head -> 5 -> 10 -> 20 -> 30
查 20: 高层先跳到 10，再下沉到底层走到 20这个过程像在多层高速路上先走快速路，再下到辅路精确定位。随机层数让节点大致呈指数级减少，高层节点少，查询路径期望 O(log n)。
三、随机层数为什么能近似平衡
插入节点时通常用抛硬币方式决定层高：第 1 层必有，每次以概率 p 晋升到更高一层。若 p=1/2，大约一半节点有第 2 层，四分之一节点有第 3 层，八分之一节点有第 4 层。
n=1024
第1层约1024个
第2层约512个
第3层约256个
...
第10层约2个这种指数衰减让跳表高度期望 O(log n)。它不是像红黑树那样给出确定结构约束，而是用概率保证整体形态不会太差。
四、和红黑树的核心对比
红黑树的优势是最坏复杂度确定，理论保证强；缺点是插入删除修复 case 多。跳表优势是实现直观，插入删除只改若干层前后指针；缺点是依赖随机，理论最坏可能退化，且需要额外多级指针空间。
| 维度 | 跳表 | 红黑树 |
|---|---|---|
| 平衡方式 | 随机层数 | 颜色 + 旋转 |
| 复杂度 | 期望 O(log n) | 最坏 O(log n) |
| 范围遍历 | 底层链表天然顺序 | 中序或后继遍历 |
| 实现难度 | 相对简单 | 删除修复复杂 |
| 空间 | 多级指针 | 左右孩子和颜色 |
工程上两者都可用，选择常取决于实现复杂度、范围查询、并发和已有库。
五、为什么 Redis zset 用跳表
Redis 有序集合需要按 score 排序、范围查询、排名查询，还需要按 member 快速定位。它采用 dict + skiplist 组合：dict 从 member 找 score，skiplist 按 score 维护顺序。跳表的底层链表非常适合范围扫描，比如取某个分数区间内的元素。
此外，跳表实现比红黑树更直观，范围遍历时从起点一路向后走即可。Redis 的跳表还维护 backward 指针和 span，用来支持逆向遍历和排名相关操作。
六、跳表是不是一定比红黑树好
不是。若场景要求严格最坏时间上界，红黑树的确定性更强。若语言标准库已经提供高质量 TreeMap/TreeSet，直接使用红黑树也更省心。跳表适合需要较简单实现、范围遍历频繁、或并发结构设计更方便的场景。
跳表的随机性通常在工程上足够可靠，但它仍是期望复杂度。面试回答时不要把跳表说成严格平衡树，它是概率型有序索引。
七、常见误区与追问
- 误区：跳表是平衡二叉树的一种。 跳表是多级链表，不是树。
- 追问：跳表为什么能 O(log n)？ 随机层数让高层节点数指数级减少，查询路径期望对数。
- 误区：跳表最坏复杂度也是严格 O(log n)。 理论最坏可能退化，常说期望 O(log n)。
- 追问：Redis zset 为什么还要 dict？ 跳表按 score 有序，dict 按 member 快速查找，两者职责不同。
- 误区：红黑树范围遍历很差。 红黑树也能范围遍历，只是跳表底层链表顺序扫描更直接。
八、加强记忆
跳表和平衡树都服务动态有序集合。红黑树用颜色和旋转提供确定最坏 O(log n)，跳表用随机层数提供期望 O(log n)。Redis 选择跳表，是因为范围查询、顺序遍历、排名辅助和实现复杂度都很合适。记住一句：跳表不是树，但它用多级索引达到了类似平衡树的查找效果。