索引与哈希：从一次磁盘访问到复杂查询

云帆零售平台保存商品、门店、库存和订单。订单表已有数亿行，客服按订单号查一笔订单，运营按“华东、已支付、下单时间”筛选一批订单，仓储系统则持续写入库存流水。它们访问的是同一批数据，却需要不同的定位方式。

如果每次查询都从第一行读到最后一行，代价会随文件一起增长。索引在数据文件之外保存“搜索键到记录位置”的导航信息，让执行器先缩小候选范围，再读取真正需要的数据页。哈希索引可以直接把等值键映射到桶；有序索引保留键的次序，适合范围、排序和前缀访问。索引并不让查询凭空变快，它把全表扫描替换成更少的索引页读取、数据页读取和比较。

图：等值、范围、多条件和高写入负载会把执行器引向不同索引结构。

---

先把“索引为什么有效”说清楚

索引项、搜索键与记录定位

一条典型索引项由搜索键值和记录定位信息组成。定位信息可能是“数据页号 + 页内槽号”，也可能是聚簇表的主键值。前者可直接找到记录，后者要再经过主索引完成一次定位。

搜索键是用来查找记录的一个属性或一组属性，它不等同于主键。主键承担唯一性和实体标识，搜索键只描述“我们按什么找”。订单表可以同时拥有订单号、用户编号、创建时间以及（区域，状态，创建时间）等多个搜索键，其中很多值都不唯一。

设文件有 $N$ 条记录，每页容纳 $r$ 条记录。一次全表扫描大约读取 $\lceil N/r\rceil$ 个数据页。若索引树高为 $h$，等值查询通常先读取约 $h$ 个树节点，再读取命中的数据页。真正有意义的比较单位不是抽象的 $O(\log N)$，而是“少读了多少页、这些页是顺序还是随机、能否命中缓冲池”。

评价索引不能只看查找速度

一个索引至少要从五个维度评估：

索引是以额外空间和写入维护换取读取效率。读多写少的订单查询库可以多建几个有针对性的索引；持续写入的流水表若索引过多，每次插入就要修改多棵树，吞吐会明显下降。

1

订单表在（区域，状态，创建时间）上建立索引。这里的“搜索键”最准确的含义是什么？

A它必须是表的主键B它是索引用来定位记录的属性组合C它必须保证每个值唯一D它只用于检查外键约束

---

有序索引怎样映射到物理文件

聚簇与非聚簇

若数据文件的物理顺序与某个索引的搜索键顺序一致，这个索引是聚簇索引。订单若按创建时间成片存放，那么“查询某一天订单”找到起点后，可以顺着相邻页读下去。一个文件通常只能维持一种主要物理顺序，因此很难同时按创建时间和用户编号都聚簇。

非聚簇索引的键顺序与数据页顺序不同。按用户编号扫描索引时，相邻索引项可能指向相距很远的数据页。它很适合返回少量记录；结果一多，回表随机读会成为主要成本。二级索引通常就是非聚簇索引。

图：聚簇范围扫描沿相邻数据页前进；非聚簇扫描可能反复跳到分散的数据页。

稠密、稀疏与重复值

稠密索引为每个搜索键值保存索引项；在非聚簇场景中，还必须能找到该键值对应的每条记录。重复值可以用一组记录标识符表示，也可以把“原搜索键 + 主键”组合成唯一键。

稀疏索引只保存部分键值，常见做法是每个数据页保存一条“页内最小键 → 该页”的入口。查找键 $v$ 时，先取不大于 $v$ 的最大索引键，再从其数据页开始顺序扫描。这个方法要求数据文件本身按同一搜索键有序，否则未被采样的键可能散落在任何位置。

稠密索引定位更直接，但占空间且维护项更多；稀疏索引更小，代价是页内或相邻页的短扫描。以页为粒度建立稀疏入口通常是好折中，因为一次页读完成后，内存中扫描该页的代价远低于再发起一次存储访问。

多级索引与更新传播

