⭐ 题目日期：

美团 - 2024/12/23

📝 题解：

数据库索引的原理是通过特定的数据结构（如B+树、哈希表等）快速定位数据，减少磁盘I/O次数，从而提升查询效率。索引类似于书籍的目录，通过预先组织和存储关键信息，避免全表扫描。以下从核心原理、数据结构、优缺点及优化策略展开详解：

---

一、索引的核心原理

1. 核心目标：减少磁盘I/O

• 问题：数据库数据存储在磁盘上，随机读取磁盘的I/O成本高（机械硬盘约10ms/次）。
• 解决：索引通过高效数据结构（如B+树）将随机I/O转化为顺序I/O，减少访问次数。

2. 索引的工作流程

1. 解析查询条件：确定哪些列参与过滤（WHERE、JOIN、ORDER BY等）。
2. 查找索引：在索引结构中定位符合条件的记录指针（如主键值或行地址）。
3. 回表查询：根据指针到主表中获取完整数据（若索引未覆盖所有查询列）。

---

二、索引的常见数据结构

1. B+树索引（主流选择）

• 结构特点：

  • 多路平衡树：每个节点存储多个键值，树高度低（通常3-4层可存百万级数据）。
  • 叶子节点链表：所有叶子节点通过指针相连，支持高效范围查询（如WHERE id > 100）。
  • 非叶子节点仅存键：仅叶子节点存储数据指针（InnoDB中为主键值或行数据）。

• 示例：

            [根节点]
         /      |      \
    [非叶节点] [非叶节点] [非叶节点]
     /  |  \     ...      ...
  [叶子节点]->[叶子节点]->[叶子节点]（链表连接）

• 优势：

  • 范围查询高效：遍历链表即可。
  • 插入/删除平衡性好：通过节点分裂与合并维持树平衡。
  • 适合磁盘存储：节点大小与磁盘页（如4KB）对齐，减少I/O次数。

2. 哈希索引

• 原理：对索引列计算哈希值，直接映射到数据地址（类似HashMap）。
• 适用场景：等值查询（=、IN），如Memcached、Redis。
• 局限性：
  • 不支持范围查询：哈希值无序。
  • 哈希冲突：需处理冲突（链地址法、开放寻址等）。
  • 无法排序：哈希值不保留原数据顺序。

3. 全文索引

• 用途：针对文本内容（如文章）的关键词搜索。
• 实现：倒排索引（Inverted Index），记录关键词到文档的映射。
• 示例：

  "数据库" → [文档1, 文档3, 文档5]
  "索引"   → [文档2, 文档4]

4. 空间索引（如R树）

• 用途：地理数据（经纬度）、多维数据查询。
• 原理：将空间划分为区域并建立层次结构，快速定位目标区域。

---

三、索引类型（以MySQL为例）

1. 聚簇索引（Clustered Index）

• 特点：
  • 数据行按索引键顺序存储（索引即数据）。
  • 每张表只能有一个聚簇索引（通常为主键）。
• 优势：范围查询和排序速度快（数据物理有序）。
• 实现：InnoDB中主键索引为聚簇索引，若未定义主键，则选择唯一非空索引替代。

2. 非聚簇索引（Secondary Index）

• 特点：
  • 索引与数据分离，叶子节点存储主键值（非行地址）。
  • 查询需回表：先查索引获取主键，再通过主键查数据。
• 示例：

  -- 创建非聚簇索引
  CREATE INDEX idx_name ON users(name);
  -- 查询流程：idx_name → 主键 → 数据行

3. 覆盖索引（Covering Index）

• 定义：索引包含查询所需的所有列，无需回表。
• 优化技巧：

  -- 联合索引（name, age）可覆盖以下查询
  SELECT name, age FROM users WHERE name = 'Alice';

4. 联合索引（Composite Index）

• 定义：多列组合的索引（如(col1, col2, col3)）。
• 最左前缀原则：查询需从索引最左列开始，否则无法命中。

  -- 索引(a, b, c)生效场景：
  WHERE a = 1 AND b = 2;
  WHERE a = 1 ORDER BY b;
  -- 不生效场景：
  WHERE b = 2; -- 未使用a

---

四、索引的优缺点

优点	缺点
加速查询（WHERE、JOIN）	增加写操作开销（维护索引结构）
加速排序（ORDER BY）	占用额外磁盘空间
加速分组（GROUP BY）	不合理的索引可能降低性能

---

五、索引优化策略

1. 选择性高的列建索引：
   • 选择性 = 不同值数 / 总行数（如性别选择性低，不适合单独索引）。
2. 避免冗余索引：
   • 联合索引(a, b)可替代单独索引(a)。
3. 使用覆盖索引：减少回表查询。
4. 监控索引使用率：删除未使用的索引（通过SHOW INDEX或性能Schema）。
5. 定期维护：重建碎片化索引（如OPTIMIZE TABLE）。

---

六、示例：B+树索引的写入过程

1. 插入数据：
   • 根据索引键找到对应叶子节点位置。
   • 若节点未满，直接插入；若已满，分裂节点并向上递归调整。
2. 删除数据：
   • 标记删除或直接移除数据。
   • 若节点利用率低于阈值，合并相邻节点。

---

总结

• 核心原理：通过高效数据结构（如B+树）减少磁盘I/O，加速查询。
• 数据结构：B+树（范围查询）、哈希（等值查询）、倒排索引（全文搜索）。
• 优化核心：平衡查询加速与写入开销，避免过度索引。
• 实践建议：结合业务查询模式设计索引，定期分析执行计划（EXPLAIN）调整优化。