《检索技术核心 20 讲》笔记

伸缩性架构是指不需要改变系统的软硬件设计，仅通过改变部署服务器数量就可以扩大或缩小系统的服务处理能力。

线性结构检索

检索核心思想：合理组织数据，尽可能快速减少查询范围。

数组 vs 链表：

维度	数组	链表
存储	连续内存	不连续内存 + 指针
访问	支持随机访问 O(1)	只能顺序访问
空间	固定大小，扩容需复制	灵活扩容
查找	效率高	效率低
增删	效率低	效率高

非线性结构检索

• 无序数组：只能顺序查找，O(n)
• 有序数组：二分查找，O(log n)，但需维护数据有序

对于数据频繁变化的场景，有序数组不是最优方案。两种更灵活的组织方式：

• 二叉检索树：平衡时 O(log n)，不平衡时退化到 O(n)。AVL 树和红黑树平衡性更强
• 跳表：O(log n)，通过随机生成层级实现平衡，实现比 AVL/红黑树更简单

核心思想：合理组织数据，平衡划分检索空间，采用二分查找快速缩减范围。

哈希检索

• 本质：通过 Hash 函数将 Key 转为数组下标，利用数组随机访问特性实现 O(1) 检索
• 核心要求：数据分布均匀，减少哈希冲突
• 冲突解决：二次探查、双散列等方案
• 与二分查找原理相通：高效检索需要均匀划分检索空间

状态检索

场景：在海量数据中快速判断对象是否存在

位图：基于位运算的哈希结构，用二进制位（0/1）表示对象是否存在，空间效率极高

布隆过滤器：使用 k 个哈希函数 表示一个对象，解决哈希冲突问题

• 判断不存在：100% 准确
• 判断存在：可能误判，可通过调整哈希函数个数和位图大小降低误判率
• 适用于对误判有一定容忍度的场景

倒排索引

• 核心原理：将内容/属性作为 key，存储对应的文档列表，实现 O(1) 查询
• 应用场景：数据库全文索引、搜索引擎、广告引擎、推荐引擎

B+ 树检索

磁盘 vs 内存：

• 内存：随机访问，速度快但昂贵
• 磁盘：顺序访问大批量数据时性能与内存接近，随机读写慢 10万~100万倍
• 磁盘最小读写单位：扇区（512B/4KB）→ 操作系统最小单位：块（Block/Cluster）

B+ 树设计要点：

• 节点大小 = 块大小：充分利用每次磁盘读取的数据
• 内部节点仅存 key + 指针，不存数据，最大化索引数据密度
• 叶子节点存 key + 数据，同层通过双向链表连接，支持范围查询
• 是一棵完全平衡的 m 阶多叉树

关键设计思想：索引与数据分离，保持索引大小可控，尽量加载到内存中

MySQL 两种实现：

• MyISAM：叶子节点存数据指针（非聚集索引），索引数据分离，需表级锁
• InnoDB：叶子节点直接存数据（聚集索引），支持行级锁

LSM 树检索

问题：B+ 树每次插入都需随机写入磁盘，性能慢

LSM 树（Log Structured Merge Trees）核心思路：

1. 延迟写磁盘：数据先写入内存中的 C0 树
2. 批量写入：内存树达到阈值时，以块为单位写入磁盘 C1 树
3. WAL 预写日志：保证崩溃恢复
4. 顺序写（Log Structured）：提高写入效率

适用场景：写多读少的 NoSQL 系统

索引构建

• 数据压缩：尽可能将数据加载到内存，索引压缩是重要研究方向
• 分支处理：大数据集拆成多个小数据集（分布式思想）

索引更新

Double Buffer（双缓冲）

内存中保存两份相同索引，一读一写，来回切换实现高性能更新。

• 优点：简单高效
• 缺点：数据量大时内存开销翻倍

全量索引 + 增量索引

• 增量索引：新数据建立的内存倒排索引，较小，可用 Double Buffer 实现无锁访问
• 全量索引：只读，无需加锁
• 查询时同时查询两者，合并结果

增量索引增长处理

• 完全重建法：定期重建全量索引，切换到新索引
• 再合并法：归并全量 + 增量，生成新全量索引
• 滚动合并法：分层索引（全量/周级/天级），逐层合并

索引拆分

水平拆分和垂直拆分

TOP K 检索

TF-IDF 算法

公式：相关性 = TF × IDF

• TF（词频）：词项在文档中出现的次数，出现越多越重要
• DF（文档频率）：词项出现在多少文档中，越普遍越无区分度
• IDF（逆文档频率）：DF 的倒数，值越大区分度越大

BM25 算法

• 词频与相关性非线性关系：随词频增加，相关性增长趋缓并有上限
• 考虑四个因子：IDF、文档长度、文档词频、查询词词频
• 三个可调参数：k1、k2、b

机器学习打分

大规模引入打分因子，自动学习权重，已成为大规模检索引擎标配

快速 TOP K

• 精准：堆排序代替全排序，时间 O(n) + O(k log n)
• 非精准：保证高质量结果包含在 Top K 中即可

空间检索

• 通过二维空间水平/垂直方向不停二分，生成一维区域编码
• 四叉树：快速划分查询空间，递归扩大查询范围，实际应用使用非满四叉树
• GeoHash 编码：通过前缀树提高检索效率

最近邻检索

向量空间模型：将所有关键词提取为 n 维向量空间，通过向量相似度计算文章相似性。

LevelDB 存储系统

LevelDB 基于 LSM 树优化而来，核心改进：

内存检索

使用跳表代替 B+ 树实现内存 C0 树

内存到磁盘转移

• MemTable：可读可写，存储新数据
• Immutable MemTable：只读，MemTable 写满后切换
• 读写分离设计，Immutable MemTable 无锁写入磁盘

数据合并

• 延迟合并：先将 Immutable MemTable 顺序写入 SSTable 文件，再分层滚动合并
• 避免原始 LSM 树 C0/C1 直接合并的高昂 IO 代价

数据检索

查找顺序：MemTable → Immutable MemTable → 磁盘 SSTable（多层二分 + BloomFilter + 缓存）

搜索/广告/推荐系统

搜索流程：分词 → 倒排索引短语检索 → 相关性打分 → 返回 Top K

广告引擎：标签检索（树形 + 倒排索引 + 过滤）+ 向量检索（聚类 + 乘积量化）+ 打分排序

推荐引擎：更灵活的检索技术，用于文章召回服务

参考资料

• 检索技术核心 20 讲