第一篇里面简要的提到了索引如何创建，并留下一个索引要新开一篇的坑。实际在学习的过程中来看，要理解Milvus全部的索引，开一篇都是不够的。所以这一篇只是叫索引篇1，后面肯定会有2.3…。要理解细节，还需要一步步来。

Milvus数据库索引

Milvus数据库索引，除了最简单的如何创建使用之外呢，比较重要的概念还包括。索引的构成、索引使用的数据结构、索引使用的量化算法、索引使用的精简器等等。先从宏观角度上看一个概念，然后再从简单的索引入手，逐步往前推进，这样相对而言会好理解一些。

索引Index整体感觉

数据库索引，似乎是比较古老的概念。非常早期的数据库产品，都会有索引。但是在Milvus数据库中，索引并不适合当老的数据库对象来学习。细品之下，向量数据库的索引，确实有本质的不同。先看官网对索引的定义：
索引是建立在数据之上的附加架构。其内部结构取决于所使用的近似近邻搜索算法。索引可以加快搜索速度，但在搜索过程中会产生额外的预处理时间、空间和RAM。此外，使用索引通常会降低召回率（虽然影响可以忽略不计，但仍然重要）。因此，本文将解释如何最大限度地减少使用索引的成本，同时最大限度的提高索引的效益。
在学习索引之前，它的不同给我带来几个感觉：
第一，在milvus中，开发者指定某个向量列搜索使用什么索引，并且向量列并不能创建多个不同的索引。传统数据库开发者当然也会设计程序应该使用什么索引。但SQL语句执行时，使用索引一般情况下，并不取决于开发者，而是可以在多个索引中，选择一个最佳的。而在Milvus中，不存在传统数据库的优化器计算代价或者选择执行计划的步骤，甚至都不会准备多个索引。且它的数据结构和算法是配套的。这表示，开发者在使用某一个向量索引时，其实是没什么灵活性可研的。它要求开发者应该了解自己使用的索引、算法。即使不知道这个索引和算法的原理和实现，最最起码，也应该了解不同的索引应该用在什么样的数据类型和场景之下。
第二，查询加速逻辑有区别。Milvus强调了，加载集合是在集合中进行相似性搜索和查询的前提。而加载的时候，所有的索引文件和原始数据都被加载到了内存里面。在传统数据库里，索引加速查询的核心逻辑，一直都在于，高效的避免无关行和无关列，被读入到内存之中，从而可以大幅的削减磁盘IO，最终实现查询优化。而向量数据库的索引，看起来并不考虑磁盘IO这块。它应该更加侧重于加速内存中的计算。这种加速可能是避免不必要的实体计算。也可以是必要的实体计算算得更快一些。从降低召回率这一点来看，甚至是为了算得更快一些，有的必要的实体，可能也不算了。既然要全部加载到内存中，那么内存空间大小，自然也变成了至关重要的。
第三，就是上面最后说的索引的选择可能改变查询结果。那它就并不是单纯的加速查询。

索引的构成

在向量数据库中，在特定字段上可创建索引。其中向量字段，是必须要创建索引。从这一条就可以看出，向量数据库并非是某种特殊的存储结构这么简单。它还包含某种向量数据相似性查找过程中，所必须要的东西。官网给出了向量索引的解刨图。Milvus的索引，有三个核心的部分。分别是：数据结构（Data Structure），量化器（Quantization）,精简器（Refiner）。
Data Structure还是指数据的存储组织结构。
Quantization指如何把数据量化并使用量化算法来计算数值。
Refiner指搜索结果如何精炼并保持召回率。

索引的工作流程

数据库收到搜索请求之后，根据索引的存储和量化的算法，根据一个比率计算出超过要求的一部分返回值。之后，再通过Refiner把这个大于的结果集，精简到需要的返回值。如图：

索引的命名

在接下来具体的索引之前。可以先看Milvus的索引命名，通常都是由两部分构成，比如IVF_FLAT，HNSW_SQ。 它的前半部分，比如IVF（倒排文档），表示内存之中数据结构部分。SQ就是Quantization的量化部分。所以，要理解每一种索引，都应从这两部分来看。
另外，在学习每一个索引的时候，我认为比较关键的理解点还有：
第一，这种索引，怎么减少不必要的实体来进行向量运算的。
第二，Quantization的算法是如何高效的利用资源，并加速查询的。

FLAT（扁平索引）

这个是最简单的。有一日聊天，有一同学问，数据库不能不要算法，应算向量距离吗？那当然是能，FLAT就可以认为是不做任何存储结构改变，把向量平铺在内存里面。它要把所有的实体都算一遍，所以它慢。慢归慢，但是召回率是100%。初看起来觉得，这个索引其实就是没有索引。官方的介绍说它无需任何高级预处理或者数据结构。那就是没有简化查询的Data Structure部分，也没有Quantization部分，就是硬算两个向量的距离。姑且，把它理解为向量查询的一种最原始的处理方式，就跟传统数据库表扫描那样。想必除了数据量特别小，不然是十分受嫌弃的存在。

IVF_FLAT索引（Inverted File Flat）

Inverted File反转文件，以前也有翻译成倒排文档。这种数据结构要分为两部来理解。为什么要提到以前的翻译，因为直接看官网那个花花绿绿的图，可能并不是那么容易理解。让我们换一个再老一点的图，Inverted File并不是在向量数据库中才出现的。以前在一些列存储或者文档型的数据库中，就有这种索引的形态。它的索引项里存着值，后面有指向这个值出现在的文档位置。比如要在下面这个索引里，找到和Gold相关的内容，就可以通过这个索引，迅速定位。

