跳到主要内容

数据库索引

**索引(index)**是数据库最核心的性能技术:以额外的空间与写代价,换取按某个搜索码定位记录的效率。没有索引,任何"WHERE 列 = 值"都必须全表扫描;有了索引,同样的查询往往只需要 3 – 5 次页面 I/O。本章按索引家族依次讨论:顺序索引与 B+ 树、散列索引、多码访问、写优化索引(LSM)、位图索引、以及针对时空数据的专用索引。


14.1 基本概念​

搜索码(search key):用于组织索引的一列或几列的组合。索引提供的功能是:给定搜索码值 kk,快速找出所有具有该搜索码的记录(或其位置)。

按不同维度可分类:

维度类别说明
存储组织顺序索引 vs 散列索引前者按码有序,支持范围;后者靠哈希函数
与数据关系聚簇索引 clustering vs 非聚簇/辅助索引 secondary聚簇:数据物理顺序 = 索引顺序,一表一份;辅助:数据顺序无关
覆盖度稠密索引 dense vs 稀疏索引 sparse每条记录一个索引项 / 每页一个索引项
唯一性唯一索引 vs 非唯一索引是否允许同一搜索码值出现多次
结构B+ 树、B 树、哈希、位图、LSM、R 树、GiST …

评估一个索引的常用指标:

  • 查找时间(access time):一次点查或范围起点定位的时间/I/O 次数。
  • 插入时间、删除时间:维护成本。
  • 空间开销(space overhead)。
  • 对何种查询有帮助:等值?范围?前缀?多码?

14.2 顺序索引​

顺序索引(ordered index)按搜索码值排好序,通常存成 <搜索码值 K, 指向记录的指针 P> 的有序数组或树。它天然支持等值查找与范围查询。

14.2.1 稠密索引和稀疏索引​

稠密索引(dense index):对每条记录都建立一个索引项。

稀疏索引(sparse index):只对每个"数据块"的第一条记录建立索引项,块内其余记录靠顺序扫找到。前提是数据文件本身按码有序(即索引是聚簇的)。

对比:

特性稠密索引稀疏索引
索引项数= 记录数≈ 页数
空间大小
点查一步定位定位到页后需页内二分
范围查询支持支持(数据必须有序)
插入维护每次插入都要更新只在跨页时更新
与数据的关系可聚簇也可辅助只能聚簇
支持非聚簇场景是否

图示(稀疏索引):

索引项          数据文件(按 id 排序)
[10] ──────► 页 P1: (10, ...) (12, ...) (15, ...) (18, ...)
[20] ──────► 页 P2: (20, ...) (24, ...) (26, ...) (29, ...)
[30] ──────► 页 P3: (30, ...) (33, ...) (37, ...) (39, ...)

查 id = 26:在索引里找到"最大 ≤ 26"的项 [20],跳到 P2 顺序扫描直到 26。

14.2.2 多级索引​

如果索引本身超过一页,找索引项就要在索引内做二分(对磁盘不友好)。多级索引(multi-level index):把一级索引再做一次稀疏索引形成二级索引,如此递归。每一级都能"分岔"很多路,磁盘 I/O 次数 = 树高。这就是 B+ 树的雏形。

14.2.3 索引更新​

插入一条记录 (Kr,r)(K_r, r):

  1. 若索引稠密:向索引插入 (Kr,r)(K_r, r);若已有相同码值,按非唯一索引规则处理。
  2. 若索引稀疏:只在 KrK_r 所在数据块新形成时需要新增索引项,一般无需更新。
  3. 若索引是有序数组:维护成本高(需移动 O(n)O(n)),故实际实现都用 B+ 树或跳表。

删除一条记录 (Kr,r)(K_r, r):对应稠密索引项也要删除;稀疏索引若被删记录是块首,需要把索引项换成新的块首。

14.2.4 辅助索引​

辅助索引(secondary index):搜索码 ≠ 数据物理顺序码。由于同一码值对应的记录可能散落多页,辅助索引必须是稠密的:每条记录一项。索引项一般存 <搜索码值, RID>,RID = <页号, 槽号>。

辅助索引的查询代价:一次辅助索引查找得到 nn 个 RID,最坏要 nn 次随机 I/O 去数据文件取记录。因此优化器在选择用不用辅助索引时会估计选择率,选择率过高(如返回 30% 以上记录)时可能反而选择全表扫描。

