近似最近邻（ANN）搜索

• 三类信号（向量、关键词、元数据）本质不可比的度量问题
• RRF 基于排名而非分值进行融合的原理
• 无参、鲁棒、抗分值分布差异的优点

向量分数（余弦/内积）与 BM25 分数（词频/逆文档频率）的值域、分布完全不同，无法直接加权求和，因此业界常用 RRF 这种"只看排名不看分值"的融合方法。RRF 对每个候选文档，把它在各检索结果列表中的排名 r 通过公式 score = Σ 1/(k + r) 累加（k 通常取 60），排名越靠前贡献越大，最终按累加分数排序。它不依赖各检索器的分值尺度，天然抗分值分布偏差，且无需训练权重。元数据过滤则通常在检索前（pre-filter）或检索后（post-filter）执行：pre-filter 先按过滤条件缩小候选集再做 ANN 检索，post-filter 检索后再剔除不满足条件的 hits。RRF 的不足是把各信号等权对待，无法体现某些信号更重要的先验，且对每个子列表的召回质量敏感。

融合的本质是把"异源、异尺度"的排序信号统一表达。RRF 用"排名"而非"分值"做融合，从而规避了向量分数与 BM25 分数不可比的核心难题，k 为光滑常数防止除零并压低长尾排名的贡献。企业实践中常用 RRF 作为零成本的 baseline，再根据效果用学习权重（如 weighted RRF 或 LLM rerank）微调。

• 暴力搜索耗时与数据量、维度成正比
• 索引构建与查询开销的权衡
• 数据量增长时索引选型的阶梯（Flat → IVF → HNSW → 分布式/DiskANN）

当数据量在万级以下且维度不高时，暴力搜索（Flat）直接遍历全部向量算内积/余弦，耗时在毫秒级，反而比 ANN 更快、更准。原因有三：一是 ANN 索引（如 HNSW）需要先构建多层图，构建本身有 O(n log n) 或更高的开销，数据量小时构建成本占比过高；二是 ANN 是近似算法，在召回率上有损失，而小数据量下暴力搜索没有召回损失；三是暴力搜索实现简单、内存零额外开销。选型阶梯：万级以下用 Flat 暴力扫描；万级到百万级用 IVF（倒排分桶）或 HNSW，IVF 实现简单、可控性高，HNSW 召回与延迟综合最优；百万到亿级用 HNSW 或 IVF-PQ（量化压缩内存）；亿级以上用分布式多机（Milvus 多分片）或 DiskANN（外置 SSD 索引）。维度越高、数据量越大，越需要更复杂的索引结构来做近似。

索引的本质是用"构建时间 + 近似召回损失"换取"查询延迟"。数据量小时这一交换不划算，暴力搜索的线性扫描在现代硬件（SIMD、缓存）下很快，且零召回损失。当数据量增长到百万级，线性扫描的延迟超过可接受阈值，才需要 ANN 索引；而越是海量，越依赖量化与磁盘来平衡内存占用与召回率。

• 多层图 + 高层粗粒度、低层细粒度的层级结构
• greedy 搜索从高层到低层的逐层下探
• 参数 M 与 efConstruction 对图连通度、召回、构建成本的影响

HNSW 把点组织成多层图：底层（level 0）包含所有点，越往上层的点越少（约按概率 1/ln(M) 逐层递减），形成类似跳表的多层结构。搜索时从最高层入口点开始，用 greedy 搜索逐层下探：每层内沿当前点邻居中距离更近的方向贪心移动，找不到更近邻居时下到下一层继续，直到最底层得到近似最近邻。高层邻居稀疏、覆盖全局，低层邻居密集、局部精细，这种"先粗后细"的搜索能把复杂度降到近似 O(log n)。参数影响：M 是每层节点的最大邻居数（连接度），M 越大图连通度越高、跨层跳转越容易、召回率越高，但构图和内存开销越大；efConstruction 是构建时搜索候选集的规模，efConstruction 越大，构图时每个点找到的候选邻居越准确、图质量越高、召回越好，但构建时间与内存越大。推理时还有 ef（搜索候选数）参数，ef 越大召回越高、延迟越高。