如果一级索引本身也有很多页，可以把它看成一个有序文件，再为它建立稀疏外层索引。这个过程可以继续，直到顶层足够小。查找时每层只读取一个相关页，多次随机二分读变成从根到叶的一条短路径。

插入、删除或修改搜索键时，所有相关索引都要同步更新。修改搜索键可以理解为“删除旧索引项，再插入新索引项”。稠密索引要处理指针集合；稀疏索引通常只在页首键改变、页分裂或页删除时调整入口。多级索引的改变会逐层向上传播，这正是平衡多路树要自动解决的问题。

2

关于稀疏索引，下列哪些说法正确？

A通常要求数据文件按同一搜索键有序B必须为每条记录保存一个索引项C可按每个数据页保存一个入口D适合直接用作任意非聚簇二级索引

检查

---

B+ 树为什么又宽又矮

节点结构与不变量

B+ 树把多级索引组织成一棵平衡的多路树。所有根到叶的路径长度相同，因此一次查找不会因为键分布不同而退化成很长的链。内部节点只保存分隔键和子节点指针，真正的索引项集中在叶节点；叶节点再按搜索键顺序串成链表。

设一棵树的阶为 $n$。一个内部节点最多有 $n$ 个孩子和 $n-1$ 个分隔键；除根以外，内部节点至少有 $\lceil n/2\rceil$ 个孩子。叶节点最多保存 $n-1$ 个键，通常至少保存 $\lceil (n-1)\mathrm{/}2\rceil$ 个键。根节点可以更少：只要树不止一个节点，根至少有两个孩子。

内部节点中的分隔键用于划定子树范围。例如节点保存 $K_1,K_2,\ldots,K_{m-1}$，那么最左指针覆盖小于 $K_1$ 的键，中间指针覆盖 ，最右指针覆盖不小于 的键。

图：内部节点负责导航，全部数据入口位于同一深度的叶层，叶链支持连续范围扫描。

查找、范围扫描与高度

等值查找从根开始。在每个内部节点中找到能覆盖目标值的区间，沿相应指针下降，直到叶节点。若叶中有目标键，索引返回记录位置；若没有，就能确定该键不存在。

范围查询 $[l,u]$ 先按 $l$ 下降到第一个可能命中的叶节点，再沿叶链向右读取，遇到大于 $u$ 的键停止。相比“对范围内每个键都从根查一次”，叶链只支付一次树下降成本。

节点一般做得接近存储页大小。若页大小为 $B$，平均键长为 $K$，指针长为 $P$，内部节点扇出可粗略估为：

$$f \approx \left\lfloor \frac{B+K}{K+P} \right\rfloor$$

扇出越大，树越矮。若最低扇出为 $\lceil n/2\rceil$，索引 $N$ 个键时的路径长度可用下面的上界理解：

$$h \le \left\lceil \log_{\lceil n/2\rceil} N \right\rceil$$

以扇出约 100 为例，一百万个键只需很少几层。根和上层节点访问频繁，常驻缓冲池后，一次查询真正触发的存储读取往往主要发生在叶层和数据页。

非唯一键的工程处理

如果状态值“已支付”重复数百万次，直接把巨大指针桶挂在一个键后面，会出现变长桶、额外 I/O 和删除定位困难。更常见的办法是加入唯一化属性，例如把（状态，订单号）作为实际索引键。查询“所有已支付订单”可转换为从（已支付，负无穷）到（已支付，正无穷）的范围扫描，删除一笔订单时也能用完整唯一键直接定位。

3

B+ 树适合范围查询的直接原因是什么？

A所有内部节点都保存完整记录B叶节点按键有序并通过指针相连C哈希函数保持键值顺序D每棵树只有两层

---

B+ 树插入与删除怎样保持平衡

插入、叶分裂与向上递归

插入先找到目标叶节点。若叶仍有空间，把“键—记录位置”放入有序位置即可。若叶已满，就把原有键和新键合并排序，分成左右两个叶节点，修复叶链，并把新右叶的最小键作为分隔键插入父节点。

父节点也可能已满。内部节点分裂时，子指针分成左右两组，中间的分隔键上移到父节点，不保留在任一新内部节点中。分裂可能一路传播到根；若根也分裂，就创建新根，树高增加 1。所有原叶仍处于同一深度。

