我在课堂上学习关于数据库的B树，我想知道B树对Binary Search Trees有什么具体优势？
对于大多数笔记操作来说，它们似乎都具有O（logN）平均复杂度，但是B树在每个子节点上还有一个额外的（可忽略的？）搜索时间，其中BST显然只花费O（1）时间来确定哪个子节点前进到 .
现实世界的优势使B树在数据库中比BST更受欢迎？
与二元搜索树相比，B树（以及一般的B树）的主要优点是它们可以很好地与缓存配合使用 . 如果你有一个二进制搜索树，其节点以或多或少的随机顺序存储在内存中，那么每次你按照一个指针，机器都必须将一个新的内存块拉入处理器缓存中，这比访问缓存中已有的内存 .
B-tree和B-tree通过让每个节点存储大量的键或值并且具有大量子节点来工作 . 它们通常以一种方式打包在一起，使单个节点可以很好地适应缓存（或者，如果存储在磁盘上，则可以在单个读取操作中从磁盘中提取） . 然后，您必须做更多的工作来查找节点中的密钥或确定下一个要读取的子项，但由于可以在不返回磁盘的情况下完成在单个节点上完成的所有内存访问，因此访问时间非常短 . 这意味着即使原则上BST在存储器访问次数方面可能更好，但是B-tree和B-tree在这些存储器访问的运行时方面可以表现得更好 .
B-tree或B-tree的典型用例是在数据库中，其中存在大量信息，并且数据太多以至于它们不能全部适合主存储器 . 因此，数据然后可以存储在某处的硬盘上的B树或B树中 . 这最大限度地减少了在查找期间引入数据所需的磁盘读取次数 . 一些文件系统（比如ext4，我相信）也出于同样的原因使用B树 - 它们最小化了必要的磁盘查找次数，这是真正的瓶颈 .
希望这可以帮助！
数据的实际存储（例如，在DB中）需要存储大量数据 . 由于数据检索是关注的基本操作，因此从磁盘读取数据比使用RAM要耗费时间 .
现在，这是 grab ......
与B树相比，BST在节点中存储较少的数据 . 这导致BST的高度增加而不是B树 . 所以它们存储在磁盘上而不是RAM中 .
每次必须从树中检索数据时，必须将来自磁盘的数据加载到主存储器中（当然，这是一个耗时的过程），而在B树的情况下，数据已经存在在RAM中，直接获取所需的节点，并从该节点检索数据，该节点可能包含许多子节点（但是在B树的情况下，数据检索的总时间较少，因为不需要将数据从磁盘加载到RAM） .
2 回答
与二元搜索树相比，B树（以及一般的B树）的主要优点是它们可以很好地与缓存配合使用 . 如果你有一个二进制搜索树，其节点以或多或少的随机顺序存储在内存中，那么每次你按照一个指针，机器都必须将一个新的内存块拉入处理器缓存中，这比访问缓存中已有的内存 .
B-tree和B-tree通过让每个节点存储大量的键或值并且具有大量子节点来工作 . 它们通常以一种方式打包在一起，使单个节点可以很好地适应缓存（或者，如果存储在磁盘上，则可以在单个读取操作中从磁盘中提取） . 然后，您必须做更多的工作来查找节点中的密钥或确定下一个要读取的子项，但由于可以在不返回磁盘的情况下完成在单个节点上完成的所有内存访问，因此访问时间非常短 . 这意味着即使原则上BST在存储器访问次数方面可能更好，但是B-tree和B-tree在这些存储器访问的运行时方面可以表现得更好 .
B-tree或B-tree的典型用例是在数据库中，其中存在大量信息，并且数据太多以至于它们不能全部适合主存储器 . 因此，数据然后可以存储在某处的硬盘上的B树或B树中 . 这最大限度地减少了在查找期间引入数据所需的磁盘读取次数 . 一些文件系统（比如ext4，我相信）也出于同样的原因使用B树 - 它们最小化了必要的磁盘查找次数，这是真正的瓶颈 .
希望这可以帮助！
数据的实际存储（例如，在DB中）需要存储大量数据 . 由于数据检索是关注的基本操作，因此从磁盘读取数据比使用RAM要耗费时间 .
现在，这是 grab ......
与B树相比，BST在节点中存储较少的数据 . 这导致BST的高度增加而不是B树 . 所以它们存储在磁盘上而不是RAM中 .
每次必须从树中检索数据时，必须将来自磁盘的数据加载到主存储器中（当然，这是一个耗时的过程），而在B树的情况下，数据已经存在在RAM中，直接获取所需的节点，并从该节点检索数据，该节点可能包含许多子节点（但是在B树的情况下，数据检索的总时间较少，因为不需要将数据从磁盘加载到RAM） .