最佳的樹數據結構

我有一個樹，有很多節點（百萬+），需要加載到內存中。因此，我需要以最有效的方式將節點及其關係存儲在內存中。什麼是最好的數據結構？到現在爲止，我有兩個選擇：最佳的樹數據結構

//more obvious but the less efficient 
class TreeNode 
{ 
Node parent; 
TreeNode[] children; 

//additional fields 
byte X; 
byte Y; 
byte marker; 
string comment; 
} 

//more efficient 
class TreeNode 
{ 
TreeNode next; //reference to the next child of parent node, 
       //if isLast=true - reference to parent node 

TreeNode firstChild; //reference to the first child of this node 

bool isLast; //true, if this node is the last parents child 

//additional fields 
byte X; 
byte Y; 
byte marker; 
string comment; 
}

注意，我需要在這棵樹執行諸如瀏覽，刪除和插入，我需要這些足夠快。

編輯：最適合這種情況是使用較少的RAM來存儲整個樹。第二個標準是快速刪除，瀏覽和插入操作 - 在我上面寫的數據結構中，它們不應該花費更多的時間。我不能制定這個標準更嚴格

來源

2013-09-28 DizzyBlack

建議使用F＃爲此！ –

我編輯了你的標題。請參閱：「[應該在其標題中包含」標籤「]（http://meta.stackexchange.com/questions/19190/）」，其中的共識是「不，他們不應該」。 –

你的標準樹算法可以工作，但是如果你在一個'List <>'中創建節點結構並且使用索引而不是引用來引用它們，那麼GC可能會更容易。 –

這聽起來像你有一個變化的，在內存中的數據集。如果是這樣，那麼知道哪些操作是常見的將是非常重要的。例如，當你提到「瀏覽」時，這是一種搜索，還是簡單地遍歷你目前正在查看的節點中的父母或孩子？

如果它是一個搜索，並且如果這通常是第一個操作（即，您找到一個具有值的節點，然後您做了一些操作），那麼您可以考慮使用Red/Black Tree。該結構需要記錄搜索，插入和刪除時間。插入和刪除過程中強加的規則保持樹的優化以進行搜索。

如果搜索速度不重要，那麼您可以使用更簡單的樹結構加快插入和刪除。

就你的空間而言，紅/黑樹就像其他所有樹型結構一樣，需要n個空間。這與你可以爲結構本身做的事情差不多。儘管如此，因爲你可以採取創造性的措施。

例如，您要在每個節點中存儲3個字節和一個字符串。是否有可能將這些數據的一部分僅存儲在內存中，並根據需要從持久性存儲（例如數據庫）中查找其餘數據？對於標準的樹操作來說，它不一定需要數據，但也許是可行的。或者，是否可以壓縮內存中的字符串數據？

來源

2013-09-28 19:18:57 rileywhite

感謝提示。我的案例最常見的操作是瀏覽（上下樹）和插入，因爲我經常需要合併幾棵樹。另外，通過包含在這3個字節中的附加信息進行搜索。是的，我在考慮優化這些額外的3個字節和一個字符串，但實際上大部分空間都是由類引用（字符串ref，next和firstchild refs）使用的。我正在考慮做的進一步優化是在加載後緩存部分樹（例如，深度> 40或其他條件的節點），並在第一次請求後再次加載它們。 – DizzyBlack

這會減慢搜索和加載速度，但我認爲它有可能找到一個很好的折中方案。 – DizzyBlack

從我直接使用C++類型的結構開始已經有一段時間了，但是當我完成時，我正在使用btree結構。前提是相似的，但是在單個節點上，每個級別可以有8個（或更多）鍵。但是如果你正在處理數以百萬計的條目，可能是需要研究的東西？

前提說在頂層節點你有8個鍵...爲了簡單理解一個90k條目的樹，頂層節點是10k，20k，30k ... 80k。因此，如果您要查找的數量少於10k，那麼它就會下降......少於20k就會下降，因此，通過測試單個節點級別上可用的一些元素，您基本上可以拋出其他80k。

因此，例如，你正在尋找26,895。它從頂層節點開始，獲得您想要的30k（小於30k，但超過20k）。現在加載下一個節點。但是這個節點跨越20,001至29,999。對於咧嘴笑，它的關鍵是21250,22500,2750,2500,26250,27500,28750,29999（每個1250的中斷）。所以現在你已經達到了27500，你還不到這個水平，而且它還要進一步深入。這個級別現在跨越你的26250到27499的差距，你只是第二級。

你顯然需要一本書或更強的參考來完成，但btrees可以相當強大和快速。

來源

2013-09-28 19:46:49 DRapp

謝謝你的提示！我會調查btrees，因爲我的問題變得更加重要。 – DizzyBlack

最佳的樹數據結構

回答

相關問題