如果想要在一个海量的数据中找到和某个向量最相似的向量，我们需要对数据库中的每个向量进行一次比较计算，但这样的计算量是非常巨大的，所以我们需要一种高效的算法来解决这个问题。

高效的搜索算法有很多，其主要思想是通过两种方式提高搜索效率：

减少向量大小——通过降维或减少表示向量值的长度。缩小搜索范围——可以通过聚类或将向量组织成基于树形、图形结构来实现，并限制搜索范围仅在最接近的簇中进行，或者通过最相似的分支进行过滤。

实际上，除了暴力搜索能完美的搜索出最相邻，所有的搜索算法只能在速度和质量还有内存上做一个权衡，这些算法也被称为近似最相邻（Approximate Nearest Neighbor，ANN）。

大部分算法共有的核心概念，也就是聚类。常见的聚类算法有 K-Means，它可以将数据分成 k 个类别，其中 k 是预先指定的。

除了聚类以外，也可以通过构建树或者构建图的方式来实现近似最近邻搜索。

这种方法的基本思想是每次将向量加到数据库中的时候，就先找到与它最相邻的向量，然后将它们连接起来，这样就构成了一个图。当需要搜索的时候，就可以从图中的某个节点开始，不断的进行最相邻搜索和最短路径计算，直到找到最相似的向量。

Hierarchical Navigable Small Worlds (HNSW) 算法采用了分层格式，最高层具有更长的边缘（用于快速搜索），而较低层具有较短的边缘（用于准确搜索）。

每一层都是一个小世界，图中的节点都是相互连接的。而且每一层的节点都会连接到上一层的节点，当需要搜索的时候，就可以从第一层开始，因为第一层的节点之间距离很长，可以减少搜索的时间，然后再逐层向下搜索，又因为最下层相似节点之间相互关联，所以可以保证搜索的质量，能够找到最相似的向量。

HNSW 算法是一种经典的空间换时间的算法，它的搜索质量和搜索速度都比较高，但是它的内存开销也比较大，因为不仅需要将所有的向量都存储在内存中。还需要维护一个图的结构，也同样需要存储。所以这类算法需要根据实际的场景来选择。

局部敏感哈希（Locality Sensitive Hashing）也是一种使用近似最近邻搜索的索引技术。它的特点是快速，同时仍然提供一个近似、非穷举的结果。LSH 使用一组哈希函数将相似向量映射到“桶”中，从而使相似向量具有相同的哈希值。这样，就可以通过比较哈希值来判断向量之间的相似度。

在向量搜索中，我们的目的是为了找到相似的向量，所以可以专门设计一种哈希函数，使得哈希碰撞的概率尽可能高，并且位置越近或者越相似的向量越容易碰撞，这样相似的向量就会被映射到同一个桶中。

等搜索特定向量时，为了找到给定查询向量的最近邻居，使用相同的哈希函数将类似向量“分桶”到哈希表中。查询向量被散列到特定表中，然后与该表中的其他向量进行比较以找到最接近的匹配项。这种方法比搜索整个数据集要快得多，因为每个哈希表桶中的向量远少于整个空间中的向量数。

#春日生活打卡季#