一.向量索引1.什么是数据库中的向量在数据库中一个向量通常表现为一个浮点数数组(是对于数据的标识)。语义相近的对象其向量在空间中通常也更接近。例:[0.12, -0.98, 0.45, 0.67]2.常见距离度量(1)欧氏距离(距离越小越相似)d(x, y) sqrt(Σ(xᵢ - yᵢ)²)(2)曼哈顿距离(距离越小越相似)d(x, y) Σ|xᵢ - yᵢ|(3)余弦相似度(余弦相似度越大方向越接近。)cos(x,y) (x · y) / (|x| |y|)二.精确KNN与近似KNN1.暴力扫描:读取每个向量计算它与查询向量的距离维护当前最相似的K个结果。优缺点:这种方法结果准确但数据量大时速度较慢。如果有N个向量每个向量有D个维度计算成本大致为O(ND)2.近似最近较(ANN)ANN不保证返回绝对最优的结果但可以显著减少搜索时间。核心思想:牺牲少量召回率,换取更低的查询延迟三.向量索引的常见方法1.空间划分:把向量空间划分为多个区域2.局部敏感哈希(LSH)相似对象 → 大概率哈希到相同桶 不相似对象 → 大概率哈希到不同桶优点查询速度快;可用于高维近似搜索缺点需要多个哈希函数或多个哈希表;召回率和空间使用之间需要权衡;查询结果是近似的3.倒排文件索引(IVF)核心流程是使用聚类算法把向量分成多个簇(按照相似度分)每个簇保存一个中心点查询时先找距离最近的若干簇只在这些簇内部搜索。4.乘积量化(PQ)基本思想把一个高维向量拆成多个子向量为每个子空间建立聚类中心用聚类中心编号代替原始浮点数。优点大幅节省空间;减少内存访问;可使用近似距离计算缺点会损失精度;需要额外训练和构建过程5.HNSW-一种图索引它把向量看成图中的节点每个节点连接若干相近节点节点A ↔ 节点B ↔ 节点C搜索时从入口节点开始移动到距离查询向量更近的邻居到达当前层的局部最优位置进入下一层最后在底层进行更精细搜索。优点查询速度快;召回率通常较高;适合高维向量缺点内存占用较大;插入和删除成本较高;动态更新比普通B树复杂四.预过滤和后过滤1.预过滤:先过滤在进行向量检索优点搜索范围小;结果满足过滤条件缺点过滤条件选择性不好时效果有限;需要同时维护标量索引和向量索引2.后过滤:先向量检索在进行过滤五.反向索引1.概念:主要用于全文搜索,不保存文档-关键字,反过来保存关键字-文档例:数据库 → 文档1、文档2 索引 → 文档1、文档3 查询 → 文档2 优化 → 文档32.倒排列表:每一个词都对应一个倒排列表3.TF-IDF和相关性排序反向索引不仅用于判断文档是否包含关键词还要对结果排序。(1)TF词频.表示一个词在当前文档中出现的频率。(2)IDF:逆文档频率.用于降低常见词的权重(3) TF-IDF:试图衡量某词在文章当中的重要程度六.过滤器1.过滤器的主要用途不是返回完整结果而是快速判断某个元素一定不存在 或 某个元素可能存在如果过滤器说“不存在” → 一定不存在 如果过滤器说“存在” → 可能存在需要进一步检查2.Bloom Filter(1)概念:Bloom Filter由一个位数组;多个哈希函数组成(2)插入元素用多个哈希函数计算多个位置将这些位置设为1。(3)查询元素计算相同的多个位置如果其中一个位置为0则元素一定不存在如果全部为1则元素可能存在。优点空间占用很小;查询速度快;适合判断“不存在”;不保存完整元素缺点存在假阳性;不支持精确删除;插入越多误判率越高;必须合理选择位数组大小和哈希函数数量(4)为什么该过滤器不能直接删除假设元素A.B都将5号位置设置为1,删除A时将5号位置请0,此时B任然有可能存在3.Cuckoo Filter:通常使用类似Cuckoo Hashing的思想保存元素指纹完整键 → 短指纹 fingerprint优点支持删除;查询速度快;某些情况下比Bloom Filter更灵活缺点仍然可能出现假阳性;高装载率下插入可能失败;需要处理元素迁移4.过滤器在数据库当中的用途(1).避免无意义的磁盘读取查询 key 100 → 过滤器判断该页一定没有100 → 不读取该页(2) LSM树中的SSTable,读取某个键时可以先查询每个SSTable的Bloom FilterSSTable A一定不存在 SSTable B可能存在 SSTable C一定不存在只读取B避免扫描A和C。(3)分布式系统中的远程访问优化如果过滤器判断某个节点一定没有数据就不必发起网络请求。七.三类索引的对比附