序幕一个让人困惑的问题很多人学B树时书上都会说“B树的层数越少I/O次数越少性能越好。”然后你点点头觉得自己懂了。但深夜躺在床上你突然想“等等为什么层数多I/O就多为什么层数少I/O就少这两件事到底是什么关系节点不都在磁盘上吗为什么不能一次把所有节点都读出来”这个问题看似简单实际上涉及到计算机存储体系的底层逻辑。让我们从头讲起。第一章磁盘是怎么工作的磁盘不是你想读哪里就能立刻读哪里的你可能以为磁盘是这样工作的 我要读地址0x3F7A的数据。 → 嗖数据来了。 我要读地址0xB2C1的数据。 → 嗖数据又来了。 就像翻书一样想翻到哪页就翻到哪页瞬间完成。不。磁盘完全不是这样工作的。机械硬盘的内部结构 一个高速旋转的金属盘片每分钟7200转。 一个可以移动的磁头臂末端是读写磁头。 ┌─────────────────────────┐ │ │ │ ┌───────────────┐ │ │ │ ╭───────────╮│ │ │ │ │ ╭───────╮ ││ │ │ │ │ │ ╭───╮ │ ││ │ │ │ │ │ │ │ │ ││ │ ← 同心圆磁道 │ │ │ │ ╰───╯ │ ││ │ │ │ │ ╰───────╯ ││ │ │ │ ╰───────────╯│ │ │ └───────────────┘ │ │ │ │ ═══════════╗ │ │ ║ ← 磁头臂│ │ [▪] ← 磁头 │ └─────────────────────────┘ 要读取数据需要三个步骤 1. 寻道Seek磁头臂移动到正确的磁道上 耗时3-15毫秒 2. 旋转等待Rotation等盘片转到正确的位置 耗时2-8毫秒平均半圈 3. 数据传输Transfer读取数据 耗时0.01-0.1毫秒读几KB数据很快 总耗时 ≈ 寻道 旋转 5-20毫秒 注意99%的时间花在找位置上 只有不到1%的时间花在读数据上。一个关键的比喻想象你在一个巨大的唱片仓库里工作。 仓库里有10万张唱片分布在不同的架子上。 你的工作根据客户的要求找到指定的唱片。 每次找一张唱片你需要 1. 走到正确的架子前走路 寻道 2. 在架子上找到正确的位置翻找 旋转等待 3. 把唱片抽出来拿取 数据传输 走路花5秒。翻找花3秒。拿取花0.1秒。 总共8.1秒。其中99%的时间在走路和翻找。 现在如果客户说我要5张唱片。 最坏情况5张唱片在5个不同的架子上。 你要走5趟。5 × 8秒 40秒。 最好情况5张唱片在同一个架子上紧挨着。 你只走1趟然后连续抽出5张。1 × 8秒 4 × 0.1秒 8.4秒。 差距40秒 vs 8.4秒。将近5倍。 这就是随机I/O和顺序I/O的区别。 每一次走到不同的架子 一次磁盘I/O。 走的趟数越多越慢。第二章为什么每一层 一次I/OB树的节点在磁盘上是分散的B树的每个节点占一个磁盘页通常16KB。 这些页分布在磁盘的不同位置。 磁盘上的布局简化 地址0x0000: [叶子节点#7的数据] 地址0x4000: [内部节点#3的数据] 地址0x8000: [叶子节点#2的数据] 地址0xC000: [根节点的数据] 地址0x10000: [叶子节点#5的数据] 地址0x14000: [内部节点#1的数据] ... 它们不是整整齐齐地排在一起的。 根节点可能在磁盘的这头 叶子节点可能在磁盘的那头。 当你要从根节点走到叶子节点时 第1步读根节点 → 磁头移动到地址0xC000 → 一次I/O寻道旋转读取 → 耗时约10ms 第2步根据根节点的指针读第二层的某个内部节点 → 磁头移动到地址0x14000 → 又一次I/O → 又耗时约10ms 第3步根据内部节点的指针读第三层的某个内部节点 → 磁头移动到另一个地址 → 又一次I/O → 又耗时约10ms 第4步根据指针读叶子节点 → 磁头移动到又一个地址 → 又一次I/O → 又耗时约10ms 4层 4次I/O 4次磁头移动 40ms 为什么不能一次把所有节点都读出来 因为你不知道要读哪些节点。 你必须先读根节点才能知道下一步该读哪个子节点。 你必须先读子节点才能知道再下一步该读哪个孙节点。 每一层的选择依赖于上一层的结果。 这是一个串行的过程无法并行。一个精确的比喻想象你在玩一个寻宝游戏。 规则 每个地点有一个信封。 信封里有一条线索告诉你下一个地点在哪里。 你必须到达当前地点打开信封才能知道下一步去哪。 4层B树 4个地点的寻宝游戏 地点1根节点图书馆门口 信封里写着去城东的咖啡馆。 → 你开车去城东。耗时10分钟。 地点2第二层节点城东咖啡馆 信封里写着去北郊的公园。 → 你开车去北郊。耗时10分钟。 地点3第三层节点北郊公园 信封里写着去公园里的第三棵柳树下。 → 你走过去。耗时10分钟。 地点4叶子节点第三棵柳树下 宝藏在这里 总耗时4 × 10分钟 40分钟。 你能跳过中间的步骤吗不能。 你不知道要去城东的咖啡馆直到你打开图书馆的信封。 你不知道要去北郊的公园直到你打开咖啡馆的信封。 每一步都依赖上一步的结果。 4个地点 4次开车 4次I/O。 7个地点 7次开车 7次I/O。 3个地点 3次开车 3次I/O。 地点越少层数越少开车次数越少I/O越少。 就这么简单。第三章为什么二叉树层数多B树层数少二叉树——每次只排除一半二叉搜索树每个节点有2个子节点。 查找时每到一个节点你做一个二选一的决策 往左走还是往右走 每次决策排除一半的数据。 1000万条数据 第1次决策排除500万剩500万 第2次决策排除250万剩250万 第3次决策排除125万剩125万 ... 第23次决策排除1剩1 → 找到了 需要23次决策 23层 23次I/O。 想象你在猜一个1到1000万之间的数字。 每次只能问大于还是小于某个数 大于500万吗 → 不是。 排除一半。 大于250万吗 → 是。 排除一半。 大于375万吗 → 不是。 排除一半。 ... 每次排除一半需要问23次。 问题出在哪里 每个节点只有2个子节点。 每次决策只能排除50%的数据。 排除的速度太慢了。 用寻宝游戏的比喻 每个信封里只有2个选项 如果你要找的数 500万去A地点。 如果你要找的数 ≥ 500万去B地点。 每次只能二选一。 23次二选一才能找到答案。 23个地点 23次开车 23次I/O。B树——每次排除99.9%B树每个节点有1000个子节点假设阶数1000。 查找时每到一个节点你做一个千选一的决策 往1000个子节点中的哪一个走 每次决策排除99.9%的数据。 1000万条数据 第1次决策排除999万剩1万 第2次决策排除9990剩10 第3次决策排除9剩1 → 找到了 只需要3次决策 3层 3次I/O。 想象你在猜一个1到1000万之间的数字。 但这次每次可以问 这个数在以下1000个范围中的哪一个 第1次 在1-1000010001-2000020001-30000... → 在第357个范围3560001-3570000。 → 排除了99.9%的数据。 第2次 在3560001-35600103560011-3560020... → 在第42个范围3560411-3560420。 → 又排除了99.9%。 第3次 是35604113560412...3560420 → 是3560417 → 找到了。 3次。不是23次。 用寻宝游戏的比喻 每个信封里有1000个选项 如果你要找的数在1-10000去地点A1。 如果你要找的数在10001-20000去地点A2。 ... 如果你要找的数在9990001-10000000去地点A1000。 每次千选一。 3次千选一就能找到答案。 3个地点 3次开车 3次I/O。直观对比同样是1000万条数据 二叉树 层1: 1个节点 层2: 2个节点 层3: 4个节点 层4: 8个节点 ... 层23: 约500万个节点 总共23层。查找 23次I/O。 ──────────────────────── 根 ├── ──────────────────── 第2层 │ ├── ────────────── 第3层 │ │ ├── ──────── 第4层 │ │ │ ├── ── 第5层 │ │ │ │ ... │ │ │ │ ... │ │ │ │ ...还有18层 │ │ │ │ ... │ │ │ └── ── │ │ └── ──────── │ └── ────────────── └── ──────────────────── 又高又瘦。像一棵竹子。 从顶到底要走23步。 B树阶数1000 层1: 1个节点根 层2: 1000个节点 层3: 100万个叶子节点 总共3层。查找 3次I/O。 ════════════════════════════════════════ 根 ├─┬─┬─┬─┬─┬─┬─┬─┬─┬─...─┬─┬─┬─┬─┬─┤ 第2层1000个节点 ████████████████████████...████████████ 第3层100万个叶子 又矮又胖。像一棵橡树。 从顶到底只要走3步。 关键公式 树高 log_m(N) m 每个节点的子节点数阶数 N 数据总量 二叉树m 2树高 log₂(10000000) ≈ 23 B树 m 1000树高 log₁₀₀₀(10000000) ≈ 2.3 → 3层 m越大树越矮I/O越少。第四章为什么B树的节点能这么胖你可能会问 为什么不让二叉树的节点也存1000个键呢 答案可以。那它就不叫二叉树了它就变成了B树。 B树的胖不是凭空来的。 它是精心设计的刚好利用了磁盘的特性。 磁盘的特性 读1个字节和读16KB花的时间几乎一样。 因为时间主要花在寻道和旋转上10ms 数据传输本身很快16KB只需0.01ms。 既然每次I/O都要花10ms的固定成本 那就应该每次尽量多读一些数据。 磁盘的最小读取单位是一个页Page通常16KB。 读1字节 → 实际读了16KB → 花了10ms 读16KB → 实际读了16KB → 花了10ms 读1字节和读16KB花的时间一样 那为什么不把16KB全部利用起来 B树的设计一个节点 一个磁盘页 16KB。 16KB能存多少个键 假设每个键8字节bigint每个指针6字节。 每个条目 8 6 14字节。 16KB / 14字节 ≈ 1170个条目。 一个节点可以有1170个子指针。 这就是B树胖的秘密 不是因为B树特别聪明 而是因为磁盘的读取方式决定了—— 既然每次都要读16KB 那就把这16KB塞满有用的信息。 二叉树每个节点只存1个键 2个指针 22字节。 一次I/O读了16KB但只用了22字节。 浪费了99.87%的带宽。 B树每个节点存1170个键 1171个指针。 一次I/O读了16KB全部用上了。 零浪费。用快递的比喻 你要从仓库运货到商店。 每次派一辆卡车不管装多少货 来回路上都要花1小时 寻道时间。 二叉树的做法 每次卡车只装1个包裹。 运23个包裹 派23趟卡车 23小时。 卡车能装10000个包裹你只装了1个。 浪费了99.99%的运力。 B树的做法 每次卡车装满1000个包裹。 运1000个包裹 派1趟卡车 1小时。 卡车装得满满的。零浪费。 同样运1000万个包裹 二叉树2300万趟卡车每趟1个包裹 B树1万趟卡车每趟1000个包裹 差距2300倍。 但等等你可能会说 卡车装了1000个包裹到了商店还要在1000个包裹里找 这不也要花时间吗 是的。但在1000个包裹里找一个 是在内存中进行的二分查找。 内存中的二分查找log₂(1000) ≈ 10次比较。 每次比较耗时几纳秒。 总耗时几十纳秒 0.00005毫秒。 磁盘I/O10毫秒。 内存查找0.00005毫秒。 磁盘I/O比内存查找慢20万倍。 在1000个键中做内存查找的时间 相比一次磁盘I/O完全可以忽略不计。 所以B树的策略是对的 用更胖的节点减少I/O次数 即使每个节点内部的查找稍慢一点 总体性能也大幅提升。第五章一张图看懂全部数据量1000万条记录 ┌─────────────────────────────────────────────────────────┐ │ │ │ 二叉搜索树 │ │ │ │ 每个节点1个键2个子节点 │ │ 树高log₂(10000000) 23层 │ │ 查找23次I/O × 10ms 230ms │ │ │ │ · ← 根第1层 │ │ ├─· ← 第2层 │ │ │ ├─· ← 第3层 │ │ │ │ ├─· ← 第4层 │ │ │ │ │ ├─· │ │ │ │ │ │ ├─· │ │ │ │ │ │ │ ... │ │ │ │ │ │ │ ... │ │ │ │ │ │ │ ... ← 还有17层... │ │ │ │ │ │ │ ... │ │ │ │ │ │ │ · ← 第23层叶子 │ │ │ │ 每走一层 磁头移动一次 一次I/O 10ms │ │ 走23层 磁头移动23次 23次I/O 230ms │ │ │ ├─────────────────────────────────────────────────────────┤ │ │ │ B树阶数 1000 │ │ │ │ 每个节点~1000个键~1000个子节点 │ │ 树高log₁₀₀₀(10000000) ≈ 3层 │ │ 查找3次I/O × 10ms 30ms │ │ │ │ ══════════════════════════ ← 根第1层1个节点 │ │ ├─┬─┬─┬─┬─┬─...─┬─┬─┬─┤ ← 第2层~1000个节点 │ │ ████████████...██████████ ← 第3层~100万个叶子节点 │ │ │ │ 每走一层 磁头移动一次 一次I/O 10ms │ │ 走3层 磁头移动3次 3次I/O 30ms │ │ │ ├─────────────────────────────────────────────────────────┤ │ │ │ 性能对比 │ │ │ │ 二叉树230ms ████████████████████████████████████████ │ │ B树 30ms █████ │ │ │ │ B树快了将近8倍。 │ │ │ │ 如果数据量是10亿条 │ │ 二叉树30层 × 10ms 300ms │ │ B树 3层 × 10ms 30ms树高几乎不变 │ │ │ │ B树快了10倍。数据越多优势越大。 │ │ │ └─────────────────────────────────────────────────────────┘第六章缓存的魔法——实际比理论更快前面说B树查找需要3次I/O。 但实际上往往只需要1次。 为什么因为缓存。 数据库有一个缓冲池Buffer Pool。 它是一块内存区域用来缓存最近读过的磁盘页。 ┌─────────────────────────────────────┐ │ 内存缓冲池 │ │ │ │ ┌──────┐ ┌──────┐ ┌──────┐ │ │ │根节点 │ │节点A │ │节点B │ ... │ │ │(常驻) │ │(热点) │ │(热点) │ │ │ └──────┘ └──────┘ └──────┘ │ │ │ │ 读取时先查缓冲池 │ │ 命中 → 直接从内存读取0.0001ms │ │ 未命中 → 从磁盘读取10ms │ │ │ └─────────────────────────────────────┘ B树的3层结构 第1层根节点只有1个节点。 每次查询都要读它。 它永远在缓冲池中。 → 0次I/O。 第2层约1000个节点。 每个节点16KB总共16MB。 数据库的缓冲池通常有几GB。 16MB轻松放下。 这1000个节点也常驻内存。 → 0次I/O。 第3层叶子约100万个节点。 每个节点16KB总共16GB。 缓冲池放不下所有叶子节点。 但热点数据经常访问的会被缓存。 → 0或1次I/O。 实际的I/O次数 最好情况叶子节点也在缓存中 → 0次I/O → 0.001ms 一般情况只有叶子节点需要读磁盘 → 1次I/O → 10ms 最坏情况所有节点都不在缓存中 → 3次I/O → 30ms 大多数查询只需要1次I/O。 如果是二叉树呢 23层每层的节点数量呈指数增长。 前几层可以缓存但中间层和底层太多了。 大多数查询需要10-20次I/O。 B树的矮胖结构不仅减少了I/O次数 还让缓存更有效 ├── 上层节点少 → 容易全部缓存 ├── 上层节点被频繁访问 → 缓存命中率高 └── 只有叶子节点可能需要磁盘I/O → 最多1次 二叉树的瘦高结构让缓存很低效 ├── 中间层节点多 → 缓存放不下 ├── 中间层节点分散 → 缓存命中率低 └── 很多层都需要磁盘I/O → 可能10-20次第七章SSD改变了什么没改变什么你可能会说 现在都用SSD了没有磁头移动不是很快吗 是的SSD比机械硬盘快很多 机械硬盘随机读取~10ms SSD随机读取~0.1ms 快了100倍 但是 内存随机读取~0.0001ms100纳秒 SSD随机读取~0.1ms100000纳秒 SSD仍然比内存慢1000倍。 所以在SSD上 二叉树23次I/O × 0.1ms 2.3ms B树 3次I/O × 0.1ms 0.3ms B树仍然快了8倍。 加上缓存后 B树1次I/O × 0.1ms 0.1ms SSD缩小了差距但没有消除差距。 只要存储介质比内存慢不管慢多少倍 减少I/O次数就永远是有意义的。 除非有一天存储介质和内存一样快。 那时候B树就不需要了。 但那一天还没有到来。 ┌──────────────┬──────────┬──────────┬──────────┐ │ │ 机械硬盘 │ SSD │ 内存 │ ├──────────────┼──────────┼──────────┼──────────┤ │ 随机读取延迟 │ 10ms │ 0.1ms │ 0.0001ms │ ├──────────────┼──────────┼──────────┼──────────┤ │ 二叉树23层 │ 230ms │ 2.3ms │ 0.0023ms │ │ B树3层 │ 30ms │ 0.3ms │ 0.0003ms │ ├──────────────┼──────────┼──────────┼──────────┤ │ B树优势 │ 7.7倍 │ 7.7倍 │ 7.7倍 │ └──────────────┴──────────┴──────────┴──────────┘ 无论什么存储介质倍数关系不变。 因为倍数取决于层数之比23/3 和存储介质的速度无关。 但绝对时间差距在缩小 机械硬盘上差200msSSD上只差2ms。 所以在纯内存数据库中如Redis 确实不用B树用跳表或哈希表就够了。 因为内存中0.0023ms和0.0003ms的差距人感知不到。第八章终极比喻——电梯 vs 楼梯你要到一栋大楼的某个房间取一份文件。 文件在哪个房间你不知道。 每层楼的前台会告诉你往上走或在本层的某个房间。 你必须一层一层问过去。 方案一23层的细长塔楼二叉树 ┌──┐ │23│ ← 每层只有2个房间 ├──┤ │22│ ├──┤ │21│ ├──┤ │20│ ├──┤ │..│ │..│ ← 23层楼 │..│ ├──┤ │3 │ ├──┤ │2 │ ├──┤ │1 │ └──┘ 每层只有2个房间。 前台说左边那个房间或右边那个房间。 你从1楼开始每层问一次前台爬一层楼梯。 爬楼梯 磁盘I/O慢费力 问前台 内存中比较快轻松 23层楼梯。气喘吁吁。 到了23楼找到了文件。 方案二3层的宽扁大楼B树 ┌──────────────────────────────────────────┐ │ 3楼1000000个房间文件都在这层 │ ├──────────────────────────────────────────┤ │ 2楼1000个房间每个房间的前台管1000个3楼房间│ ├──────────────────────────────────────────┤ │ 1楼1个大厅前台管1000个2楼房间 │ └──────────────────────────────────────────┘ 每层有很多房间。 前台说去2楼的第357号房间。 你从1楼开始每层问一次前台爬一层楼梯。 3层楼梯。轻轻松松。 到了3楼找到了文件。 对比 23层塔楼爬23层楼梯。累死了。 3层大楼爬3层楼梯。小意思。 两栋楼里的房间总数一样多都是1000万个。 但一个又高又窄一个又矮又宽。 每层楼的前台工作量不同 塔楼前台只需要在2个房间中选1个。简单。 大楼前台需要在1000个房间中选1个。稍复杂。 但前台的工作是在室内完成的内存操作。 在1000个选项中二分查找只需要10次比较。 耗时几十纳秒。 而爬楼梯是室外操作磁盘I/O。 每爬一层需要10毫秒。 前台工作耗时 vs 爬楼梯耗时 几十纳秒 vs 10毫秒 差距20万倍。 所以 让前台多干点活每个节点存更多的键 换取少爬几层楼减少I/O次数 是非常划算的交易。 这就是B树的全部智慧 ┌─────────────────────────────────────────┐ │ │ │ 把便宜的操作内存比较做多一点 │ │ 把昂贵的操作磁盘I/O做少一点。 │ │ │ │ 每个节点胖一点 → 内存中多比较几次便宜 │ │ 树矮一点 → 少读几次磁盘省大钱 │ │ │ └─────────────────────────────────────────┘第九章数字说话——从1万到100亿让我们看看不同数据量下二叉树和B树的层数对比。 B树阶数 1000每个节点1000个子指针。 ┌──────────────┬──────────────┬──────────────┬──────────────┐ │ 数据量 │ 二叉树层数 │ B树层数 │ I/O节省 │ ├──────────────┼──────────────┼──────────────┼──────────────┤ │ 1千 │ 10层 │ 1层 │ 10倍 │ │ 1万 │ 14层 │ 2层 │ 7倍 │ │ 100万 │ 20层 │ 2层 │ 10倍 │ │ 1000万 │ 23层 │ 3层 │ 7.7倍 │ │ 1亿 │ 27层 │ 3层 │ 9倍 │ │ 10亿 │ 30层 │ 3层 │ 10倍 │ │ 100亿 │ 33层 │ 4层 │ 8.3倍 │ │ 1000亿 │ 37层 │ 4层 │ 9.3倍 │ │ 1万亿 │ 40层 │ 4层 │ 10倍 │ └──────────────┴──────────────┴──────────────┘──────────────┘ 注意B树的层数增长有多慢 从1千到1万亿数据量增长了10亿倍。 B树只从1层长到了4层。 而二叉树从10层长到了40层。 B树的层数 log₁₀₀₀(N) 每当数据量增长1000倍B树才多长1层。 1层 → 最多1000条数据 2层 → 最多100万条数据 3层 → 最多10亿条数据 4层 → 最多1万亿条数据 地球上所有人类产生的所有数据 大概也就需要4-5层的B树。 4-5次I/O。 这就是B树的恐怖之处。 它几乎不会长高。第十章回答最初的问题为什么层数多I/O就多 因为B树的查找是从根到叶子的一条路径。 每经过一层就要读取一个新的节点。 每个节点在磁盘的不同位置。 读取一个节点 一次磁盘I/O。 层数 路径上的节点数 I/O次数。 这是一个严格的等式不是近似。 为什么层数少I/O就少 层数少 路径短 经过的节点少 I/O少。 为什么B树的层数特别少 因为每个节点特别胖存几百上千个键。 每经过一个节点就能排除99.9%的数据。 几步就能从几十亿条数据中定位到目标。 为什么不让二叉树也变胖 让二叉树变胖它就变成了B树。 B树本质上就是一棵极度加宽的搜索树。 为什么要加宽 因为磁盘每次读取的最小单位是一个页16KB。 读1字节和读16KB花的时间一样。 既然如此就应该把16KB塞满有用的键。 一个节点存1个键二叉树是浪费。 一个节点存1000个键B树才是物尽其用。 一句话总结 磁盘I/O很贵。 每个节点存更多的键树就更矮。 树更矮从根到叶子的路径就更短。 路径更短I/O就更少。 I/O更少查询就更快。 层数 I/O次数。 减少层数 减少I/O 提升性能。 就这么简单。尾声让我们最后回到那个比喻。 你要在一栋大楼里找一份文件。 你必须一层一层问前台一层一层爬楼梯。 如果大楼有23层—— 你爬得气喘吁吁膝盖发软 到了23楼才拿到文件。 如果大楼只有3层—— 你三步并作两步轻松上楼 几秒钟就拿到了文件。 两栋楼里的房间一样多。 文件一样多。 前台一样热情。 唯一的区别一栋又高又窄一栋又矮又宽。 B树选择了又矮又宽。 因为它知道一个朴素的道理 爬楼梯很累磁盘I/O很慢。 在房间里找东西很轻松内存操作很快。 那就少爬几层楼 每层多找几个房间。 这不是什么天才的发明。 这是最朴素的工程直觉 把时间花在值得的地方。 把力气省在昂贵的地方。 少做贵的事。多做便宜的事。 这就是B树。 这就是层数与I/O的关系。 这就是数据库快的原因。