为什么R-tree的并发性能不好

Question

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

谁能给我提示？

Answer 1

当您查看 R-Trees（或 R*Tree、R+Tree，...）的 insertion/deletion 策略时，您会发现节点的 overflow/underflow 可以轻松级联树的大部分（也称为重新平衡）。这需要锁定很多节点，这显然不利于并发。

您可以尝试写时复制策略而不是锁定，但这也很昂贵，因为复制大量节点并且很可能与其他写入线程发生冲突。

Answer 2

查询完全没有问题

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