database - 红黑树有什么缺点？

Question

从我读到的关于红黑树的所有内容来看，它们似乎是存储数据的最佳数据结构。

我正在尝试建立一个数据库，我想知道，就红黑树的实现而言，我应该在哪里更加小心，不应该做什么。

红黑真的那么完美吗？

Answer 1

这取决于您需要如何查询和更新数据。例如，如果您不需要有序数据，则哈希图可能会更好，因为它们具有（预期的）恒定时间查找/插入而不是对数。即使您确实需要有序数据，红/黑树也可能并不完美——尤其是在您实现基于磁盘的数据库时。在基于磁盘的 I/O 中，与顺序块读取相比，查找是昂贵的，因此目标是最小化磁盘访问次数。在这种情况下，B-trees（或 B+-trees，或 B*-trees）更好——这些都是为存储在磁盘上时的快速而设计的。

Answer 2

红黑树对于所有数据访问来说远非完美。它们有自己的位置，但在很多情况下，哈希映射和普通旧列表等其他方法更好。

在很多情况下，红黑树的一个显着缺点是它是二叉树，因此查找时间为 O(lg(n))，而哈希表的查找时间为 O(1)。