小程序近邻检索：基于B+树的HNSW外存实现

在小程序中，我们有许多近邻检索的场景：例如，在海量的小程序里为用户推荐潜在意图的小程序；在同样海量的小程序内容页面中，快速找到同一主题的下的资讯、视频、知识、商品等各类内容...

随着表示学习技术(Representation Learning)的不断发展，我们有了各种趁手的向量化工具，可以将海量的数据表示为高维图空间的顶点，他们的关系加上特点的距离测度则构成了图的边。那么问题就转化为如何在高维空间里实现快速近邻检索？这个问题有许多的解法，限于篇幅今天我们主要介绍基于HNSW的方法。

1. 前言

进入正题之前，我们先介绍一些基本概念，以便有更加清晰的认识。我们会先介绍一些图论的基础知识，从而引出Small World(SW)的概念和性质，在去中心搜索算法的优化上，我们引出Navigable Small World(NSW)的性质。最后，会主要介绍Malkov在基于NSW上对ANN问题的优化，即最终要介绍的HNSW算法以及在小程序近邻检索场景的改进。

2. 图的介绍

图的基本定义和性质

1、图由顶点集合V和边集合E构成，我们通常记作G=(V, E)。

2、一条记为eab的边表示顶点a和顶点b的连接，边既可以是有向的也可以是无向的。

3、顶点的邻居N是一个表示跟该顶点直连的顶点集合。

4、顶点的度表示在邻居N集合中的顶点数量，对于有向图需要将N划分为出度和入度。

5、两个顶点的距离定义为最短连接路径中边的数量dist(i,j)。

6、图的直径定义为任何顶点中最长的距离。

图的重要指标

1、 平均路径

对图中任何两个顶点可达的最短路径做加权：

2、集聚系数

集聚系数（也称群聚系数、集群系数）是用来描述图或网络中的顶点（节点）之间结集成团的程度的系数。一个节点的集聚系数等于所有与它相连的顶点相互之间所连的边的数量，除以这些顶点之间可以连出的最大边数。

图的类别

1、随机网络

特性纯粹的随机网络（如ER随机网络模型，任何两个点之间以概率p存在边的直连）有着很小的平均路径长度，但同时集聚系数也很小。

2、规则网络

规则网络中每一个顶点有相同的度，规则网络也可以是随机的，例如随机规则网络。对于纯粹的规则网络，当其中连接数量接近饱和时，集聚系数很高，平均路径长度也十分短。例如完全耦合网络（即完全图），每两个节点之间都相连，所以集聚系数是1，平均路径长度是1。

对比1和2整体上看，规则网络有着高的集聚系数，同时图的直径也非常大；随机网络有低的集聚系数，同时有较小的直径。举个下面的例子做一下随机网络和规则网络的对比：左图为规则网络，即每个点与周围k个点做连接，度为k，不难发现最长的直径正比于N/(2k)，同时对于任何一个点，其周围的点的聚集程度非常高；右图为ER随机网络模型，任何两个点之间以概率p连接，同时最多可连k个顶点，对于随机网络而言，我们可以近似的看成将图中的N个结点做k个集合的划分，每个集合即为logkN,以长连接为主，故图的直径非常小，同时集聚程度也非常低。

Watts and Strogatz的SW模型[ref1]

Watts and Strogatz 提出小世界网络可以通过对规则网络的改写，例如在规则网络的基础上，以一定的概率p改写或者增加一些顶点之间的连接。故不难发现小世界网络同时拥有规则网络和随机网络的特性，高聚合，低直径，如下图所示，但Watts and Strogatz的SW模型并没有有效去中心搜索算法。

J. Kleinberg的NSW模型[ref2]

J. Kleinberg的SW模型是适合最短路径搜索的，所以又称为Navigable Small World，他的模型如下：

      1、二维网格。

      2、曼哈顿距离作为基本计算距离。

      3、两种类型的边：短连接和长连接

            3.1、短连接即为网格的基本单元，即顶点的直连。

            3.2、长连接以如下公式做概率相连，即顶点u和顶点v之间存在边的概率与曼哈顿距离的r次方的倒数成正比。

参数r

1、 当r < dim（欧几里德空间的维数）时，我们倾向于选择距离较远的邻居（搜索算法会迅速接近目标区域，但在目标区域会放慢速度，直到最终到达目标区域）。

2、 当r > dim时，我们倾向于选择较近的邻居（如果搜索算法距离目标区域较远，搜索算法会缓慢到达目标区域，但会在附近迅速找到目标区域）。

3、 当r = 0时，均匀选择远程触点。随机图论证明每对顶点之间都存在短路径，但是没有能够找到这些路径的搜索算法。

4、 当r = dim时，算法表现出最佳性能。

参数q

1、 当q = 1（有一个远程链接）时，预期的搜索成本受O(log2N)限制。

