B+ 树刨析

B+树：从磁盘I/O驱动的数据结构到数据库索引的工业标准

引言：为什么 B+ 树会成为数据库索引的事实标准？

在MySQL的InnoDB存储引擎中，索引的底层数据结构是B+树。以用户表(user)为例，最常见的SQL查询需求有3种：等值查询(WHERE id = 123)、范围查询(WHERE id BETWEEN 123 AND 234)和排序分页查询(WHERE id < 1234 ORDER BY id DESC LIMIT 10)。这三种需求决定了索引数据结构必须具备3个核心能力：精确查找、快速区间查找和数据有序存储。

传统内存型数据结构（如二叉树、红黑树）在面对磁盘存储时，因严重的磁盘I/O开销而失效。B+树的设计初衷就是为了优化在外部存储器（如磁盘）上的数据读取和写入操作。它通过多叉平衡的特性，能极大降低树的高度，从而在查询时大幅减少磁盘I/O次数。这正是B+树从众多数据结构中脱颖而出，成为MySQL、PostgreSQL等关系型数据库索引标准的根本原因。B+树能够保持数据稳定有序，其插入与修改拥有稳定的对数时间复杂度。

第一章 B+ 树是什么：核心概念与底层原理

B+树是一种平衡的多路查找树，专为磁盘存储优化。B+树的阶数（Order，即m）指每个节点拥有的子节点个数。在InnoDB中，B+树的节点大小与磁盘页（通常为16KB）严格对齐。

1.1 核心三要素：节点、关键字与链路

• 节点