blocks|key|993858|text|看看:谷歌代码上的并发树，它提供了一种无需锁定就可以修改树状结构的方法。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|993859|该项目为Java提供并发的基数和后缀树。它们支持并发读和写，并且读取是无锁的.它通过原子地将补丁应用到树上来工作。虽然这些类型的树可能不是您想要的，但是使用TreeDesign中描述的“修补”的方法对于任何类似树的结构都是有用的。|993860|这些树用于高并发性读取--主要是用例，其中一个后台线程可能从树中插入或删除条目，而许多前台线程将继续不受修改的阻碍地遍历它。|993861|entityMap|0|LINK|mutability|MUTABLE|url|http://code.google.com/p/concurrent-trees/|1|https://code.google.com/p/concurrent-trees/wiki/TreeDesign^0|9|3|0|0|26|A|1|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@$A|W|B|X|1|Y]]|C|$]]|$1|F|3|G|5|6|7|Z|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|Q]]]]

Take a look at: <a href="http://code.google.com/p/concurrent-trees/" rel="noreferrer">Concurrent-Trees</a> on Google code for a way to modify tree-like structures without locking.

The project provides Concurrent Radix and Suffix trees for Java. They supports concurrent reads and writes, and reads are lock-free. It works by applying patches to the tree atomically. While these types of tree might not be exactly what you want, the approach using "patching" as described in <a href="https://code.google.com/p/concurrent-trees/wiki/TreeDesign" rel="noreferrer">TreeDesign</a> is useful for any kind of tree-like structure.

The trees are intended for high concurrency read-mostly use cases, where (say) a background thread might be inserting or deleting entries from the tree while many foreground threads would continue to traverse it unimpeded by the modifications.

blocks|key|993811|text|与您可能需要的最接近的ConcurrentSkipListSet结构是一个ConcurrentSkipListMap(或者是ConcurrentSkipListMap)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|993812|如果您需要更多的自定义方法，则如果您具有层次式读写锁，则可以实现自定义树结构。下面是一个关于如何实现可重入读写锁的类似问题：https://stackoverflow.com/a/6154873/272388|993813|entityMap|0|LINK|mutability|MUTABLE|url|http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListSet.html|1|http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html|2|3|https://stackoverflow.com/a/6154873/272388^0|B|L|0|11|L|1|1Q|L|2|0|1Q|16|3|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@$A|T|B|U|1|V]|$A|W|B|X|1|Y]|$A|Z|B|10|1|11]]|C|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@$A|13|B|14|1|15]]|C|$]]|$1|F|3|-4|5|6|7|16|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]|P|$5|I|J|K|C|$L|O]]|Q|$5|I|J|K|C|$L|R]]]]

The Java structure that is the closest to what you may need is a <a href="http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListSet.html" rel="nofollow noreferrer">ConcurrentSkipListSet</a> (or maybe <a href="http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html" rel="nofollow noreferrer">ConcurrentSkipListMap</a>).

<hr>

If you need a more custom approach, you can implement a custom tree structure if you have a hierarchic read-write lock.
Here is an answerto a similar question about how to implement a reentrant read-write lock:
<a href="https://stackoverflow.com/a/6154873/272388">https://stackoverflow.com/a/6154873/272388</a>

blocks|key|993746|text|您可以在结构中使用读取器锁，多个线程可以读取当前的数据，但一次只能读取一个线程。如果某些线程试图修改结构，则在所有读取器都完成其读取之前，它无法进行修改。如果一个线程想要阅读，它只能在一个作者还没有工作的情况下才能读到，或者它需要做一些修改。也许看看这个可以帮上忙：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|993747|http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html|offset|length|993748|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|2R|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@$D|O|E|P|1|Q]]|A|$]]|$1|F|3|-4|5|6|7|R|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|C]]]]

You could use a reader-writer lock in your structure, in a way that multiple threads can read cuncurrently but only one thread at a time can modify it.
If some thread tries to modify the structure it cannot do it until all of the readers have done their reads.
If a thread wants to read it can only if a writer isn't already working, or it is on shedule of doing some modifications.
Maybe a look at this could help:

<a href="http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html" rel="nofollow">http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html</a>

blocks|key|993770|text|读写锁的基本思想|type|unstyled|depth|inlineStyleRanges|entityRanges|data|993771|对于所有的写方法，请使用以下成语：|993772|someWriteMethod(){
++writeLock.lock();
++//+logic
++writeLock.unlock();
}|code-block|syntax|javascript|993773|对于所有读取方法，请使用类似的代码：|993774|someReadMethod(){
++readLock.lock();
++//+logic
++readLock.unlock();
}|993775|如果至少有一种方法执行写入，则没有人能够获得读或写锁。|unordered-list-item|993776|如果至少有一种方法执行读取，那么任意数量的线程都可以获得重新锁定。|993777|如果至少有一种方法执行读取，则没有人能够获得写锁。|993778|注意，如果您的代码(替换上面的逻辑注释)可以抛出异常，请确保在退出最后一节的方法之前释放锁。|993779|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Y|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Z|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|10|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|11|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|O|7|12|8|@]|9|@]|A|$]]|$1|P|3|Q|5|O|7|13|8|@]|9|@]|A|$]]|$1|R|3|S|5|O|7|14|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|15|8|@]|9|@]|A|$]]|$1|V|3|-4|5|6|7|16|8|@]|9|@]|A|$]]]|W|$]]

Basic idea with Read/Write lock

For all write methods use following idiom:

<pre><code>someWriteMethod(){
 writeLock.lock();
 // logic
 writeLock.unlock();
}
</code></pre>

For all read methods use similar code:

<pre><code>someReadMethod(){
 readLock.lock();
 // logic
 readLock.unlock();
}
</code></pre>

<ul>
<li>If at least one method performs writing, no one can obtain read or write lock.</li>
<li>If at least one method performs reading, any numbers of thread can obtain readlock.</li>
<li>If at least one method performs reading, no one can obtain write lock.</li>
</ul>

Note, if your code (replace logic comment above) can throw exception make sure you release locks before exit from method in finally section.

I'm looking for an efficient way to implement a concurrent tree structure. If that helps, assume that I have a lot more read accesses than changes to the structure.

The tree should support these operations:

<ul>
<li>Adding and removing nodes</li>
<li>Sort branches every time a new node is inserted</li>
<li>Iterate over all the nodes (without ConcurrentModificationException)</li>
<li>Look up an element by path</li>
</ul>

Efficient concurrent tree

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我正在寻找一种实现并发树结构的有效方法。如果这有帮助，那么假设我有更多的读取访问权限，而不是对结构的更改。树应该支持这些操作：添加和删除节点每次插入新节点时排序分支。遍历所有节点(没有ConcurrentModificationException)按路径查找元素

问有效并发树
EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问有效并发树EN

回答 4

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问有效并发树
EN