B+树的定义以及查找

1.B+树的定义

一棵m阶的B+树需满足下列条件:

• 每个分支结点最多有m棵子树(孩子结点)。
• 非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。
• 结点的子树个数与关键字个数相等。
• 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）。
• 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

要追求“绝对平衡”，即所有子树高度要相同。

例如：一颗4阶B+树

2.B+树的查找

1.多路查找

从根节点开始从上到下查找。
B+树中，无论查找成功与否，最终一定都要走到最下面一层结点。

2.顺序查找

使用指针，依次从叶子结点开始查找。

3.B+树和B树的区别

1.m阶B+树:

1. 结点中的n个关键字对应n棵子树
2. 根节点的关键字数$n=[1,m]$，其他结点的关键字数n=$[[m/2],m]$(向上取整）
3. 在B+树中，叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中
4. 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

在B+树中，非叶结点不含有该关键字对应记录的存储地址。
可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，
树高更矮，读磁盘次数更少，查找更快.

2.m阶B树：

1. 结点中的n个关键字对应n+1棵子树
2. 根节点的关键字数$n=[1,m-1]$,其他结点的关键字数$n=[[m/2]-1,m-1]$
3. 在B树中，各结点中包含的关键字是不重复的.
4. B树的结点中都包含了关键字对应的记录的存储地址