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较大时，空间存储开销大，空间利用率低。