为什么提出 B+树
B-树的缺点
所有中间结点，都存储 数据指针 和 关键字，导致可以存储在 B-树中的结点目数极大地减少了，从而增加 B-树的层数，进而增加了记录的搜索时间。
B+树
- B+树的 中间节点没有数据，所以同高度的B+树可以容纳更多的节点元素；在数据量相同的情况下，B+树的结构比B-树更加 矮胖，因此查询的IO次数也更少，查询效率更高；
- B+树的查询必须最终查找到叶子节点，而B-树只要查找匹配的元素即可，无论匹配的元素处于中间节点还是叶子节点。
- B-树的查找性能并不稳定，非叶子节点也会存储数据，最好情况只查询根节点，最坏情况是查找叶子节点。而B+树的每一次查找都是稳定的，只有访问到叶子节点才能找到对应的数据。
提示：IO一次指从硬盘读数据，读取数据大小是固定的，非叶子节点不存储数据，可以容纳更多的节点元素，所以结构 矮胖
B+树的定义
B+树是B树的一种变形形式
B+树上的叶子结点存储关键字
叶子结点以上各层作为索引使用
一棵 m阶 的B+树定义如下:
- 每个结点至多有
m个子节点； - 除根结点外，每个结点至少有
ceil(m/2)个子节点，根结点至少有两个子节点； - 有
k个子节点的节点必有k个关键字
例子
只有 叶子节点保存数据，其余中间节点仅用于索引
数据：索引元素所指向的数据记录，比如数据库中的某一行
上面的这颗树中，得出结论：
- 根节点元素
8是子节点2,5,8的最大元素，也是叶子节点6,8的最大元素； - 根节点元素
15是子节点11,15的最大元素，也是叶子节点13,15的最大元素； - 根节点的最大元素也就是整个B+树的最大元素，以后无论插入删除多少元素，始终要保持最大的元素在根节点当中。
- 由于父节点的关键字都出现在子节点中，因此所有的叶子节点包含了全部关键字
- 相邻的叶子节点之间是通过链表指针连起来的，遍历叶子节点就能获取全部数据，如下图：
查找
B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止
比如我们要查找的元素是 3
第一次磁盘IO
第二次磁盘IO
第三次磁盘IO
区间查询-案例
通过案例，体验 B+树区间查询的优势：查询下面的 B-树中 [21,63] 之间的关键字
第一步
访问根结点 [59、97] , 发现区间的左端点 21 小于 59， 则访问第一个左孩子 [15、44、59]
第二步
访问结点 [15、44、59] ，发现 21 大于 15 且小于 44 ，则访问第二个孩子结点 [21、37，44] .
第三步
访问结点 [21、37，44] ，找到了左端点 21 ，由于相邻叶子节点通过链表指针连起来，所以直接从左端点 21 开始一直遍历到左端点 63 即可，没有任何额外的磁盘 I/O 操作。
使用场景
- MySQL数据库索引
B+树 和 B-树的区别
- B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
- B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
- 查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束
- B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。
参考
https://baike.baidu.com/item/B%2B%E6%A0%91/7845683#9999
https://blog.csdn.net/jiang_wang01/article/details/113739230
https://zhuanlan.zhihu.com/p/149287061