专业书籍精读 · Database Internals · 第 2 章
Database Internals · Ch 2 · Alex Petrov · 2019
你在淘宝按订单号查一笔三年前的订单，几十亿条记录里，零点几秒就翻了出来。数据库靠的是索引——一本能瞬间定位的目录。这一章讲的就是那本目录几乎唯一的做法：B-Tree。它 1972 年被提出，五十多年过去，MySQL、PostgreSQL、SQLite、Oracle 的默认索引仍然是它。为什么偏偏是它？
计算机课上教的「查找树」，是每次问一个是非题：比它大还是比它小？往左还是往右？这在内存里非常好用。可一旦把同样的树搬到硬盘上，它就慢得不能用——快慢的账，突然算错了。
关键在于：硬盘不零卖。哪怕只想读一个字节，它也得整块整块地搬——一次最少几千字节。跑一趟很贵，搬多搬少反倒差别不大。
而那种「每次只岔两条路」的树，一个岔路口只有一个小小的路标。几十亿条数据，你得连着问三十来次「往左还是往右」，每问一次就要往硬盘跑一趟。慢就慢在跑腿的次数上，不是比大小的次数上。
第一招是不再让一个岔路口只放一个路标。既然每次都要整块搬，那就把这一整块塞满路标——一页纸上列出几百个区间：「订单号 1 万到 5 万在这架，5 万到 9 万在那架……」看一眼就知道下一步去哪，就像查字典先看侧边的字母索引。结果是树被压扁了：原来三十几层，现在三四层；最上面那两三层很小、常年待在内存里，于是查一次通常只要真去硬盘跑一趟。
第二招更妙：这棵树是从下往上长的。新数据先塞进最底下那一页；那页满了就一分为二，把中间那个路标交给上一级；上一级也满了再往上交；一直到最顶上那页也撑不住时，整棵树才整体长高一层。因为长高永远发生在顶上，每片叶子离树根永远一样远——它天生就是平的，不用像别的树那样翻来覆去调平衡。
第三招给「翻页」用：真正的数据只放最底下一层，而最底层的页手拉手串成一条链。所以「把三月一号之后的一千条订单列出来」，就是找到起点顺着链走，不用再爬回树顶。
五十年不倒，是因为它一次满足了三件事：找一条快、连着找一批也快、还能随时插删并保持有序。哈希表找一条也快，但它不认顺序，后两件都做不了。
诚实的代价只有一句：它偏爱按顺序灌进来的数据——自增编号、时间戳都省心；主键要是随机码那样到处乱插，页就会被劈得普遍只装半满，白占空间、写入也更费劲。
B-Tree 不是「更聪明的查找树」，而是为硬盘的脾气重新设计过的查找树：既然硬盘只能整块搬，那就把一整块塞满路标、一次岔出几百条路，把树从三十层压成三四层——省的不是比大小的次数，是跑硬盘的次数。
想进到具体机制、记号和示意图？ → 切到精读版
这一章的核心命题：B-Tree 不是「更快的查找树」，而是「为块设备重写过的查找树」。它优化的不是比较次数，而是磁盘往返次数——把一个节点撑到整整一页、把扇出（fanout）从 2 拉到几百上千，树高就从几十层塌成三四层；再让它从叶子往上长，于是天生完美平衡、无需旋转。这就是五十年来磁盘数据库索引的默认答案。
8 KB、InnoDB 默认 16 KB。Part I「存储引擎」的第 2 章。上承 Ch1 的三个旋钮——B-Tree 正是「缓冲 + 原地改 + 按键有序」这一角的经典实现；下启 Ch3（页内怎么摆字节）、Ch4（分裂合并与并发的工程细节）、Ch6（变体）与 Ch7（它的对立面：LSM-Tree）。对应现实里几乎所有磁盘型 OLTP 数据库的默认索引。
拿一个场景当锚：一张 20 亿行的订单表，要求按订单号点查的 p99（一百个请求里第 99 慢的那个）压在 10 ms 以内、扛 5 万 QPS。全表扫描不行；全塞内存也不行——每行 200 字节就是 400 GB。所以索引必须住在磁盘上，而磁盘的计价单位不是「比较一次」，是一次随机 I/O：机械盘约 10 ms（每盘约 100 IOPS），NVMe SSD 约 50–100 µs。
把教科书里的平衡二叉树直接搬上去会怎样？20 亿条要走大约 log₂(2×10⁹) ≈ 31 层——最多 31 次随机 I/O：机械盘上 0.3 秒，SSD 上也有 2–3 毫秒，且一次查询就吃掉三十次 IOPS 预算。这章要解决的就是：把内存里的查找结构，改造成一个「以页读次数计价」的结构。
Petrov 把原因拆得很干脆，四条：
log₂ N；而树高的单位不是「层」，是「磁盘往返」。所以这一章的钩子是：你以为查找结构比的是「问几次问题」，其实磁盘上比的是「跑几趟腿」。
磁盘不零卖。机械盘按扇区（512 字节或 4 KB）读写，文件系统按页（通常 4 KB）读写，数据库自己再定一层页（4–16 KB）。读 1 个字节和读一整页，成本几乎一样——大头是那一趟往返。SSD 更进一步：它不能原地覆写，最小擦除单位是比页更大的块，由内部的 FTL（闪存转换层，把「逻辑地址」映射到「实际闪存位置」）腾挪。
推论只有一句，却决定了整章：目标函数从「最少的比较次数」变成「最少的页读次数」。于是节点大小应当等于页大小——一趟既然躲不掉，就让搬回来的东西全都有用。算个量级：PostgreSQL 一页 8 KB，一条索引项按「键 16 字节 + 指针 8 字节 + 槽位开销 8 字节 ≈ 32 字节」估，一页约装 250 条路标，于是 3 层覆盖 1560 万条、4 层覆盖 39 亿条——刚才那 20 亿行，四层就装下了。
B-Tree 由 Bayer 与 McCreight 在 1972 年提出，Comer 1979 年的综述《The Ubiquitous B-Tree》把它推成教科书标准。它是二叉查找树的推广：一个节点不再只存一个键、只岔两条路，而是存一串有序的键、岔出很多条路。三种角色：根节点（唯一入口）、内部节点（只放路标）、叶子节点（放数据或指向数据的位置）。
最要紧的一条结构常识：一个内部节点有 n 个分隔键，就有 n+1 个指针——n 个路标把键空间切成 n+1 段。比如 50 | 90 切出「<50」「50–90」「≥90」三段，对应三个孩子。一次查找就是从根开始，在页内对这几百个分隔键做二分查找（纯内存操作，几乎免费），选中一段，顺指针读下一页，直到叶子。总代价是 log_k N 次页读——k 是扇出、N 是总条数；别被记号唬住，它只说一件事：扇出越大、树越矮、跑腿次数越少。
还有一个常被忽略的量：占用率。B-Tree 的页故意不装满，留白是为了让未来的插入能就地塞进去、不必立刻分裂；经典不变式「除根之外每个节点至少半满」正是树高不会退化的保证来源。代价是空间换时间：索引天然比数据「虚胖」一截。
原版 B-Tree 会把数据顺手放在内部节点里。而几乎所有真实数据库用的是变体 B+-Tree，两处改动：
Petrov 也直说：差异主要在实现层面，业界口语中的「B-Tree」通常指的就是这一族。面试里说清「数据在叶子、叶子串链」，比背定义更值钱。
插入：像查找一样走到目标叶子，把新项按序塞进去。塞得下，一次插入就是一次页内改写。塞不下（溢出）就分裂：把这页从中间劈成两页，把中间那个键上提给父节点当新的分隔键；父节点若也满了就继续往上分裂、继续上提。一直到根也撑不住时，根才分裂、生出新根——整棵树在这一刻长高一层。
这就是最优雅的地方：它只从根部长高，生长的动力却来自叶子。长高既然是整体性的，所有叶子到根的距离就永远相等——天生完美平衡、完全不需要旋转。红黑树那套「局部旋转维持平衡」在这里根本不存在，这是它适合磁盘的第二个理由。
删除：走到叶子删掉那一项；若占用率跌破阈值（下溢），要么向兄弟借几项（重分布），要么和兄弟合并成一页——后者让父节点少一个分隔键，可能一路向上传递，根只剩一个孩子时树矮一层。但要留一句注脚：很多真实引擎会推迟甚至跳过合并（要同时锁多个页、并发代价高，收益只是省点空间），宁可让页维持低占用、靠后台整理回收。「教科书说至少半满」和「你线上那个索引真的半满」是两回事。
表 1 · 同一批数据，两种结构在磁盘上的账（以 20 亿条、页 8 KB 为例）
| 平衡二叉查找树 | B-Tree（页式多路树） | |
|---|---|---|
| 节点大小 | 几十字节，远小于一页 | 等于一页（4–16 KB） |
| 扇出 | 2 | 200–500（键越短扇出越大） |
| 树高 | log₂ N ≈ 31 层 | log_k N ≈ 4 层 |
| 一次点查的页读 | 最多 31 次，且几乎全是随机 I/O | ≤ 4 次；上层常驻内存 → 通常 1 次真读盘 |
| 维持平衡 | 靠旋转 → 每次都改写多个页 | 不旋转，靠分裂 / 合并，只在根部改变高度 |
| 代价 | 结构简单、内存里极优 | 页留白（空间换时间）、分裂时要写多页 |
表 2 · B-Tree vs B+-Tree：为什么工业界一边倒地选后者
| 原版 B-Tree | B+-Tree（实际用的） | |
|---|---|---|
| 数据放哪 | 内部节点也能放 | 只放叶子 |
| 内部节点扇出 | 较小（项里带着数据） | 更大 → 树更矮、内部层易全缓存 |
| 点查代价 | 可能中途命中，深浅不一 | 永远走到叶子，代价均匀、延迟可预测 |
| 范围扫描 | 要中序遍历、反复回溯到父节点 | 叶子有兄弟链 → 线性往下走 |
| 代价 | — | 点查不能提前结束；兄弟指针也要维护 |
表 3 · 页大小怎么选（真实默认值作锚）
| 页大小 | 好处 | 代价 | 谁在用 |
|---|---|---|---|
4 KB | 与操作系统页对齐；一次 I/O 搬回的无用数据最少 | 扇出小 → 树更高；单项体积上限低 | SQLite 默认 |
8 KB | 树高与浪费的折中，最常见的默认 | — | PostgreSQL 默认（BLCKSZ） |
16 KB | 扇出更大、树更矮；对顺序扫描友好 | 改一条记录也要写回 16 KB → 写放大更重；页级锁争用更凶 | MySQL InnoDB 默认 |
32–64 KB | 扫描吞吐最高 | 点查浪费严重、并发争用最重 | 偏分析型 / 大块顺序读 |
分裂点也是个权衡，而且反直觉：不是永远对半分。主键若是自增 ID 或时间戳，插入永远落在最右那一页；对半分裂会让左半页永远停在 50% 满、再没人来填，索引白白虚胖一倍。PostgreSQL 的做法是最右页分裂时故意偏斜，把左页留到 fillfactor（B-Tree 默认 90）那么满。反过来，主键若是 UUID 这类随机值，插入均匀砸在所有页上、分裂到处发生、页普遍卡在半满附近——这就是「别拿 UUID 当聚簇主键」的机理。
什么时候不该选 B-Tree？写入远多于读取、键又随机、还对空间敏感时——原地改写意味着「改一条记录 = 写回一整页」，随机键又让页普遍半空。这正是日志结构存储（LSM-Tree，Ch7）的主场：把随机写攒成顺序写，代价是读要在多层里找、还要后台合并。
点名一遍就知道它多普遍：PostgreSQL 的 nbtree、InnoDB 的聚簇索引（主键就是一棵 B+-Tree，二级索引的叶子存主键值）、SQLite、Oracle、SQL Server、MongoDB 的 WiredTiger、etcd 底下的 bbolt——全是 B-Tree / B+-Tree。理解这一章等于拿到一把通用扳手：为什么索引不用哈希表（哈希点查也快，但不认顺序，做不了范围扫描和 ORDER BY）、为什么 EXPLAIN 里索引扫描代价那么低（树才 3–4 层、上层全在缓冲池）、为什么 DBA 反复念叨主键要单调递增。
fillfactor = 90。直接印证「顺序键该偏斜分裂」。postgres/…/nbtsplitloc.c ↗1172 GB、改用 LSM 的 MyRocks 只占 574 GB，写入量从 152 MB/s 降到 67 MB/s。这就是「占用率 / 原地改写」代价的线上量级。Facebook mysql-5.6 wiki「MyRocks advantages over InnoDB」 ↗O(log N) 就等于快。真正的成本是页读次数与缓存命中，不是比较次数。4 层的树、上面 3 层常驻缓冲池，一次点查往往只有 1 次物理 I/O——这个「实际 1 次」才是它真正的卖点。① B-Tree 不是更快的查找树，是为块设备重写过的查找树——优化的是磁盘往返次数，不是比较次数。
② 二叉树上磁盘就废：扇出低、节点远小于页（搬 8 KB 只用 32 字节）、局部性差（每层一次随机 I/O）、旋转要改写多页。
③ 核心一招：节点大小 = 页大小，一页塞满分隔键。扇出从 2 拉到 200–500，20 亿条的树高从 31 层塌到 4 层。
④ 结构常识：内部节点 n 个分隔键 → n+1 个指针；内部只放路标、叶子放数据；页内二分查找定位区间。
⑤ 现实中的「B-Tree」几乎都是 B+-Tree：数据只在叶子、叶子用兄弟指针串成链，于是点查代价均匀、范围扫描线性。
⑥ 增删：插入满了就分裂并把中间键上提——树只从根部长高，天生平衡、无需旋转；删除下溢则借或合并，但很多引擎为省并发代价推迟合并。
⑦ 权衡：页大小（树高 vs 写放大与锁争用）；分裂点不该永远对半分——顺序键要偏斜（PostgreSQL fillfactor=90），随机键（UUID）把页普遍劈到半满、索引虚胖。
⑧ 真实系统：PostgreSQL nbtree（Lehman-Yao B-link 树）、InnoDB 聚簇索引、SQLite、WiredTiger、bbolt；反方是 Facebook 的 MyRocks——换成 LSM 后同一份数据从 1172 GB 降到 574 GB。坑：B 不是 binary；O(log N) 不等于快（实际常只 1 次物理 I/O）。