HNSW 借鉴了跳表"高层用于快速推进、低层用于精确收敛"的思想，但用图替代链表，使每个节点可通过多个邻居路径到达，从而在稀疏的高层也能沿"最相似方向"前进。M 与 efConstruction 本质是"图质量"与"构建成本"的权衡旋钮，工程上通常固定 M（如 16），再调 efConstruction 与 ef 来平衡召回与延迟。

• LSH 用哈希桶把相似点投影到同一桶
• 随机超平面投影与夹角余弦的单调关系
• 精度（召回概率）与速度（桶数）的权衡

LSH 的核心是构造一个哈希函数，使得"相似的点以高概率落入同一桶、不相似的点以低概率落入同一桶"。对余弦相似度，常用随机超平面（random hyperplane）哈希：对每个向量生成一个随机超平面（法向量），向量与法向量的内积符号决定一层 bit，多层 bit 组成的哈希编码即桶标签。两个向量被随机投影到同一超平面同侧的概率与它们夹角的余弦单调对应，因此"落入同一桶的概率"与"余弦相似度"单调对应——相似度越高，哈希碰撞概率越高，这就是随机投影保持余弦相似度单调性的原因。权衡：LSH 是近似算法，通过多张哈希表（并行投影）提高召回率，但表越多、哈希编码越长，内存与计算开销越大；精确 KNN 无召回损失但速度慢。LSH 的优点是查询 O(1) 级（只查桶内），且天然支持海量数据；缺点是召回率由维度与投影数决定，精度无法保证百分百，且对高维数据需要很多投影才能维持召回。

随机超平面哈希的数学基础是：两个单位向量夹角为 θ 时，随机超平面恰好把二者分开的概率为 θ/π，因此"分到同侧"的概率 1 - θ/π 随夹角减小（相似度增大）而单调上升。这正是"局部敏感"所在。LSH 用"牺牲召回换取速度"的方式换取近似 KNN，多表联合可逼近精确结果，但失去精确 KNN 的确定性保证。

• 高维空间中距离集中、点间距离趋同
• 传统空间索引靠空间划分（树）剪枝，高维下剪枝失效
• 降维的低秩损失与语义保留

高维诅咒指维度增长时，数据点之间的欧氏距离趋于相等（距离集中现象），任意两点都"差不多远"，最近邻与最远邻的距离比趋近 1，导致"最近邻"概念本身变得没有区分度。传统空间索引（KD 树、R 树、四叉树）依赖"空间划分 + 剪枝"：它们把空间递归切成若干区域，查询时只访问与查询点邻近的少数区域。但高维下每个区域内的点几乎与所有其他区域等距，剪枝条件失效——要么需访问几乎全部节点，要么返回的"最近邻"并不比随机点好多少，树索引退化为暴力扫描甚至更差。降维影响：PCA 是线性降维，保留方差最大的方向，能去除噪声、加速检索，但会损失低方差但有区分度的信息；UMAP 是非线性降维，保留局部邻域结构，对可视化与检索效果好，但非线性变换会改变距离度量，可能引入失真。降维本身是"用信息损失换速度与稳定性"，具体效果取决于数据内在维度是否远低于表观维度。

KD 树等能高效工作的前提是"可剪枝"——即空间中存在明显的区域聚集与阈值分离。高维下数据的体积分布趋于球壳，距离分布严重集中，树结构的剪枝完全失效。因此才有 ANN 索引（HNSW、IVF）与降维（PCA/UMAP）的用武之地。降维能减轻诅咒，但若数据内在维度本就高，强行降维会丢失语义，导致召回下降。

• 层数按指数分布随机分配
• 每层入口点与 greedy 搜索的逐层下探
• 高层跳远、低层精修的加速原理

HNSW 中每个节点被分配到一个层数 L，分配规则是：从第 0 层开始，每有一层就近似以概率 p = 1/ln(M) 继续上升一层，即层数服从几何分布，P(L = l) ∝ p^l，这样高层节点数按指数衰减。第 0 层包含所有节点，越往上节点越少，最高层往往只有几个节点。搜索时从最高层（最稀疏层）的入口点开始，用 greedy 搜索：在当前层沿"邻居中到查询点最近"的方向反复移动，直到找不到更近的邻居，再进入下一层继续，直到第 0 层并在其中收敛到近似最近邻。加速原理：高层邻居少、连接跨度大，相当于"粗粒度跳跃"，能快速把查询引导到空间中大致接近的区域；低层邻居多、连接局部，相当于"细粒度精修"，在已定位的小区域内找到精确最近邻。这种"先粗后细"避免在低层全图范围内逐点探索，从而把搜索量从 O(n) 降到近似 O(log n)。

