红黑树的缺点是什么？

Question

从我一直在阅读的有关红色-黑色树的所有内容来看，似乎它们是用于存储数据的最佳数据结构。

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

红色-黑色真的那么完美吗？

Answer 1

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