索引全景 - 小鱼儿clouding的博客

一、哈希索引

1.1 基本结构与原理

哈希索引（Hash Index）是数据库中除 B+ 树外使用最广泛的索引结构。它的基本思想非常直观：数据通过哈希函数（Hash Function）映射到若干桶（Bucket）中，查询时只需计算哈希值即可定位到对应桶。

B+ 树索引需要一层一层从硬盘读数据，而哈希索引直接计算哈希函数就能定位，没有磁盘 I/O 操作——这是哈希效率高的根本原因。

基本结构：

维护一组固定或可变数量的桶
插入/查询数据时，先通过哈希函数 $h(key)$ 计算桶编号
到对应桶中查找或插入

例如，有 100 个桶时，一次哈希计算就让搜索空间缩小到约 1/100。

1.2 哈希索引的优缺点

优点：

等值查找效率极高，时间复杂度接近 $O(1)$
无需磁盘 I/O 遍历多层索引结构

缺点：

不适合区间查询（Range Query）。例如查找 [20, 25] 之间的值，需要对每一个可能的值单独做哈希计算，在实数域上几乎不可行
哈希函数的选择高度依赖数据分布，而数据库场景下数据分布通常事先未知

1.3 静态哈希

静态哈希（Static Hashing）是最基础的哈希索引实现。

特点：

桶的数量固定不变（如 100 个桶）
哈希函数也是固定的

核心问题——溢出链（Overflow Chain）：

当数据集中落入某些桶时，桶容量被填满
溢出数据被放到链表结构的溢出页中
如果溢出链过长，查找退化为链表遍历，复杂度变为 $O(n)$

后面的几种哈希变形，本质上都是在权衡一个问题——如何让溢出链尽可能短，以保证索引的整体效率。

应对策略：

定期重构：根据当前数据规模重新设定哈希函数和桶数量
增加桶数量以减少每个桶的负载

1.4 可扩充哈希

可扩充哈希（Extensible Hashing）通过引入一个目录（Directory）结构来避免溢出链。

结构：

一个目录（Dictionary）存放桶指针，目录本身较小，可放在内存中
哈希值先映射到目录条目，再通过指针找到对应桶
当某个桶溢出时，只分裂该桶，并将目录大小翻倍

分裂过程（例如从模 4 改为模 8）：

原来 4 个目录条目指向 4 个桶
目录扩展为 8 个条目
只有溢出的那个桶被真正分裂成两个（如余 0 和余 4）
其他未溢出的桶，新增的目录条目和原来的条目指向同一个桶（多对一）

可扩充哈希的好处是没有溢出页，通过目录一步就能找到目标桶。但缺点是每当分裂时目录大小翻倍，如果数据分布比较极端（如全是 distinct 值），目录会增长得非常快，占用大量内存。

1.5 线性哈希

线性哈希（Linear Hashing）是静态哈希和可扩充哈希的折中方案。

核心思想：

保留溢出链机制，但通过循环式分裂让溢出链保持较短
没有目录（Directory），避免了目录膨胀的问题

工作机制：

维护一个 next 指针，初始指向第一个桶
每当任意桶出现溢出时，触发 next 指针指向的桶进行分裂（一分为二）
next 指针循环后移
溢出链产生后，过一段时间（当 next 循环到该桶时）就会被分裂消除

三种哈希索引对比：

特性	静态哈希	可扩充哈希	线性哈希
溢出链	有，可能很长	无	有，但较短
目录结构	无	有（可能膨胀）	无
桶管理	固定	按需分裂	循环分裂
性能	溢出链长时差	好，但目录可能大	介于两者之间
适用场景	数据量可预估	数据增长频繁	通用折中

二、多键索引与多维空间映射问题

2.1 问题引入

在实际查询中，WHERE 子句往往涉及多个属性（如姓名和工资），因此索引也需要建在多个属性上。

B+ 树天然支持多属性索引：先按第一属性排序，再按第二属性排序。这意味着需要将二维（或多维）空间中的点映射到一维线性序列上。

2.2 B+ 树复合索引的局限

B+ 树的多属性索引做法是按属性权重逐级排序——先按属性 A 排序，再按属性 B 排序。

局限性（以年龄和工资为例）：