层数指数递减 + 高层长边跳远，正是跳表思想的图化。若只在单层图上搜索，greedy 会陷入局部最优并需要大量探索；多层结构让高层承担"快速定位"，低层承担"局部收敛"，把搜索路径压缩到对数级。层数分配是随机的，保证每层都有序候选，无需显式重建。

• 构图：插入时用 efConstruction 选邻居建边
• 入口点：全局最高层节点作为搜索起点
• greedy 搜索与 ef 参数对召回/延迟的权衡

构图时，每个新节点按层数分配规则确定其最高层，然后从入口点开始逐层进行"类似查询"的搜索，在每层用 efConstruction 大小的候选集收集最相似的候选点，从中选出最多 M 个作为邻居建立双向边，并约束每个节点的度数不超过 M（必要时用启发式剪枝，如 heuristic select 保留能覆盖不同方向的邻居）。搜索时，入口点取全局最高层节点，从它开始逐层 greedy 下探到第 0 层，在第 0 层用 ef 大小的优先队列扩展候选，最终返回最接近的 ef 个结果。权衡：构图质量（recall 上限）由 M 与 efConstruction 决定，查询召回与延迟由 ef 决定——ef 越大，搜索越接近精确、召回越高，但扩展的候选越多、延迟越高；M 越大连通度越高、召回好但内存与构图时间增加。工程上在"能接受的内存内"提高 M 与 efConstruction 提升上限，再按延迟预算调 ef。

入口点是全局宏观的起点，保证搜索从"覆盖最广"的稀疏层开始，避免因起始点偏颇而陷入局部最优。greedy 搜索在每层只沿"距查询最近"的邻居方向前进，是典型的贪心近似，ef 越大越能抵消贪心的局部性与随机性。召回与延迟的权衡本质是"做了多少近似"与"多接近精确"之间的交换。

• 实时索引与批量索引的可见性差异
• 索引构建延迟与查询延迟的权衡
• 传统数据库索引与向量索引在 update 上的差异

向量索引可分为两类构建方式。batch index（批量索引）：数据先攒批，到达一定量或每隔一段时间触发一次全量/增量重建，在重建完成前新写入的数据不可见，因此存在"写入到可见"的延迟窗口（通常秒级到分钟级），但每次重建可用高质量算法（如较高的 efConstruction）做出更优的图。real-time index（实时索引）：数据写入后立即插入 HNSW 图或 IVF 桶并立即可见，实现"写入即搜索"，但每次插入需要维护图结构，吞吐受限，且频繁增量插入可能降低图质量。实践中常采用"默认实时 + 后台批量 compact"的混合策略：新数据先进入实时 mem 索引立即可见，同时后台定期把增量合并进主索引提升质量。一致性模型通常是"最终可见"：写入后经毫秒到秒级延迟即可被搜索，不是数据库的强一致（read-your-writes 不一定立即保证）。删改多以 tombstone 标记。

一致性延迟的根源是"索引构建是异步的、有成本的"。实时索引把构建成本摊销到每次写入，换取可见性；批量索引把构建批量摊薄，换取构建质量与吞吐。两者本质是"写入可见延迟"与"索引质量/吞吐"的权衡，业界用实时+后台合并兼顾二者。

• K-means 聚簇 + 倒排桶的构成
• nprobe 与召回/延迟的权衡
• IVF 与 HNSW 的构建、查询、内存差异

