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

Question

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

Answer 1

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

• 访问磁盘非常慢(与内存或缓存相比,对磁盘上数据的随机访问速度要慢几个数量级); 和
• 每次读取都会导致整个扇区从驱动器加载 - 假设扇区大小为4K,这意味着1000个整数,或者您存储的数十个较大的对象.

因此,我们可以使用第二个事实的优点,同时也最小化磁盘访问的缺点.

所以,而不只是存储,它告诉我们,如果我们要继续向左或向右每个节点单号,我们可以创建,它告诉我们一个更大的索引,如果我们要继续第一1/100,到第二或者到第99个(想象一下图书馆中的书籍,按照第一个字母排序,然后按第二个字母排序,依此类推).只要所有这些数据都适合单个扇区,它就会被加载,所以我们不妨完全使用它.

这导致大致log _b N次查找,其中N是记录的数量.这个数字,而渐近一样日志₂ N,居然是用足够大的N和B时几次-因为我们正在谈论将数据存储到磁盘用于数据库等应用,数据量通常是大到足以证明这一点.

设计决策的其余部分主要是为了使这一工作有效,因为修改N元树比二元树更难.

Answer 2

RB树是二叉搜索树.B树可以有两个以上的子节点.实际上,子节点的数量是可变的.

因此,您可以改变子节点的数量,使节点的大小始终是文件系统块大小的倍数.这样可以减少阅读时的浪费:无论如何,你不能读取少于一个的块,你总是必须阅读整个块,所以你也可以用有用的数据填充它.增加子节点的数量也将减少树的深度,从而减少"跳"(即磁盘读取)的平均数量,这再次提高了性能.

记住:B树通常用于存储比存储器大几个数量级的数据结构,而RB树通常用于存储比存储器小几个数量级的数据结构.实际上,B树是专门设计为磁盘上数据结构而不是内存数据结构.

这是维基百科文章中的关键句子(强调我的):

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