年龄 20 岁和 21 岁的两个人，工资可能完全相同
但因为年龄不同，他们在 B+ 树的线性序列中可能相隔很远
对于相似性查询（如”找到年龄和工资都与目标相近的人”），这种组织方式效果很差

理想情况下，高维空间中相近的点，在索引的一维序列中也应该是相邻的——这样相似性查询才能高效。这就是多维索引需要解决的核心问题。

2.3 网格文件

网格文件（Grid File）将二维（或多维）空间划分成若干网格（Grid Cell），每个网格对应一个存储单元。

优点：

同一网格内的数据自然比较相似
相似性查询只需考察目标网格及其相邻网格
如果目标点离网格边界较近，则还需检查相邻网格

网格划分的挑战：

划分方式与数据到来的顺序有关
初始划分可能不够理想
数据密集区域应划分得更细，稀疏区域可以更粗
需要根据数据分布定期重构网格

三、R 树

3.1 基本结构

R 树（R-Tree）是目前低维空间（约 10 维以下）中使用最普遍的多维索引结构。

核心概念：R 树是一个平衡树，每个节点对应空间中的一个最小边界矩形（Minimum Bounding Rectangle, MBR）。每个节点存放的数据项是其子树中所有 MBR 的包围框。

叶节点存放实际数据对象及其 MBR
内部节点存放子节点的 MBR 及指针
结构上类似 B+ 树——自底向上构建，节点满了就分裂，保证平衡

3.2 查询过程

R 树的查询不同于 B+ 树的一条路径确定结果：

从根节点开始，检查查询窗口是否与各子节点的 MBR 相交
如果相交，递归进入该子节点继续查找
由于 MBR 之间可能有重叠，可能需要沿多条路径向下查找
如果查询窗口不在任何子节点的 MBR 中，则该路径结束

B+ 树是从根到叶的一条路径，而 R 树因为矩形框之间有重叠，很可能需要同时走多个分支。如果框划分得合理，同时走的路径数也不会太多，整体仍保持对数时间。

插入和删除也都是对数时间——因为需要修改的节点数等于树的高度。

3.3 插入操作

插入过程与 B+ 树类似：

递归找到合适的叶节点
如果数据点落在某个子节点的 MBR 内，继续向下
如果数据点不在任何子节点的 MBR 中，需选择一个子节点——原则是选择MBR 扩展面积最小的那个（或在面积相同的情况下选原面积最小的）
插入后更新沿途所有 MBR
如果叶节点溢出（超过容量），进行分裂

3.4 分裂操作与优化

分裂时的核心目标：使分裂后两个新节点的 MBR 重叠尽可能小。

经典方法：

在所有数据点中找到两个相距最远的”种子”点
将其余点按照距离分配到较近的种子所在的组
形成两个新的 MBR

如何在分裂时让数据尽可能分散，使 MBR 面积更小、重叠更少，是 R 树设计中的核心优化问题。

四、KD 树

4.1 基本思想

KD 树（K-Dimensional Tree）的核心做法是：在每一层按某一个维度将空间一刀切开，交替使用不同维度。

第一刀沿 X 轴切，第二刀沿 Y 轴切，第三刀再沿 X 轴……（二维情况）
每一刀都选该维度上数据的中位数作为分割点
从根节点开始自顶向下构建

4.2 分割轴的选择

KD 树构造时不是简单轮流切分，而是需要挑选合适的分割轴：

计算每个维度上数据的方差（表示数据的分散程度）
选方差最大的维度作为分割轴
再用该维度上的中位数进行切分

直觉理解：如果数据在 X 轴上分布很广、在 Y 轴上很窄，那么应该在 X 轴上切分，而不是在 Y 轴上。这样才能把密集的数据团完整地保持在一个子树分支中，避免相似的点被分割到树的不同分支上。

4.3 特性与局限

KD 树不是平衡树——数据插入不均匀时，不同分支的深度可能不同
适合静态数据或批量构建的场景
在低维空间中查找效率较高

是否可以构造一个平衡的 KD 树，或者能否对其平衡性进行优化，是一个值得探讨的方向。

五、空间填充曲线与相似性保持

5.1 高维到一维的映射问题

核心问题再述：高维空间中相近的点，映射到一维序列后，也应该位置相近——即保持局部性（Locality Preservation）。

B+ 树的逐维排序方法中，两个在 Y 轴上相近但 X 轴上稍有不同的点，在一维序列中可能相隔很远。

