R-tree并发性能不佳的原因

Question

在许多论文中，他们提到并发性能很差，但他们没有解释为什么它很差。

有人能给我个提示吗？

Answer 1

查询一点问题都没有。

只有对树的更改才会有一定的代价，并且需要锁定。它们比B树更糟糕，因为你可能需要一直更新边界框到根。R*树还执行一种特殊的重新插入来平衡树。但总的来说，它可以与B树和任何其他面向页面的树相媲美。您需要锁定您要写入的页面。

Answer 2

当您查看R-Trees (或R*树、R+Tree等)的插入/删除策略时您可以看到，节点的上溢/下溢可以很容易地通过树的大部分进行级联(也称为重新平衡)。这需要锁定大量节点，这显然不利于并发性。

您可以尝试写入时复制策略，而不是锁定策略，但这样做的代价也很高，因为要复制大量节点，并且极有可能与其他写入线程发生冲突。