B+ 树

结构与特性

B+ 树是专门为磁盘 IO 优化设计的平衡多叉树。关键设计决策是让每个节点的大小等于磁盘块（通常4KB或16KB），这样每次读取一个节点恰好是一次磁盘 IO。节点中存放尽可能多的键（高扇出），树的高度因此极低——1亿条记录的 B+ 树高度通常只有3-4层，意味着最多4次 IO 就能找到任何记录。

与 B 树的核心区别：B+ 树的内部节点不存储数据，只存键作为路由；数据全部在叶节点，叶节点之间形成有序链表。这使得范围查询只需找到起点叶节点，然后沿链表顺序读取，无需回到根节点。[1]

在数据库中的应用

InnoDB 的每张表本身就是一棵 B+ 树（聚簇索引），主键是树的键，叶节点存储完整的行数据。二级索引是另一棵独立的 B+ 树，叶节点存储二级索引键值和对应的主键值，通过主键再到主树回表取数据。

B+ 树并非唯一选择：LSM 树（Log-Structured Merge Tree）在写密集场景下性能更好，被 LevelDB、RocksDB、Cassandra 的 SSTable 采用；哈希索引在等值查找上更快但不支持范围查询；PostgreSQL 还支持 GiST（广义搜索树），可以扩展到地理、全文等特殊数据类型的索引。