结论先行：数据库选 B+ 树，不是因为它的查找复杂度比哈希表低，而是因为「磁盘按页读取」这件事，逼着索引必须是一个「矮而胖」的多叉树。哈希表点查是 O(1) 没错，但它答不了范围查询、也答不了排序；红黑树平衡得漂亮，可它是「高而瘦」的二叉树，落在磁盘上要多读几十倍页。下面把「扇出 × 树高」这笔账算给你看，全程用大白话。
一、现象：一张 16 亿行的表，点查只要 3 次磁盘 IO
先给一组能落地的数字，环境是 MySQL 8.0.32 / InnoDB，innodb_page_size=16KB（默认值）不变。
一张 t_order 表约 16 亿行，主键 id BIGINT。我做了个最朴素的点查 SELECT * FROM t_order WHERE id = 86753091234，用 SHOW STATUS LIKE 'Handler_read%' 配合 iostat 观察：
- 冷启动（buffer pool 已刷走、必须真读盘）：3 次磁盘读，端到端 P50 约 0.45ms（NVMe 云盘）；
- 同一个 id 再查一次（命中 buffer pool）：0 次磁盘读，P50 跌到 0.02ms 量级。
关键就在这个「3 次」。16 亿行，听起来该翻很多页，但 B+ 树只用了 3 层——根节点、一个中间节点、一个叶子。为什么是 3 层而不是 31 层？往下看这笔账。
反过来看两个「对照组」，你就明白为什么别的结构没被选中：
- 哈希表：
id → 行地址直接算出位置，点查理论上 1 次 IO，比 B+ 树还快。可一旦你写WHERE id BETWEEN 86753091200 AND 86753091300，哈希表就废了——它只能告诉你「某个 key 在哪」，不能告诉你「这一段 key 在哪、按什么顺序排」。 - 二叉红黑树：16 亿行的平衡二叉树高度约
log2(16e8) ≈ 31。如果每个节点占一个磁盘页，最坏要读 31 页，比 B+ 树的 3 页多 10 倍 IO。
所以这不是「谁查找快」的问题，是「谁更贴磁盘脾气」的问题。
二、原理：磁盘按「页」读，逼出了「矮胖树」
先讲两个绕不开的物理事实：
- 磁盘最小读取单位是「块/页」，不是「一个字节」。InnoDB 把数据切成 16KB 的页，一次 IO 至少读一整页。哪怕你只要页里的一行，也得把整页搬进内存。
- 顺序读远快于随机读。HDD 上随机寻道约 0.5~10ms，NVMe 随机读约 0.05~0.1ms，但「连续读 N 页」和「随机跳 N 页」的差距依然巨大。
B+ 树是专门为这两条设计的「矮胖树」，三个特征一个都不能少：
① 一个节点 = 一个页，页里塞满「指针 + 关键字」。
非叶子节点不存数据，只存「路由」：[k1, k2, ... k_n | p1, p2, ... p_n+1]。按 InnoDB 的紧凑布局，一个非叶子节点里，一条「关键字(8B) + 指针(6B)」约 14 字节，16KB 一页能塞下约 16384 / 14 ≈ 1170 个指针。这就是扇出（fan-out）≈ 1170——每个节点平均能往下接 1170 个子节点。
② 扇出决定了树高。
一层能覆盖 1170^1 个叶子，三层能覆盖 1170^3 ≈ 16 亿 个叶子。所以 16 亿行的表，3 层就够。换成二叉树（扇出=2），要覆盖 16 亿就得 2^31，高度 31。「每层节点数 × 层数 = 总行数」，扇出越大、树越矮、IO 越少——这就是 B+ 树的核心竞争力，一句话就能讲给非技术同学听。
③ 叶子节点用链表串起来，数据全在叶子。
这是 B+ 树区别于「B 树」的地方：数据只存在叶子层，且叶子之间是双向链表。点查要顺着指针一路到叶子（3 次 IO）；而范围查询到了叶子后，顺着链表顺序往后扫就行，不需要再回上层。这就是为什么 WHERE status=1 ORDER BY create_time 这种范围/排序查询，B+ 树能「一次定位 + 顺序扫完」。
三、具体做法：自己搭一个「扇出 × 树高」计算器，把账算明白
我不建议靠背，靠算。给你一段能直接跑的 Python，把 InnoDB 默认参数代进去，亲手验证「16 亿行 = 3 层」：
PAGE = 16 * 1024 # 16KB 页
KEY = 8 # BIGINT 主键 8 字节
PTR = 6 # InnoDB 指针约 6 字节
ENTRY = KEY + PTR # 每条路由 14 字节
FANOUT = PAGE // ENTRY # 扇出 ≈ 1170
rows = 1_600_000_000 # 16 亿行
height = 1
cap = FANOUT
while cap < rows:
height += 1
cap *= FANOUT
print(f"扇出={FANOUT}, 覆盖 {rows:,} 行需要树高={height} 层, 即 {height} 次磁盘读")
# 输出: 扇出=1170, 覆盖 1,600,000,000 行需要树高=3 层, 即 3 次磁盘读
# 对照：二叉树
import math
print("二叉树高度 =", math.ceil(math.log2(rows))) # 31
再给你一段「用 EXPLAIN 验证范围查询走的是顺序扫描」的复现脚本（连上你的库直接跑）：
-- 建一张 100 万行的订单表
CREATE TABLE t_order_demo (
id BIGINT PRIMARY KEY AUTO_INCREMENT,
status TINYINT,
create_time DATETIME,
amount DECIMAL(10,2)
);
-- 建「顺序友好」的联合索引：范围列在前，排序列在后
ALTER TABLE t_order_demo ADD INDEX idx_status_time (status, create_time);
-- 这条查询应命中索引且无 filesort（即叶子顺序扫）
EXPLAIN SELECT id, amount
FROM t_order_demo
WHERE status = 1
ORDER BY create_time DESC
LIMIT 20;
-- 关注 EXPLAIN 输出: key=idx_status_time, Extra 里出现 "Using index" / 无 "Using filesort"
如果 Extra 出现 Using filesort，多半是排序列没落在索引里、或范围列写成了非最左前缀——这时候 B+ 树的「顺序扫」优势就没吃上，退化成「全扫 + 内存排序」。
四、坑与反直觉的地方
坑 1：B+ 树不是「点查比哈希快」，恰恰相反。 纯单点查，哈希表 1 次 IO 完事，B+ 树要 3 次。数据库选 B+ 树，是「牺牲 2 次点查 IO，换来范围 + 排序 + 可维护」这笔整体划算的交易。如果你的场景 99% 都是精确等值、从不排序从不范围，Redis 的哈希确实更快——选型永远是「负载长什么样」决定的，不是「哪个数据结构理论最快」决定的。
坑 2：扇出会被「宽索引」吃掉。 上面算 1170 扇出用的是 BIGINT 主键。可如果你给一个 VARCHAR(255) 的手机号建普通索引，一个关键字就可能占上百字节，扇出直接掉到个位数甚至两位数，树高从 3 层涨到 5~6 层，每次点查的 IO 跟着翻几倍。所以「索引越宽、树越胖、IO 越多」，这是很多人忽略的隐藏成本。
坑 3：叶子链表只保「顺序」，不保「跳行一致」。 正因为叶子是有序链表、可以顺序扫，深分页 LIMIT 2000000, 20 才会「把前 200 万条全扫一遍再丢弃」——顺序扫是它的强项，也成了深分页慢的根因。这里引用一篇同主题经验（林亦舟《千万级表深分页》）：「按 idx_status_create_time 定位，顺序扫描满足 status=1 的索引项」，扫到 offset 条后全部丢弃。所以 B+ 树的「顺序」是双刃剑：范围查询靠它起飞，深分页被它拖垮，解法是把「页码」换成「游标」。
反直觉之最：数据全在叶子，反而是优点。 很多人以为「B 树那样中间节点也存数据」更省，其实不然——中间节点存数据会让它更快写满、更容易分裂，而且范围查询时中间节点的数据不在同一条链路上，无法顺序扫。把数据统一压到叶子 + 链表，才把「点查」和「范围查」两条路都走顺了。
五、结论与可复用清单
一句话总结：B+ 树是「磁盘按页读」这条物理约束下的最优解——用 16KB 页当节点、用 1170 的扇出把树压到 3 层、用叶子链表把范围查询变成顺序扫，一次结构同时解决了点查、范围、排序三件事。
可复用清单：
- 讲树高，先讲扇出：
扇出 ≈ 页大小 / (关键字 + 指针)，树高 = log_扇出(总行数)。把这两个公式甩出来，比背「B+ 树是平衡的多叉树」更有说服力。 - 算一笔账再下结论：16 亿行，B+ 树 3 次 IO vs 二叉树 31 次 vs 哈希 1 次——让读者自己看到「为什么不是谁都快、而是谁最贴磁盘」。
- 索引别太宽：宽索引会砍掉扇出、抬高树高，点查 IO 跟着涨。能给范围/排序建联合索引，就别建一堆单列宽索引。
- 顺序是双刃剑：范围查询靠它起飞，深分页被它拖垮；深分页优先改 keyset 游标。
- 选型看负载：99% 等值 + 无排序无范围 → 哈希（Redis）更合适；要范围 + 排序 + 持久化 → B+ 树。
留个开放问题想听听大家：如果未来的存储是「全闪存 + 大容量内存」，磁盘「按页读、随机读贵」这条约束被大幅削弱，B+ 树的「矮胖」优势还会不会这么绝对？LSM-Tree（写优化、顺序合并）会不会更主流？ 我在想，「数据结构选型」是不是其实一直在跟着「存储介质」的脾气走——你们线上有没有「明明数据量不大、但索引树特别高、点查 IO 偏多」的表？欢迎拍砖。