我们知道mysql一般的索引结构都是通过B+ tree实现。一般索引都是通过索引结构可以快速准确定位需要的数据。而向量索引就是快速查询与给定向量的最相似的N个向量。所以
- 向量索引主要是一个近似搜索，而非一般索引的准确比对；
- 向量在多维度向量空间上的点，而不像传统数据可以直接比大小，所以传统索引结构可以利用大小比较快速定位；
- 向量检索的大部分场景都是返回与该元素相似的topk个元素，而相似度（即距离相近的向量）可以是欧拉距离，也可以是夹角余弦距离。目前最大的问题就是如何快速找到相似的k个元素
如果遍历所有向量，比较获取相似度最高的k个向量，就类似全部扫描方式，也就没有索引的事了。索引就是一种可以快速查找的数据结构。
一、HNSW，分层近邻图索引
HNSW，即Hierarchical Navigable Small World graphs（分层-可导航-小世界-图）的缩写，可以说是在工业界影响力最大的基于图的近似最近邻搜索算法（Approximate Nearest Neighbor，ANN）。下面是参考网上的一些理解，列举在下面：
引子
问题：假设我们有一个海量的图像库。给定一张查询图像，如何从海量的图像库中找到最相似的K张图像？
我们可以把每个图像映射成一个向量E，假设在余弦相似度下这个Embeddding很好的度量图像间的相似度。那么，一个可能胚胎小宝宝都能想到的方法是：我们可以把查询图片的E和库里面所有图像的E计算相似度，并返回最相似的K个图像。
这就是我们熟知的KNN（K Nearest Neighbor）算法，它的时间复杂度随着库的规模变大线性递增。通常情况下，即便使用GPU也无法承受百万以上量级的库。因此，对其进行优化是必须的。
对KNN进行优化，有两个思路：
- 减少相似度的计算量;
- 减少计算相似度的次数。
ANN（Approximate Nearest Neighbor）的提出就是通过优化后者从而加速搜索速度。这里ANN返回的Top-K不是真的Top-K，只是近似的Top-K。而基于图的ANN，目的在于：对库中的向量构建一个图，使得我们只需要遍历很小的一部分子图，即可返回Top-K搜索结果。因此这里构建图的方式是关键中的关键！
什么样的图适合检索？
什么样的图适合检索？要回答这个问题，我们首先得了解怎么在图上进行搜索。就像朴素的广度优先搜索（BFS）、深度优先搜索（DFS）那样，我们通常是顺着节点的邻居去搜索的。其实这就是图方法最本质的优势：只要图设计得足够好，我们“无脑”顺着图走几步就能到达不错的解。
- 存在一个搜索入口结点，从入口结点开始搜索
- 沿着入口结点一直往下搜，同时维护和查询节点最近的K个节点
- 当某轮搜索的结果不改变Top-K的结果时停止搜索
基于这个朴素的检索思路，我们对图的属性有如下要求:
● 最优性：检索结束条件达到时，检索结果尽可能最优，否则精度损失太多，速度优化意义不大。
● 小世界：在有限的几步内找到最优解，也就是说我们要求从入口只经过几阶邻居就能找到全局最近的节点。值得注意的是，小世界的属性包含了全局联通性。
● 每个节点的邻居有上限：如果每个节点的邻居数量非常庞大，搜几阶邻居就几乎覆盖全图，那也是没有意义的。
如果用最近邻建图会如何？
如果我们每个结点都用库中跟该节点距离最近的M个结点作为它的邻居，且不说建图成本，这样联通性都是无法保证的，更不用说小世界了。即便运气很好，这样构建出来的图是联通的，如果我们查询结点和入口结点相似度很低，可想而知要搜到最优点效率有多低。
如果随机建图如何？
如果我们对每个结点随机连M个邻居的话，要么搜索条件很快就会达到，要么搜很久也搜不到最优解。也就是说最优性和小世界都无法保证的。甚至联通性都是无法保证的。
因此，一个好图构图方式似乎是：结点的邻居既有相似度高的，又有相似度低的。其中，相似度低的边，我们称之为高速公路，它连接了相似结点簇来提高搜索效率。这样图就同时兼顾了Exploration（探索更大可能性）和Exploitation（已知解里找最优）。
NSW
NSW，即Navigable Small World graphs。这是一个简单到让人怀疑正确性的构图方式：我们把库中的结点随机插入图中，每次插入结点的时候都找图中和被插入结点最近的M个每个结点连边。这样就完事了？这样就完事了！
这样构图有什么好处呢？
- 这样是能保证联通性的：假设插入结点前，图是联通的；插入结点后，因为新插入结点和插入前的图连上了边，所以插入后也是联通的。又初始一个点的时候是联通的，所以最终整个图是联通的。
- 由于插入点找最近邻连边的时候，图是不完整的，所以即便找了最近邻，也存在较远的点。这某种意义上在拟合小世界的属性。
- 构图非常结点，插入结点和搜索过程浑然一体：插入结点的时候，先搜出M个节点，然后连上边。
可是，这样的做法缺点也是明显的： - 实际上小世界属性依然不能保证。
- 对节点插入的顺是不公平的：前面插入的结点“高速公路”比较多；后面插入结点邻居都有很接近。
如何选择入口结点是个问题。原文的做法大约是，随机取若干个结点作为入口，搜多次，多次结果合在一起取top k。orz...
HNSW
如果我们分层去搜呢？先粗略地搜，然后再精细地搜。整个过程就像是，我们先初步定位，逐步把图放大，持续更精细地定位。我们可以这样构图，层的编号越大越接近顶层：
- 多层的NSW，每一层都是NSW；
- 顶层包含少量的点，逐层结点数倍数递增，底层包含所有点；
- 下一层包含所有上一层的结点，下一层搜索的入口是上一层的结点中的一个。因此结点i在第j层出现，那它在0～j层均出现。
搜索过程
这样，由于顶层的结点数量比较少，能够保证充分的可能性探索（Exploration）。我们搜索过程如下：
- 从顶层的固定入口开始搜；
- 每一层搜索都返回Top-K的结果，当前层搜到最近的结点作为下一层搜索的入口结点，继续搜下去；
- 最后一层搜到的Top-k结果作为最终搜索结果。
插入结点过程
有了搜索方法，插入方式跟NSW类似，我们搜一遍，从搜索结果中选邻居连上边就好了，这里原文提出两种选邻居方法：1.直接在返回搜索结果中选Top-K；2. 在搜索返回结果中，对返回结果扩一阶邻居计算相似度和原来结果放一起取top-K。
最后只剩下一个问题没解决了，怎么决定一个结点最高出现在哪层呢？答案是：随机！但是要注意好分布。也就是说，每次插入一个结点，我们都取一个随机数，随机数的数值代表了这个结点最高出现在哪一层：
其中，mL控制层数的参数，注意这里控制不了最高层数！
二、MariaDB向量索引实现分析
mariadb就是使用HNSW使用向量索引。下面具体来说明一下vector index的实现。向量索引实现在MariaDB的server层而非storage层（InnoDB）。InnoDB并不感知vector index的存在。一个vector index对应一张内部表。所以MariaDB的vector index更准确的表达是：vector index on B+Tree index。
创建向量索引
当用户使用如下语法：
CREATE TABLE embeddings (doc_id BIGINT UNSIGNED PRIMARY KEY, embedding VECTOR(1536) NOT NULL,VECTOR INDEX (embedding) M=8 DISTANCE=cosine);
mariadb解析SQl就会发现vector index，然后在创建表的同时，调用mhnsw_hlindex_table_def 创建索引辅助表，具体调用关系如下：
ha_create_table() // handler接口
->ha_create_table_from_share()
->ha_create() // 进入引擎层创建
->if (share.hlindexes()) // 如果存在vector index
{
sql= mhnsw_hlindex_table_def(thd, ref_length) // 构建索引辅助表sql
index_share.init_from_sql_statement_string() // 使用sql创建table_share
ha_create_table_from_share() // 创建索引辅助表
}
下面我们看一下vector index的索引辅助表具体sql情况
const LEX_CSTRING mhnsw_hlindex_table_def(THD *thd, uint ref_length)
{
const char templ[]="CREATE TABLE i ( "
" layer tinyint not null, "
" tref varbinary(%u), "
" vec blob not null, "
" neighbors blob not null, "
" unique (tref), "
" key (layer)) ";
size_t len= sizeof(templ) + 32;
char *s= thd->alloc(len);
len= my_snprintf(s, len, templ, ref_length);
return {s, len};
}
可以看到，其表文件后缀为#i#1，创建的辅助表结构如下
从上述分析上看，本质上向量索引就是基于HNSW索引结构建立了一个辅助表。
索引插入数据
当主表插入数据时，相应的触发调用mhnsw_insert函数，对vector索引辅助表进行数据插入，具体调用栈如下：
handler::ha_write_row() // 插入主表
->TABLE::hlindexes_on_insert()
->mhnsw_insert() // 插入vector索引辅助表
下面具体看一下辅助表的插入过程
// 1、获取辅助表TABLE结构体，向量信息，请进行参数检验
TABLE *graph= table->hlindex;
String buf, *res= vec_field->val_str(&buf);
DBUG_ASSERT(graph);
DBUG_ASSERT(keyinfo->algorithm == HA_KEY_ALG_VECTOR);
DBUG_ASSERT(keyinfo->usable_key_parts == 1);
DBUG_ASSERT(vec_field->binary());
// 2、获取原始表当前行信息
table->file->position(table->record[0]);
// 3、获取或者初始化HNSW图上下文，类似innodb trx事务上小文信息
// 如果是第一次插入，则初始化图结构，并直接插入第一个节点，设置为入口节点（start）
int err= MHNSW_Share::acquire(&ctx, table, true);
SCOPE_EXIT([ctx, table](){ ctx->release(table); });
if (err)
{
if (err != HA_ERR_END_OF_FILE)
return err;
// First insert!
ctx->set_lengths(res->length());
FVectorNode *target= new (ctx->alloc_node())
FVectorNode(ctx, table->file->ref, 0, res->ptr());
if (!((err= target->save(graph)))) // 在索引辅助表中存储一个记录
ctx->start= target; // 设置搜索开发位置
return err;
}
// 4、检查向量长度一致
if (ctx->byte_len != res->length())
return my_errno= HA_ERR_CRASHED;
// 5、分层插入，这是HNSW的核心，即随机决定新节点的最大层级（target_layer），层级越高，概率月底
const double NORMALIZATION_FACTOR= 1 / std::log(ctx->M);
double log= -std::log(my_rnd(&thd->rand)) * NORMALIZATION_FACTOR;
const uint8_t max_layer= candidates.links[0]->max_layer;
uint8_t target_layer= std::min<uint8_t>(static_cast<uint8_t>(std::floor(log)), max_layer + 1);
// 6、基于原始行，创建一个新的节点，这里
FVectorNode *target= new (ctx->alloc_node())
FVectorNode(ctx, table->file->ref, target_layer, res->ptr());
/* 7、分层插入与邻居搜索，从最高层到最低层，逐层搜索最优插入位置和邻居节点。
search_layer：在指定层查找与新向量最接近的节点。
select_neighbors：从候选节点中选择最优邻居，建立连接。
*/
if (int err= graph->file->ha_rnd_init(0))
return err;
SCOPE_EXIT([graph](){ graph->file->ha_rnd_end(); });
for (cur_layer= max_layer; cur_layer > target_layer; cur_layer--)
{
if (int err= search_layer(ctx, graph, target->vec, NEAREST,
1, cur_layer, &candidates, false))
return err;
}
for (; cur_layer >= 0; cur_layer--)
{
uint max_neighbors= ctx->max_neighbors(cur_layer);
if (int err= search_layer(ctx, graph, target->vec, NEAREST,
max_neighbors, cur_layer, &candidates, true))
return err;
if (int err= select_neighbors(ctx, graph, cur_layer, *target, candidates,
0, max_neighbors))
return err;
}
/* 8、保持新节点，从save实现可以看出：
layer 存储的是之前确定的最大层级
tref 存储的是原始行信息
vec 存储的是原始向量
neighbors 存储格式为从0层到最大层，每层num+邻居向量
*/
if (int err= target->save(graph))
return err;
// 9、如果当前节点在最高层，更新入口
if (target_layer > max_layer)
ctx->start= target;
// 10、更新二阶邻居
for (cur_layer= target_layer; cur_layer >= 0; cur_layer--)
{
if (int err= update_second_degree_neighbors(ctx, graph, cur_layer, target))
return err;
}
从上述向量索引插入过程我们可以知道，其节点是分层计算邻居节点，并且存储了相应的邻居信息。具体可以看下图所示。
向量索引查询
向量索引查询执行典型过程依次调用mhnsw_read_first，mhnsw_read_next，mhnsw_read_end。三个函数最重要的是第一个函数mhnsw_read_first，内部包含初始化向量查询上下文以及定位到第一个最近邻结果。后面函数mhnsw_read_next即依次读取即可。下面重点看看mhnsw_read_first函数的主要实现过程。
// 1、获取基本信息
THD *thd= table->in_use;
TABLE *graph= table->hlindex;
// 距离计算函数
auto *fun= static_cast<Item_func_vec_distance_common*>(dist->real_item());
limit= std::min<ulonglong>(limit, max_ef);
// 2、初始化候选邻居
Neighborhood candidates;
candidates.init(thd->alloc<FVectorNode*>(limit + 7), limit);
// 3、构造一个向量对象，便于距离计算
const longlong max_layer= candidates.links[0]->max_layer;
auto target= FVector::create(ctx->metric, thd->alloc(FVector::alloc_size(ctx->vec_len)),
res->ptr(), res->length());
// 4、分层搜索，每一层，遍历candidate所有邻居，选出最优的1个，下降到下一层继续，直到0层
// 每层只保留最优候选节点，加速收敛
for (size_t cur_layer= max_layer; cur_layer > 0; cur_layer--)
{
if (int err= search_layer(ctx, graph, target, NEAREST,
1, cur_layer, &candidates, false))
{
graph->file->ha_rnd_end();
return err;
}
}
// 5、底层（0层）查找最近邻
if (int err= search_layer(ctx, graph, target, NEAREST,
static_cast<uint>(limit), 0, &candidates, false))
{
graph->file->ha_rnd_end();
return err;
}
// 6、保存结果，方便后续next函数获取
auto result= new (thd->mem_root) Search_context(&candidates, ctx, target);
graph->context= result;
// 7、返回第一个结果
return mhnsw_read_next(table);
