持久（基于磁盘）R树（或R *树）
如何将R * Tree实现为持久性（基于磁盘）？ 用于保存R * Tree索引或保存叶值的文件的体系结构是什么？
注意：此外如何在这样的持久R *树中执行插入，更新和删除操作？
注释II：我已经实现了具有批量加载function的内存中R-Tree。 但是，当我们谈论基于磁盘的问题时，我认为这完全无关紧要。
如果你需要一个磁盘上的R-Tree索引，我建议使用Spatialite或Postgis 。 Spatialite重量轻，易于嵌入独立应用程序中。 或者，你看过C＃Spatial Index项目了吗？ 。 几年前我用Java编写了一个R-Tree实现，如果已存在某些内容，我不建议这样做。
文件的体系结构
好吧，这是页面（=块）。 页面应该具有底层存储的页面大小的倍数，因此可能是1kb或8kb块。 每个块都有一个数字，可以通过这种方式引用。
目录页面存储子项的边界框及其页码。
子页面存储实际的数据对象。
管理树
好吧，从理论上讲：无论何时修改内存中的页面，都要将更改写入磁盘。 而已。
实际上，您可能希望使用缓存来提高性能，并且您可能希望在应用程序崩溃时使用事务来保持树的一致性。
在这两个方面，您可以在RDBMS架构领域找到大量文献。
R * -tree的一个主要好处是它是一个常规的面向页面的树，就像你在数据库系统中一样。 如果你有一个很好的磁盘B + -tree实现，你可以重用大部分代码用于R * -tree。
如何开始
首先，您需要习惯基于磁盘的数据索引，就像在经典RDBMS中一样。 我建议从磁盘 B树或B +树开始。 允许删除，因为您需要考虑管理已删除的页面以及所有这些。
一旦你在磁盘上找到B-Tree（并且可能花一些时间来优化它！），做一个磁盘上的R树应该是相当明显的。
我没有查看代码，但这可能是一个很好的起点： http ： //www.die-schoens.de/prg/或其他一些链接在C ++中寻找基于磁盘的B +树实现或C.
如果您已经有一个主内存实现，则可以重用相同的代码，只需向磁盘添加写入。 您必须考虑页面大小并优化树节点以适应页面（您可以一次阅读）。
拥有存储在磁盘中的主存储器树的快照（当树不在高压下时可以拍摄快照）与将每个更改写入磁盘相比，会更好（性能明智）。
在您指定查询树的问题更重要的问题中，因此您应该更好地使用R * -tree，因为它最小化树节点之间的重叠。 但是，如果您的要求将侧重于更新操作（插入/删除），我建议您查看支持R树中的频繁更新：自下而上的方法论文。