GIS空间数据库（19）点四叉树索引

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

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

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

      优势&劣势

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

      其缺点有：

       树的动态性差，删除结点处理复杂；

       树的结构由点的插入顺序决定，难以保证树深度的平衡；

       区域查找性能较差；

       对于非点状空间目标，必须采用目标近似与空间映射技术，效率较差；

       不利于树的外存存储与页面调度；

       每个结点须存储2k个指针域且其中叶子结点中包含许多空指针，尤其是当k较大时，空间存储开销大，空间利用率低。