14.2.5 多码索引​

多码索引(composite index / multi-attribute index):搜索码是多个属性的元组,按字典序排序,例如索引 (dept_name, salary):

  • 支持 WHERE dept_name = 'CS' AND salary = 80000 —— 完全匹配。
  • 支持 WHERE dept_name = 'CS' —— 前缀匹配,命中一段连续叶子。
  • 支持 WHERE dept_name = 'CS' AND salary > 50000 —— 前缀 + 后缀范围。
  • 不支持 WHERE salary = 80000 —— 只能全扫索引,因为 salary 不是前缀。

索引最左前缀原则是设计多码索引时的关键。


14.3 B+树索引文件​

**B+ 树(B-Plus Tree)**是几乎所有关系数据库的默认索引结构。它既支持等值查找(点查),也支持范围扫描;插入删除维护代价可控;树高在实际数据规模下极小(3 – 5 层)。

14.3.1 B+树的结构​

B+ 树是一棵平衡多路查找树,参数为阶 n(fanout / order):

  • 每个内部节点最多 nn 个指针、n−1n-1 个搜索码;最少 ⌈n/2⌉\lceil n/2 \rceil 个指针(根除外)。
  • 每个叶子节点最多 n−1n-1 个 <K, RID>;最少 ⌈(n−1)/2⌉\lceil (n-1)/2 \rceil。
  • 所有实际数据指针只在叶子节点(这是 B+ 与 B 的关键区别)。
  • 叶子节点之间用双向链表串起,支持范围扫描时不用回溯到根。

阶 nn 的估算:假设页 4 KB,搜索码 12 字节,指针 8 字节,一条 <K, P> 20 字节,加页头 24 字节:

n=⌊(P−header)/(K+P)⌋≈⌊4072/20⌋≈203n = \lfloor (P - \text{header}) / (\text{K} + \text{P}) \rfloor \approx \lfloor 4072 / 20 \rfloor \approx 203

扇出(fanout)≈n\approx n。树高 hh 与 NN 条记录、扇出 ff 的关系:

h≤⌈log⁡⌈f/2⌉N⌉h \le \lceil \log_{\lceil f/2 \rceil} N \rceil

以 f=200f = 200、N=109N = 10^9 计算:log⁡100109≈4.5\log_{100} 10^9 \approx 4.5,即使十亿行也只需 4 – 5 层。加上根节点常驻内存,实际磁盘 I/O 通常 2 – 3 次。

14.3.2 B+树的查询​

等值查询 KK:

  1. 从根开始,找到第一个 Ki>KK_i > K(或到末位),进入相应子指针。
  2. 递归下降到叶子。
  3. 在叶子节点内二分找 KK。
  4. 若找到返回对应 RID,否则不存在。

I/O = 树高。

范围查询 K1≤K≤K2K_1 \le K \le K_2:

  1. 按上面方法定位到 K1K_1 所在叶子。
  2. 沿叶子链表向后遍历,直到超过 K2K_2。

I/O = 树高 + 结果所占叶子数。

14.3.3 B+树的更新​

插入 KK:

叶子分裂:把 nn 个键均分为两半,前一半留在 L1,后一半到新叶子 L2;把 L2 的第一个键作为分隔键插入父节点。

内部节点分裂:与叶子略不同 —— 把中间键上推到父节点,而不是复制;因此内部节点分裂后总键数 = n−1n-1,比叶子少一。

删除 KK:

  • 借(redistribution):向左/右兄弟借一个键,父节点分隔键随之更新。
  • 合并(coalesce):如兄弟也接近下限,与之合并成一个节点,从父节点删掉分隔键 —— 可能触发父节点欠满,向上递归。合并到根时,若根只剩一个指针,则根被降级,树高 -1。

14.3.4 B+树更新的复杂度​

一次插入或删除的最坏 I/O 复杂度:

O(h)=O(log⁡fN)O(h) = O(\log_f N)

即使触发一路上溯的分裂/合并,涉及节点数也不超过树高,共 O(h)O(h) 次读 + O(h)O(h) 次写。绝大多数情况下叶子未满/未满一半,一次插入/删除只涉及 1 层的一次修改,成本 O(1)O(1) 摊销。