但是，现在这个索引又有点区别，它所建立在的数据，并不是文字和文本，而是浮点型的向量。它要仿照倒排文档的方式，来建立上图这样类似的映射。
首先要把数据库里的向量，使用K-MEANS 聚类的算法，把向量分类，并放到各个可以管理的区域（REGION）里面去。
然后每一个REGION里都有一个中心点，来作为REGION内向量的参考点。
让我们把这个中心点，理解为上图Term Dictionary里面的词一样的存在。
FLAT代表向量以扁平不加工的方式来计算，向量以原始的形态出现在索引中，类似于上图Posting List的位置。
结合我前面提到的两个关注点。很显然，它的查询优化是通过，直接不计算一些域的实体，来避免没有必要的实体计算。它认为离得比较远的REGION的相似性自然是弱的。相似搜索的时候，把目标向量和备选REGION的中心点进行计算。找到最近的1个或几个中心点，再通过索引中，找到中心点对应的REGION内的向量，完成计算。这里对于查询结果，影响比较明显的地方，就是REGION是怎么划分的。
所以，这里需要先知道，什么是K-MEANS聚类算法。
K-means算法是一种基于距离度量的算法，通过迭代，把数据划分为K个簇，使簇内数据相似度最大化，簇简差异最大化。数据不重叠。
K-means基本流程为：

1. 初始化质心：随机选K个数据点作为初始中心点。
2. 分配数据点，计算没有个数据点于所有质心的距离（比如欧式距离），将其分配到最近的簇。
3. 更新质心：重新计算每个簇的均值作为新的质心
   再回来看官网这个图

理解这个索引的潜在缺点，如这个图上，搜索到的相似点，很有可能不是最接近的。如果搜索的这个点，在这个REGION的边缘，而最近那个点在另一个REGION的边缘。通过中心点检索的向量，就找不到最近的那个向量。所以，就有个参数来用于解决这个缺陷。一个是nlist，这个用于指定这个K值，也就是REGION的数量。分的范围可以是1-65536个，默认值是128个。另一个是nprobe，就是选择候选向量的时候，应该考虑几个分区，这个值要小于nlist的值，默认是8个。这个是决定选最近的几个中心点，对应的向量来检索。显而易见，nprobe会提高召回率，但是查询时的计算量肯定是大幅的增长了。
写到这个地方，IVF这个索引的数据结构就清楚了，它和字面上的反转文件或者是倒排文档其实关联不大。它主要把所有的向量分成多个聚簇，计算这些聚簇的中心点和向量的距离，完成了聚簇的筛选。从而只需要计算聚簇所包含的向量子集来加速查询。
索引的后半部分FLAT，表示扁平，就像前面FLAT索引一样，在Quantization部分，没有实质内容，就是靠硬算。也就是在聚簇了之后，向量以原始形式存储。

IVF_SQ8索引

前面IVF的数据结构部分就和前面IVF_FLAT一样。后半部分，SQ8。全称Scalar Quantization。后面这个8,表示8位的整数。这是一个减少高维度向量空间大小的技术，它用更小更紧凑的形态来显示。可以使得计算过程中的内存量大幅的减少。SQ8算法，是一个正态化的过程。分为3个步骤：

1. 范围识别，找出向量的最小值和最大值。
2. 归一化，normailzed_value=(value-min)/(max-min)
3. 8位压缩，将上面这个值乘以255
   这样，按官网的描述，通过使用IVF集中搜索和SQ8的加速计算，IVF_SQ8实现了快速搜索和高效的内存使用。
   除此之外，SQ8的压缩过程应该还有一个好处，就是使得向量的各个维度都标准化了。可以想象一下，假设向量的某一个维度，它的数值都非常的巨大，另一个维度，它的数值都很小。这样在平铺形态下，这个数值大的维度，明显对距离的影响就会表较大。SQ8之后，明显使得各维度的权重均衡了。
   这个算法还是比较好理解的，感觉不需要贴图，如果实有困惑的地方，可以去官网翻一下图就好。

IVF_PQ索引（Inverted File with Product Quantization）

PQ，又被翻译为乘积量化，是针对高维向量的压缩方法。它的流程如下：

1. 维度分解：先将高维向量分解为m个大小相等的子向量。
2. 子空间编码本生成：在每个子空间里，用k-means聚类来找到一组代表性向量（中心点）。这个步骤，是PQ算法里面，最难理解部分。所谓编码本，其实这个编码本就是K个向量，也就是这一组子向量的K个中心点。假设这K个中心点的编号，是1，2，3……K。形成了一组用于替代其他和它相似的参考系。从而完成压缩。
3. 向量量化：把原始向量中的每个子向量，找到每个子空间里，最邻近的中心点。假设某个向量的第一个子向量距离第3个中心点最近，第二个子向量距离第8个中心点最近。就按这个编号来替换占空间较大的向量，如下。
4. 压缩表示：它就会压缩成（3，8，……）这样的形式。
   显然，子向量的中心点个数K是非常重要的参数，它由参数nbits决定，中心点的个数有2nbits个。它意思就是说 ，在存储的时候，用几位存储来表示这个K的编码。8位编码，就自然可以表示256个不同的中心点K。
   这样量化之后，计算距离的时候，其实就不是精准计算每个每个向量，而是计算距离最靠近的子向量中心点的距离，再把子向量距离叠加出一个近似的距离。这个叠加可能是某种特定计算，比如欧式距离。

待续

其实IVF系列的索引，还有一个，考虑到篇幅和难度，放到下一篇索引学习笔记中再继续吧。
无论如何，向量数据库索引这一块，是跟AI应用里，相似性搜索非常强相关的一部分内容，看起来虽然痛苦，但是却重要。就这样。