高效的并发树

Question

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

树应该支持这些操作:

Answer 1

请看一下:Google代码上的Concurrent-Trees,用于修改树状结构而无需锁定.

该项目为Java提供了Concurrent Radix和Suffix树.它们支持并发读写,读取是无锁的.它的工作原理是通过原子方式将补丁应用于树.虽然这些类型的树可能不是您想要的,但使用TreeDesign中描述的"修补"的方法对于任何类型的树状结构都很有用.

这些树用于高并发读取 - 主要是用例,其中(比方说)后台线程可能正在插入或删除树中的条目,而许多前台线程将继续不受阻止地进行修改.

我会避免使用“无用”之类的词。该答案有助于自愿帮助您。如果您正在寻找只读的并发树，那么无锁算法可能是一个不错的选择。基数树可能不完全是您想要的树，但是正如我提到的，我链接到的原子修补方法可以应用于任何类型的树以进行无锁读取，即使您打算编写自己的自定义树树。附带说明，基树显然是具有父子结构的树。 (2认同)

Answer 2

最接近您可能需要的Java结构是ConcurrentSkipListSet(或者ConcurrentSkipListMap).

如果需要更自定义的方法,则可以实现自定义树结构(如果您具有分层读写锁).这是一个关于如何实现可重入读写锁的类似问题:https://stackoverflow.com/a/6154873/272388