并发控制:多线程 B+ 树用闩锁耦合(crabbing / latch coupling):从上到下逐层获取写闩,判断子节点若"绝对安全"(不会分裂/合并),则立刻释放父节点的闩,避免根锁争用。乐观法(Bayer-Schkolnick、Bw-Tree)进一步用无锁 CAS 更新。

14.3.5 非唯一性搜索码​

若允许同一搜索码值对应多条记录,最简单的方案是把搜索码扩展成 <K, RID> 复合码 —— 保证复合码唯一,B+ 树算法不变。查询时按前缀 KK 定位到范围起点,顺序扫描叶子直到 KK 变化。

另一种方案是叶子存 <K, RID列表>,节省空间但节点大小可变,实现复杂,通常不采用。


14.4 B+树扩展​

14.4.1 B+树文件组织​

B+ 树文件组织(B+ Tree File Organization):把叶子节点本身作为数据页,记录直接存在叶子里,而非只存 RID。此时索引是聚簇的,B+ 树同时充当"文件"与"索引"。

  • Oracle:索引组织表(IOT)。
  • MySQL InnoDB:聚簇索引(主键 B+ 树的叶子就是行数据)。
  • SQL Server:CLUSTERED INDEX。

优点:主键查询少一次"索引 → 数据"跳转,物理顺序 = 主键顺序,范围扫描友好。缺点:非主键的辅助索引存的是主键(不是 RID),二级查询多一次主键回表;主键必须选窄;行变长时叶子分裂更频繁。

14.4.2 辅助索引和记录重分配​

在 IOT / 聚簇表中,页内 compact 或分裂时,记录物理地址(RID)会变。若辅助索引存 RID,就必须跟着更新,代价极高。因此这类表的辅助索引一律存主键而非 RID —— 主键在页分裂时不变,查询时用主键再走一次聚簇 B+ 树。

14.4.3 对字符串的索引​

字符串作为搜索码有两个新问题:

  1. 变长:一个索引节点内的键长度不定,节点扇出不再定值。
  2. 长键:几百字节的长 URL 让扇出降到十几,树变高。

工程做法:

  • 前缀压缩(prefix compression):同一节点内相邻键往往共享公共前缀,只存增量。
  • 后缀截断(suffix truncation):内部节点的分隔键只需能区分左右子树,可以裁到最短 —— 例如键 "database" 和 "detail",分隔键存 "de" 甚至 "d" 就足够。
  • 前缀 B 树:结合以上两种方法。

14.4.4 B+树索引的批量加载​

一次性插入 NN 条记录若逐条 insert,需要 O(Nlog⁡fN)O(N \log_f N) 次分裂 + 大量随机 I/O。**批量加载(bulk loading)**优化:

  1. 先对输入按搜索码外部排序。
  2. 顺序把记录写满一个个叶子(每个叶子填到某个较高填充因子,如 70% – 90%)。
  3. 每写满一叶子,把首键写入上一层的构造缓冲;上一层满了再构造更上一层。
  4. 直到只剩一个根节点。

时间复杂度 O(Nlog⁡N)O(N \log N)(主要是排序),I/O 顺序化,比逐条插入快数十倍,这是 CREATE INDEX 的标准做法。

14.4.5 B树索引文件​

B 树(B-Tree) vs B+ 树:

差异点B 树B+ 树
数据指针位置每层都有只在叶子
叶子链表无有
范围扫描需要中序遍历顺链表扫叶子
单个节点存放的键数较少(因兼含数据指针)较多(内节点仅键 + 指针)
是否有短路查找键在中间层就能返回必须下到叶子

数据库主流选择 B+ 树是因为范围扫描在 SQL 中太常见(BETWEEN、ORDER BY、range join),扇出高、树矮、顺序扫描友好。B 树在文件系统(如 NTFS、XFS)里更常见。

14.4.6 闪存上的索引​

闪存的 erase-before-write 让原地更新 B+ 树叶子代价高。改造思路:

  • Bw-Tree(Microsoft Hekaton):叶子节点是"基页 + 增量链"(delta chain),更新只追加一个 delta 记录并 CAS 指针;后台合并回基页。避免了原地写。
  • FD-tree、BFTL:把 B+ 树的所有写累积到内存,批量刷写多个 SSTable 层。
  • 闪存感知的填充因子:叶子填充较满以减少写;内节点较空以吸收未来插入。

