1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方案 1：顺序扫描（Seq Scan）
  平均读 50 万行 → 几百毫秒

方案 2：哈希索引（Hash Index）
  哈希一次 → O(1) 找到行
  限制：只支持等值查询（=、IN），范围查询不支持

方案 3：二叉搜索树（BST）
  高度 log2(100万) ≈ 20
  每次比较一次 + 读一个节点 → 20 次 I/O（如果每节点一页）
  限制：树太高，磁盘 I/O 多

方案 4：B 树（B-Tree）
  多叉树，每节点存多个 key + 数据
  高度 logm(N)，m 通常 100+ → 100 万行高度 2~3
  限制：内部节点也存数据 → 节点能放的 key 数少 → 树高较高

方案 5：B+ 树（B+Tree）
  B 树的变种：所有数据只在叶子节点
  内部节点只放 key，叶子节点放完整数据
  叶子节点之间用双向链表连接
  → 内部节点能放更多 key，树高更低
  → 范围查询走叶子链表，极快

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

                       [10│30│50│70]              ← 根（内部节点，只放 key）
                      /      |       |       \
              [1│3│5│8] [11│15│25│28] [31│38│45│48] [51│55│65│68] [71│75│85│88]
                ↑────────叶子节点链表────────↑
              叶子节点存完整数据（IOT）或行指针（二级索引）

特性：
  - 高度通常 2~4（千万级数据）
  - 范围查询：从根定位到叶子，沿链表扫描
  - 等值查询：从根定位到叶子
  - 每节点 = 一个 Page（默认 8K / 16K）

1
2
3
4
5

B+ 树的核心优势：
  1. 树矮：每节点放百级 key，3 层就能索引亿级行
  2. 范围查询强：叶子链表，连续 I/O
  3. 排序免费：B+ 树本身有序
  4. 节点 = Page：天然适配缓冲池

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Redis 用跳表（ZSet 底层）：
  - 全内存，I/O 不是瓶颈
  - 跳表实现简单（无锁 CAS 友好）
  - 不在乎树高（27 层和 3 层在内存里差不多）

MySQL 用 B+ 树：
  - 数据在磁盘，I/O 是瓶颈
  - 必须让树矮（3 层就够）
  - 节点要按 Page 组织，匹配磁盘 I/O 单位

一句话：磁盘选 B+ 树，内存选跳表 / 哈希。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

查询：SELECT name, balance FROM accounts WHERE name = 'Alice';

InnoDB：
  1. 走 name 二级索引（B+ 树）→ 找到主键值 id=1
  2. 走主键索引（B+ 树）→ 找到 id=1 的整行（"回表"）
  → 2 次 B+ 树查找

PostgreSQL：
  1. 走 name 索引 → 找到 ctid=(0,1)
  2. 走 Heap → 直接定位到行（"回 heap"）
  → 1 次索引 + 1 次随机读

差异：
  - InnoDB：二级索引查到的主键值，再到主键 B+ 树走一遍
  - PG：二级索引直接给出物理位置，一次定位到 heap
  - 单条查询 PG 通常更省 I/O，但需要二级索引足够"宽"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

-- 状态 1：堆表（Heap），无 Clustered Index
CREATE TABLE t_heap (id INT, name VARCHAR(50));
-- 二级索引指向 RID（FileID:PageID:SlotID，8 字节）

-- 状态 2：Clustered Table（有 Clustered Index）
CREATE TABLE t_clustered (
    id INT PRIMARY KEY,  -- 自动建 Clustered Index
    name VARCHAR(50)
);
-- 二级索引指向 Clustered Key（id 值）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

-- 默认堆表
CREATE TABLE t1 (id INT PRIMARY KEY, name VARCHAR2(50));
-- PK 是独立的二级索引，指向 rowid

-- 显式 IOT
CREATE TABLE t2 (
    id INT PRIMARY KEY,
    name VARCHAR2(50)
) ORGANIZATION INDEX;
-- 表本身就是按 id 排序的 B+ 树

1
2
3
4
5
6
7

IOT / Clustered Key 的选择原则（适用 InnoDB / MSSQL Clustered / Oracle IOT）：
  1. 短：让所有二级索引都跟着变小
  2. 单调递增：减少 B+ 树页分裂（如自增 ID）
  3. 不变：改主键 → 所有二级索引重建
  4. 唯一：Clustered Key 必须唯一（不唯一时引擎会加后缀）

PG 反而没这些约束：主键可以随意选，因为所有索引都指向 ctid

1
2
3
4

CREATE INDEX idx_name ON t(name);

-- 适用：等值、范围、排序、唯一约束
-- 不适用：JSON 文档检索、全文搜索、地理数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

倒排索引：把"元素 → 行"的映射存起来
  适用：数组、JSONB、全文检索

