undergrad一般的时间复杂度：比较黑色树上的B树

Question

我是数据结构的新手。我知道我们使用B树来最小化磁盘旋转，但是为什么我们在B树上使用黑红树来存储内存？是不是都在O（log n）？在我的眼中，B型树的高度较小，需要的空间较小（可以有t-1到2t-1个按键），而红黑树必须有2个子节点用于内部节点。

Answer 1

红黑B树是一种自平衡B树。非自我平衡的B树可能会变得效率低下，尽管您和他们处理它们并手动重新平衡任何时间，这意味着一个巨大的锁！

两者都是二叉树，它们都是O（log n），直到B树随着时间变得不平衡，然后O（log n）不再被保证。