database - B+ 树相对于 BST 的优势？

Question

我在关于数据库的课程中学习 B+ 树，我想知道 B+ 树相对于二叉搜索树有哪些具体优势？

对于大多数值得注意的操作，它们似乎都具有 O(logN) 平均复杂度，但是 B+ 树在每个子节点上也有额外的（可以忽略不计？）搜索时间，其中 BST 显然只需要 O(1) 时间来确定哪个子节点前进到。

哪些实际优势使 B+ 树在数据库中比 BST 更受欢迎？

Answer 1

B+ 树（以及一般的 B 树）相对于二叉搜索树的主要优势在于它们可以很好地处理缓存。如果你有一棵二叉搜索树，它的节点在内存中以或多或少的随机顺序存储，那么每次你跟随一个指针时，机器都必须将一个新的内存块拉入处理器缓存，这比访问已经在缓存中的内存。

B+-tree 和 B-tree 通过让每个节点存储大量键或值并拥有大量子节点来工作。它们通常以某种方式打包在一起，使单个节点可以很好地放入缓存中（或者，如果存储在磁盘上，则可以在单个读取操作中从磁盘中提取）。然后您必须做更多的工作才能在节点中找到一个键或确定接下来要读取哪个子节点，但是因为在单个节点上完成的所有内存访问都可以在不返回磁盘的情况下完成，所以访问时间非常短。这意味着即使原则上 BST 在内存访问次数方面可能更好，但 B+-tree 和 B-tree 在这些内存访问的运行时间方面可以执行得更好。

B+-tree 或 B-tree 的典型用例是在数据库中，其中有大量信息并且数据非常多，以至于它们无法全部放入主内存中。因此，数据可以存储在硬盘某处的 B+-tree 或 B-tree 中。这最大限度地减少了在查找期间拉入数据所需的磁盘读取次数。一些文件系统（比如 ext4，我相信）出于同样的原因也使用 B 树 - 它们最大限度地减少了必要的磁盘查找次数，这是真正的瓶颈。

希望这可以帮助！

Answer 2

现实生活中的数据存储（例如，在 DB 中）需要存储大量数据。由于数据检索是关注的基本操作，因此从磁盘读取数据比从 RAM 读取数据非常耗时。

现在，这就是问题所在...

与 B+ 树相比，BST 在节点中存储的数据较少。这导致 BST 的高度高于 B+ 树。因此它们存储在磁盘上而不是 RAM 上。

每次必须从树中检索数据时，都必须将磁盘中的数据加载到主存中（这当然是一个耗时的过程），而对于 B+ 树，数据已经存在在 RAM 中，直接获取所需的节点并从可能包含许多子节点的节点检索数据（但在 B+ 树的情况下，数据检索的总时间较短，因为不需要将数据从磁盘加载到 RAM）。