14.4.7 主存上的索引​

在主存 DBMS 中,"I/O 次数"退化为"cache miss 次数"。B+ 树的高扇出不再必要,反而更看重紧凑与向量化:

  • T 树(T-Tree):AVL 树的每个节点存一段连续键;早期主存 DBMS 常用。
  • ART(Adaptive Radix Tree):按字节的基数树,节点大小根据孩子数在 4/16/48/256 之间自适应。前缀共享减少高度,非常适合字符串键。
  • Masstree、Bw-Tree、CSB+-Tree:cache line 感知的 B+ 树变体。
  • 哈希 + 跳表:某些主存 KV 系统直接用无锁跳表 + 哈希索引。

14.5 散列索引​

散列(hash)索引用哈希函数 h(K)h(K) 把搜索码映射到桶(bucket),一个桶通常是一页或若干页。查询时计算 h(K)h(K) 得到桶号,只需 1 次 I/O 命中桶后线性查找即可。

静态散列(static hashing):桶数 BB 固定。当数据规模显著超出 BB 时,桶溢出成链表(overflow chain),性能退化到线性扫描。适用于"数据量已知稳定"场景。

可扩展散列(extendible hashing):桶数按需增长,仍保持 O(1) 查找。

  • 用哈希值的前 dd 位(global depth)索引到目录(directory),目录大小 2d2^d。
  • 每个桶有局部深度 db≤dd_b \le d。多个目录项可指向同一桶(当 db<dd_b < d)。
  • 桶满时分裂:若 db=dd_b = d,先加倍目录(d←d+1d \leftarrow d+1,db←db+1d_b \leftarrow d_b + 1);否则只 db←db+1d_b \leftarrow d_b + 1,把桶一分为二。
  • 无需重新哈希整个索引,扩展是局部的。
结构等值查询范围查询插入有序遍历典型场景
静态散列O(1) 均摊,溢出时退化不支持O(1)不支持数据集稳定
可扩展散列O(1),目录 1 次 I/O + 桶 1 次不支持摊销 O(1)不支持大规模、增长可控
线性散列O(1) 均摊不支持O(1)不支持与可扩展类似,无需目录加倍
B+ 树O(log N)支持O(log N)支持通用默认

因此散列索引主要用于等值查询专用场景(如 MySQL Memory 引擎、PostgreSQL 的 hash index、内存哈希连接),不能承担范围查询、ORDER BY。


14.6 多码访问​

14.6.1 使用多个单码索引​

若表 T 有两个独立索引 idx_a(a)、idx_b(b),对查询 WHERE a = 5 AND b = 7 可以:

  1. 只用 idx_a:读出所有 a=5a = 5 的 RID 集合,回表逐条过滤 b=7b = 7。
  2. 只用 idx_b:对称。
  3. 索引合并(index merge / bitmap AND):两侧各自得到 RID 集合,做交集(可用位图),再回表读少量记录。

优化器基于选择率估算选谁 —— 若某侧选择率极低,单侧索引就够;若都是中等选择率,索引合并往往最优。

14.6.2 多码索引​

针对高频出现的 (a, b) 组合,建复合索引 (a, b) 更好:一次 B+ 树定位到唯一区间,无需两侧合并、无需大量回表。

列顺序很关键:(a, b) 只对以 a 为前缀的查询有效;等值列放前面、范围列放后面。

14.6.3 覆盖索引​

覆盖索引(covering index):索引本身包含查询需要返回的全部列,查询不必回表。例如:

CREATE INDEX idx ON emp(dept_id, salary) INCLUDE(name);
SELECT name, salary FROM emp WHERE dept_id = 10 AND salary > 5000;

索引叶子里已经有 name、salary,一次索引扫描搞定。SQL Server / PostgreSQL 都提供 INCLUDE(存储列)语法,让"额外的列"只出现在叶子而不参与索引排序,兼顾大小与查询效率。


14.7 索引的创建​

