列表

详情


121. 请你讲讲 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操作,这还不错。因为现在一般的磁盘每秒至少可以做100次IO操作,2~4次的IO操作意味着查询时间只需0.02~0.04秒。

上一题