use*_*332 0 algorithm binary-tree b-tree binary-search-tree data-structures
我知道这是一个常见的问题,我在Stack Overflow中看到了一些线程,但仍然无法得到它.
这是Stack溢出的公认答案:
"磁盘搜索是昂贵的.B-Tree结构专门设计用于尽可能避免磁盘搜索.因此,B-Tree将更多的键/指针打包到单个节点而不是二叉树.这个属性使得树非常平坦.通常大多数B-Tree只有3或4级深度,并且根节点可以很容易地被缓存.这只需要2-3次寻找在树中找到任何东西.叶子也是这样"填充",所以迭代一棵树(例如完整扫描或范围扫描)是非常有效的,因为您每个块(搜索)读取数百/数千个数据行.
在具有相同容量的二叉树中,您将拥有几十个级别,并且顺序访问每个值将需要至少一次搜索."
据我所知,B-Tree有比BST更多的节点(Order).所以它绝对比BST更平坦,更浅.
但是这些节点又被存储为链表吗？
我不明白他们什么时候说键被读作块,从而最小化I/O的数量.
是不是同样的论点也对BST有利？除了链接将向下？
请有人向我解释一下？
B树节点本质上是具有固定大小的对的阵列,{key, link}其在一个块中读取,通常是一定数量的磁盘块.链接都是向下的.在底层,链接指向相关记录(假设B + -tree,如在任何实际实现中).
我不知道你从哪里得到链表的想法.
我知道 B 树比 BST 有更多的节点（顺序）。所以它绝对比 BST 平坦而浅。我不明白他们什么时候说将键作为一个块读取从而最小化 I/O 的数量。同样的论点对 BST 也适用吗？除了链接会向下？
基本上，在文件系统中使用 B+树背后的想法是减少磁盘读取的次数。想象一下，驱动器中的所有块都存储为一个按顺序分配的数组。为了搜索特定块，您必须进行线性扫描，每次查找块都需要 O(n)。对？
现在，想象一下你变得聪明并决定使用 BST，太棒了！您会将所有块存储在 BST 中，这大约需要 O(log(n)) 才能找到一个块。请记住，每个分支都是磁盘访问，这是非常昂贵的！
但是，我们可以做得更好！现在的问题是 BST 真的很“高”。因为每个节点的扇出（子节点数）因子只有 2，如果我们必须存储 N 个对象，我们的树的高度将是 log(N)。所以我们最多必须执行 log(N) 次访问才能找到我们的叶子。
B+树结构背后的想法是增加扇出因子（子树的数量），降低树的高度，从而减少我们为了找到离开而必须进行的磁盘访问次数。请记住，每个分支都是一个磁盘访问。例如，如果您在 B+树的节点中打包 X 个键，则每个节点将指向最多 X+1 个子节点。
另外，请记住，B+树的结构方式是只有叶子存储实际数据。这样，您可以在内部节点中打包更多键以填充一个磁盘块，例如存储 B+树的一个节点。你在一个节点中打包的键越多，它指向的子节点就越多，你的树就会越短，从而减少磁盘访问次数，以便找到一个离开。
但是这些节点再次存储为链表，对吗？
此外，在 B+树结构中，有时叶子以链表方式存储。请记住，只有叶子存储实际数据。那样的话，根据链表的想法，当你在找到一个块后必须执行顺序访问时，你会比为了找到下一个块而不得不再次遍历树更快，对吧？问题是你仍然必须找到第一个块！为此，B+树比链表要好得多。
想象一下，如果所有访问都是顺序的，并且从磁盘的第一个块开始，数组会比链表更好，因为在链表中你仍然需要处理指针。但是，根据 Tanenbaum 的说法，大多数磁盘访问不是顺序访问，而是访问小文件（如 4KB 或更小）。想象一下，如果你每次都必须遍历一个链表来访问一个 4KB 的块需要多少时间......
这篇文章比我解释得更好，还使用了图片：https : //loveforprogramming.quora.com/Memory-locality-the-magic-of-B-Trees
在磁盘存储中实现的 B 树中的每个节点都包含一个磁盘块（通常为几千字节），其中充满了键和“指针”，这些键和“指针”作为数组而不是（如您所说的）链表进行访问。块大小通常取决于文件系统，并且选择块大小是为了有效地使用文件系统的读写操作。这些指针不是普通的内存指针，而是磁盘地址，再次选择它以便支持文件系统轻松使用。