为什么要用b 树做索引
2022-02-04 07:30:02
MySQL选择B+树（B树的一种扩展形式）作为索引结构，主要因其能高效支持磁盘数据库的查询与更新需求，具体原因如下：
1. 高效的范围查询能力B+树的叶子节点通过双向链表连接，所有关键字均存储在叶子节点上，非叶子节点仅存储索引副本（如主键值）。这种设计使得范围查询（如WHERE id BETWEEN 1 AND 100）无需回溯上层节点，只需定位到起始叶子节点后，直接沿链表扫描即可完成。相比之下，B树的非叶子节点可能存储数据，导致范围查询需多次回溯，增加磁盘I/O次数。B+树的链表结构将范围查询的复杂度从B树的O(log N + k)优化为O(log N + k/B)，其中k为结果数量，B为磁盘页大小，显著提升了效率。
2. 稳定的磁盘I/O性能B+树的高度通常较低（时间复杂度为O(log N)），且节点大小与磁盘页对齐（如16KB）。每次磁盘I/O可加载整个节点，减少随机访问次数。此外，非叶子节点不存储实际数据，仅作为索引导航，使得单节点能容纳更多关键字，进一步降低树高度。例如，存储100万条数据时，B+树可能仅需3-4层，而二叉树需约20层，磁盘I/O次数更稳定且更少。
3. 支持有序性操作B+树的内部节点和叶子节点均按关键字有序存储，叶子节点通过链表连接。这一特性使得升序/降序查询（如ORDER BY）无需额外排序，直接利用索引结构即可高效完成。例如，查询SELECT * FROM table ORDER BY id DESC时，数据库可直接从链表末尾反向遍历，避免全表排序的开销。
4. 动态数据集的高效维护B+树通过节点分裂与合并保持自平衡，确保插入和删除操作后仍维持平衡状态。这一特性避免了二叉树或红黑树在频繁更新时可能退化为链表的问题，适合数据库的高并发写入场景。例如，当节点数据量超过阈值时，B+树会分裂为两个节点，并更新父节点索引，保证查询效率。
5. 对比其他数据结构的优势- 哈希表：虽支持O(1)查找，但无法处理范围查询（如WHERE id > 100），且内存消耗大，不适合磁盘存储。
- B树：非叶子节点存储数据，导致单节点索引容量减少，查询需更多I/O次数，且范围查询效率低于B+树。
- 二叉树/红黑树：树高度较大，磁盘I/O次数多，无法满足数据库对性能的要求。
总结：B+树通过优化范围查询、稳定I/O、有序性支持和动态维护能力，成为MySQL等磁盘数据库索引的首选结构，尤其适合处理大规模数据和高并发场景。
热门标签