示例表：tags 是 text[]
  id | tags
  ---|------
  1  | {a, b, c}
  2  | {b, c, d}
  3  | {a, c}

GIN 索引内部：
  a → [1, 3]
  b → [1, 2]
  c → [1, 2, 3]
  d → [2]

查询 WHERE 'b' = ANY(tags) → 直接用 GIN，O(log n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

-- 数组索引
CREATE INDEX idx_tags ON t USING GIN(tags);
SELECT * FROM t WHERE tags @> ARRAY['b'];

-- JSONB 索引
CREATE INDEX idx_data ON t USING GIN(data);
SELECT * FROM t WHERE data @> '{"city": "Shanghai"}';

-- 全文索引
CREATE INDEX idx_fts ON docs USING GIN(to_tsvector('english', body));
SELECT * FROM docs WHERE to_tsvector('english', body) @@ to_tsquery('postgres & index');

1
2
3
4

GIN 特点：
  - 查询快（O(log n)）
  - 写入慢（每条记录要拆成多个元素入索引）
  - 适合"低频更新、高频查询"场景

1
2
3
4
5
6
7
8
9

GiST 是一个"框架"，可以塞各种数据类型：
  - 地理数据（PostGIS 核心依赖）
  - 范围类型（int4range、tstzrange）
  - 模糊匹配（pg_trgm）

示例：找"附近 1km 的店铺"
CREATE INDEX idx_location ON shops USING GIST(location);
SELECT * FROM shops
WHERE ST_DWithin(location, ST_Point(121.4, 31.2), 1000);

1
2
3
4
5
6

BRIN：块范围索引
  适用：超大的、物理顺序与某列相关的表（如按时间追加的日志）

原理：
  每 128 个 Page 一组，记录这组的最小/最大值
  查询时根据 min/max 跳过大块

1
2
3
4
5

-- 时序日志场景
CREATE INDEX idx_log_ts ON logs USING BRIN(ts);

SELECT * FROM logs WHERE ts >= '2026-06-01' AND ts < '2026-06-02';
-- BRIN 让 PG 跳过 ts 不在范围的大块

1
2
3
4

BRIN 特点：
  - 索引极小（KB 级，不是 GB 级）
  - 适合"自然有序"的数据（时间序列）
  - 不适合随机写入的数据

1
2

SP-GiST：用于"非平衡"数据结构（如 trie 树、四叉树、k-d 树）
  适用：电话区号、IP 路由、字符串前缀匹配

1
2
3
4
5
6
7

PG Hash 索引：
  - 早期版本（< 10）有 bug，不推荐用
  - 10+ 修复，支持 WAL 复制
  - 只支持等值查询（=）
  - 比 B-tree 略快，但功能受限

CREATE INDEX idx_id ON t USING HASH(id);

1
2
3
4

CREATE INDEX idx_name ON t(name);

-- Oracle 的 B-Tree 实际是 B+ 树
-- 叶子节点存：索引键 + rowid

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

适用：低基数列（如性别、状态、地区）
原理：每个 key 值对应一个位图，每一位代表一行

  表（5 行）：
  id | gender
  ---|-------
  1  | M
  2  | F
  3  | M
  4  | M
  5  | F

  Bitmap Index on gender:
    M → [1, 0, 1, 1, 0]
    F → [0, 1, 0, 0, 1]

查询 WHERE gender='M' AND region='East':
  M 位图 AND East 位图 → 一次位运算

1
2
3
4

CREATE BITMAP INDEX idx_gender ON users(gender);

-- 适合：低基数列 + 数据仓库（不频繁更新）
-- 灾难场景：高并发 OLTP 写入 → 锁整个位图段

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

解决"热块"问题：
  场景：主键是顺序 ID（1, 2, 3, ...），所有插入都打到 B+ 树最右侧叶子
       → 该页成为热块，并发插入互相阻塞

反向键索引：把 key 字节反转
  原 key: 12345 → 反向: 54321
  原 key: 12346 → 反向: 64321
  → 插入分散到 B+ 树不同叶子

代价：范围查询失效（不再连续）

1

CREATE INDEX idx_id_reverse ON t(id) REVERSE;

1
2
3
4
5
6
7

-- 经典场景：大小写不敏感查询
CREATE INDEX idx_lower_name ON t(LOWER(name));
SELECT * FROM t WHERE LOWER(name) = 'alice';  -- 走索引

-- 计算列
CREATE INDEX idx_amount_usd ON t(amount * 7.2);
SELECT * FROM t WHERE amount * 7.2 > 100;

1
2
3
4

CREATE INDEX idx_a_b_c ON t(a, b, c);

-- B+ 树叶子节点按 (a, b, c) 排序：
-- (1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 2, 3) (2, 1, 1) (2, 1, 5) ...

1
2
3
4
5
6
7
8
9

能用上 idx_a_b_c 的查询：
  WHERE a = 1                       ✅ 用 a
  WHERE a = 1 AND b = 2             ✅ 用 a, b
  WHERE a = 1 AND b = 2 AND c = 3   ✅ 用 a, b, c
  WHERE a = 1 AND c = 3             ✅ 用 a（c 用不上，跳过 b）
  WHERE a > 1 AND b = 2             ✅ 用 a（范围后断）
  WHERE b = 2                       ❌ 不用（缺最左 a）
  WHERE b = 2 AND c = 3             ❌ 不用
  WHERE a = 1 ORDER BY b, c         ✅ 用 a + 排序免费

1
2
3
4
5
6

B+ 树是有序的，按 (a, b, c) 排序：
  (1, 1, 1) < (1, 1, 2) < (1, 2, 1) < (2, 1, 1)

WHERE a = 1：从 (1, ?, ?) 段开始扫
WHERE a = 1 AND b = 2：进一步缩到 (1, 2, ?) 段
WHERE b = 2：B+ 树不是按 b 排序的，无法定位 → 退化为全索引扫描

1
2
3
4
5
6
7

WHERE a > 1 AND b = 2：
  a 是范围 → B+ 树定位到 a > 1 的范围，但 b 在这个范围内无序
  → 只能用 a，b 不能用索引

如何绕过：
  方案 1：调整索引列顺序（按"等值在前，范围在后"排）
  方案 2：把范围改成 IN 列表（a IN (2, 3, 4) AND b = 2）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

联合索引列顺序的优先级：
  1. 等值查询的列（最左）
  2. 排序列（中间，利用 B+ 树天然有序）
  3. 范围查询列（最右，避免截断）

反例：
  WHERE status = 'A' AND create_time > '2026-06-01'
  → idx(status, create_time)：先等值定位 status，再范围扫 create_time ✅
  → idx(create_time, status)：先范围扫 create_time，再过滤 status ❌（无效）

观察执行计划验证：
  MySQL: EXPLAIN SELECT ... → key_len 看用了几列
  PG: EXPLAIN (BUFFERS) SELECT ... → "Index Cond" 看用了哪些列
  Oracle: EXPLAIN PLAN → "Access Predicates" vs "Filter Predicates"
  SQL Server: SET SHOWPLAN_TEXT ON → Seek Predicate 是真用，Predicate 是过滤

1
2
3
4
5
6
7

如果 SELECT 的所有列都在索引里 → 不需要回表

InnoDB 示例：
  CREATE INDEX idx_name_age ON users(name, age);
  SELECT name, age FROM users WHERE name = 'Alice';
  → 命中 idx_name_age，叶子节点存 (name, age, id)
  → 所有需要的列都在 → "Using index"（不回表）

1
2
3
4
5
6
7

-- MySQL 验证
EXPLAIN SELECT name, age FROM users WHERE name = 'Alice';
-- Extra: Using index → 覆盖索引生效

-- 故意触发回表
EXPLAIN SELECT name, age, email FROM users WHERE name = 'Alice';
-- Extra: <空> → 需要回表取 email

1
2
3
4
5
6

-- MySQL 8.0+
CREATE INDEX idx_name ON users(name) INVISIBLE;
ALTER TABLE users ADD INDEX idx_name_age_email (name) INCLUDE (age, email);
-- INCLUDE 列只放在叶子节点，不参与排序

-- Oracle / SQL Server / PG 都有类似 INCLUDE 子句

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

MySQL 5.6+ 引入，针对联合索引：

  CREATE INDEX idx_a_b ON t(a, b);
  SELECT * FROM t WHERE a = 1 AND b LIKE '%abc%';

无 ICP（5.6 之前）：
  1. 走 idx_a_b 找到 a = 1 的所有行（比如 1000 行）
  2. 全部回表取整行
  3. 在 Server 层过滤 b LIKE '%abc%'
  → 1000 次回表

有 ICP：
  1. 走 idx_a_b 找到 a = 1 的所有行（1000 行）
  2. 在存储引擎层直接用 b LIKE '%abc%' 过滤（剩 10 行）
  3. 只回表 10 次
  → 减少 100 倍回表

1
2

EXPLAIN SELECT * FROM t WHERE a = 1 AND b LIKE '%abc%';
-- Extra: Using index condition → ICP 生效

1
2
3
4
5
6

PG 和 Oracle 都有类似的下推机制：
  PG：把 WHERE 条件推到 Scan 节点（Index Scan 的 Index Cond）
  Oracle：谓词下推到 Table Access
  SQL Server：Seek Predicate（下推）vs Predicate（残留过滤）

判断方法：执行计划里"过滤发生得越早越好"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

1. 函数包装列
   WHERE LOWER(name) = 'alice'     -- 不走 idx_name
   → 解决：建函数索引 或 改写为 name = 'Alice' COLLATE ...

2. 隐式类型转换（经典坑）
   WHERE phone = 13800000000       -- phone 是 VARCHAR，传 INT
   → MySQL：函数 CAST(phone) → 不走索引
   → PG：报错（更严格）
   → 解决：传字符串 '13800000000'

3. LIKE 前缀通配
   WHERE name LIKE '%abc'          -- 不走索引
   WHERE name LIKE 'abc%'          -- 走索引
   → 解决：用全文索引（PG GIN / MySQL FULLTEXT）

4. OR 中部分列无索引
   WHERE a = 1 OR b = 2           -- 如果 b 没索引，整条不走索引
   → 解决：UNION ALL 或给 b 加索引

5. 计算 / 表达式
   WHERE id + 1 = 100              -- 不走索引
   → 改写为 WHERE id = 99

6. NULL 不被索引（部分数据库）
   Oracle：单列索引不存 NULL
   → 解决：建复合索引包含 NOT NULL 列

1
2
3
4
5
6
7
8

用途：临时禁用索引，观察是否真的没用，再决定删

MySQL 8.0+：
  ALTER TABLE t ALTER INDEX idx_name INVISIBLE;
  -- 优化器看不见 → 如果性能没变差 → 可以 DROP
  -- 如果变差 → 改回 VISIBLE

Oracle / PG（PG 12+ 也支持）都有类似机制

1
2
3
4
5

-- PG 用 ALTER INDEX ... ALTER COLUMN ... SET (attndims = 0) 不直接
-- 推荐用 extension：hypopg（虚拟索引，模拟）
CREATE EXTENSION hypopg;
SELECT * FROM hypopg_create_index('CREATE INDEX idx_test ON t(name)');
-- 不真建索引，只让优化器"以为"有 → 看 EXPLAIN 是否选择

1
2
3
4
5
6
7
8

索引值不值得建？看选择性：
  选择性 = 不同值的数量 / 总行数

  低选择性（< 0.1）：性别、状态、布尔 → 一般不建
  中选择性（0.1 ~ 0.5）：地区、年龄段 → 看场景
  高选择性（> 0.5）：用户 ID、订单号 → 必建

  PG：SELECT 1.0 * COUNT(DISTINCT col) / COUNT(*) FROM t;

1
2
3
4
5
6
7
8
9

每加一个索引，每次 INSERT 都多写一份：
  原表 + N 个索引 = N + 1 次写入

  UPDATE / DELETE 也要同步维护索引

经验值：
  - 一张表索引数建议 ≤ 5 个
  - 高写入表 ≤ 3 个
  - 数仓表（只读为主）可以多

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

B+ 树插入时，如果目标页满了：
  → 把页分裂成两页，各放一半
  → 物理位置不连续，磁盘 I/O 变慢

  顺序插入（自增主键）：基本不分裂
  随机插入（UUID 主键）：频繁分裂

碎片化监控：
  MySQL: ANALYZE TABLE t; SHOW TABLE STATUS LIKE 't';
  PG: VACUUM (VERBOSE) t; 看 free space
  SQL Server: SELECT * FROM sys.dm_db_index_physical_stats(...)
  Oracle: ANALYZE INDEX idx VALIDATE STRUCTURE;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

-- MySQL（在线 DDL，8.0+）
ALTER TABLE t ENGINE=InnoDB;       -- 重建表（含所有索引）
ALTER TABLE t DROP INDEX idx, ADD INDEX idx (...);  -- 单独重建

-- PostgreSQL（CONCURRENTLY 不阻塞写）
REINDEX INDEX CONCURRENTLY idx_name;
REINDEX TABLE CONCURRENTLY t;

-- SQL Server
ALTER INDEX ALL ON t REBUILD;
ALTER INDEX ALL ON t REORGANIZE;   -- 轻量整理

-- Oracle
ALTER INDEX idx_name REBUILD ONLINE;

1
2
3
4
5
6
7
8

优化器依赖统计信息决定走不走索引：
  行数、基数、最值、直方图

定期收集：
  MySQL: ANALYZE TABLE t;  （8.0 默认自动采样）
  PG: ANALYZE t;           （autovacuum 自动）
  Oracle: DBMS_STATS.GATHER_TABLE_STATS(...)
  SQL Server: UPDATE STATISTICS t;  （自动）

1
2
3
4

记住三句话：
  1. 关系数据库索引绝大多数是 B+ 树——因为磁盘 I/O 模型
  2. InnoDB 二级索引存"主键值"，PG/Oracle 存"行位置"——这是回表成本的根源
  3. 索引不是免费的——每加一个，写入代价线性增加