常见索引结构

索引是数据库优化查询性能的核心机制。不同索引结构在查询效率、存储方式和支持的操作上存在显著差异。

哈希表

哈希表基于哈希函数实现键值映射，适用于精确匹配查询。

• 工作方式：
  • 通过哈希函数将输入键映射为固定长度的哈希值，定位存储桶（bucket）。
  • 每个存储桶包含键值对，查询时直接根据哈希值访问对应存储桶。
• 优点：
  • 等值查询效率极高，时间复杂度为 $\mathcal{O}(1)$。
• 缺点：
  • 不支持范围查询，需全表扫描，时间复杂度退化为 $\mathcal{O}(n)$。
  • 哈希冲突可能影响性能，需额外处理（如链地址法）。
• 适用场景：
  • 键值数据库或需要快速等值查询的场景，如缓存系统。

二叉搜索树

二叉搜索树使用节点结构存储数据，但存在严重性能瓶颈。

• 工作方式：
  • 每个节点存储一个键值对，左子树键值小于节点，右子树键值大于节点。
  • 查询时从根节点开始，比较键值后递归选择左或右子树，直至找到目标或确认不存在。
• 问题：
  • 数据量大时树高度激增（例如百万数据时高度约 20 层），导致查询需多次磁盘 I/O，效率低下。
  • 不平衡树（如倾斜树）进一步恶化性能，实际场景中较少直接使用。
• 适用场景：
  • 小规模数据或内存操作，需额外平衡机制（如 AVL 树或红黑树）。

B 树

B 树是一种自平衡树结构，非叶子节点同时存储索引键和记录数据。

• 工作方式：
  • 每个节点包含多个键和指向子节点的指针，节点大小固定为磁盘页。
  • 查询时从根节点开始，根据键值比较选择子节点，逐层定位目标数据。
  • 插入/删除时通过节点分裂或合并保持平衡，确保树高度较低。
• 特点：
  • 每个节点大小固定为磁盘页（通常 16 KB），存储索引键和关联记录。
  • 通过多叉结构维持平衡，确保操作时间复杂度为 $\mathcal{O}(\log n)$。
• 优点：
  • 相比二叉树，数据量大时树高度更低（例如百万数据时高度约 3-4 层），减少 I/O 次数。
• 缺点：
  • 节点存储记录数据，导致单个节点有效索引键较少（分支因子小），树高度仍较高。
  • 范围查询效率低，需遍历多个节点。
• 适用场景：
  • 适合点查询为主的数据库场景，如早期文件系统。

B+ 树

B+ 树是 B 树的优化版本，非叶子节点仅存储索引键，数据集中在叶子节点。

• 工作方式：
  • 非叶子节点存储索引键和子节点指针，查询时通过键值比较逐层定位到叶子节点。
  • 叶子节点存储索引键和完整记录，通过双向链表连接，便于顺序遍历。
  • 插入/删除时通过节点分裂或合并保持平衡，维持低树高。
• 特点：
  • 非叶子节点只存储索引键，叶子节点存储索引键和完整记录。
  • 叶子节点间通过双向链表连接，支持高效顺序访问。
• 优点：
  • 分支因子大（单个节点可存储更多索引键），树高度显著降低（例如百万数据时高度约 2-3 层），I/O 次数更少。
  • 范围查询高效，通过链表直接遍历叶子节点。
  • 查询稳定性高，数据始终在叶子节点获取。
• 适用场景：
  • 现代关系型数据库（如 MySQL InnoDB）的首选索引结构，适合点查询和范围查询。

B 树与 B+ 树的区别

特性	B 树	B+ 树
数据存储	所有节点存储索引键 + 记录	非叶子节点仅存索引键；叶子节点存索引键 + 记录
分支因子	较低（节点存储记录占用空间）	较高（节点仅存索引键）
范围查询	不支持高效范围查询	支持（叶子节点双向链表）
查询稳定性	数据可能在中途节点获取（不稳定）	数据仅在叶子节点获取（稳定）
适用场景	点查询为主	点查询和范围查询兼顾

