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

Question

如何将 R* Tree 实现为持久(基于磁盘)树？保存 R* 树索引或保存叶值的文件的体系结构是什么？

注意:此外，如何在这种持久性 R* 树中执行插入、更新和删除操作？

注意事项二:我已经实现了一个具有批量加载功能的内存中 R-Tree。但我认为当我们谈论基于磁盘的时，这完全无关紧要。

Answer 1

文件结构

好吧，它是页面(= block )。这些页面应该是底层存储页面大小的倍数，所以可能是 1kb 或 8kb block 。每个 block 都有一个编号，可以通过这种方式引用。

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

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

管理树

好吧，理论上:无论何时修改内存中的页面，都会将更改写入磁盘。就是这样。

在实践中，您可能希望使用缓存来提高性能，并且您可能希望拥有事务以在应用程序崩溃时保持树的一致性。

关于这两个方面，您可以找到 RDBMS 体系结构领域的大量文献。

R*-tree 的一个主要优点是它是一个常规的面向页面的树，就像您在数据库系统中到处都有它们一样。如果您在磁盘上有良好的 B+ 树实现，您可以将大部分代码重用用于 R* 树。

如何开始

要开始使用，您需要习惯基于磁盘的数据索引，就像在经典 RDBMS 中所做的那样。我建议从磁盘上 B 树或 B+ 树开始。一定要允许删除，因为您需要考虑管理已删除的页面等等。

一旦您确定了磁盘上的 B 树(并可能花一些时间对其进行优化!)，在磁盘上创建 R 树应该是相当明显的。

我没有看过代码，但这可能是一个很好的起点:http://www.die-schoens.de/prg/或 Looking for a disk-based B+ tree implementation in C++ or C 中链接的其他一些内容