使用2维时，R-Trees可以维护Z阶吗？

Question

我正在根据Guttman的原始论文撰写R-Tree的实现。我正在考虑将R-Tree用于我正在编写的程序，该程序涉及屏幕上许多矩形，这些矩形可以使用鼠标移动/重新尺寸。

我想有效地选择特定矩形中的矩形并绘制它们（而不是通过潜在的100个以上的项目迭代并检查边界是否相交）。在读几对古特曼论文后，我发现的问题是，不能为2D对象维护z订单。

例如，如果我移动一个对象，则将其删除然后重新插入。重新插入时，插入的节点将无法跟踪正确的顺序。我看到的大多数R-Tree的实现都使用了数组，只是找到空位置。重新插入基本上将破坏任何Z阶定位。

因此，当我去绘制与矩形相交的所有矩形时，返回的顺序不一定正确。

我在这个假设上错了吗？我在想，而不是使用阵列，我可以使用AVL或红色树并使用 Comparer 相比之下，z索引将其插入树上。这样，始终保持Z阶（这是最重要的因素）。

我也只是想在返回时对它们进行分类，但这可能更昂贵。

Answer 1

R-Tree不应该以某种方式订购答案记录。

只要对答案进行排序。它不太慢。

顺便说一句，我可以邮寄我的R-Tree代码。这对我来说很好，但是如果有人检查是古特曼或贝克曼在他们的论文中写的...

空间索引的顺序与严格的顺序基本不同……这是空间索引和仅B+树之间的差异。

您也可以有两个索引并加入它们。您真的需要索引吗？有些东西缓慢吗？