紅黑樹的缺點是什麼？

Question

從我讀到的關於紅黑樹的所有內容看來，它們似乎是存儲數據的最佳數據結構。

我想建立一個數據庫，我想知道，只是在紅黑樹實現方面，我應該在哪裏更加小心，什麼我不應該做。

紅色 - 黑色是否真的很完美？

Answer 1

紅黑樹對於所有的數據訪問來說都非常完美。他們有自己的位置，但其他方法（如哈希映射和普通舊列表）在很多情況下都更好。

在很多情況下，紅黑樹的一個顯着缺點是它是二叉樹，因此查找是O（lg（n）），其中散列表查找O（1）。

Answer 2

這取決於您如何查詢和更新數據。例如，如果您不需要有序數據，hashmaps可能會更好，因爲它們具有（預期的）恆定時間查找/插入而不是對數。即使你確實需要有序的數據，紅/黑樹也許並不完美 - 尤其是，如果你正在實現一個基於磁盤的數據庫。在基於磁盤的I/O中，與連續塊讀取相比，尋找成本較高，因此目標是儘可能減少磁盤訪問次數。在這種情況下，B樹（或B +樹或B樹）更好 - 這些都是爲了在存儲在磁盤上時速度很快而設計的。