GIS中KD树空间索引

关于KD树

在计算机科学里，k-d树（k-维树的缩写）是在k维欧几里德空间组织点的数据结构。k-d树是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分区成两部分。在超平面左边的点代表节点的左子树，在超平面右边的点代表节点的右子树。超平面的方向可以用下述方法来选择：每个节点都与k维中垂直于超平面的那一维有关。因此，如果选择按照x轴划分，所有x值小于指定值的节点都会出现在左子树，所有x值大于指定值的节点都会出现在右子树。这样，超平面可以用该x值来确定，其法矢为x轴的单位矢量。（来自维基百科）

GIS中的KD树

KD树的基本形式存储了K维空间点。KD树的每个内部节点都包含一个点，并且和一个矩形区域相对应。树的根节点和整个研究区域相对应。树中奇数层次上的点的X坐标和偶数层次上的点的Y坐标把矩形区域分成两部分。在KD树结构中，通过沿着树下降到达一个树叶节点的方式来添加一个新点。KD树的查找是从根节点开始，查看所存储的节点（分裂的点）是否被包括在查找范围内以及和左子树或者右子树是否有交叠。对于每个和查询范围交叠的子树，查询过程将重复执行直到到达树叶那一级为止

示意图如下：