索引构建
向量数据库主要使用多种高效的索引算法来加速相似性搜索。这些算法设计用于解决"维度灾难"问题，并在高维空间中实现快速近似最近邻(ANN)搜索。以下是主要索引算法的详细介绍：
1. HNSW (Hierarchical Navigable Small World)
工作原理：
构建一个多层的图结构，顶层是稀疏连接，底层逐渐变得密集
搜索从顶层开始，通过"梯度下降"方式逐层接近目标
利用贪婪搜索+分层策略，实现对数级复杂度的查询
特点：
查询速度极快，表现出色
内存占用较大
不支持动态删除（只能标记删除）
构建时间较长但查询性能优异
被Qdrant、Milvus、Weaviate等广泛采用
2. IVF (Inverted File Index)
工作原理：
将向量空间分割成多个聚类
查询时先找到最近的聚类中心，再在相关聚类中搜索
基本上是"粗搜索+精搜索"的两阶段方法
特点：
构建速度快
内存占用适中
支持动态添加和删除
查询速度与HNSW相比略慢
Faiss和许多向量数据库都提供IVF实现
3. 积木量化 (Product Quantization, PQ)
工作原理：
将高维向量分解为多个低维子向量
对每个子空间独立进行向量量化
通过查表计算近似距离，大幅减少内存使用
特点：
显著减少内存占用
允许处理更大规模的向量集
牺牲一定精度换取效率
常与其他索引方法结合使用(如IVF-PQ)
在Faiss、Milvus等实现中广泛应用
4. LSH (局部敏感哈希)
工作原理：
设计特殊哈希函数，使相似向量更可能被哈希到同一桶
查询时只需检索相同或相近桶中的向量
通常使用多个哈希表提高查询精度
特点：
理论基础扎实
对高维数据表现良好
构建简单，易于理解
精度不如图结构方法
主要用于初筛或与其他方法结合
5. 树结构索引 (KD-Tree, Ball Tree等)
工作原理：
递归地将向量空间划分为子空间
构建树结构，每个节点代表一个划分
查询时递归遍历树找到最近邻
特点：
对低维数据(10维以下)效果好
高维空间效率急剧下降
构建简单，内存占用适中
主要用于低维场景或特殊应用
6. DiskANN
工作原理：
结合图索引和分层策略
专为磁盘存储优化的图遍历算法
使用预取机制减少随机IO
特点：
允许处理超大规模向量集
相比纯内存解决方案降低成本
牺牲部分速度换取存储扩展性
对SSD存储进行优化
Milvus和某些专门数据库采用此方案
7. 混合索引策略
现代向量数据库通常结合多种索引方法：
IVF + HNSW: 先做粗聚类，再在聚类内应用HNSW
IVF + PQ: 先聚类，再对每个聚类应用PQ压缩
HNSW + PQ: 在HNSW图上应用PQ压缩向量
多级量化: 使用多层量化策略降低内存占用
8. 过滤器加速
除了基本索引外，向量数据库还实现了各种过滤优化：
预过滤: 先应用属性过滤再做向量检索
后过滤: 先做向量检索再过滤结果
混合过滤: 同时考虑向量相似度和属性条件
位图索引: 加速标量属性的过滤操作