要解决的问题

  • 范围查询

在一个二维平面上,有很多点,给定一个矩形,怎么快速的将落在矩形中的点找出来?

这个问题还可以推广到任意维度,一维就是区间查询,三维就是在长方体内部。

  • 近邻查询

离我最近的餐馆有哪些?

这个问题可以抽象成二维空间中,要找出距离某个点最近的点的集合。

一维的场景

这个场景非常简单,只需要将数值类型数据做个全排序,不管是范围查询还是近邻查询只需要进行二分搜索就好了。

如果数据集特别大,内存中放不下,上面的方案就会有问题,因为所有数据没有办法全部load到内存中。

这个时候可以在内存中维护一份索引,索引的构建过程如下:

step 1: 对数据进行外排序。
step 2: 构建二叉搜索树,选取step 1中数据中位数作为根节点的值,并在在根节点中记录下中位数的位置。
step 3:递归构造根节点左子树和右子树,左子树的根节点依据step 2中中位数左侧的数据集构造,
右子树依据step 2中中位数右侧的数据集构造。
step 4: 持续上述递归构造过程直到节点关联的数据数集数量小于某个阈值。

上述索引构造完成之后,查询过程中首先将索引load到内存中,先在索引中查询,最后再将命中的数据块load到内存中进行查询。

范围查询

step 1: 如果根节点和query range相交,则依据根节点将query range划分成左右两个query range,
使用left query range在左子树中查询,right query range在右子树中查询。如果不相交,则根据范围在左或者右子树中查询。
step 2: 命中的数据block中,需要对起点和终点block进行精确的过滤,中间的block结果肯定都满足查询范围。

k 近邻查询

step 1: 比较查询值和根节点的大小,如果大于,则递归查找右子树,否则左子树。
step 2: 对递归路径维护一个k个数据的小根堆,使用路径命中的数据block中距离查询值最近的k个值初始化小根堆,比较函数是距离。
step 3: 在当前的路径节点中,如果索引节点表示的超平面距离查询点比堆中最大值近,则将超平面另一侧的数据加入到小根堆中。
step 4: 沿着递归路径向上回溯,直到将根节点处理完。

此时小根堆中的k个数据就是查询数值的k近邻。

说明:

  • 如果查询值和索引值相等,则左右子树中任选一边进行递归查找就可以了,不需要在两边都进行递归。

高维场景

有了一维场景,非常容易推广到高维的场景。

构建过程

step 1: 选择一个维度,将数据按照该维度排序,数据量大的话使用外排序。
step 2: 选取中位数作为根节点的split value,除此以外,根节点需要记录下是哪一个维度的split value。
step 3: 前面两步将数据集划分成两部分,分别对两部分重复step 1、step 2,构造根节点的左右子树。
step 4: 持续上述递归构造过程直到节点关联的数据数集数量小于某个阈值。

这里的关键就是怎么选择在哪一个维度上将数据进行划分,这个和数据在该维度上的分布关系很大,遵循的原则是在这一步骤中,该维度的数据分布最散。

范围查询

和一维的区别在于每一次划分query range要在相应的维度划分,其他没有任何变化。

k近邻查询

和一维的区别在于回溯的过程中,查询点到超平面距离计算要相应的变化,其他没有区别。

merge过程中的优化

两份索引merge,对于一维的数据,可以使用归并排序,高维场景则需要当成一份数据集来处理,目前没有什么好的方法来优化高维数据merg