Skip to content

索引的原理是什么

索引原理

  • 定义：
  • 索引是数据库中用于加速查询的数据结构，通过减少扫描数据量提高效率。
  • 核心机制：
  • 将数据按某种顺序组织（如 B+ 树、哈希），快速定位目标记录。
  • 实现：
  • MySQL 常用 B+ 树索引，将键值排序存储，支持等值和范围查询。

工作原理

  1. 存储：索引列的值和数据位置（指针）单独存储。
  2. 查找：通过索引树快速定位，减少全表扫描。
  3. 维护：增删改时同步更新索引。

核心点

  • 索引本质是“以空间换时间”。

1. 索引原理详解

(1) 基本概念

  • 作用：
  • 避免全表扫描，提升查询性能（如 WHERE、JOIN）。
  • 本质：
  • 数据结构（如 B+ 树、哈希）+ 指针，映射键到记录。
  • 存储位置：
  • MySQL InnoDB：索引文件（.ibd）与数据分离或集成。

(2) B+ 树索引原理（主流）

  • 结构：
  • 非叶子节点：存储键值，用于导航。
  • 叶子节点：存储键值+数据指针（或数据本身），链表连接。
  • 查找过程：
  • 从根节点开始，比较键值。
  • 按层向下，定位到叶子节点。
  • 在叶子节点找到目标记录或范围。
  • 示例：
CREATE INDEX idx_age ON user(age);
SELECT * FROM user WHERE age = 25;
  • B+ 树：
根: [20]
中间: [10 | 15]  [25 | 30]
叶子: [5->r1, 10->r2] -> [15->r3, 20->r4] -> [25->r5, 30->r6]
  • 查询 age = 25：根 → 中间（25） → 叶子（25），返回记录 r5。

(3) 性能提升

  • 全表扫描：
  • 时间复杂度：O(n)，n 为记录数。
  • 索引查询：
  • B+ 树：O(log_m n)，m 为阶数。
  • 磁盘 I/O：
  • B+ 树多路，树高低，一次 I/O 读多数据（页大小 16KB）。

(4) 类型

  • 主键索引：
  • InnoDB 聚簇索引，数据按主键排序存储。
  • 二级索引：
  • 非聚簇索引，叶子存主键，需回表。
  • 哈希索引：
  • 等值查询快（O(1)），不支持范围。

2. 工作机制

(1) 创建索引

  • 过程：
  • 提取索引列，构建 B+ 树。
  • 叶子节点记录数据位置（主键或行指针）。
  • 示例：
CREATE TABLE user (id INT PRIMARY KEY, name VARCHAR(50));
CREATE INDEX idx_name ON user(name);
  • idx_name：B+ 树按 name 排序。

(2) 查询过程

  • SQL 执行：
SELECT * FROM user WHERE name = 'John';
  1. 查 idx_name 的 B+ 树。
  2. 找到 John 的主键（如 1）。
  3. 用主键回表取整行。
  4. 覆盖索引：
SELECT name FROM user WHERE name = 'John';
  • 直接从索引取值，无需回表。

(3) 维护成本

  • 增删改：
  • 插入：B+ 树分裂。
  • 删除：标记或重组。
  • 更新：可能重建部分树。
  • 代价：
  • 额外存储空间。
  • 写操作变慢。

3. 为什么用 B+ 树

  • 磁盘优化：
  • 多路树高低，减少 I/O。
  • 范围查询：
  • 叶子链表顺序访问。
  • 缓存友好：
  • 非叶子只存键，占用小。

与 B 树对比

  • B 树：数据分散，范围查询需回溯。
  • B+ 树：数据集中叶子，顺序性好。

4. 延伸与面试角度

  • 哈希索引：
  • 原理：键哈希到槽位，O(1) 查询。
  • 局限：不支持范围。
  • 实际应用：
  • InnoDB：主键聚簇索引。
  • 电商：WHERE order_id = 123。
  • 优化：
  • 复合索引：多列查询。
  • 覆盖索引：减少回表。
  • 面试点：
  • 问“原理”时，提 B+ 树和查找。
  • 问“优势”时，提磁盘和范围。

总结

索引通过 B+ 树等结构加速查询，原理是排序键值并快速定位，减少扫描。MySQL 用 B+ 树优化磁盘 I/O 和范围查询，代价是维护开销。面试时，可画 B+ 树或提覆盖索引，展示理解深度。