InnoDB为何不青睐跳表，Redis又怎舍B树？
- 内容介绍
- 文章标签
- 相关推荐
哎呀， 聊起 InnoDB 和 Redis 的“偏爱”，我心里总是七上八下的，像是刚打开的盒子里蹦出一只小猫，又像是半夜被闹钟吵醒的梦魇——糊里糊涂又不敢怠慢那个。
先说 InnoDB，为什么它不爱跳表？
共勉。 先抛个大招：磁盘！InnoDB 是磁盘为王的老古董， 硬盘的转头嗡嗡作响，SSD 的闪光灯眨呀眨，它们都不想被乱七八糟的链表拖慢。
性价比超高。 跳表在内存里跑得飞快， 却在磁盘上像蜗牛背着壳爬——每一次指针跳转都要一次随机 I/O，磁头得来回扫来扫去，那叫一个卡！于是 InnoDB 毅然决定：B+ 树才是正道。
B+ 树的优势简直是天经地义：
- 节点大小恰好和磁盘页对齐，读写一次就能把整层节点塞进页缓存。
- 叶子节点之间用链表串起来范围查询只要顺序遍历几页就搞定。
- 多路平衡，让树高保持在 O，深度低到可以直接忽略不计。
- 并发控制成熟：行锁、MVCC、细粒度锁……这些玩意儿都是围绕 B+ 树设计的。
磁盘友好的特性
哎，对！ 页面对齐——每个节点恰好占满 16KB 页面；顺序预读——叶子链表让范围查询几乎是线性扫描；分裂合并——插入删除时只动局部页面不会全局重排。
| 特性 | B+树 | 跳表 |
|---|---|---|
| I/O 友好度 | ★★★★★ | ★☆☆☆☆ |
| 实现复杂度 | ★★★☆☆ | ★★★★★ |
| 范围查询效率 | ★★★★★ | ★★☆☆☆ |
| 并发支持度 | ★★★★☆ | ★☆☆☆☆ |
| 空间占用率 | ★★★☆☆ | ★★★★☆ |
看完这张表， 你可能会想：“哎呀，这么明显，还用跳表干嘛？”别急，后面还有更刺激的内幕，薅羊毛。。
再说 Redis，为何它抛弃了 B+ 树而拥抱跳表？
Redis 本质上是内存数据库 + 网络服务层叠加体”，所以它根本不需要考虑磁盘那点破事儿。内存里乱弹琴，指针随意跳跃，就是它的狂欢节，ICU你。！
跳表在 Redis 中有两个主要角色：
- 实现 Sorted Set的底层结构， 让排名、区间、打分操作都能在 O 时间完成。
- 配合哈希表，实现键值对快速定位与有序遍历两手抓，两手都硬。
我们来看看 Redis 跳表实现细节吧：
- 每个节点都有 forward 指针数组， 长度由随机函数决定，一般概率 p=0.25； - 随机层数让整体高度呈几何分布，从而保证平均 O 的查找代价； - 插入时只需要更新前驱节点的 forward 指针，不必像 B+ 树那样做页面分裂或合并； - 删除同理，只要把指针重新指向后继即可。
| # 排名 | Redis 跳表 vs B+树 对比 | |
|---|---|---|
| 1. | 性能维度||
| 查找速度 | ≈ O | |
| 插入/删除 | ≈ O | |
| 空间开销 | 略高于单链表， 但远低于 B+树页结构冗余 | |
| “简单”往往胜过“严谨”。 | ||
| 如果你硬要把 B+ 树搬进 Redis， 那就等着面对频繁 GC、指针碎片和极端情况下的性能崩溃吧！ | ||
| 再聊点“情感”吧——我对这两种结构的个人感悟：
A. 当我第一次看到 InnoDB 的 B+ 树代码， 我仿佛看到了老爷爷在篝火旁慢慢雕刻木棍，每一刀都精确无误，却花了好几天才完成。那种稳重、可靠，却带点“老派”的味道，让我敬畏不已，这就说得通了。。 B. 而当我第一次调试 Redis 的 skiplist 时我感觉自己像是在玩一款无限升级的跑酷游戏。每次 insert 都像给角色加速，一瞬间冲到顶层，然后再轻飘飘地滑下来。爽啊！但有时候也会卡住——特别是随机层数太高时那种 “哎呀，我到底该怎么走？” 的迷茫感，比起 B+ 树来的更真实、更刺激，KTV你。。
| ||
哎呀， 聊起 InnoDB 和 Redis 的“偏爱”，我心里总是七上八下的，像是刚打开的盒子里蹦出一只小猫，又像是半夜被闹钟吵醒的梦魇——糊里糊涂又不敢怠慢那个。
先说 InnoDB，为什么它不爱跳表？
共勉。 先抛个大招：磁盘！InnoDB 是磁盘为王的老古董， 硬盘的转头嗡嗡作响，SSD 的闪光灯眨呀眨，它们都不想被乱七八糟的链表拖慢。
性价比超高。 跳表在内存里跑得飞快， 却在磁盘上像蜗牛背着壳爬——每一次指针跳转都要一次随机 I/O，磁头得来回扫来扫去，那叫一个卡！于是 InnoDB 毅然决定：B+ 树才是正道。
B+ 树的优势简直是天经地义：
- 节点大小恰好和磁盘页对齐，读写一次就能把整层节点塞进页缓存。
- 叶子节点之间用链表串起来范围查询只要顺序遍历几页就搞定。
- 多路平衡，让树高保持在 O，深度低到可以直接忽略不计。
- 并发控制成熟：行锁、MVCC、细粒度锁……这些玩意儿都是围绕 B+ 树设计的。
磁盘友好的特性
哎，对！ 页面对齐——每个节点恰好占满 16KB 页面；顺序预读——叶子链表让范围查询几乎是线性扫描；分裂合并——插入删除时只动局部页面不会全局重排。
| 特性 | B+树 | 跳表 |
|---|---|---|
| I/O 友好度 | ★★★★★ | ★☆☆☆☆ |
| 实现复杂度 | ★★★☆☆ | ★★★★★ |
| 范围查询效率 | ★★★★★ | ★★☆☆☆ |
| 并发支持度 | ★★★★☆ | ★☆☆☆☆ |
| 空间占用率 | ★★★☆☆ | ★★★★☆ |
看完这张表， 你可能会想：“哎呀，这么明显，还用跳表干嘛？”别急，后面还有更刺激的内幕，薅羊毛。。
再说 Redis，为何它抛弃了 B+ 树而拥抱跳表？
Redis 本质上是内存数据库 + 网络服务层叠加体”，所以它根本不需要考虑磁盘那点破事儿。内存里乱弹琴，指针随意跳跃，就是它的狂欢节，ICU你。！
跳表在 Redis 中有两个主要角色：
- 实现 Sorted Set的底层结构， 让排名、区间、打分操作都能在 O 时间完成。
- 配合哈希表，实现键值对快速定位与有序遍历两手抓，两手都硬。
我们来看看 Redis 跳表实现细节吧：
- 每个节点都有 forward 指针数组， 长度由随机函数决定，一般概率 p=0.25； - 随机层数让整体高度呈几何分布，从而保证平均 O 的查找代价； - 插入时只需要更新前驱节点的 forward 指针，不必像 B+ 树那样做页面分裂或合并； - 删除同理，只要把指针重新指向后继即可。
| # 排名 | Redis 跳表 vs B+树 对比 | |
|---|---|---|
| 1. | 性能维度||
| 查找速度 | ≈ O | |
| 插入/删除 | ≈ O | |
| 空间开销 | 略高于单链表， 但远低于 B+树页结构冗余 | |
| “简单”往往胜过“严谨”。 | ||
| 如果你硬要把 B+ 树搬进 Redis， 那就等着面对频繁 GC、指针碎片和极端情况下的性能崩溃吧！ | ||
| 再聊点“情感”吧——我对这两种结构的个人感悟：
A. 当我第一次看到 InnoDB 的 B+ 树代码， 我仿佛看到了老爷爷在篝火旁慢慢雕刻木棍，每一刀都精确无误，却花了好几天才完成。那种稳重、可靠，却带点“老派”的味道，让我敬畏不已，这就说得通了。。 B. 而当我第一次调试 Redis 的 skiplist 时我感觉自己像是在玩一款无限升级的跑酷游戏。每次 insert 都像给角色加速，一瞬间冲到顶层，然后再轻飘飘地滑下来。爽啊！但有时候也会卡住——特别是随机层数太高时那种 “哎呀，我到底该怎么走？” 的迷茫感，比起 B+ 树来的更真实、更刺激，KTV你。。
| ||