MySql索引为什么采用B树的结构
目录
MySql索引为什么采用B+树的结构
MySQL（尤其是其默认存储引擎InnoDB）使用B+树作为索引和数据组织方式，是基于其设计目标和硬件特性做出的最优选择。
简单来说，核心原因是为了减少磁盘I/O次数，从而高效地支持大规模数据的增删改查，特别是常见的范围查询和全表扫描。
下面我们通过对比和分解，来详细解释为什么是B+树。
1. 与其他数据结构的对比
为什么不用别的数据结构？对比一下就清楚了。
| 数据结构 | 缺点（在数据库索引的语境下） | 为何B+树更好 |
|---|---|---|
| 哈希表 (Hash Table) | 优点：等值查询极快（O(1)）。 致命缺点：无法进行范围查询（如 WHERE id > 5）。数据是无序的，>、<、BETWEEN、ORDER BY 等操作效率极低。 | B+树的所有叶子节点形成了一个有序链表，范围查询非常高效。 |
| 二叉搜索树 (BST) | 可能退化成链表，查询时间复杂度和树高相关（O(n)）。每个节点最多2个子节点，树会非常高。对于存在大量数据的数据库，树高意味着需要很多次磁盘I/O（非常慢）。 | B+树是多路搜索树，一个节点可以有很多子节点（百上千个），极大地降低了树的高度，从而减少了磁盘访问次数。 |
| 平衡二叉搜索树 (AVL树) | 解决了退化问题，但依然是二叉树，树高仍然很高。例如，存储100万条数据，二叉树大概有20层，意味着最坏情况需要20次磁盘I/O。 | B+树的“胖扁”结构让树高通常只有3-4层，3-4次I/O就能在亿级数据中定位到记录。 |
| B树 (B-Tree) | B树是B+树的前身，它在每个节点中都存储了数据（Data域）。这意味着每个节点能容纳的键（Key）更少，导致树高比B+树略高。同时，无法进行高效的范围查询，因为数据分散在各个节点中。 | B+树的非叶子节点只存键和指针，不存数据。因此，一个节点可以容纳更多的键，树高更低。所有数据都存储在叶子节点，且叶子节点用指针相连，查询更加稳定（每次查询都要到叶子节点），且范围查询无敌。 |
2. B+树的核心优势详解
B+树完美地契合了磁盘的工作特性和数据库的查询需求。
1. 矮胖的树形结构，极大减少磁盘I/O
磁盘I/O是数据库操作的主要成本。磁盘读写以页（Page，通常是4KB或16KB） 为单位。
B+树的一个节点的大小被设计为等于一个磁盘页的大小。
因为非叶子节点只存储键和指针（不存储实际数据），所以单个节点可以容纳非常多的键（比如1000个）。这意味着这棵1000叉的树：
- 深度为1：最多存储
1000个键。 - 深度为2：最多存储
1000 * 1000 = 1,000,000个键。 - 深度为3：最多存储
1000 * 1000 * 1000 = 1,000,000,000个键。
- 深度为1：最多存储
只需3次磁盘I/O，就能在10亿条数据中定位到一条记录，效率极高。
2. 叶子节点双向链表，支持高效范围查询
B+树的所有叶子节点通过指针串联成一个有序双向链表。
当进行范围查询（如
WHERE id BETWEEN 10 AND 50）时：- 首先通过根节点找到下限值（id=10）所在的叶子节点。
- 然后只需沿着叶子节点的链表指针向后遍历，直到超过上限值（id=50）即可。
这个过程几乎不需要再从上层节点回溯，效率非常高。而B树进行范围查询则需要在不同层级的节点之间来回穿梭，性能差很多。
3. 数据全部存储在叶子节点，查询更稳定
- 在B+树中，任何一次查询都必须最终走到叶子节点才能拿到数据。因为数据只存在于叶子节点。
- 这意味着每一次查询的磁盘I/O次数都是稳定的（等于树的高度），便于性能预测和优化。
- 而B树的数据可能分布在任何节点，有时可能在根节点就找到数据（1次I/O），有时需要到叶子节点（3次I/O），不稳定。
4. 更适合扫库和全表扫描
- 有时候需要进行全表扫描（例如没有WHERE条件的查询）。
- 对于B+树，只需要遍历叶子节点的链表即可，非常高效。
- 而对于B树，则需要对整棵树进行一次复杂的中序遍历。
5. 更利于利用“磁盘预读”特性
- 磁盘预读（Read-Ahead）是磁盘的一种优化策略：当一次磁盘I/O发生时，不仅会读取请求的数据，还会预读相邻的一些数据到内存缓冲区（因为局部性原理，接下来很可能会用到）。
- B+树的节点大小设置为页的整数倍，并且由于其顺序访问的特性（特别是在范围查询时），使得预读机制的效果非常好，进一步减少了未来潜在的磁盘I/O次数。
总结
MySQL（InnoDB）选择B+树，是在综合考虑了磁盘I/O效率、范围查询频率、全表扫描成本、以及稳定性之后的最佳权衡。
| 特性 | 对数据库的益处 |
|---|---|
| 多路搜索树 | 树高极低 -> 磁盘I/O次数极少 |
| 非叶子节点只存Key | 单个节点容量大 -> 进一步降低树高 |
| 数据只存于叶子节点 | 查询性能稳定，都等于树高 |
| 叶子节点形成有序链表 | 范围查询和全表扫描性能极佳 |
因此，虽然B+树在等值查询上可能略逊于哈希表，但它在数据库最常用的范围查询、排序、分组等操作上拥有无可比拟的优势，使其成为关系型数据库索引的事实标准。