5.2 Z 曲线

Z 曲线（Z-Order Curve / Morton Curve）通过递归画”Z”字将二维空间中的所有点串成一条折线。

构造方式：

最小尺度：2x2 的四个格子画一个 Z
更大尺度：将 2x2 个 Z 用一个大 Z 连接
递归进行

Z 曲线不能完美保证所有相邻点的距离都近，但它比简单的逐维排序要好得多——总体上空间相近的点在 Z 曲线上的位置也比较接近。这样就实现了将二维空间点映射到一维空间的目标。

其他空间填充曲线还包括希尔伯特曲线（Hilbert Curve）等。

5.3 其他保持局部性的方法

局部敏感哈希（Locality-Sensitive Hashing, LSH）：设计哈希函数，使相近的点得到相近的哈希值，可用于聚类和索引
聚类方法（如 K-Means）：先分析数据分布，将相近数据聚为一类，在类之上组织索引结构

六、专用数据的索引方法

6.1 图数据索引

图数据上直接做子图匹配（Subgraph Isomorphism）是 NP 难问题，因此需要建立索引来加速。

基于频繁子图模式的索引：

在所有图中找出频繁出现的子结构
这些子结构具有较好的区分度
记录每个子结构在哪些图中出现
查询时通过子结构匹配快速定位候选图

基于路径的索引：

从图中提取路径（如一条含 12 个碳原子的链）
用一维路径序列来近似表示图结构
将图匹配问题转化为序列匹配问题，大幅降低计算复杂度

图神经网络方法：

将图中每个节点映射为向量（Embedding）
在向量空间中进行计算，速度快得多
准确性可能有所损失，但可通过各种方法优化

6.2 时序数据索引

对时间序列（Time Series）数据，重点关注其整体形状和局部形状的相似性。

主要的表示/压缩方法：

方法	原理
DFT（离散傅里叶变换）	用正弦波组合拟合时间序列，转换为频域表示
DWT（离散小波变换）	用不同频率的方波（小波基函数）拟合序列
PAA（分段聚合近似）	将序列分割为区间，用各区间均值表示
SAX（符号聚合近似）	将每段转为一个符号，重点关注形状特性
分段线性表示	将序列转换为线段序列，在线段上进行比对

这些方法的共同思路是——将数据量大、结构复杂的数据转换成结构简单的描述方式，大幅压缩数据规模后再建索引，从而提高查询效率。

七、位图索引

7.1 基本原理

位图索引（Bitmap Index）用位数组（Bit Array）来表示属性的取值。

对于一张表：

每个属性（列）的每个不同取值，生成一个位图
位图中第 $i$ 位为 1 表示第 $i$ 个元组在该属性上取该值
例如：性别有男/女两个取值，则男的位置图和女的位置图各一个

例：5 个元组的性别列

元组	1	2	3	4	5
男	1	0	1	0	1
女	0	1	0	1	0

7.2 查询执行

查询”性别=男 AND 系别=计算机”时：

取出”男”的位置图字符串和”计算机系”的位置图字符串
做按位与（Bitwise AND）操作
结果中为 1 的位置就是符合条件的元组

位运算的速度是计算机中最快的操作。位图索引将复杂的多条件查询转化为简单的位运算，效率极高。

7.3 适用场景与局限

适用场景：

低基数列（Cardinality 低，即取值种类少）：如性别（2 种）、系别、职称等
列存储（Columnar Storage）数据库
云数据库和数据仓库中的 OLAP 查询

局限：

高基数列（如年龄、工资）取值太多，每个值一个位图会占据大量存储空间，且位图稀疏

7.4 与云数据库的契合

随着云端列存储的发展，位图索引使用大幅增加。原因：

列存储天然按列组织数据，每一列可以直接用位图表示
存储空间的优势：原本一个汉字占 16 bits，位图只需 2 bits（男/女两列）
数据量下降几个数量级

八、学习型索引

8.1 基本思想

学习型索引（Learned Index）用机器学习模型替换传统索引中的节点。

传统索引中：

B+ 树每个节点存放键值和指针，查找时需要在节点内遍历和比较
R 树每个节点用 MBR 描述空间范围

学习型索引：

每个节点换成一个小型模型（如神经网络）
模型直接根据输入值预测该值应该在哪个分支/位置
模型较小，可以常驻内存

