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

县级土地利用数据库标准 GIS空间数据库(14)BSP树索引

作者:,GIS爱好者。
分享本文,请您带上本文链接
分享到:

发表评论