2、 当q = k（有恒定数目的远程链接时），预期的搜索成本受O(logN)/k限制。

3、 当q = logN，预期搜索成本受O(logN)。

不难发现长连接的数量或者质量会十分影响搜索算法的性能，后面会提到长连接又可以称为高速公路。上面的NSW网络的性质十分的好用，高集聚，低直径，如果我们把近似近邻图放在NSW不是就可以在O(logN)的复杂度下做一些检索，而不是暴力的O(N2)。下面的章节会优先对ANN做一下回顾。

3. ANN介绍

NNG和ANN

为了引出近似近邻图(Approximate Nearest Neighbor Graph ,后记作ANN）的概念，我们先看看什么是近邻图(Nearest Neighbor Graph , 后记作NNG)，一般NNG分为两种，一种是k-NNG，一种是ε-NNG。

k-NNG的定义

简单来讲，就是在有向图G上，图中每个节点只与距离它最近的k个节点建立连接，距离的度量可以是余弦，欧几里得距离等。

ε-NNG的定义

与k-NNG的区别在于度量的标准不同，ε-NNG就是通过引入距离阈值来选择每个点与其附近周围的关系。

两者的比较与区别

k-NNG选择每个点最近的k个点来作为与周围点的关系，通常情况下十分有效，ε-NNG通过阈值的选择，阈值的选择有时候会很容易导致它存在“孤岛”，不适用于许多情况，后面的介绍主要围绕前者展开。

前面介绍的k-NNG和ε-NNG，如果严格按照这个约定去建立关系，这其实是一种ENN(Exact Nearest Neighbor Graph)，对于海量高维数据，如果要建立这样一个ENN，计算消耗是巨大的，通常计算的复杂度在O(〖dn〗^2)，其中n为数据量大小，d为每个数据的维度（不考虑Top k）。正因此，能不能存在一些算法让构建图算法复杂度计算量稍微小一点，不要求百分百精确呢（后面会讲到，就算不是百分百精确，我们也可以用图上搜索算法让结果尽可能精确）。于是，有很多的研究是集中在如何降低复杂度并尽可能与ENN接近，同时配合适合的ANNS(Approximate Nearest neighbor search)算法能得到几乎完美的匹配结果。

ANNS

为了便于读者理解，假设已经有了一个构建好的ANN，输入一个向量，怎么在图上找到与该向量最接近的向量节点呢？

NNS的目标是在NNG上面找到距离输入q最接近的一些向量，ANNS同样如此，只不过是在ANN上进行查询，通常的ANNS需要配合ANN的构建算法进行适配，但核心的思想不变，ANNS通过在ANN上随机选择一些种子作为出发的点，分别对这些点广度优先或者深度优先的遍历，不断与q计算距离，最后得到最接近的K个点即作为输入q的返回结果。通常来讲，像KD Tree，RP Tree，K-means Tree (Balanced K-means Tree)，Randomized KD Trees (NKD-Tree , RKD-Tree , PKD-Tree)，Ball Tree, PCA Tree,  Spill Tree, VP Tree,  TP Tree, ……等等，宏观上可以理解成是对空间的切分方法和切分函数不同，同时搜索的时候也是根据对应的切分函数寻找合适的查找函数来不断进行搜索。上面主要介绍了ANN图的构建和搜索的一些常用算法，下面主要介绍ANN如何和NSW做结合，同时主要介绍HNSW的算法的一些实现和优化点。

4.B+树

首先我们来简单认识一下什么是B树和B+树。

一个m阶的B树结构的定义为：

1 每个结点至多有m个子结点。

2 除根结点和叶结点外，其他结点的至少有[m/2]个子结点，即所谓的半满到全满的状态。

3 根结点至少有两个子结点，除非是根结点为叶子节点。

4 所有的叶结点都在同一层。

5 有k个子结点的非根结点包含k-1个关键字，如上图中的23，30这个结点有3个子结点，他们的关键字为2个。

B树的一些重要性质，相关记录放在一个磁盘页，利用了局部访问原理。B树保证一定比例的结点是满的，减少层数。

那B+树对比B树有什么特别之处呢？

在结构定义上，B+树基本跟B树一致，区别在于，每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

B+树是mysql最常用的一个索引结构。如果说B树是有序数组加平衡多叉树组成的，那B+树就是有序数组链表加平衡多叉树的实现。B+树相比其他的优势在于动态索引，更少的IO次数（更少的层数），区间利用率大大提升等优点。这里将B+树作为kv外存，主要的优化是，我们会为每一个图中的顶点分配一个独一无二的node ID，之前都是直接将其放在内存用一个map绑定id和向量的关系，而这里会将向量压缩之后，以ID作为B+树构建索引依据，指向向量压缩的外存地址，这样就能将原本在内存的向量用于外存存储。

根据node ID存储到外存：

根据node ID读取向量:

5.HNSW[ref3]

先讲一下对HNSW宏观理解，HNSW其实构建的是L-ANN的结构，L指图的层数，层与层之间存在连接，查询的时候L层分为两个阶段，阶段1为ep的查找，阶段2为通过ep寻找每一层的最近点。后面会看到代码实现的时候，其实每一个点会跟每一层的部分点都会有连接，只不过最底层连接的最多，往上的话每一层按照密度概率函数不断减少。

参数

先说明参数的意义：

HNSW：指我们构建的L层的ANN GRAPH。

q：需要插入HNSW的向量点。

M：新插入的点在第三阶段每一层建立的连接数。

Mmax：每一层每个点最多的连接数。

efConstruction：与某个点最近的动态候选列表。

INSERT

首先是图的构建阶段，也就是INSERT，下面把他分成四阶段：

第一阶段：主要是参数初始化。具体包括entry point（后面简称ep）的选择，ep对应的历史最高层L，密度算法得到的当前点能投影的最高层l层，以及第二阶段（即ep在L层到l+1层）和第三阶段（及l层到0层）的分界。

第二阶段：主要目的是寻找在L层到l+1层中与q最接近的向量作为最新的ep。通过第一阶段划分的L层到l+1层中，用SEARCH-LAYER的算法（下面会介绍本质上就是从L层到l+1层上不断通过广度优先找到与q距离近的点作为ep）逐层寻找与q距离最近的向量，即在L层到l+1层中确定与q最近的向量作为ep。

第三阶段：主要从l到0层上，需要建立q与各个层的距离q最近点的边的关系,具体做法是SEARCH-LAYER在l到0层上每个层上都得到与q最近的候选集W，同时SELECT-NEIGHBORS做减枝，具体为限制W候选数量为M个，然后使得q和这M个做双向连接，同时更新这M个邻居点中如果最大连接数数超过Mmax，则需要裁剪该点放入边，具体是取Mmax个与q最小的距离建立连接。后面会详细介绍SEARCH-LAYER和SELECT-NEIGHBORS算法。

第四阶段：如果密度算法得到的l是大于上一个ep的L，那么将新插入的点q作为ep，同时更新L为算法密度得到的l。

SEARCH-LAYER

该算法的主要目的是在第lc层上从ep出发扩散，找到|ef|个在该层与q距离最小的点集合ef。主要思想如下，首先以ep作为W集合和C集合，以及visited集合v。从C集合中选取距离q最近的点c，从W集合中选取距离q最远的点f(实际使用中可以用最大优先队列和最小优先队列来存储距离，降低复杂度),如果c点的距离比f还远，条件终结直接返回；如果c的距离更近，会遍历c的邻居，如果e距离q的距离比f的小，会加入C集合中，同时不断更新W中的点。

SELECT-NEIGHBORS

该算法的主要作用是筛选候选集合的数量，实现有两种方式：

一种就是在C中直接取距离q最近的M个点与q建立连接的。

另外一种启发式的算法如下：在lc层上，首先对C集合做一下扩充，具体是对于C集合中的每个点，将他们的邻居也加到C集合上，重新筛一遍距离q最近的点集合R。

6. 基于B+树的HNSW实现

目前流行的HNSW开源基本都是全内存的实现，在海量高维的情况将占据非常大的内存，对于小程序近邻检索场景来说将是较大的开销。我们考虑将边的关系的索引放内存，然后顶点的向量的存储采用B+树作为kv外存。同时查询和建索引的时候都支持两种模式，即全内存和边内存顶点向量外存，可以根据具体场景来筛选。具体复现的下面几个函数：

add函数

add函数对应伪代码的INSERT函数，主要逻辑跟伪代码是一样的，如下所示支持建索引支持fast和slow两种模式，slow模式情况下，每次的顶点向量都会通过B+树从外存读取，fast模式下会用一个map在内存映射全面的顶点id和向量关系。

search_at_layer函数

search_at_layer函数对应SEARCH-LAYER的代码，如下fast模式我们会直接用id_to_vec的内存信息，slow模式下会用get_point方法通过B+树从外存读取。

get_neighbors_by_heuristic_closest_last函数

get_neighbors_by_heuristic_closest_last函数对应SELECT-NEIGHBORS-HEURISTIC部分的实现：主要是确定候选之后再进行一次对候选的邻居做一次更深入的筛选，同样我们这里也支持fast和slow模式：

实验表明，内外存方式对于查询阶段速度影响不大，但内存占用率大大降低。

7. REFERENCE

• Watts D J, Strogatz S H. Collective dynamics of ‘small-world’networks[J]. nature, 1998, 393(6684): 440-442.
• Kleinberg J M. Navigation in a small world[J]. Nature, 2000, 406(6798): 845-845.
• Malkov Y A, Yashunin D A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs[J]. IEEE transactions on pattern analysis and machine intelligence, 2018.
• Navigable Small-World Networks, Based on slides by Šarūnas Girdzijauskas