持久(基于磁盘)R树(或R*树)

Question

R*Tree如何实现为持久性(基于磁盘)？用于保存R*Tree索引或保存叶值的文件架构是什么？

注意:此外如何在这样的持久R*树中执行插入,更新和删除操作？

注释II:我已经实现了具有批量加载功能的内存中R-Tree.但是,当我们谈论基于磁盘的问题时,我认为这完全无关紧要.

Answer 1

文件的体系结构

好吧,这是页面(=块).页面应该具有底层存储的页面大小的倍数,因此可能是1kb或8kb块.每个块都有一个数字,可以通过这种方式引用.

目录页面存储子项的边界框及其页码.

子页面存储实际的数据对象.

好吧,从理论上讲:无论何时修改内存中的页面,都要将更改写入磁盘.而已.

实际上,您可能希望使用缓存来提高性能,并且您可能希望有一些事务可以在应用程序崩溃时保持树的一致性.

在这两个方面,您可以在RDBMS架构领域找到大量文献.

R*-tree的一个主要好处是它是一个常规的面向页面的树,就像你在数据库系统中一样.如果你有一个很好的磁盘B + -tree实现,你可以重用大部分代码用于R*-tree.

首先,您需要习惯基于磁盘的数据索引,就像在经典RDBMS中一样.我建议从磁盘 B树或B +树开始.允许删除,因为您需要考虑管理已删除的页面以及所有这些.

一旦你在磁盘上找到了B-Tree(并且可能花了一些时间来优化它!),那么做一个磁盘上的R-tree应该是相当明显的.

我没有查看代码,但这可能是一个很好的起点:http://www.die-schoens.de/prg/或其他一些链接在C++中寻找基于磁盘的B +树实现或C.

Answer 2

如果您需要有一个磁盘上的 R-Tree 索引，我建议使用Spatialite或Postgis。Spatialite 是轻量级的并且易于嵌入到独立应用程序中。或者，您是否看过C# 空间索引项目？。几年前，我用 Java 编写了一个 R-Tree 实现，如果某些东西已经存在，我不建议这样做。