IVF 先用 K-means（或更快的聚类）把所有向量聚成 nlist 个簇，每个簇中心一个，属于同一簇的向量放进同一个"桶"（倒排表）。查询时，先计算查询向量到 nlist 个簇中心的距离，选出最近的 nprobe 个簇，只在这 nprobe 个桶内做暴力扫描（或用 PQ 距离近似），返回最近邻。权衡：nprobe 越大，探查的桶越多、覆盖的候选越多、召回率越高，但查询耗时越长；nlist 越大，每桶向量越少、扫描越快，但簇中心变多、查询时算中心距离的开销增大，且可能把本应相近的向量分到不同桶从而漏掉。与 HNSW 差异：IVF 构建快、内存可控、实现简单，适合"可离线批量构建、数据规模大、内存有限"的场景，配合 PQ 可大幅压缩内存；HNSW 查询延迟更低、召回率对高数据量更稳定，但构建慢、内存占用大（需存图邻接表），适合"查询性能要求高、内存充足"的场景。二者常组合成 IVF-HNSW（先用 IVF 粗筛，再用 HNSW 精查）。

IVF 的本质是"先粗分后再就近精查"，把全量线性扫描降为"少数桶内扫描"。nprobe 是召回与速度的转盘，nlist 决定桶的粒度。相比 HNSW 的图结构，IVF 更结构化、更易扩展与量化，因此在存储服务器和量化场景（IVF-PQ）中更受欢迎。

• 数值精度降低对距离计算的影响
• INT8 量化与标量量化（scalar quantization）
• PQ 分块聚簇码本 + 查表近似距离

向量以 FP32 存储时精度最高、内存最大（每维 4 字节）；FP16 内存减半，精度损失小，召回率几乎不变；INT8 内存再减半（每维 1 字节），用标量量化把每维映射到 256 个区间，召回率有一定下降但通常可接受。量化通过减少内存使更多数据驻留内存，从而允许更大 ef 或更多候选，往往能部分抵消精度损失。Product Quantization（PQ）：把 d 维向量切分成 m 段（每段 d/m 维），对每一段用 K-means 训练码本（一个码本含 k 个中心，通常 k=256），每个向量每段用最近的码本中心 id 表示，最终向量被压缩成 m 个字节（每段 1 字节）。查询时，先计算查询向量每一段到该段码本所有中心的距离，形成距离查找表，再对候选向量用"查表累加"近似原向量距离，即 d(q, x) ≈ Σ 段内距离（查表）。这样无需解压原向量，距离计算 O(m) 而非 O(d)，且每向量只存 m 字节。PQ 的主要代价是距离近似带来的精度损失，可用查询感知的编码（如 ScaNN）或残差量化改善。

内存与精度权衡的本质是"位宽越少，能驻留内存的数据越多、检索越快，但距离计算越粗糙"。INT8 标量量化适用所有维度，PQ 通过"分块聚簇 + 查表"把内存压到极致（m 字节/向量），是十亿级检索（IVF-PQ、ScaNN）的核心。码本训练的 k-means 是离线的一步，查询时查表近似的策略是 PQ 提速的关键。

• Flat 适合小数据量
• HNSW 与 IVF 的召回/延迟/内存差异
• 查询模式（低延迟、高召回、批量）对选型的影响

选型核心是数据规模、内存预算、查询模式（延迟与召回要求）。Flat（暴力）：适合数据量小（万级以下）或需要精确结果、且数据能常驻内存的场景，实现简单、零召回损失，但延迟随数据量线性增长。HNSW：适合百万级到千万级、查询延迟要求高、内存充足（需存图邻接表，开销约为数据本身的 1-2 倍）的场景，是 Qdrant 的默认索引，召回/延迟比最优。IVF（IVF-Flat / IVF-PQ）：适合千万级以上、内存有限、可接受近似召回的场景，通过聚簇分桶 + 可选 PQ 压缩内存，比 HNSW 更省内存、构建更快，但若要高召回需加大 nprobe 增加延迟。量化组合：IVF-PQ 用于十亿级、内存受限；DiskANN 用磁盘支撑超十亿。pgvector 里 Flat 用于小数据、IVFFlat 用于中等、HNSW 用于大数据量高召回。查询模式：要求高召回且低延迟优先 HNSW；要求省内存、可批量检索优先 IVF；要求精确小规模用 Flat。

向量库的索引选型是"内存-延迟-召回"三角的平衡。HNSW 以内存换延迟与召回，IVF 以召回换内存，Flat 以延迟换精确。工程上先评估数据能否全部驻留内存与内存预算，再按延迟与召回要求定 HNSW 或 IVF，超大基础上叠加 PQ 与磁盘。