8.2 优势

减少 I/O：模型在内存中，无需每次从磁盘读节点
压缩树结构：一个模型的表达能力较强，可能替代 2-3 层传统索引节点，从而将 5 层树压缩到 2-3 层
索引整体变小：压缩后的结构更紧凑

8.3 当前挑战

动态更新：数据频繁增删时，模型的更新速度跟不上（不像 B+ 树那样可以快速分裂/合并）
模型管理：多个模型如何共享和协调
训练代价：每个节点是否需要反复训练，代价可能很大

学习型索引在复杂场景下已经展现出很好的效果，但完全在商用数据库中落地还有一些问题需要解决。这属于近年来刚兴起的新技术方向。

九、LSM 树

9.1 起源与动机

LSM 树（Log-Structured Merge Tree）最早由阿里在 OceanBase 数据库中提出。

原始动机——冷热数据分离：

互联网场景（如双十一）中，大量用户同时涌入
当前活跃用户（热数据）的数据应放在内存中快速访问
不活跃用户（冷数据）的数据可以放在磁盘上

但后来发现 LSM 架构还有一个重要的优势——与磁盘（尤其是 SSD）的特性高度契合。

LSM 已经不简简单单是一个索引结构，它变成了数据库底层存储的一个架构。目前几乎所有新的数据库——包括很多国产关系型数据库——底层存储都是基于 LSM 架构来构建的。

9.2 核心结构

LSM 树分为内存和磁盘两部分：

内存部分：

一棵平衡二叉搜索树（如红黑树、AVL 树）
存放最新访问/修改的热数据
所有插入、更新、删除首先在内存中进行

磁盘部分：

分为多个层级（Level 1, Level 2, Level 3, …）
每层数据都是已排序的数组
每层的容量是上一层的约 2 倍（等比递增）

9.3 基本操作

插入：

新数据直接插入内存中的二叉搜索树
内存树达到一定规模后，生成排序序列写入 Level 1
Level 1 满了后与 Level 2 合并，以此类推

删除：

不直接从磁盘删除数据
在内存中插入一个带墓碑标记（Tombstone）的同键值条目
在后续合并过程中，墓碑标记与磁盘中的旧数据相遇时，旧数据被丢弃

更新：

同样先修改内存中的对应条目
在合并时用新值覆盖旧值

9.4 合并过程与磁盘友好性

合并（Merge）是 LSM 最核心的操作：

内存中二叉搜索树可以中序遍历生成排序序列
Level 1 已有排序数据
两个排序序列做归并（Merge），生成新的排序序列
并入 Level 2，再与 Level 2 数据合并……
所有读写都是顺序的（连续读入、连续写出）

不管是机械硬盘还是 SSD/Flash，顺序读写效率都远高于随机读写。Flash 甚至更极端——它所有数据的修改都变成增量式管理。LSM 的分层合并模式完美利用了磁盘的这一特性。

9.5 查询过程

先在内存二叉搜索树中查找
若未找到，逐层在磁盘 Level 中查找（二分查找，因为每层都是排好序的）
若仍未找到，去原始数据文件中查找

由于最新数据总是在内存或较近的层中，查询效率很高。

9.6 应用现状

最初用于云数据库和 NoSQL 数据库
现在关系型数据库也开始采用 LSM 架构
国产数据库大量基于 LSM 构建底层存储

十、行存储与列存储

10.1 行存储

行存储（Row-Oriented Storage）是传统数据库的存储方式：

一条元组的所有属性连续存放在一起
插入/更新操作效率高——只需操作一个位置
适合 OLTP（联机事务处理）场景

缺点：查询只用到少数几列时，整行数据都要被读出来，产生大量不必要的 I/O。

10.2 列存储

列存储（Column-Oriented Storage）最早由 Sybase 在 Sybase IQ 版本中提出：

表的每一列单独存储
查询只涉及某几列时，只需读取这些列的数据
适合 OLAP（联机分析处理）场景

优点：

查询效率高（只读需要的列）
与位图索引配合极好——每一列可以直接用位图表示和压缩
数据压缩率高（同一列的数据类型相同，取值往往重复）

缺点：

插入/更新代价高——需要修改多个列的存储位置
元组重组（Tuple Reconstruction）需要额外开销

10.3 HTAP 与行列混合

行存储与列存储的对比如下：

