java - 高效的并发树

Question

我正在寻找一种有效的方法来实现并发树结构。如果这有帮助，假设我有比结构更改更多的读取访问权限。

树应该支持这些操作:

• 添加和删除节点
• 每次插入新节点时对分支进行排序
• 遍历所有节点(没有 ConcurrentModificationException)
• 通过路径查找元素

Answer 1

看看:Concurrent-Trees在 Google 代码上寻找一种无需锁定即可修改树状结构的方法。

该项目为 Java 提供并发基数树和后缀树。它们支持并发读取和写入，并且读取是无锁的。它通过原子地向树应用补丁来工作。虽然这些类型的树可能不是您想要的，但使用“修补”的方法如 TreeDesign 中所述对于任何类型的树状结构都很有用。

树旨在用于高并发读取为主的用例，其中(比方说)后台线程可能正在从树中插入或删除条目，而许多前台线程将继续遍历它而不受修改的阻碍。