删除、借位、合并与降高

删除先从叶中移除目标项。若节点仍达到最低占用率，操作结束；若低于下限，优先尝试向相邻兄弟借一项，也就是重分配。借位后，父节点中的分隔键必须改成新的边界值。

如果相邻兄弟与当前节点的全部内容能装进一个节点，就合并两者，并从父节点删除多余的指针和分隔键。父节点因此也可能下溢，借位或合并会递归向上。若根最终只剩一个孩子，就删除旧根，让唯一孩子成为新根，树高减 1。

为什么实际代价通常低于最坏情况

插入和删除的最坏 I/O 次数与树高同阶，但分裂或合并不是每次都会发生。高层节点数量远少于叶节点，通常更容易留在内存；随机插入下，节点平均占用率也常高于最低的二分之一。工程上可让分裂同时考虑邻居，先做重分配，必要时把两个满节点和一个新节点的内容均匀分到三个节点，从而提高空间利用率，但代价是一次更新涉及更多页。

当 B+ 树叶节点直接保存数据记录时，它同时承担文件组织。叶分裂会移动记录，若二级索引保存物理地址，所有受影响的二级索引都要修改。常用缓解办法是让二级索引保存主键值；记录搬家不再改二级索引，但二级访问需要“二级索引 → 主索引 → 记录”两步。

4

B+ 树叶节点分裂后，应把新右叶的最小键写入父节点，必要时分裂可继续向根传播。

正确错误

---

B+ 树的扩展与批量构建

字符串键、前缀压缩与节点大小

字符串键长度不固定，节点是否“满”应按已用字节而不是只按条目数判断。长字符串还会降低扇出，使树变高。内部节点并不一定保存完整字符串，只要某个前缀足以区分左右子树，就可以只保存这个最短分隔前缀；叶节点仍保留可完成精确比较的完整键。

磁盘环境常让节点接近一个块，固态盘环境则更关注闪存页写入。节点过大，一次小修改可能重写多个物理页；节点过小，树会增高。内存索引还要考虑缓存行：把大节点内部再组织成贴近缓存行的小结构，可以减少 CPU 缓存未命中。

批量加载为什么先排序

逐条向一棵大树随机插入时，每条记录都可能触碰不同叶页。若叶层远大于缓冲池，就会产生大量随机读写。批量加载先生成“搜索键—记录位置”临时项，按搜索键排序，再按顺序填充叶页。每个叶页连续写一次，后续层再用下层节点最小键自底向上构建。

图：排序让同一叶页的索引项连续出现，自底向上构建减少随机页访问。

批量加载的步骤可以概括为：

顺序插入普通 B+ 树往往使每次分裂后的左、右节点接近半满；专门的自底向上构建可以按预定填充率装页。若一次导入的数据量非常大，暂时移除不必要的二级索引、导入后重建，可能比维护每个索引更便宜，但唯一性与业务可用性约束必须另行保证。

B 树与 B+ 树的取舍

B 树允许记录指针出现在内部节点，某些等值查询可能提前结束，也少重复一些分隔键。但内部节点需要保存额外记录指针，扇出会降低；范围扫描也不如统一叶层直观；删除内部键更复杂。数据库索引通常更偏好“内部只导航、叶层放完整入口”的 B+ 树布局。

5

为一张远大于内存的表首次建立 B+ 树索引，通常哪种方法最省随机 I/O？

A按表中原顺序逐条随机插入B先排序索引项，再自底向上构建C每插入一项就重建整棵树D只构建根节点

---

哈希索引从静态桶走向动态增长

桶、冲突与溢出链

哈希函数 $h:K\rightarrow B$ 把搜索键集合映射到桶地址集合。内存哈希索引的桶可以是链表头；磁盘哈希索引的桶通常对应一个页或一组页。查找键 $k$ 时计算 $h(k)$，只检查目标桶内的项；插入和删除也从同一映射开始。

