如何提升搜索系统查询速度？

本文主要是介绍如何提升搜索系统查询速度？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 导语

为什么同样的查询我的代码要1s，别人的只要50ms？

为什么百度搜图可以处理上亿数据最近邻而我的机器几百万数据查询就很慢？

对于大部分互联网服务，网站相应时间和用户满意度是非常相关的。如果你是一家电商创业公司，用户输入一个Query后1~2s都没有结果显示，这时间就足够他放弃你们的产品转而去访问淘宝或者京东，开始新的一次查询。

在当今这个移动互联网时代，我们的日常生活每天都面临着海量数据地冲击，诸如像个人信息、视频记录、图像采集、地理信息、日志文档等，面对如此庞大且日益增长的数据信息，如何对我们需要的海量信息有效的存储及索引，以便快速查询是目前国内外研究的热点。

2 最近邻搜索

日志、图像、视频等数据的查找的本质是最近邻搜索任务。

最近邻检索就是根据数据的相似性，从数据库中寻找与目标数据最相似的项目，而这种相似性通常会被量化到空间上数据之间的距离，可以认为数据在空间中的距离越近，则数据之间的相似性越高。

最近邻搜索一般方法：线性查找

最简单的近邻搜索涉及数据集中所有成对点之间距离的暴力计算,也就是平常所说的穷举搜索。

在数据库中依次计算其中样本与所查询数据之间的距离，抽取出所计算出来的距离最小的样本即为所要查找的最近邻。

一般方法索面临的挑战：

对于小数据样本，高效的暴力近邻搜索是非常有竞争力的。然而，随着样本数N的增长，暴力方法失去了可行性。

搜索和推荐系统的计算量很大，我们面对和需要处理的数据往往是海量并且具有很高的维度（high dimensional spaces），同时数据中又普遍存在着近似相同的情况（例如相似的对话、相似的网页、相似的图片等），怎样快速地从海量的高维数据集合中找到与某个数据近似相似（approximate or exact Near Neighbor）的一个数据或多个数据，成为了一个难点和问题。

3 近似最邻近搜索

面对庞大的数据量以及数据库中高维的数据信息，现有的基于 最近邻搜索 的检索方法无法获得理想的检索效果与可接受的检索时间。进而有研究人员开始关注近似最近邻检索（Approximate Nearest Neighbor，ANN）

近似最近邻检索利用了数据之间形成簇状聚集分布的特性，通过对数据分析聚类的方法对数据库中的数据进行分类或编码，完成对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一子空间，然后在该子空间里做遍历。

近似最近邻检索的核心思想是搜索可能是近邻的数据项而不再只局限于返回最可能的项目，在牺牲可接受范围内的精度的情况下提高检索效率。

可以将ANN的方法分为三大类：基于树的方法、哈希方法、矢量量化方法。

3.1 基于树的近似最近邻算法

当待搜索数据维度为一的时候：只要采用传统的二分查找法或者各类平衡树就能找到最近邻，比如下图利用二分检索树总众多一维数据中快速找到符合要求的数据可以大幅缩小计算的次数。

二分检索树

当数据维度不太高（如d< 20)，通常采用树型索引结构对数据进行分区以实现高效索引，如最经典的KD树算法、R树、M树等等，它们的时间和空间复杂度都是以d为指数的指数级别的，在实际搜索时也取得了良好的效果。

其中，KD-Tree 是由 Finkel 和 Bentley 共同设计提出的对二叉搜索树的推广，利用KD-Tree 我们可以对一个由 K 维数据组成的数据集合进行划分，划分时在树的每一层上根据设定好的分辨器（discriminator）选取数据的某一维，比较待分配数据与节点数据在这一维度上数值的大小，根据结果将数据划分到左右子树中。

比如X= {（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}这样的一个由6个点构成的二维点集，我们首先对它的第一维X进行划分，根据二分将（7,2）作为根节点，那么数据点的x轴小于7的划分到左子树，大于7的划分到右子树；再对第二维Y进行划分时，则根据数据点的y轴的大小进行左右划分。

undefined