索引的底层数据结构

MySQL 索引的底层数据结构通常是 B+树，也有一些特殊情况采用 哈希表 或其他结构（例如全文索引）。在 InnoDB 存储引擎中，主要使用 B+树作为索引的数据结构。

---

为什么选择 B+树？

1. 数据存储效率高

• B+树的叶子节点存储实际数据：
  在 InnoDB 的聚簇索引中，叶子节点存储表的完整数据行；在二级索引中，叶子节点存储主键值，减少存储冗余。
• 平衡性：
  B+树是平衡树，所有叶子节点在同一层，保证查询的时间复杂度为 O(log n)。

2. 优化磁盘 I/O

• 多路性（M 阶树）：
  B+树是多路平衡树，每个节点存储多个键值，树的高度较低。大多数情况下，B+树的高度为 2-3 层，访问数据时只需 2-3 次磁盘 I/O，性能非常高。
• 顺序读取：
  B+树的叶子节点通过双向链表连接，适合顺序扫描，有效利用磁盘的预读特性。

3. 适合范围查询

• 连续存储：
  叶子节点的链表结构使得 B+树非常适合范围查询，只需顺着链表从起点扫描到终点即可，无需多次查找。
• B-树的改进：
  B+树的所有数据都集中在叶子节点，而非叶子节点只存储索引信息，数据访问效率更高。

4. 支持动态调整

• 自动分裂和合并：
  插入或删除操作会自动触发节点分裂或合并，保持树的平衡性，适应动态变化的数据场景。

5. 磁盘友好

• 节点大小与页大小匹配：
  通常一个节点的大小设计为接近磁盘页的大小（如 16 KB），读写时充分利用磁盘预读和写回机制，减少磁盘访问次数。

---

为什么不用其他数据结构？

1. 哈希表

• **优点：**查询效率为 O(1)。
• 缺点：
  • 不支持范围查询。
  • 哈希冲突可能导致性能下降。
  • 无法保证数据有序性。
  • 动态扩容会引发性能问题。

2. 二叉搜索树（BST）或 AVL 树

• 缺点：
  • 树的高度可能过高，导致查询性能下降。
  • 动态调整成本较高。
  • 不适合存储大规模数据，磁盘访问性能差。

3. 跳表

• **优点：**适合范围查询。
• **缺点：**在数据库中实现复杂，性能和磁盘适配性不如 B+树。

---