GIS空间数据库(19)点四叉树索引

本文目录
  • 正文

点四叉树是QuadTree的一个变种,主要是针对空间点的存储表过与索引(Finkel and Bentley,1974),与KD树相似,两者的差别是在点四叉树中,空间被分割成四个矩形,四个不同的多边形对应于SW、NW、SE、NE四个象限。

对于k维数据空间而言,以新插入的点为中心将其对应索引空间分为两两不相交的2k个子空间,依次与它的2k个孩子结点相对应,对于位于某一子空间的点,则分配给对应的子树。

点四叉树的每个结点存储了一个空间点的信息及2k个孩子结点的指针,且隐式地与一个索引空间相对应。其搜索过程和KD树相似,当一个点包含在搜索范围内时被记录下来,当一个子树和搜索范围有交叠时它将被穿过。如果想从Point QuadTree中删除一个点的话,则会引起相应的子树的重建,一个简单的方法是将所有子树上的数据重新插入。如图是二维空间的一棵点四叉树的例子。

优势&劣势

点四叉树的优点是结构简单,对于精确匹配的点查找性能较高。

其缺点有:

  1. 树的动态性差,删除结点处理复杂;
  2. 树的结构由点的插入顺序决定,难以保证树深度的平衡;
  3. 区域查找性能较差;
  4. 对于非点状空间目标,必须采用目标近似与空间映射技术,效率较差;
  5. 不利于树的外存存储与页面调度;
  6. 每个结点须存储2k个指针域且其中叶子结点中包含许多空指针,尤其是当k较大时,空间存储开销大,空间利用率低。

如您有疑问,可在文末留言,或到QQ群提问。
本站QQ群:291616564 麻辣GIS
微信公众号:malagis,扫描二维码直接关注。

打赏¥1

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

发表评论