Java面试题：说说B树和B+树的区别

得分点：

平衡多路查找树、磁盘IO

标准回答：

平衡多路查找树是在二叉查找树的基础上改进而来的数据结构。在二叉查找树中，最坏情况下的查找次数取决于树的深度，当数据量较大时，查询次数可能会非常大，从而导致大量的磁盘IO操作，影响查询效率。

为了降低磁盘IO的次数，必须减小树的深度，因此在二叉查找树的基础上引入了多叉树，并添加了一些限制条件，从而形成了B树。

B+树是B树的一种变种，其主要区别在于：对于k阶的B树，每个中间节点只存储k-1个值和k个指针，而B+树则存储k个值和k个指针；在B树中，所有节点中的值的总集是全部关键字集合，而在B+树中，所有叶子节点中的值的总集就是全部关键字集合；B+树为所有叶子节点增加了链接，从而实现了快速的范围查找。

加分回答：

B+树是由B树和索引顺序访问方法演化而来的，它是一种平衡查找树，特别适用于磁盘或其他直接存取辅助设备。

在B+树中，所有记录节点都按键值的大小顺序存放在同一层的叶子节点中，各叶子节点通过指针进行链接。这种特性使得B+树在数据库中具有高扇出性，例如在InnoDB存储引擎中，每个页的大小通常为16KB。因此，B+树的高度通常在2到4层之间，这意味着查找某一键值最多只需要2到4次IO操作，这在数据库中是相当高效的。

考虑到现代磁盘每秒可以执行数百次IO操作，2到4次的IO操作意味着查询时间通常只需要0.02到0.04秒，这对于数据库性能来说是相当可观的提升。