Lec 8-9 索引与过滤器

0. 学习地图

这篇笔记围绕一个问题展开：「针对这种查询类型，应该选哪种数据结构？」

查询意图	首选结构	原因
结构化键上的点查 / 范围查	B+Tree	有序、精确、更新友好
快速“不存在”预检查	Bloom 类过滤器	低成本过滤负例
内存中的有序集合	Skip List	更新简单，期望 `O(log n)`
前缀 / 数字化键查找	Trie / Radix	按键的位/前缀逐层匹配
全文关键词检索	倒排索引	`term -> posting list`
语义相似度检索	向量索引（IVF/HNSW）	在嵌入空间做 ANN

1. B+Tree（Lec 8 核心）

1.1 核心思想

B+Tree 是 DBMS 里的默认有序索引：一个结构同时支持点查询和范围扫描，并且在磁盘场景下表现稳定。

1.2 物理结构

内部节点（Inner node）：路由键 + 子指针。
叶子节点（Leaf node）：键 + 负载（RID / 主键 / 元组数据）。
叶子兄弟指针：让有序扫描更高效。

B-Tree vs B+Tree

维度	B-Tree	B+Tree
值存储位置	各层都存	仅叶子层
范围扫描	不够自然	通过叶子链天然支持
工程实践	较少用	主流选择

1.3 更新逻辑（写入时会发生什么）

插入

向下遍历到目标叶子。
按序插入键。
若溢出则分裂节点。
将分隔键上推到父节点。
若父节点也溢出，继续向上级联。

删除

在叶子删除目标键。
若低于阈值，先尝试向兄弟借键。
借不到则与兄弟合并。
更新父节点分隔键。
若父节点下溢，继续向上级联。

重复键

推荐：存 (key, rid) 以保证唯一性。
不推荐：溢出链（overflow chain），维护成本高。

1.4 设计旋钮（Design Knobs）

旋钮	常见选择	权衡
节点大小	慢介质更大	I/O 更少，但节点内扫描更重
合并阈值	不一定“半满就合并”	写放大更低，但会暂时更稀疏
变长键存储	指针/变长节点/填充/间接映射	空间效率 vs 实现复杂度
节点内搜索	线性(SIMD)/二分/插值	CPU 效率 vs 分布假设

1.5 工程优化

Pointer swizzling：页常驻缓冲池时用原始指针替代 page id。
写优化 B+Tree：内部节点先缓冲更新，再批量下推。
Partial index：只给满足谓词的子集建索引。
Include columns：支持 index-only scan。
前缀压缩 / 去重 / 后缀截断：降低索引体积。
Bulk build：先排序，再自底向上建树。

1.6 何时优先用 B+Tree

当你需要以下能力时，B+Tree 应该是第一选择：

精确点查 + 范围查询
频繁更新
可预测的事务行为

2. 过滤器（Lec 9 Part A）

2.1 Bloom Filter

核心思想

位图 + k 个哈希函数，用于成员关系判断。

语义保证

假阴性（False negative）：不会发生
假阳性（False positive）：可能发生

操作

Insert(x)：置位 k 个比特。
Lookup(x)：只要有一位为 0 就一定不存在；全为 1 则“可能存在”。

最佳用途

放在昂贵索引/表访问之前，先做廉价预过滤。

2.2 其他过滤器

Counting Bloom：用计数器代替比特，支持删除。
Cuckoo Filter：基于 fingerprint，支持动态增删。
SuRF：压缩的静态 trie 类过滤器，支持近似点查/范围过滤。

3. 有序结构替代方案（Lec 9 Part B）

3.1 Skip List

核心思想

多层链表，键的“层高”通过随机方式决定。

存在意义

更新路径比严格平衡树更简单
期望复杂度为 O(log n)

权衡

在内存场景很好用（如 MemTable）
在磁盘/缓存局部性上通常不如 B+Tree

3.2 Trie / Radix Tree

Trie

按键的位/前缀逐步匹配。
复杂度 O(k)，k 为键长度。
结构依赖键前缀，不依赖插入顺序。

Radix（Patricia）

压缩单子路径。
比普通 trie 更省空间。
某些压缩路径匹配可能需要回表/回键验证。

4. 文本检索：倒排索引（Lec 9 Part C）

4.1 核心结构

词典（Dictionary）
每个词对应的 posting list

对于 contains keyword 这类查询，倒排索引通常比 B+Tree + LIKE '%...%' 更合适。

4.2 课程中提到的系统

Lucene：FST 词典 + 分段 + 后台合并。
PostgreSQL GIN：词典 + posting list/tree + pending list。

4.3 检索质量层

排序：TF-IDF / BM25
分词：n-gram / trigram
归一化：标点、空格等变体处理

5. 语义检索：向量索引（Lec 9 Part D）

5.1 为什么需要向量索引

关键词重合不足以表达语义相似。先把文本/对象映射成 embedding，再做最近邻检索。

5.2 IVF 风格向量检索

先把向量聚类到若干中心。
建立 中心 -> 向量列表 映射。
查询时先探测最近簇，再对候选重排。

5.3 图索引风格（HNSW）

在向量之间建近邻图。
从入口点做贪心导航，逐步靠近查询向量。
多层图结构提升速度与质量。

5.4 实践提示

向量检索通常会和元数据过滤（前置或后置）组合使用。

6. 最终选型指南

如果你的查询是…	先用	再叠加
`a = ?` 或 `a between ? and ?`	B+Tree	Partial/Covering 索引
“这个键大概率存在吗？”	Bloom Filter	对阳性再走主索引
“找包含某个词的文档”	倒排索引	BM25 + 分词调优
“找语义相似内容”	向量索引（IVF/HNSW）	元数据过滤 + 重排
前缀密集的键检索	Trie/Radix	压缩与自适应节点布局