21

我正在阅读 B 树，看起来它们在 O(lg n) 时间内实现了动态集合操作。红黑树（Java中的TreeMap）也在渐近相同的时间范围内实现了相同的操作。所以我想知道是什么让 B 树对数据库和文件系统更有用

4

3 回答 3

28

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

  • 访问磁盘真的很慢（与内存或缓存相比，随机访问磁盘上的数据要慢几个数量级）；和
  • 每次读取都会导致从驱动器加载整个扇区 - 假设扇区大小为 4K，这意味着 1000 个整数或数十个您要存储的较大对象。

因此，我们可以利用第二个事实的优点，同时尽量减少缺点——即磁盘访问次数。

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

这导致大致 log b N 查找，其中 N 是记录数。这个数字虽然与 log 2 N渐近相同，但实际上在 N 和 b 足够大的情况下要小几倍——而且由于我们正在讨论将数据存储到磁盘以供数据库等使用，因此数据量通常为大到足以证明这一点。

其余的设计决策主要是为了使这一工作有效地完成，因为修改 N 叉树比二叉树更棘手。

于 2012-10-10T21:10:20.380 回答
11

RB树是二叉搜索树。B 树可以有两个以上的子节点。事实上，子节点的数量是可变的。

因此，您可以改变子节点的数量，使节点的大小始终是文件系统块大小的倍数。这减少了阅读时的浪费：无论如何，你不能阅读少于一个块，你总是必须阅读整个块，所以你最好用有用的数据填充它。增加子节点的数量也会降低树的深度，从而减少“跳”的平均数量（即磁盘读取），这再次提高了性能。

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

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

B树针对读写大数据块的系统进行了优化

于 2012-10-10T12:27:25.007 回答
2

我们需要不同的算法，因为内存中的访问速度比磁盘上的快得多。红/黑树会进行多次内存访问，因此它与内存的快速访问速度配合得很好。b-tree 进行更少、更大的访问，因为正在访问的磁盘很慢。

于 2012-10-10T12:53:46.777 回答