用户通过 CREATE INDEX 显式建索引。DBMS 内部要做:

  1. 锁:默认长时间独占表锁(写会阻塞);CREATE INDEX CONCURRENTLY(PostgreSQL)用多阶段扫描 + 变更日志跟踪,在不阻塞写的前提下建索引。
  2. 批量加载:外部排序 + bottom-up B+ 树装载。
  3. 可见性:建成前的索引对查询不可用;系统目录里标记为 invalid,扫描器忽略。
  4. 统计信息:完成后收集直方图,让优化器知道有此索引。

自动索引:Autonomous DB、Oracle Auto Indexing 会跟踪工作负载、自动创建/删除索引;开源系统则依赖 DBA 或工具(如 pg_qualstats + hypopg)给出建议。


14.8 写优化索引结构​

B+ 树对读友好(树矮扇出高),但对大量随机写仍然会出现叶子分裂、随机 I/O 抖动。当写吞吐是主要瓶颈时,需要"写优化"结构。

14.8.1 LSM树​

**LSM 树(Log-Structured Merge Tree)**由 O'Neil 等在 1996 年提出,被 BigTable / LevelDB / RocksDB / Cassandra / HBase / ScyllaDB 广泛采用。核心思想:把随机写转化成顺序写。

结构:

写入流程:

  1. 追加一条 WAL 日志(顺序写)。
  2. 在内存 MemTable 里按码插入(跳表/红黑树,O(log⁡n)O(\log n))。
  3. MemTable 达阈值(如 64 MB)→ 冻结成 immutable、后台线程刷成 **SSTable(Sorted String Table)**顺序写到 Level 0。
  4. 后台 Compaction 将若干 SSTable 合并、按码归并排序,去除旧版本,输出到下一层。

读流程:

  1. 依次查 MemTable → immutable MemTable → Level 0 各 SSTable → L1 → …。
  2. 每个 SSTable 附布隆过滤器,能快速排除"码不在其中"。
  3. 找到最新版本即返回。

Compaction 策略:

  • Leveled:每层容量固定倍增(10 倍),L1 起每层内 SSTable 键范围不重叠。空间放大低(约 1.11),读放大低,写放大高(10 – 30 倍)。
  • Tiered / Size-Tiered:每层若干个大小近似的 SSTable,攒够就合并到下层。写放大低,空间/读放大高,Cassandra 默认。

LSM 与 B+ 树的对比:

维度B+ 树LSM 树
写路径定位 + 就地改,随机 I/O顺序追加,写放大由 compaction 决定
读路径一次树高的定位可能查多层 SSTable,用 Bloom filter 缓解
空间放大低(页填充 60% – 90%)Leveled 1.1 – 1.3;Tiered 2 – 3
范围扫描顺链表扫叶子多层归并
删除就地tombstone,等 compaction 清理
典型系统关系型数据库KV 存储、宽列存储

14.8.2 缓冲树​

缓冲树(Buffered Tree / Buffer Tree)是另一类写优化结构。B+ 树的每个内部节点附加一段写缓冲区:插入时把新元素只塞进根节点的缓冲区,缓冲区满了才向下推到子节点的缓冲区,逐层下推。

优点:单次插入只写一层节点,被摊销到批量下推时才真正修改叶子。适合外存排序、批量插入。缓冲 B-tree(Bε-tree)是 Ext4/TokuDB 系列的核心结构,写吞吐比 B+ 树高一个数量级,读性能与 B+ 树相近。


14.9 位图索引​

**位图索引(bitmap index)适合低基数(cardinality 低)**属性——即列的不同值很少的情况,如"性别"、"婚姻状态"、"订单状态"。

结构:对每个可能取值 vv 维护一个位向量 BvB_v,位数 = 表的记录数,第 ii 位为 1 表示第 ii 行的该列 = vv。

示例:一张 8 行的表,gender 列取值为 M 或 F:

行号:     0  1  2  3  4  5  6  7
gender: M F F M M F M F

B_M = 1 0 0 1 1 0 1 0
B_F = 0 1 1 0 0 1 0 1

多条件按位与:WHERE gender = 'M' AND marital = 'single':

B_M            = 1 0 0 1 1 0 1 0
B_single = 1 1 0 1 0 0 1 1
AND 结果 = 1 0 0 1 0 0 1 0
↑ ↑ ↑
行 0, 3, 6 命中

