6.3.2 B+树基本概念

B+是应用数据库所需而出现的一种B树的变形树。

一棵B+树需满足下列条件： 1）每个分支结点最多有m棵子树（子结点）。

2）非叶根（不是叶子的根结点）结点至少有两棵子树，其他每个分支结点至少有【m/2】（向下取整）棵子树。（B树是要求至少2棵子树）

3）结点的子树个数与关键字个数相等。

4）所有叶结点包含全部关键字及指向相应记录的指针，而且叶结点中将关键字按大小顺序排列，并且相邻叶子结点按大小顺序相互链接起来。

5）所有分支结点（可看成是索引的索引）仅包含它的各个子节点（即下一级的索引块）中关键字的最大值及指向其子节点的指针。

m阶的B+与m阶的B树的主要差异在于：

1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。

2）在B+树中，每个结点（非根结点）关键字个数n的范围是【m/2】向下取整<=n<=m（根结点：1<=n<=m）,在B树中，每个结点（非根结点）关键字个数n的范围是(【m/2】向下取整）-1<=n<=m-1(根结点1<=n<=m-1)。

3）在B树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字所对应记录的存储地址。

4）在B+树中，叶结点包含全部关键字，即在非叶子结点中出现的关键字也会在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

通常在B+树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此，可以对B+树进行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始，进行多路查找。

B+树的查找、插入和删除操作和B树基本类似。只是在查找过程中，如果非叶结点上的关键字值等于定值时并不终止，而是记录向下查找直到叶结点上的该关键字为止。所以B+树中，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。