数据库索引原理

为什么需要索引

索引是加速数据检索的数据结构。没有索引时，数据库需要全表扫描（顺序读取所有数据页），时间复杂度 O(n)。有了索引，可以将时间复杂度降低到 O(log n) 甚至 O(1)。

B+ 树索引

结构

B+ 树是关系型数据库中最常用的索引结构：

• 所有数据存储在叶子节点
• 内部节点只存储键值和指向子节点的指针
• 叶子节点之间通过链表连接，支持范围查询

             [50, 70]
            /    |    \
      [20, 30]  [50, 60]  [70, 80]
      /    |    /    |    /    |    \
   数据页 数据页 数据页 数据页 数据页 数据页

查找过程

以查找 id = 55 为例：

1. 从根节点开始，55 < 70，进入左子树
2. 55 > 50 且 55 < 70... 实际是通过节点内的键值二分查找定位到对应分支
3. 最终到达叶子节点，在数据页中找到 id=55 的记录

范围查询

B+ 树的叶子节点链表结构使得范围查询非常高效。查询 id BETWEEN 50 AND 60 时，只需找到 50 然后顺序遍历链表。

哈希索引

结构

哈希索引使用哈希函数将键映射到桶（bucket）中：

hash(key) % bucket_count => bucket_number

特点

• 优点：等值查询 O(1)，性能极高
• 缺点：不支持范围查询、不支持排序、哈希冲突处理复杂

适用场景

• Redis 等内存数据库广泛使用
• PostgreSQL 支持哈希索引类型
• MySQL InnoDB 的自适应哈希索引（自适应决策）

聚簇索引与非聚簇索引

聚簇索引

数据行的物理顺序与索引顺序一致。InnoDB 的主键索引就是聚簇索引：

• 叶子节点直接存储完整数据行
• 一个表只能有一个聚簇索引
• 主键查询不需要回表

非聚簇索引（二级索引）

索引顺序与数据物理顺序不同：

• 叶子节点存储主键值（InnoDB）或行指针
• 通过二级索引查询时可能需要回表查询
• 一个表可以有多个二级索引

索引设计原则

高选择性列

选择性 = 不同值的数量 / 总行数。选择性越接近 1，索引效果越好。

-- 性别列选择性低，不适合单独建索引
-- 邮箱列选择性高，适合建索引
CREATE INDEX idx_email ON users(email);

最左前缀原则

复合索引 (a, b, c) 可以匹配：

• WHERE a = ? ✅
• WHERE a = ? AND b = ? ✅
• WHERE a = ? AND b = ? AND c = ? ✅
• WHERE b = ? ❌（跳过了最左列）

避免冗余索引

-- idx_a 已覆盖 idx_a_b 的功能
CREATE INDEX idx_a ON t(a);
CREATE INDEX idx_a_b ON t(a, b);  -- 保留这个，删除 idx_a

索引的代价

• 存储空间：索引也需要磁盘空间
• 写入性能：INSERT/UPDATE/DELETE 时需要同时维护索引
• 查询优化器：过多的索引可能让优化器做出次优选择