数据库索引底层原理：B-Tree 如何工作以及为什么一半索引无效
一位开发者在 Dev.to 上发表文章，深入讲解了数据库索引的底层原理。文章以一个常见的场景开场：同一个查询、同一张表、同样的百万行数据，某一天需要 4 秒，第二天只需要 4 毫秒。数据没有变化，唯一的变化是加了一行 SQL——创建了一个索引。一行 SQL 带来一千倍的性能提升，但很少有人告诉你：人们添加的索引中有一半根本不起作用。查询仍然慢，写入变得更慢，而他们不知道为什么。
没有索引时：全表扫描
工作原理
当你查询一个用户的邮箱，但该列没有索引时，数据库只能做一件事：
SELECT * FROM users WHERE email = 'vlad@stack.dev';
数据库从第一行开始读取，检查是否匹配。不匹配，读取第二行。不匹配，继续。它会检查每一行，直到找到目标或遍历完所有行。
- 百万行表：需要一百万次检查
- 性能：O(n)，表越大越慢
- 十倍数据：等待时间十倍增长
这就是全表扫描（Full Table Scan），也是那 4 秒的来源。
索引到底是什么
常见误解
很多人对索引有误解：
- 不是表的副本：索引不是复制整张表
- 不是缓存：索引不是某种缓存机制
- 不是魔法：索引不是加了就一定快
真正的定义
索引是一个有序映射（Sorted Map）：
- 只包含搜索列：只存储你要搜索的那一列的值
- 保持有序：这些值按顺序排列
- 指向完整行：每个值都有一个指针，指向表中的完整行
索引结构（以 email 列为例）：
alice@example.com → 行指针 #1023
bob@example.com → 行指针 #456
charlie@example.com → 行指针 #789
...
vlad@stack.dev → 行指针 #2341 ← 二分查找快速定位
...
zack@example.com → 行指针 #567
因为索引是有序的，数据库可以使用二分查找（Binary Search）：
- 百万行数据：只需要约 20 次比较（log₂(1,000,000) ≈ 20）
- 性能：O(log n)，表增大十倍，只多一次比较
- 对比：全表扫描需要 1,000,000 次检查 vs 索引需要 20 次检查
这就是从 4 秒到 4 毫秒的原因。
B-Tree：索引的底层数据结构
为什么不是简单的有序数组
理论上，有序数组加二分查找就够了，但实际中有一个问题：插入和删除。
- 插入：在有序数组中间插入一个元素，需要移动后面所有元素，O(n)
- 删除：删除元素后需要移动填补空缺，O(n)
- 数据库需要频繁写入：每次 INSERT/UPDATE/DELETE 都要更新索引
如果用有序数组，写入性能会非常差。
B-Tree 的解决方案
B-Tree（Balance Tree，平衡树）是索引的标准数据结构：
- 多路搜索树：每个节点可以有多个子节点（不是二叉树）
- 自平衡：插入和删除后自动保持平衡，所有叶子节点在同一层
- 块友好：每个节点大小通常等于一个磁盘块（4KB 或 8KB），一次磁盘读取获取整个节点
- 层级少：百万行数据只需要 3-4 层
B-Tree 结构示意（简化版）：
[ M | T ]
/ | \
[A-F] [G-P] [Q-Z] ← 中间节点
/ | \ / | \ / | \
[叶][叶][叶][叶][叶][叶] ← 叶子节点（存储实际值和指针）
B-Tree 的查找过程
查找 vlad@stack.dev：
- 根节点：比较
M和T，vlad>T，走最右侧分支 - 中间节点：在
[Q-Z]中比较，vlad在V附近，走对应分支 - 叶子节点：在叶子节点中找到
vlad@stack.dev，获取行指针 - 回表：根据行指针读取完整行
每次节点访问都是一次磁盘读取，但因为节点大小等于磁盘块，效率很高。百万行数据只需要 3-4 次磁盘读取。
B-Tree 的插入和删除
- 插入：找到应该插入的叶子节点，如果节点已满则分裂（Split），分裂可能向上传播
- 删除：找到并删除，如果节点过小则合并（Merge）或借用（Borrow）
- 自平衡：这些操作保证树始终平衡，所有叶子节点在同一层
- 性能：插入和删除都是 O(log n)，不需要移动大量数据
为什么一半索引不起作用
这是文章的核心问题。人们添加了索引，但查询没有变快。原因有以下几个：
1. 最左前缀原则（Leftmost Prefix Rule）
这是最常见的原因。
假设你有一个复合索引：
CREATE INDEX idx_name_age ON users (last_name, first_name, age);
这个索引可以加速以下查询：
-- ✅ 可以使用索引（使用最左列 last_name）
WHERE last_name = 'Smith'
-- ✅ 可以使用索引（使用最左两列）
WHERE last_name = 'Smith' AND first_name = 'John'
-- ✅ 可以使用索引（使用全部三列）
WHERE last_name = 'Smith' AND first_name = 'John' AND age > 30
但不能加速以下查询：
-- ❌ 不能使用索引（没有使用最左列 last_name）
WHERE first_name = 'John'
-- ❌ 不能使用索引（跳过了中间列 first_name）
WHERE last_name = 'Smith' AND age > 30
规则：复合索引从最左列开始使用，遇到范围查询（>、<、BETWEEN、LIKE 'xxx%'）后停止。后面的列无法用于索引查找。
2. 函数导致索引失效
在索引列上使用函数，会导致索引失效：
-- ❌ 索引失效（在索引列上使用了函数）
WHERE LOWER(email) = 'vlad@stack.dev'
WHERE YEAR(created_at) = 2026
WHERE DATE(created_at) = '2026-09-06'
原因：索引存储的是原始值，函数计算后的值不在索引中。数据库必须对每一行计算函数值，然后比较——退化为全表扫描。
解决方案：
-- ✅ 避免在列上使用函数
WHERE email = 'vlad@stack.dev' -- 应用层统一小写
WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'
WHERE created_at >= '2026-09-06' AND created_at < '2026-09-07'
-- ✅ 或者创建函数索引（PostgreSQL）
CREATE INDEX idx_email_lower ON users (LOWER(email));
3. 隐式类型转换
当查询参数的类型与列的类型不匹配时，数据库会进行隐式类型转换，导致索引失效：
-- 假设 phone 列是 VARCHAR 类型
-- ❌ 隐式类型转换，索引失效
WHERE phone = 13800138000 -- 数字与字符串比较
-- ✅ 使用正确的类型
WHERE phone = '13800138000'
这在 MySQL 中尤其常见。当字符串列与数字比较时，MySQL 会将字符串转换为数字，导致索引失效。
4. LIKE 前缀通配符
-- ❌ 前缀通配符，索引失效（无法利用有序性）
WHERE email LIKE '%@stack.dev'
WHERE name LIKE '%ohn'
-- ✅ 后缀通配符，可以使用索引（范围查找）
WHERE email LIKE 'vlad%'
WHERE name LIKE 'John%'
原因：B-Tree 索引是按值的前缀排序的。vlad% 可以定位到以 vlad 开头的范围，但 %@stack.dev 无法利用有序性。
解决方案：如果需要后缀匹配，可以创建反转索引，或者使用全文索引。
5. OR 条件
-- ❌ OR 条件可能导致索引失效
WHERE email = 'vlad@stack.dev' OR username = 'vlad'
-- 如果 email 和 username 都有单独的索引，
-- 某些数据库（如 MySQL）可能使用 index merge，
-- 但很多情况下会退化为全表扫描
解决方案：
-- ✅ 使用 UNION 代替 OR
SELECT * FROM users WHERE email = 'vlad@stack.dev'
UNION
SELECT * FROM users WHERE username = 'vlad'
6. 数据类型不适合索引
某些数据类型的列，索引效果很差：
- 低选择性列：性别（男/女）、状态（启用/禁用）等只有少数几个值的列
- 大文本列：TEXT、BLOB 等大字段（需要前缀索引或全文索引）
- 频繁更新的列：更新成本高
对于低选择性列，索引的区分度很低，数据库可能认为全表扫描更快，从而不使用索引。
7. 统计信息过时
数据库基于统计信息决定是否使用索引。如果统计信息过时，可能做出错误的决策：
-- 更新统计信息
ANALYZE TABLE users; -- MySQL
ANALYZE users; -- PostgreSQL
索引的代价
索引不是免费的，它有代价：
1. 写入开销
每次 INSERT、UPDATE、DELETE 都需要更新索引：
- 索引越多：写入越慢
- 复合索引：更新成本更高
- 高写入表：索引数量需要谨慎控制
2. 存储空间
索引需要额外的存储空间：
- 每个索引：存储索引列的值 + 行指针
- 大表：索引大小可能达到表大小的 50%-100%
- 多个索引：存储空间成倍增加
3. 维护成本
- 索引碎片：频繁更新导致索引碎片，需要定期重建
- 统计信息：需要定期更新统计信息
- 监控：需要监控索引使用情况，删除未使用的索引
索引设计最佳实践
1. 基于查询设计索引
- 不要盲目加索引：基于实际查询模式设计
- 分析慢查询：使用 EXPLAIN 分析慢查询，确定需要哪些索引
- 覆盖索引：如果查询只需要索引中的列，创建覆盖索引避免回表
-- 覆盖索引示例：查询只需要 last_name 和 first_name
CREATE INDEX idx_name ON users (last_name, first_name);
-- 查询不需要回表，因为所有需要的列都在索引中
SELECT last_name, first_name FROM users WHERE last_name = 'Smith';
2. 复合索引列顺序
- 等值查询列在前：等值条件（=）的列放在前面
- 范围查询列在后：范围条件（>、<、BETWEEN）的列放在后面
- 高选择性列在前：区分度高的列放在前面
-- 好的顺序：等值列在前，范围列在后
CREATE INDEX idx_dept_age ON employees (department_id, age);
WHERE department_id = 10 AND age > 30 -- ✅ 两列都能用上
-- 不好的顺序：范围列在前
CREATE INDEX idx_age_dept ON employees (age, department_id);
WHERE age > 30 AND department_id = 10 -- ❌ 只有 age 用上，department_id 用不上
3. 定期审查索引
- 查找未使用的索引：删除从未使用的索引
- 查找重复索引：删除重复或冗余的索引
- 监控索引使用：持续监控索引使用情况
-- MySQL：查看索引使用情况
SELECT * FROM sys.schema_unused_indexes;
-- PostgreSQL：查看索引使用情况
SELECT schemaname, relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0;
4. 使用 EXPLAIN 验证
创建索引后，使用 EXPLAIN 验证索引是否被使用：
EXPLAIN SELECT * FROM users WHERE email = 'vlad@stack.dev';
-- 关注 key 行：是否使用了预期的索引
-- 关注 type 行：ref（使用索引）比 ALL（全表扫描）好
-- 关注 rows 行：扫描的行数越少越好
总结
数据库索引是一个有序映射，底层使用 B-Tree 数据结构，通过二分查找将查询从 O(n) 降低到 O(log n)。
核心要点：
- 索引原理：索引是有序映射，只存储搜索列+行指针，B-Tree 实现自平衡
- 性能提升：百万行数据从 1,000,000 次检查降到约 20 次检查
- 索引失效原因：最左前缀原则违反、函数操作、隐式类型转换、前缀通配符、OR 条件、低选择性、统计信息过时
- 索引代价：写入开销、存储空间、维护成本
- 最佳实践：基于查询设计、复合索引列顺序（等值在前范围在后）、定期审查、EXPLAIN 验证
对于数据库开发者来说，理解索引的底层原理和失效条件至关重要。添加索引不是一行 SQL 那么简单——需要理解查询模式、设计合理的索引、验证索引是否被使用、定期审查和维护。只有这样，才能真正发挥索引的威力，避免"加了索引但查询还是慢"的困惑。
原文链接：https://dev.to/vladut02/what-actually-happens-in-a-database-index-and-why-half-of-them-do-nothing-3mh6