麻辣GIS微信平台

更多 GIS 干货

微信关注不错过

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-Sailor

作者:

GIS爱好者,学GIS,更爱玩GIS。

声明

1.本文所分享的所有需要用户下载使用的内容(包括但不限于软件、数据、图片)来自于网络或者麻辣GIS粉丝自行分享,版权归该下载资源的合法拥有者所有,如有侵权请第一时间联系本站删除。

2.下载内容仅限个人学习使用,请切勿用作商用等其他用途,否则后果自负。

手机阅读
公众号关注
知识星球
手机阅读
麻辣GIS微信公众号关注
最新GIS干货
关注麻辣GIS知识星球
私享圈子

留言板(小编看到第一时间回复)