gis笔记 r树 一种用于空间查找的动态索引结构

《gis笔记 r树 一种用于空间查找的动态索引结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、GIS笔记R树一种用于空间查找的动态索引结构正文之前先吐槽。这篇文章很老了。最初发表于1984年，比我还大三岁。但它是很多种空间索引乃至时空索引的技术基础。文献上经常会遇到类似"本索引结构采用了与R树类似的插入算法"的表达，所以还是要先从这篇论文看起。之前走马观花地看了一遍，主要内容明白了，可感觉上总是有种隔膜。后来想了想还是把文章的主要内容翻译一遍吧，一方面印象深一些，另一方面以后再看的时候看中文总比看英文更容易接受。其实原本打算本周内把这篇文章和另外一篇R*树的文章都翻译出来，合并成一篇。但是一方面逍遥书生效率比较低下(太逍遥了?囧)，另一方面

2、翻译实在是一件痛苦的工作，最后只完成了这一篇。6页论文我翻译了3天，效率太低，以后不能这么干了。考虑以后看英文文献的时候边看边记，把重要的内容记下来就差不多了。现在这一篇的篇幅已经有5000多字，就直接发上来。R*树以后单独再写一篇。水平有限，翻译实在称不上好。以前看别人翻译的英文书总是感觉不是那么回事，现在自己翻译一遍才知道原来翻译本身就是一件坑爹的事。为了让翻译出来的内容保持汉语的特征，不至于变成鸟语，有的时候不能太忠于原文。即使如此，翻译出来的东西还是很像鸟语。再加上逍遥书生的表达能力不强，本科毕业论文被导师评价为"口水话太多"，前一段时间写

3、了一篇论文被导师称为"读起来不够专业"，而且这篇译文里逍遥书生加入了一些翻译的过程中想到的东西，可想而知翻译出来的这篇东西的水平也就是那么回事吧。把这篇东西发到网上来，一方面是山寨"云存储"技术，做一备份，更重要的是期望以文会友。万望各位前辈高人以及各位同行批评指正。最后说一句，本文甚长，各位看官做好心理准备。吐槽结束，上正文。==分割线===R树简介。R树是一种与B树类似的高度平衡树。这种索引是动态的，不需要定期重建。索引记录(IndexRecords)保存在叶节点中，索引记录包含指向数据对象的指针。注意原文中将索引的终端称为索引记录而不是空间对

4、象。空间数据库由一系列元组(tuple)构成，每个元组代表一个空间对象，并且每个元组都有一个唯一的标识符，标识符的作用是用于检索。R树中的叶节点是以下面这种方式保存条目(entry)的：(I，tuple-identifier)。其中，I是一个n维矩形，表示空间对象的外廓矩形。Tuple-identifier是一个指向空间对象的指针。另外，原文中写到允许矩形I趋向于无穷大，却没有写到是否允许矩形I在某个维度上宽度为0。R树中的非叶节点是这样保存条目的：(I，child-pointer)。其中，I是其所有子节点的外廓矩形的总外廓矩形。Child-poi

5、nter是指向下一级节点的指针。原文中的表达方式似乎表明，节点中保存有多个条目，每个条目都有一个外廓矩形。我过去认为每个节点有一个外廓矩形及若干指针。但是从原文来看，我过去的理解是错误的。原文是这样的"Non-leafnodescontainentriesoftheform(I，child-pointer)"记M为一个节点中的最大条目数。取m=M/2，约定此m为一个节点中的最小条目数。此时，R树具有如下性质：(1)若叶节点不是根节点，则每个叶节点所包含的索引记录个数介于m与M之间(2)对于叶节点中的索引记录(I，tuple-identifier)，

6、I是其最小外包矩形。(3)若非叶节点不是根节点，则其中包含的子节点个数介于m与M之间。(4)对于非叶节点中的条目(I，child-pointer)，I表示能够覆盖其所有子节点的外包矩形的外包矩形。注意原文中没有使用索引记录(indexrecord)这个词，而用了条目(entry)。(5)根节点若非叶节点，则其至少有两个子节点。(6)所有叶子节点都在同一层。一个有N个索引记录的R树，其高度最大为logm(N)-1，这是因为其每个节点至少要有m个记录。节点的总个数最多为N/m+N/m2+…+1。最差的情况下，除根节点外的各节点空间利用率为m/M。通常情

7、况下节点中的条目数不会只有m个，所以树的实际高度通常小于logm(N)-1，空间利用率通常高于m/M。如果节点中有超过3或4个条目，这个R树就会非常宽，从而导致绝大多数空间都用于保存叶节点，也就是保存索引记录。我无法理解原文是赞成这一现象还是反对这一现象。不同的m值会影响索引的性能。搜索算法R树搜索算法与B树类似，都是从根节点向下搜索。然而，在搜索到某个节点后，接下来可能需要搜索这个节点下属的几个子树(而不是只搜索其中一个)。也就是说，搜索不是单向的。因此，在某些糟糕的情况下，R树可能无法保证性能。虽然如此，对于绝大多数的数据来说，R树的更新算法可

8、以保证R树有一个相对较好的结构，能够保证在进行搜索的时候，无关的区域不会参与检索，只有在搜索区域附近的数据才会被检索(ex