1 · db-index#

来源: https://use-the-index-luke.com (Markus Winand)

S 数据库表数据量增长后，查询性能下降，需要高效定位数据
C 索引加速读取但拖慢写入；索引结构设计不当反而导致全表扫描
Q 索引的底层结构是什么？如何针对不同查询模式正确使用索引？
A 见下文

1.1 · 1. 索引的本质#

索引是数据库中独立的数据结构，拥有自己的磁盘空间，持有被索引列数据的有序副本（纯冗余）。类比书末的索引：占用额外空间、高度冗余、指向实际信息的存储位置。

1.2 · 2. 索引的结构 (Anatomy)#

索引由两种数据结构组合而成：

1.2.1 · 2.1 叶子节点 (Leaf Nodes) —— 双向链表#

• 叶子节点存储索引条目（indexed columns + ROWID），按索引列有序排列
• 节点之间通过双向链表连接，维护逻辑顺序（而非物理顺序）
• 每个叶子节点对应一个数据库 block/page（通常几 KB），尽可能多装条目
• 插入新条目时只需更新指针，不需移动大量数据
• 叶子节点中的 ROWID 指向表中散乱存放的行数据（heap structure）

1.2.2 · 2.2 B-Tree —— 平衡搜索树#

• B-Tree（Balanced Tree，不是 binary tree）建立在叶子节点之上
• 每个分支节点记录其下叶子节点中的最大值，层层向上直到根节点
• 树遍历：从根节点出发，按升序比较，找到 >= 搜索值的条目，沿引用向下，直至叶子节点
• 对数增长：每层可容纳的条目数呈指数增长。实际索引中一个节点可存数百条目，百万级记录的 B-Tree 深度通常只有 4~5 层
• 树遍历效率极高，称为索引的第一力量 (First Power)

1.2.3 · 2.3 索引查找的三个步骤#

步骤	说明	性能特征
① Tree Traversal	从根到叶子	有上界（= 树深度），极快
② Leaf Node Chain	沿链表扫描所有匹配条目	无上界，匹配越多越慢
③ Table Access	按 ROWID 回表取数据	每命中一行一次 IO，数据分散则很慢

慢索引的根因：不是树”退化”了，而是步骤②③访问了太多 block。重建索引(rebuild)长期不能解决问题。

Oracle 的三种基本操作对应这三步：

• INDEX UNIQUE SCAN — 仅树遍历（唯一约束保证至多一条）
• INDEX RANGE SCAN — 树遍历 + 链表扫描
• TABLE ACCESS BY INDEX ROWID — 回表取行

1.3 · 3. WHERE 子句与索引#

WHERE 子句定义搜索条件，是索引发挥作用的核心场所。

1.3.1 · 3.1 等值查询 (Equals)#

• 主键 / 唯一索引：INDEX UNIQUE SCAN，最快
• 复合索引 (Concatenated Index)：多列索引中，列的顺序至关重要。最左前缀匹配原则：查询必须使用索引定义中从左到右的连续列才能有效利用索引

1.3.2 · 3.2 函数与表达式#

• 在索引列上使用函数（UPPER(), TO_CHAR() 等）会导致索引失效
• 解决：创建 function-based index，如 CREATE INDEX ... ON UPPER(name)
• 大小写不敏感搜索：对列建 UPPER/LOWER 的函数索引

1.3.3 · 3.3 范围查询 (Ranges)#

• >, <, BETWEEN：可用索引，但列顺序影响 access predicate vs filter predicate
  • 复合索引中，等值列放前面，范围列放后面，可最大化 access predicate 的过滤效果
• LIKE 'prefix%'：可使用索引（前缀匹配）
• LIKE '%keyword%'：不能使用索引（全文搜索应使用专门的全文索引）
• Index Combine / Index Merge：为每列单独建索引不如一个精心设计的复合索引

1.3.4 · 3.4 部分索引 (Partial Index)#

• 只索引满足条件的行，如 CREATE INDEX ... WHERE status = 'active'（PostgreSQL、SQL Server 支持）
• Oracle 不直接支持，可用 function-based index 模拟

1.3.5 · 3.5 NULL 的处理#

• 大多数数据库（尤其 Oracle）中，全 NULL 的条目不会进入索引
• 因此 IS NULL 条件通常不能使用索引
• 解决：添加 NOT NULL 约束，或在索引中包含常量列

1.3.6 · 3.6 常见反模式 (Obfuscated Conditions)#

反模式	问题	解决
日期用函数截断 TRUNC(date_col)	索引失效	改用范围查询 date_col >= X AND date_col < Y
数字列用字符串比较	隐式类型转换，索引失效	保持类型一致
列拼接后比较	索引失效	拆为多个 AND 条件
Smart Logic (OR 1=1)	优化器无法判断，全表扫描	动态拼 SQL 或拆分查询
对索引列做数学运算 col + 1 = X	索引失效	移到另一侧 col = X - 1

