我在一堂关于数据库的课上学习了B+树，我想知道B+树比二进制搜索树有什么具体优势？
对于大多数值得注意的操作，它们似乎都有O(Logn)的平均复杂度，但是B+树还有一个额外的(可以忽略不计？)在每个子 node 上的搜索时间，其中BST显然只需要O(1)时间来计算出要前进到哪个子 node .
B+树在数据库中比BST更受欢迎的实际优势是什么？
我在一堂关于数据库的课上学习了B+树，我想知道B+树比二进制搜索树有什么具体优势？
对于大多数值得注意的操作，它们似乎都有O(Logn)的平均复杂度，但是B+树还有一个额外的(可以忽略不计？)在每个子 node 上的搜索时间，其中BST显然只需要O(1)时间来计算出要前进到哪个子 node .
B+树在数据库中比BST更受欢迎的实际优势是什么？
与二叉搜索树相比，B+树(通常还有B-树)的主要优势在于它们可以很好地处理缓存.如果您有一个二叉搜索树，其 node 或多或少以随机顺序存储在内存中，那么每次您跟随指针，机器将不得不在处理器缓存中引入一个新的挡路内存，这比访问缓存中已有的内存要慢得多.
B+树和B树的工作方式是让每个 node 存储大量的键或值，并具有大量的子 node .它们通常打包在一起，使得单个 node 可以很好地装入缓存(或者，如果存储在磁盘上，则可以在一次读取操作中从磁盘中取出).然后，您必须做更多的工作来查找 node 内的键或确定下一步读取哪个子 node ，但是因为在单个 node 上进行的所有内存访问都可以在不返回磁盘的情况下完成，所以访问时间非常短.这意味着即使原则上BST在number次存储器访问方面可能更好，B+树和B树在runtime次存储器访问方面也可以执行得更好.
B+树或B树的典型用例是在数据库中，那里有大量的信息，并且数据太多，以至于它们不能全部放入主内存.因此，数据然后可以存储在硬盘上某处的B+树或B树中.这最大限度地减少了在查找期间拉入数据所需的磁盘读取次数.出于同样的原因，一些文件系统(我相信像ext4)也使用B-tree-它们最大限度地减少了必要的磁盘查找次数，这才是真正的瓶颈.
希望这能有所帮助！