要解决的问题

  • 范围查询

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

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

  • 近邻查询

离我最近的餐馆有哪些？

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

一维的场景

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

如果数据集特别大，内存中放不下，上面的方案就会有问题，因为所有数据没有办法全部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