高效併發樹

我正在尋找一種有效的方法來實現併發樹結構。如果這有幫助，假設我有更多的讀取訪問比結構的更改。高效併發樹

樹應支持這些操作：

添加和刪除節點
排序每一個新的節點插入
遍歷所有節點（不ConcurrentModificationException的）
查找時間分支機構路徑中的元素

來源

2012-06-25 Aaron Digulla

看看：在谷歌代碼Concurrent-Trees一種方式來修改樹狀結構沒有鎖定。

該項目爲Java提供了併發基數和後綴樹。它們支持併發讀取和寫入，並且讀取是無鎖的。它通過以原子方式將修補程序應用於樹來工作。雖然這些類型的樹可能不是您想要的，但使用TreeDesign中描述的「修補」的方法對於任何類型的樹狀結構都很有用。

這些樹旨在用於高併發讀取主要用例，其中（例如）後臺線程可能會插入或從樹中刪除條目，而許多前臺線程將繼續無障礙地通過修改。

來源

2012-07-02 17:13:06 npgall

這很有趣，但在我的用例中沒用。我的樹是真正的樹（父子結構），而不是鍵值映射。 –

我會避免使用「無用」這樣的詞。這個答案有助於你自願幫助你。如果您正在尋找以大部分爲主的併發樹，那麼無鎖算法可能是一個好方法。基數樹可能並不完全符合您的要求，但正如我所提到的，我鏈接到的原子修補方法可以應用於任何類型的樹以實現無鎖讀取，即使您打算編寫自己的自定義樹。附帶說明，基數樹顯然是具有親子結構的樹。 – npgall

+1我改進了措辭，使你的意圖更清晰。 –

您可以在您的結構中使用讀寫器鎖，我n多線程可以正常讀取的方式，但一次只能有一個線程可以修改它。如果某個線程試圖修改該結構，那麼直到所有讀者完成讀取操作後才能完成該操作。如果一個線程想要閱讀它，只有當一個作者還沒有工作時，或者它正在做一些修改。也許一看這能幫助：

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

來源

2012-06-25 13:04:56 giocarmine

+1對於讀/寫鎖 – mishadoff

基本思路與讀/寫鎖定

所有寫方法使用下面的語句：

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

對於所有的閱讀方法使用類似代碼：

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

如果至少有一個方法執行寫操作，則沒有人可以獲得讀取或寫入鎖定。
如果至少有一個方法執行讀取，任何數量的線程都可以獲得讀取鎖定。
如果至少有一個方法執行讀取操作，則沒有人可以獲得寫入鎖定。

請注意，如果您的代碼（上面的替換邏輯註釋）可以拋出異常，請確保您在finally節的方法退出之前釋放鎖。

來源

2012-06-25 13:12:22 mishadoff

讀寫鎖有一個缺點：您不能將讀取升級到寫入鎖，因此您需要事先知道您的操作是否會修改樹。所以這需要兩個迭代器，其中一個可能會鎖定太多。 –

我假設你事先知道使用哪些樹來修改你的樹，不是嗎？ – mishadoff

當我問樹的迭代器時，創建迭代器的方法無法知道我是否會調用remove（）或不。 –

與您可能需要的最接近的Java結構是ConcurrentSkipListSet（或可能是ConcurrentSkipListMap）。

如果您需要更多的自定義的方法，你可以，如果你有一個層次讀寫鎖實現自定義的樹結構。這裏是一個answerto有關如何實現折返讀寫鎖一個類似的問題： https://stackoverflow.com/a/6154873/272388

來源

2012-06-25 13:15:06 Kru

CSLM並不是非常接近。它是一個*排序的地圖*與樹結構無關。所以它只與'TreeMap'共享一個屬性，因爲它是一個有序的映射 - 這在這裏不重要。 –

這就是爲什麼有答案的第二部分，因爲我不知道Java中包含的任何支持所有這些操作的樹結構。而且，對於一些類似的情況，CSLM可能已經足夠了。 – Kru

Kru仍然是正確的：它是官方運行時中唯一與我的問題最接近的數據結構。我可以使用嵌套的ConcurrentSkipListMaps +鎖來構建樹。 –

回答

相關問題