优点:

  • 存储超省:位图可以做 RLE / 字节对齐压缩,10 亿行、每行 1 bit 只需 125 MB。压缩后往往更小。
  • 按位与/或只是位运算,CPU 一次处理 64 – 256 bit,对大表极高效。
  • 特别适合OLAP 星型模型上的多维过滤(Oracle Bitmap Index、Vertica、Druid)。

缺点:

  • 高基数列(几万几十万个不同值)位图数量爆炸。
  • 频繁 DML(插入/删除)会引发大量位图更新,通常在数据仓库这种批量加载场景使用。

位图连接索引(bitmap join index):对连接结果预先建位图,进一步加速星型查询。


14.10 时空数据索引​

B+ 树只能对一维有序属性建索引。若查询是"半径 5 km 内的餐厅"或"过去 3 天里被订单表引用的行",就需要专门的多维索引。

14.10.1 空间数据索引​

R 树(R-Tree):类比 B+ 树的多维推广。每个节点存若干"最小包围矩形(MBR, Minimum Bounding Rectangle)",覆盖其子节点的空间范围;查询时若 MBR 与查询窗不相交则整棵子树被剪枝。

支持的查询:

  • 范围查询(window query):找与某矩形相交的所有对象。
  • 最近邻(k-NN):分支界限 + 优先队列。
  • 空间连接:两张空间表按相交/包含关系连接。

变体:R+ 树(不允许 MBR 重叠)、R* 树(更好的插入启发式)、四叉树(Quad-Tree,按象限均匀切分)、KD 树(内存中的多维二叉划分)、Geohash(把二维坐标编码成字符串再用 B+ 树)。

GiST(Generalized Search Tree,PostgreSQL):通用可扩展索引框架,用户定义"一致函数、并集函数、惩罚函数",可以把 R 树、trie、全文索引都实现为 GiST 索引。

14.10.2 时态数据索引​

时态数据的关键属性是区间 [start, end](有效期)。查询典型形式:"在时刻 t 有效的所有对象"、"与区间 [t1, t2] 有交集的对象"。

  • 有效时间(valid time):现实世界事实成立的时间段。
  • 事务时间(transaction time):数据库中该行有效的时间段(bitemporal 表同时维护两者)。

索引选择:

  • 单点查询("当下有效"):可用普通 B+ 树 + end IS NULL 条件。
  • 时间区间与区间相交查询:本质二维空间问题(把 [start, end] 视为 x-y 平面上的一点/一段),可用 R 树或 Interval Tree。
  • 仅追加型时序(如日志、指标):LSM 树 + 按时间分区,配合时间戳前缀的复合主键最常用(TimescaleDB、InfluxDB、Prometheus、ClickHouse 均如此)。

14.11 总结​

  • 索引以额外空间与写代价换取按搜索码定位记录的效率。分类维度包括顺序 vs 散列、聚簇 vs 辅助、稠密 vs 稀疏、唯一 vs 非唯一。
  • B+ 树是关系数据库最重要的索引结构:高扇出让树高 3 – 5 层就能覆盖十亿记录;叶子链表支持范围扫描;插入/删除通过分裂/合并保持平衡。工程上还发展出前缀压缩、批量加载、闩锁耦合、Bw-Tree 等扩展。
  • 散列索引支持 O(1) 等值查询但不支持范围。可扩展散列通过目录 + 局部深度支持动态扩容。
  • 多码访问可以走多个单码索引 + 位图 AND,也可以直接建复合索引;覆盖索引把查询列纳入索引避免回表。
  • 写吞吐主导的场景选择LSM 树:内存 MemTable + 顺序刷 SSTable + 分层 compaction,把随机写变顺序写;用 Bloom filter 缓解读放大。缓冲树在 B+ 树里加缓冲区,达到类似效果。
  • 位图索引在低基数列上极其省空间且支持超快按位运算,是数据仓库星型模型的利器。
  • 时空索引(R 树、四叉树、Geohash、Interval Tree、GiST)把 B+ 树的一维顺序推广到多维,支撑地理信息、时序、区间查询。
  • 现代 DBMS 常常"多索引家族并存":B+ 树承担主库、LSM 承担写热点、位图承担 OLAP 过滤、R 树承担空间——没有单一最优索引,选型取决于数据规模、访问模式与硬件特性。