数据结构——B+树

一、B+树的概念

B+树是应数据所需而出现的一种B树的变形树。一棵m阶的B+树需要满足下列条件：

1. 每个分支节点最多有m棵子树（孩子节点）；
2. 非叶根节点至少有两棵子树，其他每个分支节点至少有⌈m/2⌉棵子树；
3. 节点的字数个数与关键字个数相等；
4. 所有叶节点包含全部关键字及指向相应记录的指针，叶节点中将关键字按大小顺序排列，并且相邻叶节点按大小顺序相互链接起来；
5. 所有分支节点（可视为索引的索引）中仅包含他的各个子节点（即下一级的索引块）中关键字的最大值及指向其子节点的指针。

二、B+树和B树的差异

1. 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。
2. 在B+树中，每个节点（非根内部节点）的关键字个数n的范围为⌈m/2⌉~m(而根节点：1~m)；而在B树中，每个节点（非根内部节点）的关键字个数n的范围为⌈m/2⌉-1~m-1(根节点：1~m-1)。
3. 在B+树中，叶节点包含了全部关键字，非叶节点中出现的关键字也会出现在叶节点中；而在B树中，最外层的终端节点包含的关键字和其他节点包含的关键字是不重复的。
4. 在B+树中，叶节点包含信息，所有非叶节点仅起索引作用，非叶节点的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

   

三、B+树的查找

B+树中的所有数据均保存在叶子结点，且根结点和内部结点均只是充当控制查找记录的媒介，并不代表数据本身，所有的内部结点元素都同时存在于子结点中，是子节点元素中是最大（或最小）元素。

例如在上图中的B+树中查找55这个关键字，步骤如下：

• 在根节点中对比55和根节点中的元素[60, 85]，发现55