从我读到的关于红黑树的所有内容来看,它们似乎是存储数据的最佳数据结构。
我正在尝试建立一个数据库,我想知道,就红黑树的实现而言,我应该在哪里更加小心,不应该做什么。
红黑真的那么完美吗?
从我读到的关于红黑树的所有内容来看,它们似乎是存储数据的最佳数据结构。
我正在尝试建立一个数据库,我想知道,就红黑树的实现而言,我应该在哪里更加小心,不应该做什么。
红黑真的那么完美吗?
这取决于您需要如何查询和更新数据。例如,如果您不需要有序数据,则哈希图可能会更好,因为它们具有(预期的)恒定时间查找/插入而不是对数。即使您确实需要有序数据,红/黑树也可能并不完美——尤其是在您实现基于磁盘的数据库时。在基于磁盘的 I/O 中,与顺序块读取相比,查找是昂贵的,因此目标是最小化磁盘访问次数。在这种情况下,B-trees(或 B+-trees,或 B*-trees)更好——这些都是为存储在磁盘上时的快速而设计的。
红黑树对于所有数据访问来说远非完美。它们有自己的位置,但在很多情况下,哈希映射和普通旧列表等其他方法更好。
在很多情况下,红黑树的一个显着缺点是它是二叉树,因此查找时间为 O(lg(n)),而哈希表的查找时间为 O(1)。