2

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

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

红黑真的那么完美吗?

4

2 回答 2

5

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

于 2011-05-10T15:07:18.960 回答
4

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

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

于 2011-05-10T15:03:18.793 回答