Milvus 索引类型详细介绍

Milvus 索引类型详细介绍概述Milvus 是一个高性能的向量数据库支持多种索引类型来优化向量检索性能。不同的索引类型适用于不同的应用场景在查询速度、精度和资源消耗之间提供不同的权衡。本文档详细介绍 Milvus 中的主要索引类型及其适用场景。IVF (Inverted File) 索引适用场景大规模数据集通常超过 100 万向量需要在查询速度和精度之间取得平衡的场景内存资源相对充足的环境特点聚类基础: 使用 K-means 等聚类算法将向量空间划分为多个聚类倒排结构: 为每个聚类维护一个倒排列表包含属于该聚类的所有向量查询可控: 通过调整聚类数量nlist控制搜索精度和速度分层搜索: 首先在聚类中心间进行搜索然后在相关聚类内进行精确匹配工作原理IVF 索引的工作过程可以分为两个阶段构建阶段:使用 K-means 算法将向量空间划分为nlistnlistnlist个聚类计算每个向量的聚类中心距离将向量分配到最近的聚类中查询阶段:计算查询向量与所有聚类中心的距离选择距离最近的nprobenprobenprobe个聚类仅在这些聚类中搜索最相似的向量数学表达给定查询向量qqq和聚类中心C{c1,c2,...,cnlist}C \{c_1, c_2, ..., c_{nlist}\}C{c1​,c2​,...,cnlist​}IVF 的搜索过程为计算距离d(q,ci)∣∣q−ci∣∣2d(q, c_i) ||q - c_i||_2d(q,ci​)∣∣q−ci​∣∣2​fori1,2,...,nlisti 1, 2, ..., nlisti1,2,...,nlist选择聚类选择nprobenprobenprobe个距离最小的聚类在选定聚类中搜索argminv∈S∣∣q−v∣∣2argmin_{v \in S} ||q - v||_2argminv∈S​∣∣q−v∣∣2​其中SSS是选定聚类中的向量集合典型参数nlist128: 聚类数量影响索引大小和查询精度nprobe10: 搜索时检查的聚类数量平衡查询速度和精度metric_typeL2: 欧几里得距离度量优势查询速度快尤其在大数据集上内存占用相对合理参数调优灵活可根据需求调整精度劣势需要额外的聚类计算在某些分布不均匀的数据集上可能表现不佳参数选择对性能影响较大HNSW (Hierarchical Navigable Small World) 索引适用场景高维向量数据通常 128 维对查询精度要求较高的场景实时性要求高的应用内存资源充足的环境特点分层图结构: 多层导航小世界图顶层连接稀疏底层连接密集精度优先: 相比 IVF通常提供更高的查询精度渐进式搜索: 从顶层开始逐层向下搜索减少不必要的计算动态构建: 支持增量式添加新节点工作原理HNSW 索引构建一个多层图结构图构建:多层图L0L_0L0​最底层到LmaxL_{max}Lmax​最顶层每层使用不同的连接概率使用启发式算法选择连接节点查询过程:从顶层开始搜索在每层找到最近的邻居将这些邻居作为下一层的搜索起点逐层向下直到最底层数学表达HNSW 的搜索过程可以表示为对于查询向量qqq和图G(V,E)G (V, E)G(V,E)从顶层LmaxL_{max}Lmax​开始在当前层lll中找到qqq的最近邻居集合Nl(q)N_l(q)Nl​(q)将Nl(q)N_l(q)Nl​(q)作为l−1l-1l−1层的搜索起点重复直到到达最底层L0L_0L0​在L0L_0L0​中找到最终的最相似向量典型参数M16: 每个节点的最大连接数影响图的密度ef200: 构建时的候选列表大小影响索引质量ef_search100: 搜索时的候选列表大小影响查询精度metric_typeIP: 内积距离度量优势查询精度高尤其在高维数据上表现优秀查询速度快适合实时应用支持动态插入和更新对数据分布不敏感劣势内存占用较大特别是对于大规模数据集构建时间较长参数调优相对复杂ANNOY (Approximate Nearest Neighbors Oh Yeah) 索引适用场景中等规模数据集10万-1000万向量内存敏感的环境需要快速构建索引的场景对查询精度要求不是极端严格的场景特点随机森林结构: 使用多个随机树构建森林低内存占用: 相比 HNSW内存消耗更少快速构建: 构建速度快适合频繁重建索引可扩展性好: 支持并行构建工作原理ANNOY 使用随机森林来近似最近邻搜索树构建:随机选择两个点作为分割超平面递归地将空间分割成子空间构建n_treesn\_treesn_trees棵随机树查询过程:在每棵树中搜索到叶子节点收集所有叶子节点中的候选向量计算这些候选向量与查询向量的距离选择最相似的向量数学表达给定n_treesn\_treesn_trees棵随机树T1,T2,...,Tn_treesT_1, T_2, ..., T_{n\_trees}T1​,T2​,...,Tn_trees​查询过程为对于每棵树TiT_iTi​找到包含查询向量qqq的叶子节点Li(q)L_i(q)Li​(q)收集候选集合C⋃i1n_treesLi(q)C \bigcup_{i1}^{n\_trees} L_i(q)C⋃i1n_trees​Li​(q)计算距离并排序result{v∈C∣∣∣q−v∣∣2}result \{v \in C | ||q - v||_2\}result{v∈C∣∣∣q−v∣∣2​}sorted by distance返回前kkk个最相似的向量典型参数n_trees10: 随机树的数量影响精度和内存build_speedbalanced: 构建速度与精度的平衡search_k100: 搜索时检查的候选数量metric_typecosine: 余弦相似度度量优势内存占用低适合内存受限环境构建速度快支持频繁重建算法简单易于理解和实现支持多种距离度量劣势查询精度相对较低特别是在高维数据上对参数选择较为敏感不支持动态插入需要重建索引FLAT 索引适用场景小规模数据集通常 10 万向量需要 100% 召回率的场景查询次数较少的场景作为基准测试使用特点暴力搜索: 对所有向量进行线性扫描精确匹配: 保证找到真正的最近邻简单直接: 无需复杂的索引结构零调优: 不需要调整复杂参数工作原理FLAT 索引的工作原理非常简单直接构建阶段:将所有向量存储在内存中无需额外的索引结构查询阶段:计算查询向量与所有存储向量的距离按距离排序返回最相似的kkk个向量数学表达给定查询向量qqq和向量集合V{v1,v2,...,vn}V \{v_1, v_2, ..., v_n\}V{v1​,v2​,...,vn​}FLAT 搜索过程为计算所有距离di∣∣q−vi∣∣2d_i ||q - v_i||_2di​∣∣q−vi​∣∣2​fori1,2,...,ni 1, 2, ..., ni1,2,...,n排序(d1,v1),(d2,v2),...,(dn,vn)(d_1, v_1), (d_2, v_2), ..., (d_n, v_n)(d1​,v1​),(d2​,v2​),...,(dn​,vn​)sorted bydid_idi​返回前kkk个结果{(di,vi)∣i1,2,...,k}\{(d_i, v_i) | i 1, 2, ..., k\}{(di​,vi​)∣i1,2,...,k}典型参数无需特殊参数是最简单的索引类型优势保证 100% 召回率精度最高实现简单无复杂参数适合小数据集和基准测试查询结果可预测且稳定劣势查询速度慢时间复杂度为O(n)O(n)O(n)内存占用随数据量线性增长不适合大规模数据集无法利用数据的空间局部性DISKANN (Disk-based ANN) 索引适用场景超大规模数据集通常 1 亿向量内存资源受限的环境需要持久化存储的场景对查询延迟有一定容忍度的应用特点磁盘驻留: 主要索引结构存储在磁盘上内存缓存: 使用内存缓存热点数据分层设计: 结合内存和磁盘的优势减少内存依赖: 大幅降低内存使用量工作原理DISKANN 索引采用分层存储策略索引结构:将向量数据分块存储每个块构建内存中的子索引使用布隆过滤器快速判断向量是否存在查询过程:首先在内存缓存中搜索如果未命中访问磁盘上的索引块使用布隆过滤器跳过不相关的块在相关块中进行精确搜索数学表达DISKANN 的搜索过程涉及多个层次缓存层:检查查询向量qqq是否在缓存CCC中如果q∈Cq \in Cq∈C返回缓存结果索引层:使用布隆过滤器BBB判断可能包含qqq的块对于候选块BiB_iBi​执行resultisearch(Bi,q)result_i search(B_i, q)resulti​search(Bi​,q)合并所有结果result⋃iresultiresult \bigcup_i result_iresult⋃i​resulti​磁盘层:对于未缓存的块从磁盘读取执行精确搜索并更新缓存典型参数search_cache_size2GB: 搜索缓存大小index_cache_size4GB: 索引缓存大小num_threads8: 并行搜索线程数filter_ratio0.1: 过滤器过滤比例优势支持超大规模数据集内存占用低利用磁盘存储成本优势通过缓存机制保证热点数据快速访问适合内存受限的部署环境劣势查询延迟较高受磁盘 I/O 影响缓存命中率对性能影响很大实现复杂调优难度大不适合对延迟敏感的应用索引类型对比总结索引类型适用数据规模查询速度查询精度内存占用构建时间动态支持FLAT 10万慢100%低最快不支持ANNOY10万-1000万中等中等低快不支持IVF100万-1亿快高-中中等中等支持HNSW10万-1亿快高高慢支持DISKANN 1亿中等-慢高低-中慢支持选择建议小数据集 高精度需求: 选择 FLAT中等数据集 内存敏感: 选择 ANNOY大规模数据 平衡需求: 选择 IVF高维数据 高精度: 选择 HNSW超大数据 内存受限: 选择 DISKANN性能优化建议IVF: 合理设置nlist和nprobe参数HNSW: 调整M和ef参数以平衡精度和速度ANNOY: 增加n_trees提高精度但会增加内存DISKANN: 优化缓存大小和过滤策略FLAT: 仅用于基准测试和小数据集结论Milvus 提供了丰富的索引类型来满足不同应用场景的需求。选择合适的索引类型需要在查询速度、精度、内存占用和构建时间之间进行权衡。理解各种索引的特点和适用场景对于构建高性能向量检索系统至关重要。在实际应用中建议先使用小规模数据进行测试比较不同索引类型的性能表现然后根据实际需求选择最适合的索引类型。同时合理的参数调优可以显著提升索引性能达到最佳的使用效果。