2024年10月 IDC 发布全球数据量预测报告：2028年全球数据量将增长至393.8 ZB，相比于2018年增长9.8倍。其中非结构化数据量占比，从2023年的92.9%降低至2028年的82.3%，虽然占比有所下降，但其仍然是最主要的数据形式。从IDC报告可知，未来全球数据主要以非结构化形式存在。
全球数据量预测，来自 IDC
数据 Embedding 流程，来自 Qdrant
在Ai时代，万物皆需向量表达。用户基于文本、音频、图片等非结构化数据搜索数据时，先对数据 embedding 转换成向量数据，再把向量数据进行相似性搜索，返回最相似的 TOP-K 个结果，这个过程中离不开向量数据库。因此，高效存储、快速检索和管理高维度向量数据的系统称为向量数据库。
向量数据库检索过程，来自Zomi
向量数据库既然是数据库，就可以和传统数据库进行比较。它们的相同点是两则都可以数据的有效存储、高效检索和管理；不同的是传统关系型数据库是基于表格存储和关键字的精确搜索，而向量数据库是基于向量存储的相似性搜索。理论上相似性搜索也可以通过无限维度的拆分实现精确查找，但考虑到业务需求、工程实现以及商业价值，向量数据库一般不需要也不提供绝对精准的查询，意味着向量维度并不会无大。
实际上企业生产和用户使用中，系统往往更需要高并发、低延迟、多模态的处理海量数据，而这些向量数据大多以浮点或者二进制的向量形式存在。因此，具有高并发、低延迟、高压缩存储、易水平扩展、多模态等能力才是向量数据库重要特性。要具备这些能力，向量数据库需要通过多种技术实现，其中相似性度量、相似性搜索是两个核心技术点。
传统数据库基于关键字精确查找，通过等值、范围等条件查找数据。而向量数据库是近似搜索，通过比较向量的相似性查找目标数据。因此，向量的相似性度量是向量数据库中重要概念。常见的相似性度量指标：点积（Dot Product），从数值层面反映向量间的关联强度，；余弦相似度（Cosine Similarity），主要反映向量的一致性，在文本、图像特征向量匹配上应用广泛；欧几里得距离（Euclidean Distance），通过计算向量在空间中的直线距离，直观量化差异。
Dot Product
点积，又称数量积或者内积，是向量每个对应元素相乘后求和的值，通过一个实数值来度量两个向量的相似性。如果点积为正，则两个向量大致指向相同的方向；如果点积为零，则两个向量是正交的，即彼此垂直，不存在线性相关性；如果点积为负，则表示两个向量指向相反的方向，数值越大向量相似性越高。其n维代数公式：
Cosine Similarity
余弦相似度是通过计算两个向量夹角的余弦值来衡量相似性，等于两个向量的点积除以两个向量长度的乘积。代数公式：
取值范围是 [-1, 1]，值越接近 1 表示向量越相似，越接近 -1 表示越不相似，只关注向量的方向，忽略大小。在文本数据处理中广泛应用，因为文本转化为词向量后，向量的长度不能反映语义的相似性。余弦相似度几何图形表示：
Euclidean Distance
欧几里得距离是计算两个向量在空间中的直线距离，向量对应元素差的平方和的平方根。其n维代数公式：
取值范围为[0,+∞)，距离值越小，表明向量越相似。欧氏距离对向量的绝对数值变化较为敏感，适用于特征分布相对均匀，且数值变化能够反映实际差异的场景，不仅感知方向，也关心向量之间的距离。比如在基于数值特征的用户画像分析中，欧几里得距离可准确的衡量用户之间的相似程度。
点积、余弦相似度、欧几里得距离三者关系可以整理为下表格。
其他
向量的相似性度量除了点积、余弦距离、欧几里得距离三种常见度量方式方式外，还有比较两个等长字符串在对应位置上值的汉明距离，用于沿水平和垂直方向移动所经过的距离的曼哈顿距离，用于表述元素和集合关系的杰卡德相似度，用于表述线性关系的皮尔逊系数等指标，这些指标在不同的场景均有广泛的使用，有兴趣的读者可以进一步了解这类向量度量指标。
向量数据库相似性搜索，是通过计算输入向量与目标向量的相似度，快速找出与输入向量最相似数据的搜索技术。这其中以 Approximate Nearest Neighbor（近似最近邻，ANN）搜索和以K-Means 为代表的聚类搜索最具代表性。
常见的 ANN 算法有基于图的分层导航小世界（Hierarchical Navigable Small World, HNSW），基于哈希的局部敏感哈希（Locally Sensitive Hashing, LSH），基于量化压缩的方式则包括乘积量化（Product Quantization, PQ），以及基于逆文本和树等数据结构的算法。
相似性搜索对程序猿来说并不模式，传统数据库通过 SQL 的 like、in等谓词也有相关能力。但传统数据库的相似性搜索有明显的缺点，不能根据语义进行搜索。比如在搜索引擎中输入【关羽】，只能返回带有【关羽】的网页，却无法识别【关二哥、关云长、汉寿亭侯、关圣帝君】等语义相同的内容。
K-Means
早在上世界60年代，一篇《Some Methods for classification and Analysis of Multivariate Observations》论文，首次给出 k-means 的实现步骤。
1.将数据集分为k 聚类，每类中随机选择一个点作为中心点。
2.把数据集中的向量点和随机选择的中心点最近的划分为一个聚类。
3.再根据每个聚类中的所有向量计算出平均点，该点为新的中心点，又称质心。
4.重复2、3步，进行多次迭代，最终实现中心点趋于稳定，或者收敛
步骤中的 k 表示把数据分成聚类的数量，means 是均值的意思。将一个数据集划分为K数个聚类，通过迭代计算数据点到聚类中心的距离并更新中心，到达所有聚类中每个点到其所属簇质心的欧几里得距离平方和的总和尽可能小，从而实现对数据的有效划分。
K-means动态示意图，图片来自网络
示意图中圆点是向量元素样本，X是聚类的中心点，同样颜色的圆点为一个聚类。观察示意图的变化，聚类的中心点需要进行多次迭代计算后才能稳定，实现聚类趋于稳定或者收敛。
其代数公式表示如下：
参数含义：
K 是聚类的数量；
Si 表示属于第i 个聚类的数据集合；
Ui 是第 i 个聚类的质心，即该聚类中所有点的平均值;
|| xj — ui || 2 表示数据点x j 与质心μ i之间的欧几里得距离的平方。
HNSW
Hierarchical Navigable Small World Graph（HNSW，分层导航小世界图），一种基于图（Graph）数据结构近邻搜索算法。由六度分离理论（全球任意两个人，最多通过五个人即可以认识）、 Navigable Small World（NSW）算法等演进而来。因其在高纬度情况下仍有极高的搜索速度和出色的召回率，在向量搜索领域有广泛的使用，被称为工业界影响力最大的搜索算法之一。
本节主要根据《Efficient and robust approximate nearestneighbor search using Hierarchical NavigableSmall World graphs》一文，介绍其算法原理、实现过程。下图为该论文提供的是 HNSW 搜索图示，搜索从顶层的红色节点开始，红色箭头表示从开始点到查询目标绿色节点的方向，共分为Layer 0、1、2 三层。
Layer=2：最高层，节点较少，连接较稀疏，边长最长。
Layer=1：中间层，节点适中，连接较为密集，边长居中。
Layer=0：最低层，节点最多，连接最密集，边长最短。。
HNSW 搜索示意图，来自《Efficient ..》一文
由HNSW 搜索示意图可知，随着图层数的增加，特征半径减小。因此，在较低层中节点数更多、更密集、节点间的距离更近，这保障了在低层搜索更精确的找到相似数据；而在高层中，节点数较少、相对稀疏、节点间距离较长，这保障了在高层查询中的速度。可见，HNSW 图的构建对应查询效率至关重要，这篇论文对新元素插入时的构图的构图过程也做了详细介绍。
HNSW 插入元素过程，来自《Efficient ..》一文
输入参数
hnsw: 表示多层图结构。
q: 待插入的新向量元素。
M: 要建立的连接数。
Mmax: 每层中每个元素的最大连接数。
efConstruction: 动态候选列表的大小。
mL: 用于生成层级的归一化因子，控制每层元素个数，值越大上层元素越多。
算法步骤
1. 初始化一个空列表 W，用于存储当前找到的最近元素。
2. 获取进入点 ep，即进入HNSW图的起始点。
3. 确定进入点 ep 所在的层级 L，这是HNSW图的顶层。
4. 根据随机函数和 mL 计算新元素 q 所在的层级 l。
5. 从顶层 L 到新元素层级 l+1
- 在每一层中调用 SEARCH-LAYER 函数搜索与 q 最近的元素，并更新 W。
- 从 W 中选择距离 q 最近的元素作为新的进入点 ep。
6. 从 min(L, l) 到层级0，在每一层中：
- 调用 SEARCH-LAYER 函数搜索与 q 最近的元素，更新 W。
- 调用 SELECT-NEIGHBORS 函数从 W 中选择 M 个邻居。
- 在当前层 lc 为新元素 q 与这些邻居建立双向连接。
- 检查每个邻居的连接数，如果超过 Mmax，则调用 SELECT-NEIGHBORS 函数缩减连接。
7. 更新进入点 ep 为 W。
8. 如果新元素层级 l 大于顶层 L，则将进入点设置为新元素 q。
输出结果
插入了新元素 q ，建立相应的连接，并返回更新后的HNSW图。
从插入算法可知，HNSW 在处理插入和删除操作时而无需重建索引。因此，它支持冷启动，而 K-Means 等实现则要求数据预先进行训练才能有效执行搜索任务，即所谓的热启动。尽管HNSW提供了这种灵活性，其实际部署时还需细致调节一些关键参数，如层级归一化因子mL、连接数M及最大连接数Mmax，这些都直接影响到算法性能。
LSH
Locality Sensitive Hashing（LSH，局部敏感哈希），一种基于哈希（Hash）数据结构近邻搜索算法。
介绍 LSH 前，先回顾传统 Hash 算法。传统哈希算法是将数据经过哈希函数（如MD5、SHA等）处理，输出一段固定长度的哈希值存放到一个哈希表中。为了保证搜索的时间复杂度实现 O（1），传统哈希函数要尽可能得保证原始数据生成的 哈希值不同。在极端情况，如果所有原始数据经过哈希后，值均相同，则此时复杂度退回到O（N）。因此，传统 Hash 算法是尽可能将数据生成不同的哈希值，从而提高查询效率。
LSH 算法则相反，需要将相似的哈希数据放在一个哈希桶中。数据经过特定哈希函数处理，将高维数据向量转换为低维哈希值，转换过程中保留了数据点之间的相似性信息，需要将更多的相似向量数据映射到到相同的哈希桶中，在从哈希桶中找到目标数据。总的来说，LSH是利用哈希函数来简化高维空间中相似点的查找，通过哈希碰撞概率来保证相似度，并在保持局部几何结构的前提下，压缩了高维数据的特征，是一种典型的概率性算法。
LSH 算法示意图，来自Zomi
LSH 算法优点是通过降低维度和小范围搜索，可以快速处理高维数据；由于是通过哈希函数实现，可以根据自定义哈希函数，以满足不同应用场景。缺点是需要多次哈希计算，就需要创建多个哈希表，也会增加存储和计算开销；其次对哈希函数的设计要求比较高，既要保证相似性不丢失，又要保证更多相似数据放在一个哈希桶中。
PQ
前文介绍的K-Means、HNSW、LSH 等都存在面对大规模数据或高维数据时，通常需要使用大量内存来存储索引对象。而 Product Quantization (PQ，乘积量化)，一种基于量化压缩的 ANN 搜索算法，可以极大地减少对内存的需求。
PQ 算法示意图，来自Zomi
其他
除了 K-means、HNSW、LSH 和 PQ 等相似性搜索算法外，基于树（tree）和逆文本（Inverted file）数据结构等常见算法，在向量数据库中同样占据重要地位和广泛应用。
基于树的算法有 KD-tree、Ball-tree、Annoy 等，通过对数据空间进行层次化划分，构建树形结构索引，提高了相似性搜索的效率，尤其适用于处理低维向量数据。逆文本算法是一种基于文本特征反向索引的技术。在向量数据库中，它将文本内容转化为向量表示后，建立起文本特征与向量之间的反向映射关系。当进行相似性搜索时，系统可以根据文本特征快速定位到相关向量，从而实现基于文本语义的相似性检索。
2022年底，随着 ChatGPT 的全球爆火，向量数据库的风头一时无两，也从幕后走向台前。回顾向量数据库的发展，大致可分为三个阶段。
第一阶段，以 Lucene （其作者是有Hadoop 之父之称的大神 Doug Cutting）为代表，其主要功能是文件形式存储向量数据。第二阶段，2017 年Google 发表《Attention Is All You Need》以及 Facebook 开源 Faiss 框架 为标志。第三阶段，是019年以来陆续出现一些独立的向量数据库，代表产品有国内Milvus，国际上Pinecone、Chroma 等产品。
向量数据库发展，图来自Zomi
向量数据库从早期以 Lucene 为代表的文件系统，发展到以 Faiss 为代表的搜索库，再到如今以 Milvus、Pinecone 为代表的功能更完善的向量数据库。这些产品对向量数据处理能力、检索效率、功能丰富度和易用性等方面不断进化，从而满足Ai时代万物皆向量的数据处理需求，也推动了人工智能、机器学习等领域的发展 。
Milvus
Milvus 是一款开源的向量数据库，支持单机和分布式两种形态，通过高效的搜索算法、分布式存储和计算能力，实现产品的高度可扩展性和高性能搜索能力。也有着非常活跃的社区，目前 github 33.5 k stars、3.1 k forks、273 位contributors ，开源协议是比较宽松的 Apache 2.0。
Milvus 采用共享存储架构，计算节点具有计算分解及快速横向扩展能力，整体架构可分为访问层、协调器服务、工作节点和存储四层。
Milvus 架构图
访问层由一组无状态 proxy 组成，对外提供用户连接的 endpoint，同时负责验证客户端请求；其次还提供负载均衡和提供统一的服务地址能力。接入层负责验证客户端请求并减少返回结果。此外 Milvus MPP 架构，proxy还承担着聚合和后处理中间结果的职责，对查询结果进行整合、筛选，最终结果返回给客户端 。
协调服务是系统大脑，负责向执行节点分配任务，包括集群拓扑节点管理、负载均衡、时间戳生成、数据声明和数据管理等，主要包括四类角色Root coordinator、Query coordinator、Data coordinator、Index coordinator 。
工作节点负责完成协调服务下发的指令和 proxy 发起的SQL命令。由于采取了存储计算分离，执行节点是无状态的，可以配合 Kubernetes 快速实现扩缩容和故障恢复，实现高并发下的查询性能。主要包括三类角色Query node、Data node、Index node
存储层负责数据的持久化，也是系统的重要部分，分为数据文件和索引文件。其中数据文件均以日志的形式存在，实现日志即数据，通过日志持久化和日志快照来保证数据的可靠性。索引层支持多种索引类型，提供 HNSW、IVF_FLAT、DiskANN 等，支持 GPU 加速优化性能，能根据不同的应用场景选择合适的索引来加速查询。
Pinecone
Pinecone 是一个完全托管的闭源向量数据库，提供开箱即用的向量存储与检索能力，用户只需通过 API 即可轻松进行向量的存储、检索和管理操作，无需关系其架构等。此外，Pinecone 提供了灵活的查询语言，支持海量数据低延迟、高并发的实时查询场景，在实时推荐、广告系统等业务场景有广泛的应用。
Data Plane 接收到基于索引的查询时，查询路由器会先执行准入控制，并做相关约束验证。完成验证后，查询路由器将判断哪些层与此次查询相关联，并将查询路由到负责这些层的执行器中进行执行，还会对包含尚未纳入层的最新数据的 memtable 查询，将结果发送回查询路由器。
每个查询执行器扫描其负责的数据库块（slabs） ，并将 top_k 候选列表返回给查询路由器。如果查询包含元数据过滤器，执行器在确定 top_k 候选之前会排除不符合指定标准的记录。在大多数情况下，数据块会在执行器的内存和 SSD 之间进行缓存，从而实现可预测的高查询性能。。如果数据库未缓存，执行器将从对象存储中检索它，并为未来的查询缓存它。这通常发生在层首次访问或有一段时间未被查询时。
最终，查询路由器会汇总所有执行器返回的结果，将其与 memtable 中的结果进行合并及去重处理，挑选出最终的候选集，并将这些结果返回给客户端。
Pinecone 查询示意图，来自Pinecone Document
Chroma
Chroma是一款轻量级向量数据库。它能本地部署，也支持云环境使用，方便开发者快速集成向量搜索功能。其功能涵盖向量存储与检索，支持多样向量数据类型与相似度度量方式，可依不同场景灵活选择。此外，Chroma有着活跃的社区，目前 github 18.5 k stars、1.5 k forks、153 位contributors ，开源协议同为比较宽松的 Apache 2.0。
Chroma 最大特点是易用性强，API简洁直观，几行代码就能完成向量存储与查询操作，部署和维护成本低，对新手与小型项目友好。但在处理大规模数据和复杂场景时，性能和功能完整性逊于大型向量数据库。在使用场景上，适合小型智能应用，像简单文本分类工具；也适用于教学场景，助力快速验证向量数据库相关算法与模型 。
| 产品 | 版本 | 功能特点 | 使用场景 |
|---|---|---|---|
| Milvus | 开源 | 支持海量数据高效混合搜索，分布式易扩展，活跃的社区 | 企业级图像检索、自然语言处理、推荐系统等大规模场景 |
| Chroma | 开源 | 轻量级，简单易用， 活跃的社区 | 小型智能应用、教育科研场景 |
| Pinecone | 闭源 | 开箱即用，灵活查询方式，强大搜索性能 | 企业级 AI 应用、大规模内容推荐 |
其他
伴随着大模型和Ai的快速，不仅出现了大量向量数据库，过去传统的数据库也几乎都具备向量能力，比如PostgreSQL、Elasticsearch 和 OceanBase 等产品。
PostgreSQL 通过扩展 pgvector 插件具备向量能力。pgvector 允许用户高效地存储和查询高维向量，不仅可以对向量进行四则运算，也提供向量多种相似度度量方法和相似性搜索算法，从而帮助用户更好地理解和分析向量数据。在科学研究领域、机器学习领域，还是在其他需要处理向量数据的应用中，pgvector 都能够发挥重要作用。
ElasticSearch 应该是过去十年搜索和数据库领域最成功、最具影响力的开源项目之一，内部基于 Apache Lucene 构建，凭借高性能、高扩展性和分布式架构广受欢迎。从 8.0 版本开始，本通过对dense_vector字段类型的强化、引入先进的ANN算法以及提供多种向量度量方式，提供了基于向量的搜索和自然语言处理功能，从而满足用户基于文本、图片、音频等各种数据的语义搜索。
