B- 树，读作B树，千万不要读作B减树，会被人笑掉大牙的^-^。

有哪些产品使用了这种数据结构

像MongoDB,SQLite等部分关系型或非关系型数据库以及大部分文件系统的索引都会使用到这种数据结构。

什么是B-树

全称Balance-tree(平衡多路查找树)，平衡的意思是左边和右边分布均匀。多路的意思是相对于二叉树而言的，二叉树就是二路查找树，查找时只有两条路，而B-tree有多条路，即父节点有多个子节点。

B树与红黑树最大的不同在于，B树的结点可以有多个子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的B树的高度也为O（lgn），但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。

阶的概念

对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。

即遍观整棵树，子节点最多的个数是m，那么这棵树就是m阶树。

节点最多包含3个孩子节点，故为3阶

B-树的特性

B-树示例

一个m阶的B-树具有以下特性（图示3阶）：

1.根节点至少有两个子节点（图示2个子节点）

2.每个中间节点包含k-1个元素和k个子节点，其中 m/2<=k<=m.（图示中间节点至少包含一个元素和2个孩子节点）

3.每个叶子结点包含k-1个元素，其中 m/2<=k<=m.（叶子节点至少包含一个元素）

4.所有的叶子结点位于同一层（所有叶子结点位于同一层）

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划（图示叶子节点（2,6）恰好是（1），（3,5），（8）的分化），如下图：

B-树的查找

树的查找类似二叉排序树的查找，不同的是B-树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。

假设要查找的数据为5：

1.从根节点开始，5<9，查询（2,6）节点

2.内存中定位，2<5<6，开始查找其中间子节点，即（3,5）节点

3.第三次内存定位，找到节点最右侧元素为5

B-树元素的插入

由于情况繁多，此处只进行简单示例：

如图为3阶的B-树(图中略去F结点(即叶子结点))，假设需依次插入关键字30，26，85

（1）首先通过查找确定插入的位置。由根节点a开始查找，确定30应插入的在d 节点中。由于d 中关键字数目不超过2（即m-1），故第一个关键字插入完成,如下图：

（2）同样，通过查找确定关键字26亦应插入 d， 由于d节点关键字数目超过2，此时需要将 d分裂成两个节点，关键字26及其前、后两个指针仍保留在 d 节点中。而关键字37 及其前、后两个指针存储到新的产生的节点 d` 中。同时将关键字30 和指示节点 d 的指针插入到其双亲的节点中。由于 b节点中的关键字数目没有超过2，则插入完成.

查找及定位26的具体位置

由于本树为3阶，每个节点最多包含2个元素，故节点d需要分裂，如下图:

插入完成

（3）插入元素85

定位85的位置，发现节点元素超过2，节点分裂

节点分裂后，中间元素70膨胀到父节点中，此时父节点元素超过2，接着分裂

接着70膨胀到根节点，由于节点的孩子节点不能超过3个，故53和90两个节点分裂，再对孩子节点拆分

B-树元素的删除

假设删除的元素为11：

删除图示红色节点11

删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）

删除后，不符合B-树性质2（至少包含2个孩子节点），此时左旋

删除完成

以上就是关于B-树查找，插入和删除的简单示例，数据库的索引要复杂的多，当然这也是学习B-树最绕的部分。谈到数据库索引，就必须考虑到磁盘IO，数据查找的时候，是否耗时取决于磁盘IO的次数，磁盘IO的次数取决于B-的高度，这也是为什么二叉树不适合数据库索引的原因所在，虽然他们查找的时间复杂度都是O（logn）.

下文我们接着讲B+树。

备注：图片来源于网络，如有侵权，请私信作者，谢谢。