5

如何将 R* 树实现为持久（基于磁盘）的树？保存 R* 树索引或保存叶值的文件架构是什么？

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

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

4

3 回答 3

8

文件架构

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

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

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

管理树

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

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

关于这两件事，您可以在 RDBMS 体系结构领域找到大量文献。

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

如何开始

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

一旦你弄清楚了磁盘上的 B-Tree（可能会花一些时间优化它！），做一个磁盘上的 R-tree 应该是相当明显的。

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

于 2012-12-02T10:59:46.320 回答
4

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

于 2012-11-28T14:21:46.173 回答
2

如果您已经有一个主内存实现，您可以重用相同的代码，只需将写入添加到磁盘。您必须考虑页面大小并优化树节点以适应页面（您可以一口气阅读）。

将主内存树的快照存储在磁盘中会更好（在性能方面）（可以在树不处于高压下时拍摄快照）而不是将每个更改都写入磁盘。

在问题中，您指定查询树具有更高的重要性，因此您应该更好地使用 R*-tree，因为它可以最大限度地减少树节点之间的重叠。但是，如果您的要求将集中在更新操作（插入/删除）上，我建议您看一下Supporting rapid updates in R-trees: a bottom-up approach paper。

于 2012-11-28T14:40:10.143 回答