java - 高效并发树

Question

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

树应该支持这些操作：

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

Answer 1

看一下： Google 代码上的Concurrent-Trees，了解一种无需锁定即可修改树状结构的方法。

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

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

Answer 2

最接近您可能需要的 Java 结构是ConcurrentSkipListSet（或者可能是ConcurrentSkipListMap）。

---

如果您需要更自定义的方法，如果您有分层读写锁，则可以实现自定义树结构。以下是关于如何实现可重入读写锁的类似问题的答案： https ://stackoverflow.com/a/6154873/272388

Answer 3

您可以在结构中使用读写器锁，这样多个线程可以同时读取，但一次只有一个线程可以修改它。如果某个线程试图修改结构，则在所有读者都完成阅读之前，它不能这样做。如果一个线程想要读取它，那么只有在编写器尚未工作时才能读取它，或者它正在做一些修改。也许看看这个可能会有所帮助：

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

Answer 4

读/写锁的基本思想

对于所有写入方法，请使用以下成语：

someWriteMethod(){
  writeLock.lock();
  // logic
  writeLock.unlock();
}

对于所有读取方法，使用类似的代码：

someReadMethod(){
  readLock.lock();
  // logic
  readLock.unlock();
}

• 如果至少有一种方法执行写入，则没有人可以获得读或写锁。
• 如果至少有一种方法执行读取，则任意数量的线程都可以获得读锁。
• 如果至少有一种方法执行读取，则没有人可以获取写入锁。

请注意，如果您的代码（替换上面的逻辑注释）可能引发异常，请确保您在从 finally 部分中的方法退出之前释放锁。