图解MySQL索引--B-Tree（B+Tree）
2021-02-23 15:58:22
B-Tree（B+Tree）作为MySQL索引的核心结构，通过多路平衡搜索树的设计优化了磁盘IO效率，尤其适合数据库的增删改查场景。 以下从结构特性、与Hash/二叉树的对比、存储引擎实现及优化建议四个方面展开说明：
一、B-Tree与B+Tree的结构特性- B-Tree
每个节点存储多个键值和子节点指针，数据可能分布在任意节点。
查询需从根节点逐层向下，路径不唯一，可能导致较多磁盘IO。
范围查询需遍历所有子树，效率较低。
- B+Tree（MySQL默认）
数据仅存储在叶子节点，非叶子节点仅存储键值和子指针，单节点可容纳更多索引项，降低树高度。
叶子节点通过双向链表连接，支持高效范围查询（如WHERE id BETWEEN 1 AND 10仅需遍历叶子链表）。
查询路径稳定（始终从根到叶子），磁盘IO次数更可预测。
- Hash索引的局限性
仅支持精确匹配（如=、IN），无法处理范围查询（如>、BETWEEN）或排序（ORDER BY）。
哈希冲突会导致性能下降，且无法利用索引排序优化排序操作。
哈希表为全内存结构，无法直接适配磁盘存储的索引需求。
- 二叉树/红黑树的缺陷
树高度问题：二叉树在数据倾斜时会退化为链表，红黑树虽平衡但高度仍随数据量增长（O(logN)），导致磁盘IO次数增加。
磁盘友好性差：B+Tree通过多路分支（通常100+）将树高度压缩至3-4层，显著减少磁盘访问次数（每次IO加载一个节点，通常16KB）。
- MyISAM引擎
非聚簇索引：索引文件（.MYI）和数据文件（.MYD）分离，B+Tree叶子节点存储数据行指针。
查询需二次检索：先通过索引定位指针，再从数据文件读取行数据。
- InnoDB引擎
聚簇索引：主键索引的B+Tree叶子节点直接存储完整数据行，二级索引叶子节点存储主键值（需回表查询）。
自适应哈希索引：对频繁访问的索引页自动构建哈希索引，加速等值查询（但无法控制且仅适用于内存）。
- 减少页分裂：自增主键保证数据按顺序插入，B+Tree叶子节点从左到右填充，仅在节点满时分裂（且仅分裂当前节点）。
- 降低数据移动：非自增主键（如UUID）可能导致随机插入，频繁触发页分裂并移动大量数据，增加IO开销。
插入连续数据（自增主键）
插入非连续数据（随机主键）
总结B+Tree通过多路平衡、数据聚集和链表连接等设计，在磁盘IO效率、范围查询和排序支持上显著优于Hash和二叉树结构。InnoDB的聚簇索引进一步优化了数据存储，而自增主键则通过减少页分裂和数据移动维持索引的高效性。理解这些原理有助于设计更优的数据库表结构和查询策略。
热门标签
