data-structures - 为什么我们需要一个单独的数据结构(例如B-Tree)用于数据库和文件系统？

Question

我正在阅读B树，看起来它们在O（lg n）时间内实现了动态设置操作。 Red Black Tree（Java中的TreeMap）还可以在渐近相同的时间范围内实现相同的操作。所以我想知道是什么使B树对数据库和文件系统更有用

Answer 1

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


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


因此，我们可以利用第二个事实的优点，同时也可以最大程度地减少缺点-即磁盘访问次数。

因此，我们不仅可以在告诉我们是否应该继续向左还是向右的每个节点中存储单个数字，还可以创建一个更大的索引来告诉我们是否应该继续到第一个1/100，再到第二个索引或到第99位（想象一下图书馆中的书，按第一个字母排序，然后第二个字母排序，依此类推）。只要所有这些数据都适合单个扇区，无论如何都将加载它们，因此我们不妨完全使用它。

这将导致大约logb N次查询，其中N是记录数。这个数字虽然渐进地与log2 N相同，但实际上实际上要小几倍，并且N和b足够大-并且由于我们正在谈论将数据存储到磁盘以供数据库等使用，因此数据量通常很大足以证明这一点。

设计决策的其余部分主要是为了使这一设计有效地进行，因为修改N元树比二元树更棘手。