GIS空间数据库（13）KDB树索引

KDB树是KD树与B树的结合，它由两种基本的结构——区域页（region pages，非叶结点）和点页（point pages，叶结点）组成。如图所示

点页存储点目标，区域页存储索引子空间的描述及指向下层页的指针。在KDB树中，区域页则显式地存储了这些子空间信息。区域页的子空间（如s11，S12和s13）两两不相交，且一起构成该区域页的矩形索引空间（如S1）即父区域页的子空间。

其中KD树可以参考空间数据库（12）KD树索引（二叉树索引），B树可以参考：B树。

KDB-tree包括两种类型的页:

• 区域页面: (region, child)对的集合包含边界区域的描述，加上该区域指向子页面的指针。
• 点页面:(point, location)对的集合。数据库方面，location可能指向数据库记录的索引，对于K维空间中的点，可以被看成该空间中的点坐标。

当向KDB树插入元素时，导致节点的规模超过它的最优规模，页面溢出。因为KDB-tree的目的是优化外部内存访问，例如硬盘访问，当节点的规模超过外部内存页大小，一个叶被认为是溢出。通过插入和删除操作，KDB树保持一些属性:

• 该图是一个多叉树，区域页面指向子页面，并且不能为空。点页面是叶子节点。
• 对于所有查询，到达叶节点的路径长度是相同的。
• 如果根节点是区域页面，区域的联合是整个搜索空间。
• 当一个区域页面的(region, child)对的儿子也是一个区域页面，所有儿子区域的联合是该页面。
• 如果儿子是一个点页面，儿子中所有点必须被该区域包含。

参考：[译]K-D-B-tree