特性	行存储	列存储
数据组织	元组连续存放	按列分别存放
插入/更新	快	慢
查询少数列	慢（读整行）	快（只读所需列）
压缩效率	一般	高（同列数据类型一致）
适用场景	OLTP（事务型）	OLAP（分析型）

分布式架构带来的统一：

云数据库每个数据块通常有 3 个备份
可以一份用行存（服务事务型查询），一份用列存（服务分析型查询）
由此实现了 HTAP（Hybrid Transactional/Analytical Processing）——兼顾事务型和分析型

列存储在 Sybase 提出来以后很长时间没有被广泛采用，因为当时的存储只存一份——大家还是更看重事务型应用。分布式多副本架构出现后，行存和列存终于可以统一起来了。

十一、查询处理概述

11.1 查询处理三阶段

一条 SQL 语句从输入到执行完成，大致分为三个阶段：

第一步：查询解析（Query Parsing）

词法分析（Lexical Analysis）：将 SQL 语句拆分为 Token
语法分析（Syntax Analysis）：构建语法树
语义分析（Semantic Analysis）：检查表是否存在、列是否在表中、用户是否有访问权限等
最终生成一棵查询树（Query Tree），对应关系代数表达式

第二步：查询优化（Query Optimization）

输入：查询树（可能是性能最差的形式——如先笛卡尔积再做选择）
生成逻辑计划树（Logical Plan Tree）：对关系代数表达式做等价变换（如谓词下推）
生成物理计划树（Physical Plan Tree）：为每个操作指定具体算法（如用索引嵌套循环连接还是哈希连接）
核心环节——代价估计（Cost Estimation）：估算每个候选物理计划的 I/O 代价
选择代价最小的物理计划

代价估计是查询优化中最重要的环节。

第三步：查询执行（Query Execution）

根据物理计划树执行查询
涉及流式处理（Pipeline）还是物化（Materialization）的选择
现代数据库还有编译执行（Compiled Execution）的方式：将查询计划编译成可执行代码，在编译阶段做更多优化，并结合并行技术提高效率

11.2 SQL 语句到关系代数

任何 SQL 语句都可以转化为最基础的关系代数表达式——所有表做笛卡尔积，再做选择，最后做投影。但这显然是性能最差的形式。查询优化的目标就是将这种最简单但最低效的计划转化为高效计划。

十二、外部排序

12.1 为什么需要外部排序

数据库中的数据量通常超出内存容量，而传统排序算法（如快速排序）依赖内存中的随机访问和交换。

在磁盘上做随机交换的巨大代价：

两个要交换的数据可能在不同磁盘块中
需要把两块分别读入内存、修改、再写回——I/O 开销极大

因此传统内排序算法不适用于外排序场景。

12.2 外排序的基本策略

外排序一律采用归并排序（Merge Sort）的思想——因为它天然只涉及顺序读写。

核心：利用 3 个与磁盘块大小相同的内存缓冲区：

2 个输入缓冲区（Input Buffers）
1 个输出缓冲区（Output Buffer）

12.3 二路归并排序

第一阶段——生成初始 Run：

将文件按磁盘块逐一读入内存
在内存中对每块数据做内排序（快速排序等皆可）
排好序后写回磁盘——每个排好序的块称为一个 Run（每个 Run 的长度为一个 Page）

第二阶段——归并：

从两个输入 Run 中各读一块到输入缓冲区
对两个已排序序列做归并
结果写入输出缓冲区
输出缓冲区满后写回磁盘
当一个输入缓冲区耗尽时，从对应的 Run 中再读一块
如此反复，直到两个 Run 全部处理完毕，生成一个长度翻倍的新 Run

第三阶段——递归归并：

将第一阶段生成的每个 Run（长度为 1 页）两两归并，得到长度为 2 页的 Run
再将长度为 2 页的 Run 两两归并，得到长度为 4 页的 Run
如此反复，直到只剩下一个 Run——最终排序结果

12.4 代价分析

设文件有 $N$ 页，则：

共需 $\log_2 N$ 趟归并
每趟每个数据页都要读一次、写一次，即 $2N$ 次 I/O
总 I/O 代价：$2N \cdot \log_2 N$

以上是最基础的二路归并排序，在此基础上可以扩展到多路归并、利用更多内存缓冲区来提高效率等优化方向。