B树和B+树详解

B树

定义：一个节点可以拥有多于2个子节点的二叉查找树

m阶B树的性质：

• 每个结点至多有m个孩子结点，每个结点至多有m-1个关键字
• 根结点至少有两个子结点。除根结点外，每个结点至少有⌈m/2⌉个孩子结点，至少有⌈m/2⌉-1个关键字
• 所有的叶子结点都在同一层上，即B树是所有结点的平衡因子均等于0的多路查找树

B树的操作

B树的查找

1. 把15所在节点读到内存中，然后与8做比较，小于15，找到下一个节点（5和9对应的节点）
2. 把5和9所在的节点读到内存中，然后与8做比较，5<8<9，找到下一个节点（6和8对应的节点）
3. 把6和8所在节点读到内存中，然后与8做比较，找到了元素8

B树的插入

1. 自顶向下查找元素7应该在的位置，即在6和8之间
2. 三阶B树中的节点最多有两个元素，把6 7 8里面的中间元素上移（中间元素上移是插入操作的关键）
3. 上移之后，上一层节点元素也超载了，5 7 9中间元素上移，现在根节点变为了 7 15
4. 要对B树进行调整，使其满足B树的特性，最终如下图：

B+树

B+树是B树的一种变形体，B+树的非叶结点存储的是关键码，叶结点存储的是数据元素。

m阶B+树的性质：

• 除根节点和叶结点外，每个结点至多有m个孩子结点，每个结点至少有(m+1)/2个孩子结点
• 根节点至少有两个孩子结点
• 所有的叶结点添加一个链指针，所有关键字都在叶子结点出现，非叶子结点存储的是指向叶子结点中关键字的索引，所以任何关键字的查找必须走一条从根结点到叶子结点的路
• 除了叶子结点，其他结点的孩子数目等于关键字数目