B树和B+树

B树

类似于这种

一个m阶的B树有以下特征：

• 根节点至少有两个孩子。
• 每个中间节点都包含k-1个元素和k个孩子，其中m/2<=k<=m
• 每一个叶子节点都包含k-1个元素，其中m/2<=k<=m
• 所有的叶子节点都位于同一层
• 每个节点元素从小到大排列，节点当中的元素正好是孩子包含的元素值域分划（比如2 6 节点的孩子3 5节点正好在2和6之间，2 6又在1 8 之间）

特点：

• 高度相对于二叉平衡树低，查询次数虽然和二叉平衡树差不多，但是减少了最耗时间的IO操作

• 在插入删除元素时，可以通过拆分左旋等操作让树进行自平衡

应用：
文件系统，部分数据库索引（比如MongoDB）等。

B+树

类似于这种

一个m阶的B+树有以下特征：

1. 有k个子树的中间节点包含有k个元素（B树是k-1个元素）每个元素不保存数据，只用来当索引，所有的数据都保存在叶子节点。
2. 所有的叶子节点包含了全部元素，每一个叶子节点都有指向下一个叶子节点的指针，形成了一个有序链表。
3. 每一个父节点的元素都出现在子元素中，是子节点最大（或最小）元素。

关于卫星数据：
索引元素所指向的数据记录，比如索引指向数据库中某一行。

B+树和B树的区别：

1. 在B树中，无论中间节点还是叶子节点都有卫星数据，而在B+树中只有叶子节点有，其余节点只是索引，没有数据关联。且B+树由于没有卫星数据，同样大小的磁盘页就可以存放更多数据。
2. 如果B+树和B树数据量相同，B+树更加矮胖，查询IO操作更少。
3. B+树查询必须查找到最后的叶子节点，而B树找到匹配元素即可（无论在中间节点还是叶子节点），所以B树的查找性能可能不稳定，B+树则很稳定。
4. 进行范围查询时，B树要查询两个节点之间的所有元素，要做很多IO操作。而B+树只要找到边界元素延后根据链表遍历到另一个边界元素即可。

参考资料：
https://mp.weixin.qq.com/s/rDCEFzoKHIjyHfI_bsz5Rw
https://mp.weixin.qq.com/s/jRZMMONW3QP43dsDKIV9VQ