B-树比二叉查找树好在哪里？

Question

为何我们需要B-树？

Answer 1

对于索引数据的查询与存储来说，B树在时间和空间上效率更好。

Answer 2

和深度有关吧 比如同样的数量思维元素B树查找迭代的层数 要比 二叉树少好多

比如我有16个元素的集合 ，我要从中找出某个元素

---

使用2叉树最坏的情况是 log2 16 = 4 也就是说需要算法调用4次。
使用一个有4个节点的B树最坏的情况是 log4 16 = 2也就是说算法调用两次即可。

如果每次的算法调用都读一次硬盘的话，大部分的时间都花在了IO开销上，所以既然IO开销较大的话那么我就每次多读点，减少IO查询次数即可，在我看来还是权衡的结果，不同的场景使用的方法也不同，思路是类似的。

维基百科关于B树的描述:
B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实作上。

Answer 3

如果考虑磁盘储存结构，B树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)。

Answer 4

首先要明确的是，数据结构的作用：
通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
那么我们为什么要选择B-树呢？
首先B-树是一种多叉平衡树，是由平衡二叉树演变而来，所以在明白为什么使用它之前，要明白平衡二叉树对比二叉树的优势：搜索效率上从n提升到log(n)，推荐视频：清华大学邓俊辉老师的数据结构
讲得异常详细，课件也非常精致。
再回到B-树，B-树是多路平衡树，（每个节点有至多有阶数-1的关键码，阶数个分支）更大效率上降低了树高，而且保证每个节点的搜索和插入效率，所以速度有了更深一步的提升。

总的来讲，高级一点的数据结构都是在基本数据结构上的升级，目的都一致，那就是：利用更少的空间实现更快的搜索，插入，删除。

Answer 5

对于IO开销比较大的设备访问，B树的结构可以减小IO次数，达到整体的高性能。如果纯粹的内存访问，或者高性能固态硬盘访问，要看数据量的大小，一般的在这种场景下，二叉树会比B树快得多。