1.3.7 · 3.7 绑定变量 (Bind Variables / Parameterized Queries)#

• 使用绑定变量可复用执行计划，避免每次硬解析
• 同时防止 SQL 注入
• 表越多（JOIN 越复杂），绑定变量越重要——n! 阶乘级执行计划枚举

1.4 · 4. JOIN 操作#

JOIN 每次只处理两张表，多表 JOIN 通过 pipeline 中间结果来减少内存。

1.4.1 · 4.1 三种 JOIN 算法#

算法	原理	索引需求
Nested Loops	外层每一行去内层查找（类似 N+1）	内层表的 JOIN 列需要索引
Hash Join	将小表构建哈希表，大表探测	不需要索引；适合大数据集等值 JOIN
Sort-Merge Join	两表各自排序后拉链合并	若有索引可避免排序；适合范围 JOIN

• Nested Loops 对索引依赖最大，ORM 的 N+1 问题本质就是大量 Nested Loop
• Hash Join 需要完全不同的索引策略（甚至不需要索引）

1.5 · 5. 聚集数据 (Clustering Data) —— 索引的第二力量#

将相关数据在物理上存放在一起，减少 IO 次数。

1.5.1 · 5.1 Index Filter Predicates#

• 即使某些列不能用作 access predicate，放入索引后可作为 filter predicate 在索引层面过滤，减少回表次数

1.5.2 · 5.2 Index-Only Scan (Covering Index)#

• 如果查询所需的所有列都在索引中，数据库可完全避免回表
• 这是最快的查询方式之一

1.5.3 · 5.3 Index-Organized Table / Clustered Index#

• Oracle IOT / SQL Server & MySQL InnoDB Clustered Index：表数据本身按索引顺序存储
• 优点：对主键的范围扫描极快（数据物理连续）
• 缺点：二级索引需要额外的间接查找；INSERT 可能导致页分裂

1.6 · 6. 排序与分组 (Sorting & Grouping) —— 索引的第三力量#

1.6.1 · 6.1 Indexed ORDER BY#

• 如果索引顺序与 ORDER BY 一致，可避免排序操作（pipelined order by）
• 排序是资源密集型操作：必须读取全部输入才能产出第一行结果
• 利用索引的流水线执行：可以立即返回第一行，适合分页场景
• 需注意：当 WHERE 和 ORDER BY 使用同一索引时效果最佳

1.6.2 · 6.2 ASC/DESC 与 NULL FIRST/LAST#

• 索引可以按 ASC 或 DESC 创建
• 复合索引中混合排序方向时，所有列的方向必须同时翻转才能反向扫描

1.6.3 · 6.3 Indexed GROUP BY#

• 索引同样可以流水线化 GROUP BY，原理与 ORDER BY 类似

1.7 · 7. 分页查询 (Partial Results)#

1.7.1 · 7.1 Top-N 查询#

• 配合 pipelined order by，LIMIT/FETCH FIRST/ROWNUM 可以只读取前 N 行即停止
• 极低的启动成本

1.7.2 · 7.2 翻页方式对比#

方式	原理	问题
OFFSET	跳过前 N 行	越往后越慢，数据库仍需扫描被跳过的行
Seek Method (Keyset)	用上一页最后一行的值作为下一页的起始条件	性能恒定，但不能跳页

1.7.3 · 7.3 窗口函数 (Window Functions)#

• ROW_NUMBER() OVER (ORDER BY ...) 可用于分页
• 如有合适索引，窗口函数也能利用 pipelined 执行

1.8 · 8. DML 对索引的影响#

索引是冗余数据，写操作必须同步维护索引。

操作	影响
INSERT	必须更新所有索引（不能从索引受益），是索引开销最大的操作
DELETE	WHERE 子句可利用索引定位要删的行，但也需要从所有索引中删除条目
UPDATE	只影响包含被修改列的索引，未涉及的索引无需维护

核心权衡：索引越多，读越快，写越慢。应只创建必要的索引。

1.9 · 9. 索引设计总结#

          ┌─────────────────────────────────────────┐
          │          索引的三大力量                    │
          ├─────────────────────────────────────────┤
          │ 1. B-Tree Traversal   → 快速定位         │
          │ 2. Clustering         → 减少 IO          │
          │ 3. Pipelined Order By → 避免排序          │
          └─────────────────────────────────────────┘

设计原则：

1. 复合索引列序：等值条件列在前，范围条件列在后
2. 覆盖索引：尽量让查询只访问索引（Index-Only Scan）
3. 避免冗余索引：(A, B) 的索引已覆盖 (A) 的查询
4. 不要盲目为每列建索引：一个精心设计的复合索引优于多个单列索引
5. 保持 WHERE 条件”可索引”：不要在索引列上施加函数、运算、类型转换
6. 使用绑定变量：复用执行计划，防注入
7. 权衡读写：只为真正需要的查询建索引，避免写入瓶颈