2.倒排索引、KNN、ANN、PQ乘积量化-育师

1.倒排索引

倒排索引（Inverted Index）就是一张词→文档编号的查找表。

假设你手里三张纸：

1：我爱北京

2：北京好大

3：我爱吃烤鸭

问题：哪张纸上写了“北京”？

正排索引：把三张纸从头看到尾，一张张找。
倒排索引：相当于提前做一个小抄：北京[1, 2]，烤鸭[3]，爱[1, 3]，根据北京对应文档编号直接答出1号和2号。

总结：

1.提前做小抄：建索引要花时间，但之后每次查都很快。

2.小抄里不存原文：只存编号。所以查到编号后，还得回去把那几张纸拿出来看，这叫“回表”。

3.比的是步数：笨办法要翻一万张，小抄只要看一眼。

2.KNN

KNN（K-Nearest Neighbors）就是K个相邻邻居。K就是取几条的意思，如K=5意思是取最近的5条数据。

还是那三张纸的例子换成这三句：

1 号：想买台便宜点的笔记本

2 号：北京烤鸭真好吃

3 号：有没有性价比高的电脑推荐

现在你搜「便宜电脑」。

用倒排索引：翻小抄查「电脑」，只会命中 3 号；1 号写的是「笔记本」，而小抄里没有「电脑」这个词，所以搜不到。

明明是一个意思，却漏了。这就是关键词搜索最大的毛病：字不一样，就找不到。

KNN 换了另一套办法

它不比较文字，而是比较句子之间的意思够不够近。

做法分两步：

1.先给每句话算出一串数字，相当于在图上给每句话画一个“点”；意思越接近，点就挨得越近。

2.搜索时，先把你问的这句话也画成一个点，然后看周围哪几个点离得最近，把它们挑出来。

这样，1 号和 3 号因为意思像，位置是挨着的，都能被挑出来。

总结：

1.倒排比字，KNN 比意思。

2.KNN 要先算数字：每句话都变成一串数（叫向量），这一步很贵，所以一般提前算好存起来。

3.两个一起用最香：先用 KNN 捞一批“意思像的”，再用倒排索引保证“对的别漏”——这就是大家说的混合检索。

3.ANN

ANN（Approximate Nearest Neighbor）：近似最相邻。它不保证找的绝对准，只保证找的足够准，同时快很多。

ANN 怎么偷懒

一句话：先缩小范围，只在“可能最近的那一小片”里找。

打个比方，你要找全城离你最近的 5 家火锅店：

精确 KNN = 把全城几千家店全部跑一遍，量完再排序。结果绝对准，但你得跑断腿。
ANN = 先看地图大致范围，判断你的位置大概在哪个片区，然后只在这几个片区里挑。可能漏掉隔壁片区一家没招牌的店，但 5 家里有 4.9 家是对的，而且你快了几百倍。

这就是全部思想：接受 1% 的漏，换 100 倍的快。

文本 → 模型算成一串数字（embedding）
→ 用 ANN 建好“地图”存进向量库（HNSW 图 / IVF 簇）
→ 用户 query 也算成一串数字
→ 拿这串数字在地图上找最近的 K 条 → 返回结果

ANN是一类方法的总称，具体实现方法：

HNSW：把点连成一张关系网，还分出“快速通道层”。先坐电梯到高层、粗略定位到大致区域，再一层层往下走，到最底层精挑，常用于Elasticsearch、Milvus、Qdrant、pgvector 的默认选择
IVF：先把全库点分成若干簇（像分成若干小区），搜索时只查离你最近的那几个簇，Faiss 常用
PQ：把 768 个数压缩成 96 个字节（像把大照片压成缩略图），省内存、算得快，代价是精度略降，是内存不够时的救命方案

4.PQ乘积量化

把一整条精确向量抄成几个档位编号，用查表代替浮点乘法。用精度换内存和速度。

为什么要它：1 亿条 128 维 float32 = 50 GB，装不下。压到 4 字节/条后是 400 MB，装得下才算得快。

比方：档位代替精确值

不写「身高 179.3 cm、体重 68.4 kg」，写「身高：高、体重：中」。损失精度，但判断「这两个人像不像」完全够用。

比方	PQ
一个人	一条向量
一个字段	一段子向量
档位表	码本，256 个聚类中心
填好的档位	1 个编号 = 1 字节

建库三步

切分：把 D 维向量切成 M 段，每段 D/M 维。例：128 维切成 8段 × 16维
训练：对每一段单独跑 k-means，聚成256 个中心。每段各有一套独立码本，段 1 的 256 个中心和段 2 的 256 个中心毫无关系。256 是为了让编号刚好塞进 1 字节（uint8）
编码：每段去自己的码本里找最近的中心，记下编号（0~255）。M 段 → M 个编号 → M 字节

关键区别：码本是训练出来的（离线一次），编号是编码算出来的（每条向量一次）。

手算一遍

为了手算，把 256 个中心缩成 4 个。真实档位由 k-means 从样本学出。

原始向量：[1.0, 1.2, 5.0, 4.8, 9.1, 8.9]，切 3 段，每段 2 维。档位：(0,0)、(1,1)、(5,5)、(9,9)等等256个

段	原始	最近档位	编号
1	(1.0, 1.2)	(1, 1)	1
2	(5.0, 4.8)	(5, 5)	2
3	(9.1, 8.9)	(9, 9)	3

存储结果：[1, 2, 3]—— 3 个字节（原来 6 个 float = 24 字节）

为什么 6 个数变 3 个数？因为每 2 个数组成一段，一段整体换成一个编号（2 合 1）。
为什么这里只压缩 8 倍？压缩比 = 每段维数 × 4，这里每段 2 维 → 2×4 = 8 倍。工程里每段 1632 维，所以是 64128 倍。
小注：4 个档位其实 2 bit 就够，说「3 字节」是为了对齐「1 编号 = 1 字节」的工程口径。

解码（近似还原）：查表拼回(1,1, 5,5, 9,9)≈ 原始向量，只差一点点。