B树与B+树

B树与B+树

1. B树

B树又成多路平衡查找树，B树中所有节点的孩子节点数的最大值成为B树的阶（order）。

一棵m阶B树的组成：根节点、内部节点、叶子节点

一棵m阶B树，或为空树，或为满足如下特性的m叉树：

• 树中每个节点至多有m个孩子，即最多含有m+1个key，每个节点的key以非降序存放。根节点至少有两个孩子；

• 除根节点外的所有非叶子节点至少含有ceil(m/2)个孩子

• 所有的叶子节点位于同一层，不包含孩子

m的阶数越高，树的高度越小

2. B+树

B+树的叶子节点包含了所有的key。

3. 区别与联系

• B+树的内部节点仅存储数据对应的key不存储具体的数据，而完整数据存储于叶子节点中（或者说叶子节点存储了指向完整数据的具体地址），而B树内部节点和叶子节点存储了数据的key和完整的数据，当数据量特别大可能会很占内存

• B+树的叶子节点包含了是有序的且用链表进行串联。

• B树的key值在树中是唯一的，而B+树允许重复。

• 在添加、删除节点上。B+树更加高效；在B树中搜索时，可能到不了叶子节点，即在中间节点就找到了目标，而B+树中一定会搜索到叶子节点。

MySQL为何选择B+树而不是B树作为索引？

• B+树索引非叶子节点不存储具体数据，这就使得索引文件“体积”更小，进而在索引查询时能够减少磁盘IO次数，提升查询效率。
• B+树叶子节点包含了所有的key且用链表进行有序连接，方便MySQL进行全表扫描和范围查询。