索引类型-cuda ebook

5．2索引类型

5．2．1格网型空间索引

思路比较简单，容易理解和实现。其基本思想是将研究区域用横竖线条划分为大小相等或不等的格网，记录每一个格网所包含的空间实体。当用户进行空间查询时，首先计算出用户查询对象所在格网，然后再在该网格中快速查询所选空间实体，这样一来就大大地加速了空间索引的查询速度。

5．2．2 BSP树空间索引

BSP树是一种二叉树，它将空间逐级进行一分为二的划分。BSP树能很好地与空间数据库中空间对象的分布情况相适应，但对一般情况而言，BSP树深度较大，对各种操作均有不利影响。

5．2．3 KDB树空间索引

KDB树是B树向多维空间的一种发展。它对于多维空间中的点进行索引具有较好的动态特性，删除和增加空间点对象也可以很方便地实现；其缺点是不直接支持占据一定空间范围的地物要素，如二维空间中的线和面。该缺点可以通过空间映射或变换的方法部分地得到解决。空间映射或变换就是将2n维空间中的区域变换到2n维空间中的点，这样便可利用点索引结构来对区域进行索引，原始空间的区域查询便转化为高维空间的点查询。但空间映射或变换方法仍然存在缺点：高维空间的点查询要比原始空间的点查询困难得多；经过变换，原始空间中相邻的区域有可能在点空间中距离变得相当遥远，这些都将影响空间索引的性能。

5．2．4 R树和R+树

R树根据地物的小外包矩形建立，可以直接对空间中占据一定范围的空间对象进行索引。R树的每一个结点N都对应着磁盘页D（N）和区域I（N），如果结点不是叶结点，则该结点的所有子结点的区域都在区域I（N）的范围之内，而且存储在磁盘页D（N）中；如果结点是叶结点，那么磁盘页D（N）中存储的将是区域I（N）范围内的一系列子区域，子区域紧紧围绕空间对象，一般为空间对象的外接矩形。

想深入了解R树空间索引的朋友，可以参考《R树空间索引》、《R树空间索引详解》以及《R树空间索引的改进》。如果你对R树在实际应用中的优化研究感兴趣，那么《R树索引的查询研究》和《基于聚类的Hilbert R树空间索引算法》也值得一读。

空间索引的世界真是令人着迷，不是吗？