紅黑樹與B樹

我有一個項目，我必須在數據範圍從兆字節到兆字節的範圍內實現快速搜索，插入和刪除操作。我一直在研究最近的數據結構並分析它們。作爲具體的，我想對引進3例，提出問題：紅黑樹與B樹

的數據比什麼內存可以一氣呵成處理（10-15 TB的樣本範圍）等等。在這種情況下，我會將數據結構存儲在磁盤上。
與系統的內存相比，數據相對較少，因此可以在存儲器本身中存儲和操作以提高速度。
數據不僅僅是空閒內存，並且假定它小於分頁文件中可能的連續數據塊的大小。因此我將數據結構存儲在磁盤上的一個文件中，並執行文件的內存映射。

我已經得出的結論是：

對於情況1，I應，因爲它節省了由磁盤旋轉產生滯後使用B樹以便更快地訪問

對於情況2，I應該使用紅色黑色樹來更快地訪問數據，因爲數據在內存中並且沒有。在最壞的情況下需要掃描的元素將少於我使用B樹時必須要做的一個元素

對於案例3，我對此有疑問，頁面文件在磁盤上使用本機OS I/O對文件進行操作，那麼B樹應該是更好的選擇還是紅黑樹？

我想知道上述三個結論是正確的，哪裏出了問題，以及如何在三個不同的情況下改進性能。

我使用的是C++語言，帶有一個紅黑樹和一個B樹，兩者都是我從頭開始設計的。我正在使用Boost庫進行文件映射。

更新1 ::通過this通過閱讀文章在stackoverflow。得到了一些真正的好的見解，這讓我覺得我在案例中所做的比較類型可能是錯誤的。答案最多的一個鏈接發佈了http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html

來源

2011-06-19 swanar

你要做什麼樣的搜索？按鍵簡單搜索？鑰匙是怎麼樣的？ – svick

你或多或少正確。繼續執行，如果遇到問題，請在此處詢問。 – nikhil

@svick是的我正在按鍵進行簡單的搜索，以最一般的方式，他們可能是一個謹慎的，或以數字連續的順序，從1開始的不同的自然數集合表示一個值，如（2^8）-1 – swanar

紅色/黑色樹或多或少等同於2-3-4樹，它只是一種B型樹。如果您執行B樹節點值的二進制搜索，最差情況下的性能是相同的。

B樹的明顯缺點是浪費空間，但根據所使用的語言/內存分配器，您可能會發現2-3-4樹平均使用的空間少於紅黑樹。例如，在32位Java中，每個對象大約有8個字節的開銷。（這也很大程度上取決於分配器; IIRC phkmalloc向上舍小分配到功率的-2的尺寸）

要回答你的情況下，

磁盤延遲大致均勻尋道時間之間的分裂並等待磁盤旋轉。
如果你做得對，B樹應該能夠勝過紅黑樹（特別是，如果節點適合緩存線，B樹應該更快。）
它不需要在頁面文件中連續;它只需要在進程的虛擬地址空間中連續。對於理智的操作系統，它與案例1幾乎完全相同，除非數據足夠小以至於大部分都適合內存，memcpy開銷很大。

爲了簡單起見，我會使用B樹並在各種節點大小上運行一些基準測試。

來源

2011-06-19 15:40:11

非常感謝投入;即使數據集很大，你是否會建議使用2-3-4樹？如果節點大小與磁盤中的頁面大小相似，不是更好嗎？雖然 – swanar

我確實說過「在各種節點尺寸上運行一些基準測試」，但您確實有支持2-3-4樹作爲紅黑樹替代品的優勢。僅使用B樹的優點是可以運行一些基準並根據自己的喜好進行調整。您還可能想要考慮數據局部性（即，如果您的密鑰是字符串，則可能希望將這些字符串保留在節點附近）。如果分頁速度很慢，那麼您肯定希望節點至少與頁面大小一樣大，但可能會更大（假設您的磁盤沒有預讀）。然後對於SSD的答案是不同的... –

非常感謝您的幫助！ – swanar

爲了理解這些差異，下面2個點讀：

1）A「紅 - 黑樹」是「自動平衡」，「二進制搜索樹」，與每個節點標有顏色（ 2）所有「紅黑樹」均爲「二元搜索樹」，但所有「二元搜索樹」均不是「二元搜索樹」紅黑樹「

來源

2016-03-09 18:28:20

這個解釋使得它聽起來好像BST和B-Tree一樣。比較不在RBT和BST之間，它在RBT和B-Tree之間。 RBT和B-Tree都是BST。 RBT和B-Tree都是平衡的。 –

回答

相關問題