• pre-filter 先过滤再检索 vs post-filter 先检索再过滤
• 过滤对候选集与召回率的影响
• HNSW 图结构与过滤条件的冲突

pre-filter（预过滤）：先按元数据条件（如 price > 100）筛选出满足条件的向量子集，再对该子集构建/检索 ANN 索引。优点是结果天然满足过滤条件、无漏筛；缺点是过滤出的子集可能太小或分布不均，导致 ANN 索引失效（退化为对子集暴力扫描），且过滤条件变化时索引无法复用，延迟高。post-filter（后过滤）：先做 ANN 检索返回 top-K 候选，再剔除不满足元数据条件的候选，若剩余不足 K 个则扩大检索量。优点是检索走完整索引、索引复用性好、延迟低；缺点是可能漏掉"满足条件但不在 top-K 的最近邻"，召回率下降。为何破坏 HNSW 邻居质量：HNSW 的图按"向量相似度"建边，邻居关系只反映几何距离，不反映元数据是否满足条件。过滤条件是对向量空间之外属性的约束，当检索时跳过不满足条件的节点，greedy 沿图移动的路径可能被"切断"——被过滤节点阻断的路径无法继续下探，导致搜索无法到达真正满足条件的更近邻，召回率下降。因此过滤条件与 HNSW 近似搜索天然冲突。

过滤的本质是"在相似度之外叠加一个硬约束"，而 ANN 索引只优化了相似度维度。pre-filter 牺牲检索效率保召回，post-filter 牺牲召回保效率，二者都有代价。业界改进是"过滤感知的图索引"（把过滤条件纳入建图/搜索）或把过滤写入索引元数据做条件倒排。

• 传统量化关注最小化重建误差
• 各向异性量化同时考虑查询方向
• 内积搜索的误差再分配

传统乘积量化（PQ）量化时只追求"最小化每个向量/块的量化重建误差"，即让量化后的向量尽量接近原向量。但内积搜索关心的是 q·x 的近似精度，而不是 x 本身的重建精度。ScaNN 的各向异性量化观察到：量化误差在"与查询方向平行的分量"上会显著影响内积排序，而在"垂直分量"上影响很小。因此它在量化时除最小化重建误差外，还引入一个"查询方向依赖"的项，即选择码本时让错误尽量落在与查询方向正交的方向上，从而在其实内积值上减少排序误差。这样，虽然每个向量的重建误差未必最小，但"内积近似值"的排序更接近真实，检索精度更高。ScaNN 由此在保持高速（查表 + 树状分桶）的同时，达到比传统 PQ 更高的召回率。

关键洞察是"最小化内积误差 ≠ 最小化重建误差"。各向异性量化把误差预算重新分配，把误差导向不影响内积排序的方向，是在"量化约束下的内积排序最优"这一目标上做优化，因此比追求重建误差最小的 PQ 对检索精度更友好。

• HNSW 增量插入与按层建边
• HNSW 删除用 tombstone 标记
• IVF 聚类中心随数据变化漂移的重建

HNSW 增量插入：新向量确定其层数后，从入口点开始逐层 greedy 搜索，用 efConstruction 找候选，选出最多 M 个邻居建双向边，并维护每点的度数上限，插入是点级的、可在线进行。HNSW 删除：直接删点会破坏图连通性（其他点可能仍指向它），故常用 tombstone（墓碑）策略——把待删节点标记为已删除，查询时跳过该节点，但保留其结构，代价是内存不释放、图质量随时间下降；需定期清理（重建受影响区域或全量 compact）来释放墓碑并优化图。IVF 聚类中心漂移：当数据不断增删，桶内向量分布变化，原 K-means 中心不再准确，导致新向量被分到错误桶、召回下降。处理方式：定期对索引做增量簇更新或全量重建（重跑 K-means），或采用"增量聚类"（新向量插入到最近簇，只轻微更新该簇中心），并配合后台 compact。

动态更新的核心矛盾是"索引结构依赖静态分布"与"数据持续变化"的对立。HNSW 用墓碑保留结构、牺牲空间保连通；IVF 用定期重建/簇更新对抗中心漂移。任何 ANN 索引真正做到高质量的动态更新，都离不开后台周期性重建（compact）来抵消累积退化。

