algorithm - 为什么 B-Tree 用于文件系统？

Question

我知道这是一个常见问题，我在 Stack Overflow 中看到了几个线程，但仍然无法理解。

以下是 Stack overflow 的公认答案:

" Disk seeks are expensive. B-Tree structure is designed specifically to avoid disk seeks as much as possible. Therefore B-Tree packs much more keys/pointers into a single node than a binary tree. This property makes the tree very flat. Usually most B-Trees are only 3 or 4 levels deep and the root node can be easily cached. This requires only 2-3 seeks to find anything in the tree. Leaves are also "packed" this way, so iterating a tree (e.g. full scan or range scan) is very efficient, because you read hundreds/thousands data-rows per single block (seek).

In binary tree of the same capacity, you'd have several tens of levels and sequential visiting every single value would require at least one seek. "

我知道 B-Tree 比 BST 有更多的节点(顺序)。所以它肯定比 BST 更平更浅。

但是这些节点再次存储为链表，对吗？

我不明白他们说键是作为一个 block 读取的，从而最大限度地减少了 I/O 的数量。

同样的论点不也适用于 BST 吗？除了链接将向下？

有人给我解释一下吗？

Answer 1

I understand that B-Tree has more nodes (Order) than a BST. So it's definitely flat and shallow than a BST. I don't understand when they say that the keys are read as a block thereby minimising the no of I/Os. Isn't the same argument hold good for BSTs too? Except that the links will be downwards?

基本上，在文件系统中使用 B+ 树背后的想法是减少磁盘读取次数。想象一下，驱动器中的所有 block 都存储为顺序分配的数组。为了搜索一个特定的 block ，你必须进行线性扫描，并且每次都需要 O(n) 来找到一个 block 。对吧？

现在，假设您很聪明并决定使用 BST，太棒了!您可以将所有 block 存储在 BST 中，这大约需要 O(log(n)) 来找到一个 block 。请记住，每个分支都是一次磁盘访问，这是非常昂贵的!

但是，我们可以做得更好!现在的问题是，BST 真的很“高”。因为每个节点只有 2 的扇出(子节点数)因子，如果我们必须存储 N 个对象，我们的树将按 log(N) 高的顺序排列。因此，我们最多必须执行 log(N) 次访问才能找到我们的叶子。

B+树结构背后的想法是增加扇出因子( child 的数量)，降低树的高度，从而减少我们为找到叶子而必须进行的磁盘访问次数。请记住，每个分支都是一次磁盘访问。例如，如果你在 B+ 树的一个节点中打包 X 个键，每个节点将指向最多 X+1 个子节点。

另外，请记住 B+ 树的结构是只有叶子存储实际数据。这样，您可以在内部节点中打包更多键以填满一个磁盘 block ，例如，存储 B+ 树的一个节点。您在一个节点中打包的键越多，它指向的子节点就越多，您的树就会越短，从而减少为找到一个叶子而访问磁盘的次数。

But these nodes are again stored as linked lists right?

此外，在 B+ 树结构中，有时叶子以链表方式存储。请记住，只有叶子存储实际数据。这样，使用链表的思想，当你必须在找到一个 block 后执行顺序访问时，你会比必须再次遍历树才能找到下一个 block 更快，对吧？问题是你还得找到第一个方 block !就此而言，B+树比链表好得多。

想象一下，如果所有的访问都是顺序的并且从磁盘的第一个 block 开始，那么数组会比链表更好，因为在链表中你仍然需要处理指针。但是，根据 Tanenbaum 的说法，大多数磁盘访问不是顺序的，而是对小文件(如 4KB 或更小)的访问。想象一下，如果你每次都必须遍历一个链表来访问一个 4KB 的 block ，这将花费多少时间......

这篇文章解释得比我好得多，而且还使用了图片: https://loveforprogramming.quora.com/Memory-locality-the-magic-of-B-Trees