B-Tree和B+Tree
什么是B-Tree
B-Tree就是我们常说的B树，一定不要读成B减树，否则就很丢人了。B树这种数据结构常常用于实现数据库索引，因为它的查找效率比较高。
磁盘IO与预读
磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分，这三个部分耗时相加就是一次磁盘IO的时间，大概9ms左右。这个成本是访问内存的十万倍左右；正是由于磁盘IO是非常昂贵的操作，所以计算机操作系统对此做了优化：预读；每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明：当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。一页的大小与操作系统有关，一般为4k或者8k。这也就意味着读取一页内数据的时候，实际上发生了一次磁盘IO。
B-Tree与二叉查找树的对比
我们知道二叉查找树查询的时间复杂度是O（logN），查找速度最快和比较次数最少，既然性能已经如此优秀，但为什么实现索引是使用B-Tree而不是二叉查找树，关键因素是磁盘IO的次数。
数据库索引是存储在磁盘上，当表中的数据量比较大时，索引的大小也跟着增长，达到几个G甚至更多。当我们利用索引进行查询的时候，不可能把索引全部加载到内存中，只能逐一加载每个磁盘页，这里的磁盘页就对应索引树的节点。
一、 二叉树
我们先来看二叉树查找时磁盘IO的次：定义一个树高为4的二叉树，查找值为10：
第一次磁盘IO：
第二次磁盘IO
第三次磁盘IO:
第四次磁盘IO：
从二叉树的查找过程了来看，树的高度和磁盘IO的次数都是4，所以最坏的情况下磁盘IO的次数由树的高度来决定。
从前面分析情况来看，减少磁盘IO的次数就必须要压缩树的高度，让瘦高的树尽量变成矮胖的树，所以B-Tree就在这样伟大的时代背景下诞生了。
二、B-Tree
m阶B-Tree满足以下条件：
1、每个节点最多拥有m个子树
2、根节点至少有2个子树
3、分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
4、所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列
如下有一个3阶的B树，观察查找元素21的过程：
第一次磁盘IO：
第二次磁盘IO：
这里有一次内存比对：分别跟3与12比对
第三次磁盘IO:
这里有一次内存比对，分别跟14与21比对
从查找过程中发现，B树的比对次数和磁盘IO的次数与二叉树相差不了多少，所以这样看来并没有什么优势。
但是仔细一看会发现，比对是在内存中完成中，不涉及到磁盘IO，耗时可以忽略不计。另外B树种一个节点中可以存放很多的key（个数由树阶决定）。
相同数量的key在B树中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。
三、B树的新增
在刚才的基础上新增元素4，它应该在3与9之间：
四、B树的删除
删除元素9：
五、总结
插入或者删除元素都会导致节点发生裂变反应，有时候会非常麻烦，但正因为如此才让B树能够始终保持多路平衡，这也是B树自身的一个优势：自平衡；B树主要应用于文件系统以及部分数据库索引，如MongoDB，大部分关系型数据库索引则是使用B+树实现。
B+Tree的定义
B+Tree是B树的变种，有着比B树更高的查询性能，来看下m阶B+Tree特征：
1、有m个子树的节点包含有m个元素（B-Tree中是m-1）
2、根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。
3、所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。
4、叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接。
更直观的图
1、红点表示是指向卫星数据的指针，指针指向的是存放实际数据的磁盘页，卫星数据就是数据库中一条数据记录。
2、叶子节点中还有一个指向下一个叶子节点的next指针，所以叶子节点形成了一个有序的链表，方便遍历B+树。
B+树的优势
1、更加高效的单元素查找
B+树的查找元素3的过程：
第一次磁盘IO
第二次磁盘IO
第三次磁盘IO
这个过程看下来，貌似与B树的查询过程没有什么区别。但实际上有两点不一样：
a、首先B+树的中间节点不存储卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素，如此一来，相同数量的数据下，B+树就相对来说要更加矮胖些，磁盘IO的次数更少。
b、由于只有叶子节点才保存卫星数据，B+树每次查询都要到叶子节点；而B树每次查询则不一样，最好的情况是根节点，最坏的情况是叶子节点，没有B+树稳定。
2、叶子节点形成有顺链表，范围查找性能更优
B树范围查找3-8的过程
a、先查找3
b、再查找4、5、6、7、8，中间过程省略，直接到8的查找
这里查找的范围跨度越大，则磁盘IO的次数越多，性能越差。
B+树范围查找3-11的过程
先从上到下找到下限元素3，然后通过链表指针，依次遍历得到元素5/6/8/9/11；如此一来，就不用像B树那样一个个元素进行查找。
总结
1.单节点可以存储更多的元素，使得查询磁盘IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。
3.所有叶子节点形成有序链表，便于范围查询。
PS:在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。