1

假设我们在内存中实现 B+ 树，键位于内部节点，键-数据对位于叶节点。如果 B+tree 带有扇出 f，这意味着 B+ 树的高度为 log_f N，其中 N 是键的数量，而相应的 BST 的高度为 log_2 N。如果我们不进行任何磁盘读取并写道，B+tree 的搜索性能能否优于 Binary Search Tree 的搜索性能？如何？因为对于每个内部节点的 B+tree，我们已经对 F 多个选择做出了决定，而不是 1 用于 BST？

4

1 回答 1

0

至少与高速缓存相比，主存储器具有许多与磁盘驱动器相同的特性——它具有相当高的带宽，但比高速缓存高得多的延迟。它具有相当大的最小读取大小，并且当读取是可预测的（例如，当您在连续地址读取多个高速缓存行时）提供显着更高的带宽。因此，它受益于相同的一般优化类型（尽管细节通常有所不同）。

B 树（以及 B* 和 B+ 树之类的变体）被明确设计为可以很好地与磁盘驱动器支持的访问模式一起工作。由于无论如何您都必须读取相当大量的数据，因此您不妨打包数据以最大化您从必须读取的内存中完成的数量。在这两种情况下，您还经常通过以可预测的模式读取最小读取的一些倍数（尤其是在连续地址上的多次连续读取）来获得可观的带宽增益。因此，将单个页面的大小增加到比您一次可以阅读的最小值更大的大小通常是有意义的。

同样，在这两种情况下，我们都可以计划在找到我们真正关心的数据之前通过树中的多个节点层进行下降。就像从磁盘读取时一样，我们受益于最大化我们读取的数据中的键密度，直到我们真正找到我们关心的数据。使用典型的二叉树：

template <class T, class U>
struct node {
    T key;
    U data;
    node *left;
    node *right;
};

...我们最终会读取一些我们没有实际用途的数据项。只有当我们找到了我们需要/想要获取相关数据的正确密钥时。公平地说，我们也可以用二叉树来做到这一点，只需对节点结构进行相当小的修改：

template <class T, class U>
struct node {
    T key;
    U    *data;
    node *left;
    node *right;
};

现在该节点只包含一个指向数据的指针，而不是数据本身。如果它很小，这不会完成任何事情data，但如果它很大，则可以完成很多事情。

总结：从 CPU 的角度来看，从主存读取与从磁盘读取具有相同的基本特征；磁盘只是显示了这些相同特征的更极端版本。因此，导致设计 B 树（和变体）的大多数设计考虑现在类似地适用于存储在主存储器中的数据。

B-trees 运行良好，并且在用于内存存储时通常会提供实质性的好处。

于 2017-12-13T07:16:58.020 回答