• 图按段（block）存储，SSD 顺序读
• 内存中只存图结构与粗粒度定位
• 压缩向量 + 精排回读

DiskANN 把十亿级向量索引放在 SSD 上，核心设计是"内存只存紧凑结构，海量向量放磁盘，靠顺序读与预取保持毫秒级延迟"。具体做法：1) 在内存中构建并存放一个 HNSW 式的高层图结构（邻接信息），但图按"段/块"组织，每个节点及其邻居聚在同一块，保证搜索时一次磁盘读就能取到一片邻接；2) 磁盘上存每个向量的量化（压缩）版本，搜索时用压缩向量做距离粗算，选出候选；3) 对 top 候选再回读原始/高精度向量做精排。由于 SSD 顺序读+块预取远快于随机小读，DiskANN 把随机访问转化为块级顺序访问，配合"只读图结构 + 压缩向量"控制内存，使十亿级数据也能在毫秒级延迟内完成检索。它还用"预热"与"预取"（搜索时预取下一条路径的块）进一步隐藏磁盘延迟。

十亿级向量无法全驻内存，DiskANN 的要点是"内存放图结构 + 磁盘放压缩向量 + 块顺序读 + 量化粗算 + 精排回读"。它以"增加磁盘读"为代价换取"内存可控"，配合块级顺序读与预取，把磁盘延迟隐藏到毫秒级，是超大规模检索的典型工程方案。

• 召回-延迟-内存三者的相互制约
• IVF-PQ 省内存、中等召回
• HNSW 高召回、低延迟、内存高

ANN 检索存在"召回率、延迟、内存"三角：三者不可兼得，任何算法都在这一三角上各居一端。HNSW：以高内存（需存图邻接表，内存约为数据的 1-2 倍）换取高召回 + 低延迟，适合数据量适中（百万级）、内存充足、对延迟和召回要求都高的在线服务场景。IVF-PQ：用 PQ 把向量压缩到每向量几字节，内存极省，配合 IVF 分桶，延迟可控，但召回率因量化近似而略低，适合数据量巨大（千万到亿级）、内存受限、可接受近似召回的场景（如全量离线检索、低成本高容量检索）。选型：内存充足求极致性能选 HNSW；内存紧张求容量选 IVF-PQ；超大基础可叠加 DiskANN 或分布式。若追求高召回可用 HNSW 加大 ef，或用 IVF 加大 nprobe（牺牲延迟）。

三角权衡的本质是资源分配：HNSW 用"内存"换"延迟+召回"，IVF-PQ 用"召回"换"内存+容量"。工程上根据内存预算与延迟/召回 SLA 在三角上取点，必要时组合（如 IVF-HNSW、HNSW-PQ）在三角内折中。

• IVF 分桶粗筛 + PQ 压缩存储
• PQ 压缩的内存收益与距离近似
• 与 HNSW 在构建/查询/内存上的对比

IVF-PQ 是两大技术的组合：先用 IVF（倒排文件）把向量按 K-means 分成 nlist 个桶，查询时用 nprobe 选出最近的桶做粗筛；同时用 PQ（乘积量化）把每个向量压缩成 m 个字节（每段 1 字节码本 id），大幅降低内存。查询时先算查询点到各桶中心的距离选出 nprobe 个桶，再对桶内每个压缩向量用"距离查找表 + 分段累加"近似算距离，返回最近邻。与 HNSW 对比：IVF-PQ 内存占用远低于 HNSW（每向量 m 字节 vs 图邻接表的大开销），适合海量数据与内存受限场景；但召回率因量化近似而较低，查询延迟随 nprobe 增大而上升。HNSW 无需量化即可高召回、低延迟，但内存大、构建慢。IVF-PQ 构建快、易扩展、易量化，适合超大规模离线/在线检索；HNSW 适合内存充足、追求极致延迟与召回的服务。二者可组合（IVF 分桶后桶内用 HNSW）。

IVF-PQ 抓住"海量数据的内存瓶颈"这个主要矛盾，用聚簇缩搜索范围 + 量化缩内存，是"压缩存储 + 粗分桶"的结晶。相比 HNSW 的纯图结构，IVF-PQ 更结构化、内存更友好，是十亿级检索的事实标准，代价是召回率与延迟（需更大 nprobe / 多粗选）。