b+树

B+Tree是在B-Tree基础上的一种优化，B-Tree中每个节点同时保存key和data，而B+Tree非叶子节点上只存储key值信息，这样可以增加每个节点存储的key值数量，降低B+Tree的高度，因为每一页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小。当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

b树是一种多路平衡查找树，阶数表示一个节点最多有几个孩子节点。m阶b树定义如下：

1. 每个节点至多有m-1个关键字
2. 如果根节点不是叶子结点，则其至少有两颗子树（即1个关键字）
3. 每个节点中关键字递增排序，每个关键字的左子树中的所有关键字都小于它，右子树中的所有关键字都大于它，

4. 所有叶子节点都位于同一层

   
   b树.jpg

b+树除了以上要求外，还有

• b+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
• 内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。

• 每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。

  
  b+树.jpg

参考
b树和b+树