B+树

B+树的定义

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

m阶的B+树与m阶的B树的主要差异

B+树 VS B树

• m阶B+树 –> 结点中的n个关键字对应n颗子树
• m阶B树 –> 结点中的n个关键字对应n+1颗子树
  
  
• m阶B+树 –> 根结点的关键字数∈[ 1,m ],其他结点的关键字数n∈[ ⌈m/2⌉,m ]
• m阶B树 –> 根结点的关键字数∈[ 1,m-1 ],其他结点的关键字数n∈[ ⌈m/2⌉-1,m-1 ]
  
  
• m阶B+树 –> 在B+树中，叶结点包含全部关键字，非叶结点中出现过的关键字也会出现在叶结点中。
• m阶B树 –> 在B树中，各结点中包含的关键字是不重复的
  
  
• m阶B+树中 –> 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
• m阶B树 –> B树的结点中都包含了关键字对应的记录的存储地址
  
  

总结