为什么我们需要像B-Tree这样的单独数据结构来支持数据库和文件系统？

Question

我正在学习B树，它似乎可以在O(lg n)的时间内实现动态集合操作。红黑树（Java TreeMap）也可以在渐近相同的时间范围内实现相同的操作。因此，我想知道什么使得B树更适用于数据库和文件系统。

- Geek

---

维基百科对B-Tree解决的问题有很好的描述 - http://en.wikipedia.org/wiki/B-tree#The_database_problem。 - Ivan Vergiliev

@IvanVergiliev，您能否总结维基中相关部分并以答案的形式呈现，以便我接受它。 - Geek

Answer 1

B树存在的主要原因是更好地利用读写大块数据设备的行为。当数据必须存储在磁盘上时，使B-Tree优于二叉树的两个属性很重要：

• 访问磁盘真正缓慢（与内存或高速缓存相比，对磁盘上的数据进行随机访问的速度慢得多）；以及
• 每次读取都会导致整个扇区从驱动器加载 - 假设扇区大小为4K，则意味着1000个整数，或者您存储的一些较大对象的十个。

因此，我们可以利用第二个事实的优点，同时最小化缺点-即磁盘访问次数。

所以，我们可以创建一个更大的索引，告诉我们是否应该继续前1/100，第二个还是第99个（想象一下按其第一个字母排序的图书馆中的书籍，然后按第二个字母排序，依此类推）。只要所有这些数据适合单个扇区，它就会被加载，因此我们完全可以使用它。

这导致大约对数_b N次查找，其中N是记录的数量。这个数字虽然渐近地与log₂ N相同，但是当N和b足够大时，这个数字实际上会减少几倍-由于我们正在讨论将数据存储到用于数据库等的磁盘中，因此数据量通常足够大以证明这一点。

其余设计决策主要是为了使其有效地工作，因为修改N-ary树比二叉树棘手。

- Ivan Vergiliev

---

谢谢！我至少阅读了50篇关于B树使用的文章，但没有人提到磁盘访问的第二个缺点，而B树将其转化为优点。 - ernesto

我可以在哪里学习如何实现B树？谢谢。 - tonix

Answer 2

红黑树是二叉查找树。B树可以有超过两个子节点。事实上，子节点的数量是可变的。

因此，您可以变化子节点的数量，使得节点的大小始终是文件系统块大小的倍数。这样做可以减少读取时的浪费：无论如何，您都不能少于一个块读取，您总是必须读取整个块，因此您可能会将其用有用数据填满。增加子节点的数量也会减少树的深度，从而减少“跳跃”（即磁盘读取）的平均次数，进而提高性能。

请记住：B树通常用于存储比内存大几个数量级的数据结构，而红黑树通常用于存储比内存小几个数量级的数据结构。事实上，B树是专门设计为磁盘上的数据结构，而不是内存中的数据结构。

这是来自维基百科文章的关键句子（重点在我方）：

B树被优化用于读写大块数据的系统

- Jörg W Mittag

Answer 3

我们需要不同的算法，因为内存访问速度比磁盘快得多。红黑树进行许多内存访问，因此它可以很好地与内存的快速访问速度配合使用。B树进行较少但更大的访问，因为被访问的磁盘速度较慢。

- user448810