B +树优于BST的优势？

Question

我正在学习关于数据库的类中的B +树,我想知道B +树对二元搜索树有什么具体优势？

对于大多数笔记操作来说,它们似乎都具有O(logN)平均复杂度,但B +树在每个子节点上还有一个额外的(可忽略的？)搜索时间,其中BST显然只花费O(1)时间来确定哪个子节点前进到.

现实世界的优势使B +树在数据库中比BST更受欢迎？

Answer 1

与二元搜索树相比,B +树(以及一般的B树)的主要优点是它们可以很好地与缓存配合使用.如果你有一个二进制搜索树,其节点以或多或少的随机顺序存储在内存中,那么每次你按照一个指针,机器都必须将一个新的内存块插入处理器缓存中,这比访问缓存中已有的内存.

B + -tree和B-tree通过让每个节点存储大量的键或值并且具有大量子节点来工作.它们通常以一种方式打包在一起,使单个节点可以很好地适应缓存(或者,如果存储在磁盘上,则可以在单个读取操作中从磁盘中提取).然后,您必须做更多的工作来查找节点中的密钥或确定下一个要读取的子项,但由于可以在不返回磁盘的情况下完成在单个节点上完成的所有内存访问,因此访问时间非常短.这意味着即使原则上BST在存储器访问次数方面可能更好,但是B +树和B树在这些存储器访问的运行时方面可以表现得更好.

B +树或B树的典型用例是在数据库中,其中存在大量信息且数据太多以至于它们不能全部适合主存储器.因此,数据然后可以存储在某处硬盘上的B +树或B树中.这最大限度地减少了在查找期间引入数据所需的磁盘读取次数.一些文件系统(比如ext4,我相信)也出于同样的原因使用B树 - 它们最小化了必要的磁盘查找次数,这是真正的瓶颈.

希望这可以帮助!