MySQL B+Tree索引底层结构与为什么使用B+Tree
请详细解释MySQL InnoDB中B+Tree索引的底层数据结构。为什么InnoDB选择B+Tree而不是B-Tree、红黑树或哈希表作为索引结构？B+Tree相比于B-Tree有哪些关键优势？
回答
专业代码师
B+Tree底层结构：
- 非叶子节点只存储键值（索引列值）+ 指向子节点的指针，不存数据
- 叶子节点存储完整的行数据（聚簇索引）或主键值+索引列值（二级索引）
- 叶子节点之间通过双向链表连接，形成有序链表
为什么选择B+Tree：
- 相比B-Tree：B+Tree非叶子节点不存数据，每个节点可容纳更多键值，树高度更低（通常3-4层），磁盘IO更少；叶子节点链表支持范围查询和顺序遍历
- 相比红黑树：红黑树是二叉树，高度约log₂N（1000万数据需24层），磁盘IO次数过多；B+Tree是多叉树，扇出更大
- 相比哈希表：哈希表仅支持等值查询O(1)，不支持范围查询、排序、模糊匹配；B+Tree支持范围查询、排序、LIKE前缀匹配
关键优势：树高度稳定（3-4层）、磁盘IO少、叶子节点链表支持高效范围扫描、数据存储在叶子节点查询性能稳定。