一个m阶的B-树具有如下几个特征：
- 根节点至少有两个子女
- 每个中间节点都包含k-1个元素和k个孩子，其中m/2<=k<=m
- 每个叶子节点都包含k-1个元素，其中m/2<=k<=m
- 所有的叶子结点都位于同一层
- 每个节点中的元素从小到大排序，节点当中k-1个元素正好是K个汉子包含的元素的值域划分。
例：3阶的B-树
3.png
B-树查询的过程，假如我们要查询的数值是5
第一次磁盘IO:
4.png
在内存中定位（和9比较）：
5.png
第二次磁盘IO
6.png
在内存中定位（和2、6比较）：
7.png
第3次磁盘IO：
8.png
在内存中定位（和3、5比较）
9.png
通过整个流程我们可以看出，B-树在查询中的比较次数其实不比二叉查找树少，尤其当单一节点中的元素数量很多时。可是相比磁盘IO的速度，内存中比较耗时几乎可以忽略。所以只要树的高度足够低，IO次数足够少，就可以提升查找性能。相比之下节点内部元素多一些也没有关系，仅仅是多了几次内存交互，只要不超过磁盘页的大小即可。这就是B-树的优势之一。
插入节点
B-树插入新节点的过程比较复杂，而且分成很多种情况。例如插入值4
自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间
10.png
节点3，5已经是两元素节点，无法再增加。父亲节点2，6也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。
1.png
B-树能够始终维持多路平衡，这也是B-树的一大优势：自平衡。
删除节点
比如删除元素11
2.png
删除11后，节点12只有一个孩子，不符合B树规范。因此找出11，12，15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子（这个过程称为左旋）
3.png
4.png
B-树主要应用于文件系统以及部分数据库索引，比如著名的非关系型数据库MongoDB.
而大部分关系型数据库，比如Mysql,则使用B+树作为索引。
