B-树总结分析

B-树

首先要区分的一个问题就是：B树和二叉树BinaryTree没有太大的联系。
B树的B是balanced平衡的意思，而不是binary的意思。也就是说B树一种多叉平衡树，二叉树仅有两个分支，B树可以有多个分支。
B-树是一种多路搜索树，一颗m阶B树就是一颗平衡的m路搜索树。m阶的意思是
B树中的每个节点至多可以拥有m个子节点。

一颗m阶的B-树的特性如下：

• 1.每个节点至多有m个子节点.
• 2.根节点若不是叶子节点，则至少有两个子节点.
• 3.除根节点和叶子节点外，其他节点至少拥有ceil(m/2)个子节点.[mV2,m]
• 4.所有的叶子节点都出现在同一层.
• 5.每个非根子节点包含的关键字的个数k满足： ceil(m/2)-1 <= k <= m-1.

B-树的特点：

• 任意非叶子节点最多有m个子节点，并且m>2.
• 根节点的子节点数为[2,m].
• 除根节点外的非叶子节点的子节点数为[mV2,m].
• 每个节点存放的关键字的个数为[ ceil(m/2)-1,m-1].
• 非叶子节点的关键字个数= 子节点数-1.
• 非叶子节点中的关键字k[1],k[2]...k[m-1],满足k[i] < k[i+1]
• 非叶子节点的子节点的指针p[1],p[2]...p[m],满足p[1]指向的关键字小于k[1],p[m]指向的关键字都大于k[m-1]。
• 所有的叶子节点都在同一层

B-树的特性决定了所有的关键字都会分布在整颗树种，任何一个关键字只能出现在一个节点中。对于一个关键字的搜索可能在非叶子节点中找到，搜索性能相当于在关键字全集中做一次二分查找。