不同键得到相同哈希值就是冲突。数据库常用闭地址法，把冲突项放在桶内或溢出链上。桶满时分配溢出页，继续用指针串接。开放地址法通过探测别的位置解决冲突，删除处理更复杂，不适合许多持久化索引场景。

哈希函数应让实际键分布尽量均匀，不能只在理想输入上均匀。即使函数设计良好，重复键或业务热点仍会造成倾斜。为降低溢出概率，可以预留空闲容量。若记录数为 $n_r$，每桶容量为 $f_r$，预留系数为 $d$，初始桶数可粗略取：

$$b \approx \frac{n_r}{f_r}(1+d)$$

$d=0.2$ 表示平均约保留两成余量。它只能降低溢出概率，不能解决数据持续增长。

图：静态桶靠溢出链吸收增长；动态哈希通过局部分裂逐步扩大地址空间。

静态哈希的边界

静态哈希在创建时固定桶数。数据规模远超预估后，一个桶可能挂上多个溢出页，等值查询从“一次定位”退化成遍历长链。整体重建能扩桶，却要扫描和重分布全部项，可能造成长时间维护。

哈希索引保留的是分布，不保留搜索键顺序。因此它适合等值条件，不适合 $l\le k\le u$、按键排序或前缀范围。所谓“平均 $O(1)$”还隐含桶负载可控；发生严重倾斜时，实际访问仍取决于桶和溢出链长度。

可扩展哈希与线性哈希

可扩展哈希维护一个目录。全局深度 $g$ 表示用哈希值的 $g$ 位选择目录项，每个桶还有局部深度 $l$，表示该桶实际由多少位区分。目录项可以共享同一个桶。

桶溢出时：

• 若 $l<g$，只分裂该桶，局部深度加 1，并重定向相关目录项。
• 若 $l=g$，先把目录加倍、全局深度加 1，再分裂溢出桶。
• 删除后若一对伙伴桶足够小，可合并；若目录上下两半指向完全相同的桶集合，目录可以缩半。

线性哈希不使用指数大小的目录，而是按固定顺序逐桶分裂。它维护当前轮次和分裂指针；当负载达到阈值或出现溢出时，分裂指针指向的桶，把其中记录按更大模数重分布，然后指针前移。完成一轮后，桶数近似翻倍并进入下一轮。它扩张更平滑，但一次溢出不一定立刻分裂发生溢出的那个桶。

6

关于哈希索引，下列哪些说法正确？

A适合等值查询B天然支持有序范围扫描C静态哈希可能形成长溢出链D可扩展哈希可通过目录和局部深度增量扩桶

检查

---

多键访问、组合索引与覆盖索引

多个单列索引的交集

查询“华东区域且状态为已支付”时，执行器可以走区域索引取一组记录标识符，走状态索引再取一组，然后求交集。只有一个条件很有选择性时，也可以只走该索引，回表后检查另一个条件。

多索引求交不总是好选择。若两个条件各自都命中数百万行，交集却只有几百行，生成、排序或合并两大组标识符的代价可能很高。位图能把集合交集变成机器字上的按位与，但是否值得仍取决于候选规模和记录布局。

组合索引与最左连续前缀

组合搜索键按字典序排列。对索引（区域，状态，创建时间），先比较区域，相同才比较状态，再相同才比较创建时间。因此它高效支持：

• 区域等值；
• 区域等值 + 状态等值；
• 区域等值 + 状态等值 + 创建时间范围；
• 完整组合键的等值定位。

只给状态而没有区域时，相同状态值分散在每个区域段中，通常不能形成一段连续扫描。若区域先使用范围条件，那么后续状态也会分散在许多区域值下，很难继续缩小为单一连续键区间。这就是“等值前缀之后接一个范围”的直观边界。

覆盖索引减少回表

覆盖索引在搜索键之外携带查询需要的附加列。例如查询只返回订单号和金额，可以在（用户编号，创建时间）索引叶项中附带金额；执行器从索引就能得到结果，无需逐条访问数据页。附加列不参与内部节点的键比较，通常比把所有列都塞进组合搜索键更节省内部节点空间。

