每日一博 | 面试官问你 B 树和 B+ 树,就把这篇文章丢给他
原文链接:面试官问你B树和B+树,就把这篇文章丢给他 1 B树 在介绍B+树之前, 先简单的介绍一下B树,这两种数据结构既有相似之处,也有他们的区别,最后,我们也会对比一下这两种数据结构的区别。 1.1 B树概念 B树也称B-树,它是一颗多路平衡查找树。二叉树我想大家都不陌生,其实,B树和后面讲到的B+树也是从最简单的二叉树变换而来的,并没有什么神秘的地方,下面我们来看看B树的定义。 每个节点最多有m-1个关键字(可以存有的键值对)。 根节点最少可以只有1个关键字。 非根节点至少有m/2个关键字。 每个节点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。 所有叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同。 每个节点都存有索引和数据,也就是对应的key和value。 所以,根节点的关键字数量范围:1 <= k <= m-1,非根节点的关键字数量范围:m/2 <= k <= m-1。 另外,我们需要注意一个概念,描述一颗B树时需要指定它的阶数,阶数表示了一个节点最多有多少个孩子节点,一般用...

