|
本帖最后由 高冷的哥哥 于 2017-6-23 14:38 编辑
KDB树是KD树与B树的结合,它由两种基本的结构——区域页(region pages,非叶结点)和点页(point pages,叶结点)组成。如图所示
GIS空间数据库:KDB树索引
点页存储点目标,区域页存储索引子空间的描述及指向下层页的指针。在KDB树中,区域页则显式地存储了这些子空间信息。区域页的子空间(如s11,S12和s13)两两不相交,且一起构成该区域页的矩形索引空间(如S1)即父区域页的子空间。
其中KD树可以参考空间数据库(12)KD树索引(二叉树索引),B树可以参考:B树。
KDB-tree包括两种类型的页:
区域页面: (region, child)对的集合包含边界区域的描述,加上该区域指向子页面的指针。
点页面: (point, location)对的集合。数据库方面,location可能指向数据库记录的索引,对于K维空间中的点,可以被看成该空间中的点坐标。
当向KDB树插入元素时,导致节点的规模超过它的最优规模,页面溢出。因为KDB-tree的目的是优化外部内存访问,例如硬盘访问,当节点的规模超过外部内存页大小,一个叶被认为是溢出。通过插入和删除操作,KDB树保持一些属性:
该图是一个多叉树,区域页面指向子页面,并且不能为空。点页面是叶子节点。
对于所有查询,到达叶节点的路径长度是相同的。
如果根节点是区域页面,区域的联合是整个搜索空间。
当一个区域页面的(region, child)对的儿子也是一个区域页面,所有儿子区域的联合是该页面。
如果儿子是一个点页面,儿子中所有点必须被该区域包含。
|
|