我正在学习B树,它似乎可以在O(lg n)的时间内实现动态集合操作。红黑树(Java TreeMap)也可以在渐近相同的时间范围内实现相同的操作。因此,我想知道什么使得B树更适用于数据库和文件系统。
我正在学习B树,它似乎可以在O(lg n)的时间内实现动态集合操作。红黑树(Java TreeMap)也可以在渐近相同的时间范围内实现相同的操作。因此,我想知道什么使得B树更适用于数据库和文件系统。
红黑树是二叉查找树。B树可以有超过两个子节点。事实上,子节点的数量是可变的。
因此,您可以变化子节点的数量,使得节点的大小始终是文件系统块大小的倍数。这样做可以减少读取时的浪费:无论如何,您都不能少于一个块读取,您总是必须读取整个块,因此您可能会将其用有用数据填满。增加子节点的数量也会减少树的深度,从而减少“跳跃”(即磁盘读取)的平均次数,进而提高性能。
请记住:B树通常用于存储比内存大几个数量级的数据结构,而红黑树通常用于存储比内存小几个数量级的数据结构。事实上,B树是专门设计为磁盘上的数据结构,而不是内存中的数据结构。
这是来自维基百科文章的关键句子(重点在我方):
B树被优化用于读写大块数据的系统
我们需要不同的算法,因为内存访问速度比磁盘快得多。红黑树进行许多内存访问,因此它可以很好地与内存的快速访问速度配合使用。B树进行较少但更大的访问,因为被访问的磁盘速度较慢。