代价是叶项更宽、缓存容纳的项更少、更新附加列也要改索引。覆盖应服务于高频且稳定的查询投影，不能把二级索引变成一份完整表副本。

7

索引为（区域，状态，创建时间）。哪类条件最容易形成一段连续而狭窄的索引范围？

A状态等值且创建时间范围，不给区域B区域等值、状态等值、创建时间范围C区域范围且状态范围D只给创建时间范围

---

创建索引与让优化器做选择

建索引只是声明可选路径

常见 SQL 形式如下：

CREATE INDEX idx_order_region_status_time ON orders(region, status, created_at);

CREATE UNIQUE INDEX idx_order_no ON orders(order_no);

DROP INDEX idx_order_region_status_time;

唯一索引除了访问路径，还用于检查候选键不能重复。很多系统会自动为主键建立索引；外键索引通常需要显式考虑，它能加速“从父记录找子记录”的连接，也能降低删除或更新父键时检查引用的成本。

创建索引后，查询不是被强制走索引。优化器根据统计信息估算候选行数、树下降成本、索引页数量、回表随机读和顺序扫描成本，然后选择计划。若统计信息过旧、列值相关性被错误地当作独立，估算就可能偏离实际。

用访问代价而不是“出现于 WHERE”来设计

我们可以把二级索引计划粗略拆成：

$$C_{\text{index}} = C_{\text{descend}} + C_{\text{leaf}} + C_{\text{fetch}}$$

$C_{\text{descend}}$ 是下降到叶层，$C_{\text{leaf}}$ 是扫描命中叶项，$C_{\text{fetch}}$ 是回表。返回比例上升时，最后一项通常增长最快。全表扫描成本则接近数据页总数，但顺序读和预取使单页成本更低。

选择索引列时应从真实查询出发：

• 高频等值列通常放在组合键前部，但还要兼顾选择性和可复用前缀；
• 范围列通常放在连续等值前缀之后；
• 排序方向与分组需求可能让一个索引同时消除额外排序；
• 查询只需少量列时，可评估覆盖索引；
• 低频查询不应让每次高频写入都承担维护成本；
• 定期观察实际计划、扫描行数、回表次数和索引使用率，再删掉重复或长期不用的索引。

8

哪些因素会影响优化器是否选择二级索引？

A条件选择性B预计回表随机读数量C表扫描的顺序读成本D索引名称是否更长

检查

---

写优化索引把随机修改变成批量顺序写

LSM 树的层级与归并

普通 B+ 树随机写会反复修改分散的叶页。LSM 树先把新项写入内存有序结构 $L_0$，内存达到阈值后形成磁盘有序文件；较小层积累到条件后，与下一层按键序归并。写入从“每条记录随机改页”变成“成批顺序生成新文件”。

图：写入先进入内存层，再逐层归并；读取可能检查多层，布隆过滤器用于跳过确定不含目标键的文件。

若内存容纳 $M$ 个索引项，层级大小比约为 $T$，总项数为 $N$，层数可粗略理解为：

$$L \approx \left\lceil \log_T \frac{N}{M} \right\rceil$$

每层只有一个大有序结构时，查询要检查的结构少，但归并会频繁重写旧数据。每层允许多个有序文件时，写放大降低，查询却要查更多文件。布隆过滤器能快速回答“某个文件一定不含此键”，从而减少无效读取，但它不能证明键一定存在。

删除不立刻去所有层找旧值，而是写入删除标记。查询按新到旧合并结果，遇到标记就屏蔽更旧版本；归并时标记与旧记录相遇，二者可以一起清除。更新也可以写成新版本，读取选择最新项。

缓冲树的另一条路线

缓冲树在每个内部节点附加更新缓冲。插入先进入根缓冲，缓冲满后按键排序，把一批更新推给相应孩子。一次读取和写回孩子页的成本由多条更新分摊。

查询除下降树结构，还要检查路径上尚未下推的缓冲；范围查询涉及的内部缓冲更多。缓冲树通常比多层 LSM 少查一些结构，但向孩子推送仍可能产生随机 I/O。固态盘随机读写较快时，这个取舍可能更有吸引力。

