先说结论:InnoDB 选择 B+ 树而不是哈希表或 B 树,核心目的是让等值查询和范围查询都能在很少的磁盘 IO 内完成;而随机主键(如 UUID)导致的页分裂,是很多线上写入性能问题的隐形元凶。 理解这两点,比背"索引是 B+ 树"这个名词有用得多。

为什么是 B+ 树

数据库索引要解决的根本问题是:数据在磁盘上,随机读一次的代价是内存访问的十万倍量级,所以好的索引结构必须让"找到目标数据"所需的磁盘 IO 次数足够少。InnoDB 数据页默认 16KB,整棵树的节点就是一个个页,读一个节点等于一次页读取。B+ 树有三个关键特征:

  • 非叶子节点只存键值和指针,不存数据,一个页能容纳上千个"路标",扇出极大;
  • 全部数据都在叶子节点,等值查询稳定在"树高次数"IO 内结束;
  • 叶子节点之间用双向链表串联,范围查询只需定位起点后顺着链表顺序扫——这是哈希索引做不到的。

和其他候选结构对比,选型逻辑一目了然:

能力B+ 树哈希索引B 树
等值查询树高次 IO,稳定可预期O(1),单次最快树高次 IO,但数据分布在所有层
范围查询叶子链表顺序扫描,高效完全不支持需中序遍历,跨层往返
排序 / 最左前缀匹配支持不支持有限支持
磁盘友好度高:节点与页对齐,路径极短高但无范围能力低:访问数据要经过多个内部节点

二叉平衡树、红黑树这类结构为什么不行?二叉意味着一个节点只有两个分叉,存一亿行数据树高接近 30 层,每次查询就是 30 次磁盘读。B+ 树把"每个节点的分叉数"拉满到一个页能装下的极限,树高压到 3~4 层,这就是全部的秘密。

做个数量级估算:主键 bigint 占 8 字节、指针 6 字节,非叶子节点扇出约 16384 / 14 ≈ 1170;假设一行数据 1KB,叶子页每页约 16 行。三层 B+ 树可容纳约 1170 × 1170 × 16 ≈ 2000 万行。这就是"两千万行"常被当作单表心理阈值的原因——数据量再涨,树高从 3 变 4,每次查询多一层页读取。内存数据库(如 Redis 的 ZSet)用跳表不用 B+ 树,恰恰因为内存访问不存在"页"的约束,跳表实现更简单。

聚簇索引与二级索引

InnoDB 的表就是索引组织表,主键索引即数据本身:

  • 聚簇索引:叶子节点存整行数据,表本身就是按主键组织的这棵树;
  • 二级索引:叶子节点只存索引列 + 主键值,查到主键后还要回聚簇索引取整行(回表)。

二级索引存主键值而不是物理地址,还带来一个副产物:行发生移动(页分裂导致行换页)时二级索引不用维护,只有主键值不变就行,省掉了大规模更新指针的成本。代价是主键越长,所有二级索引跟着越长,所以主键要短。

回表不是免费动作:二级索引扫出 10 万条记录,就要回聚簇索引读 10 万次,如果这些行分散在 10 万个不同页里,代价远超一次全表扫描。这解释了两条经典经验:select * 容易产生大量回表;高频查询尽量设计成覆盖索引,让索引里就包含全部需要的列,省掉回表。

-- 错误写法:select * 让 idx_user_id 只能提供主键,10 万条命中全部回表
-- explain Extra 不会出现 Using index,且 rows 越大回表成本越高
SELECT * FROM orders WHERE user_id = 10086;

-- 正确写法:业务只需要这三个列时,建联合索引 idx_user_cover(user_id, amount, created_at)
-- 索引叶子已包含全部所需列,免回表,explain Extra 显示 Using index
ALTER TABLE orders ADD INDEX idx_user_cover(user_id, amount, created_at);
SELECT user_id, amount, created_at
FROM orders
WHERE user_id = 10086;

页分裂:随机写入的代价

主键顺序写入时,新行总是追加到最后一个页,页满了就开新页,树始终保持"向右生长",这是最理想的情况:旧页接近填满,缓冲池命中的页都是热的,写入只碰最后一两个页。但如果主键是 UUID 这类随机值,新行可能落在树的任意位置:

  1. 定位到目标页,目标页已满,需要申请新页;
  2. 原页数据从中间一分为二,分别放入新旧两页,两页填充率都降到约 50%;
  3. 上层节点插入新目录项,可能触发连锁分裂,极端情况整层逐级分裂。

页分裂除了数据搬运本身,还会留下大量填充率约 50% 的"半满页",同样的数据占了近两倍的页数,页变多导致缓冲池命中率下降,写入放大明显。删除数据引发的页合并则是分裂的逆过程:当页内数据低于 MERGE_THRESHOLD(默认 50%),InnoDB 尝试把相邻两页合并,同样消耗资源。插入与删除混合的表,最终状态是页空间利用率长期低下,这就是"表碎片"的来源之一。

缓冲池的角度同样能解释页分裂的危害:Buffer Pool 以页为调度单位,同样的内存,紧凑存储能缓存的逻辑数据远多于半满页——碎片直接折损了缓存命中率的分母。所以判断一张写入频繁的表是否健康,除了看分裂指标,还可以对比 information_schema.TABLES 里 data_free 与 data_length 的比值,碎片占比持续偏高就说明页空间利用率出了问题。

页分裂活动可以直接从 metrics 表观测:

-- 页分裂与页合并的累计次数,插入高峰期增速异常说明写入模式不健康
SELECT name, count
FROM information_schema.INNODB_METRICS
WHERE name IN ('index_page_splits', 'index_page_merges');

实战建议

  • 主键尽量自增,或使用雪花 ID 这类趋势递增的分布式 ID;自增主键的另一个好处是二级索引更短、更省内存;
  • 业务必须用 UUID 时,换有序版本(如 UUIDv7),前缀带时间戳,写入仍大致有序;
  • 避免冗余索引:单列能覆盖的不要重复建多列索引,每个二级索引都是一棵要维护的树,写入时每棵树都可能分裂;
  • 批量导入前按主键排序再写入,导入后的大表不要频繁小批量乱序插入;
  • 大表大量删除历史数据后,评估用 ALTER TABLE ... ENGINE=InnoDB(即表重建)回收碎片空间;
  • 表重建时可配合 innodb_fill_factor 控制页填充百分比:留白能降低后续分裂概率,代价是瞬时空间放大,按读写比例权衡;
  • 用 sys.schema_unused_indexes 定期盘点长期零使用的索引,确认后下线。

一句话总结:顺序写入让 B+ 树"只长高、不歪长",随机写入让树矮胖且满是空洞——索引设计的第一原则,是让主键写入尽量有序。

生产案例

某次大促备战压测,订单写入链路 TPS 始终上不去,数据库 CPU 不高、磁盘 IO 也不满,团队一度怀疑是连接池配置问题。最后用 INNODB_METRICS 抓到线索:压测期间 index_page_splits 的增速与写入行数同量级,等于几乎每次插入都在分裂页。定位根因是订单表主键用了 UUID 字符串,写入位置完全随机,缓冲池里大量半满页互相竞争。改造方案分两步走:新订单主键切换为雪花 ID(趋势递增),存量数据按主键有序重建到新表后双读切流。改造之后同样的压测场景,分裂指标增速下降到可忽略,写入链路的瓶颈转移到正常的磁盘刷脏上。复盘的结论写进了团队建表规范:任何新表主键评审,第一件事就是确认写入是否有序。