聚集索引和二级索引

在 InnoDB 存储引擎中，索引主要分为聚集索引 (Clustered Index) 和二级索引 (Secondary Index)。

聚集索引 (Clustered Index)

• 定义: 叶子节点存储完整行数据，物理存储顺序与索引逻辑顺序一致。
• 结构: 每张表有且仅有一个聚集索引。
• 选择规则:
  1. 如果表定义了 PRIMARY KEY，则主键索引就是聚集索引。
  2. 如果没有 PRIMARY KEY，InnoDB 会选择第一个不包含 NULL 值的 UNIQUE 索引作为聚集索引。
  3. 如果以上两者都没有，InnoDB 会隐式地创建一个名为 GEN_CLUST_INDEX 的 6 字节隐藏主键作为聚集索引。
• 叶子节点存储内容: 主键值 + 完整的行记录。

二级索引 (Secondary Index)

• 定义: 二级索引，也称为非聚集索引。它的叶子节点不存储完整的行数据，而是存储索引键的值和对应记录的主键值。
• 结构: 一张表可以拥有多个二级索引。
• 叶子节点存储内容: 索引列的值 + 主键值。

回表和索引覆盖

回表 (Table Access by Index RowID)

• 定义: 使用二级索引查询时，若所需列未完全覆盖，需用主键值回查聚集索引获取完整数据。这个再次查询聚集索引的过程，就称为“回表”。
• 示例:

  -- age 列上存在二级索引
  SELECT id, age, name FROM student WHERE age = 20;

• 执行过程:
  1. 在 age 索引树中搜索 age = 20 的记录，找到对应的叶子节点。
  2. 从叶子节点中获取该记录的主键值 (例如 id = 101)。
  3. 使用获取到的主键值 101，回到主键索引 (聚集索引) 中进行查找。
  4. 在主键索引的叶子节点中找到 id = 101 的完整行记录，并从中读取 id, age, name 字段返回。
• 影响: 回表操作需要进行两次索引查找，增加了额外的磁盘 I/O 和查询开销，应尽量避免。

索引覆盖 (Covering Index)

• 定义: 当一个查询语句所需要获取的所有列数据，都恰好能从一个二级索引的叶子节点中直接获取时，就不再需要进行回表操作。这种情况就称为“索引覆盖”。
• 示例:

  -- age 列上存在二级索引
  SELECT id, age FROM student WHERE age = 20;

• 执行过程:
  1. 在 age 索引树中搜索 age = 20 的记录，找到对应的叶子节点。
  2. 二级索引的叶子节点本身就存储了 age 和 主键 id 的值。查询所需的所有列 (id, age) 均已获取。
  3. 直接返回结果，无需回表查询主键索引。
• 优势: 索引覆盖是一种高效的查询优化策略，它减少了查询主键索引的步骤，避免了回表带来的性能损耗，显著提升了查询效率。

总结

为什么使用 B+ 树作为索引的数据结构？

数据库选择 B+ 树，其实是一个历史演进的过程，而并不是在众多索引方式中选出来的结果。

1. 首先是哈希表：查单个值很快，但完全不支持范围查询，而且在磁盘上扩展和冲突处理都很低效，所以不适合数据库。
2. 然后是二叉树：逻辑上能查和遍历，但每个节点太小，树高太大，大量数据时磁盘 I/O 次数太多，即使平衡二叉树也不够友好。
3. 接着是 B 树：它是专门为磁盘设计的多路平衡树，每个节点能容纳很多关键字，树高大幅下降，I/O 大幅减少。但 B 树的缺点是数据分散在所有节点，范围查询需要反复在树中跳，效率不理想。
4. 最后演进到 B+ 树：它把所有数据都放在叶子节点，内部节点只存索引键，这样树更矮更轻；同时叶子节点通过链表顺序连接，非常适合范围查询。再加上继承了 B 树的平衡和动态特性，所以成为数据库和文件系统的标准索引结构。