读放大、写放大与空间放大

写优化结构不是免费午餐：

高写入流水、日志型数据适合优先压低随机写；强范围扫描和稳定低延迟点查则要控制层数、文件数和归并抖动。

9

LSM 树为什么能提高高写入负载下的吞吐？

A它完全不需要磁盘写入B它把更新先缓存在内存并批量归并为顺序写C它让所有范围查询只读一个页D它删除了所有旧数据

---

位图索引怎样把条件变成按位运算

从记录编号到位向量

位图索引要求记录能够映射到稳定编号。对于低基数属性的每个可能值，建立一个与记录数等长的位向量：第 $i$ 条记录取该值，就把第 $i$ 位设为 1，否则为 0。

假设 8 条订单的状态位图为：

区域“华东”的位图为 10110100。查“华东且已支付”只需按位与：

$$11010100 \land 10110100 = 10010100$$

结果中为 1 的位置就是候选记录。多个条件的交、并、非可分别转换为 AND、OR、NOT；处理器一次能运算一个机器字，压缩位图还能跳过长段全 0 或全 1。

图：每个属性值对应一个位向量，多条件查询先在位图层求交，再读取少量候选记录。

适用边界

位图尤其适合取值种类少、分析查询多、数据批量更新的场景。单独按“性别”或“订单状态”查询往往命中很多记录，未必比扫描省多少数据页；但多个低基数条件结合后，交集可能很小，位图优势才显现。

高频逐行更新会不断修改位图中的离散位置，可能带来锁、版本和压缩块重写成本。高基数列若为每个值都建一张位图，目录和元数据也会膨胀。工程实现会使用编码位图、压缩位图或 B+ 树与位图混合结构，但核心仍是把集合运算变成批量位运算。

10

位图索引只要建在低基数列上，单个条件查询就一定比顺序扫描更便宜。

正确错误

---

空间与时间数据需要不同的“顺序”

空间点、区域与最近邻

餐厅坐标是二维点，配送范围是多边形。普通组合 B+ 树按（经度，纬度）做字典序排列，只把二维空间压成一条顺序。它能精确找某个坐标，却难以高效回答“当前位置 500 米内有哪些门店”“这个矩形视窗内有哪些仓库”或“最近骑手是谁”。

k-d 树在不同层轮流按各维切分空间；二维四叉树每次把区域分成四块。它们适合点数据的矩形范围和最近邻搜索。R 树更适合线段、矩形和多边形：每个节点保存能包住所有孩子对象的最小边界矩形。查询区域与某个边界框不相交时，就能剪掉整棵子树。

R 树的兄弟边界框可能重叠，所以一次查询可能走多条路径。它以这种搜索代价换来“每个空间对象只保存一次”和平衡多路树的存储效率。

图：R 树用边界框剪枝空间对象；时间索引要处理区间重叠与“当前有效”的无穷结束时间。

时间点与有效区间

订单状态、商品价格或门店营业规则可能只在某段时间有效。一条时间记录包含开始时间、结束时间，以及端点开闭信息。当前仍有效的记录可以把结束时间概念化为正无穷。

只在业务键上建索引，会取回该键的全部历史版本，再逐条检查区间是否包含查询时刻。把“业务键 + 时间”看成二维对象后，可以用空间索引处理“给定键在时刻 $t$ 有效的版本”或“与时间范围重叠的版本”。

无穷结束时间会造成很大的边界框。常见做法是把当前记录和历史记录分开：当前记录用（业务键，开始时间）的 B+ 树，历史闭合区间用 R 树或专门的区间索引。查询某个时刻时访问两个索引，再合并结果。

时间主键还要保证同一业务键的有效区间不重叠。插入新版本时，索引不仅定位查询结果，也用于快速检查新的时间区间是否与现有版本冲突。

11

哪些查询通常需要空间或时间专用索引，而不是普通单维 B+ 树或哈希索引？

A查订单号等于某个固定值B查当前位置 500 米内的门店C查与给定有效期重叠的价格版本D按主键判断一行是否存在

检查