適合嵌套散列的數據結構

什麼是適當的數據結構來表示像下面的關係？例如，我最好是將它表示爲一棵樹嗎？如果是這樣，那三個看起來如何？我的目標是在記憶中擁有最佳記憶足跡的A級實例，並且還可以快速插入到任意一層的嵌套。適合嵌套散列的數據結構

每個嵌套字典雲有幾百萬個項目，E類大小可以是每個類大約10MB。

public class A 
    { 
     private Dictionary<int, B> someName; 
    } 

    public class B 
    { 
     private Dictionary<int, C> someName; 
    } 

    public class C 
    { 
     private Dictionary<int, D> someName; 
    } 

    public class D 
    { 
     private Dictionary<int, E> someName; 
    } 

    public class E 
    { 
      //10 Mb worth of properties 
    }

來源

2013-02-14 iCode

int的範圍如何？ – StarPinkER 2013-02-14 05:05:54

這是隨機的。任何32位int – iCode 2013-02-14 09:01:36

有很多算法和數據結構上的外部存儲器，其中可能包含你想要什麼，因爲你的數據量是非常大的。

當我們處理外部內存問題時，我們通常使用每個操作的I/O來評估數據結構的有效性。

I/O Model

你想表示此爲一棵樹，我認爲這是一個可行的解決方案。基本上，我們需要一棵搜索樹，就像一棵B樹。更具體地說，外部存儲器上的平衡B樹。

我想你可以使用B樹和BB [α]樹的組合來解決這個問題。

A重量平衡的B-樹具有參數B和K（B> 8，k≥8）保持以下約束條件：

在同一高度的所有葉以及k/4與k之間包含元素。
在級別l的內部節點v具有w（v）< b^l * k。
除根以外，級別l處的內部節點v具有w（v）> 1/4 * b^l * k。
根有多個孩子。

我們可以推斷，內部節點度是之間（1/4 * B^L * K）/（B^L * K）= 1/4B和（b^L * K）/（1/4 * b^l-1 * k）= 4b。

重平衡B-樹與分支參數b和葉參數k =Ω（B）具有以下性能：

Weight-Balanced B-Tree

空間：O（N/B）
高度：O（日誌（b，N/k））的
O（日誌（b，N））的更新後的重新平衡操作

的證明不是很複雜，可以在Lars Arge所寫的External Memory Geometric Data Structures中看到。關於外部存儲器數據結構的說明非常好，我強烈建議您閱讀。您可以從閱讀L.Arge的lecture notes開始，它可以快速幫助您理解這些數據結構並作出決定。

來源

2013-02-14 10:42:49 StarPinkER

非常感謝您的好評。如果我的實例類A實際上適合內存，那麼購買該怎麼辦？我仍然會使用相同的數據結構嗎？ – iCode 2013-02-15 21:31:13

我以爲你正在請求一些數據結構來處理int-> E映射。那麼如果數據量非常大，這個數據結構非常好。但我意識到你想保持int-> B（int-> C（...））映射。由於A/B/C/D的單個實例可以放入內存，我認爲您可以直接使用您在該問題中發佈的代碼。 – StarPinkER 2013-02-16 02:10:11

適合嵌套散列的數據結構

回答

相關問題