本文目录

• 1.问题引入
• 2.B树的介绍
• 3.2-3树介绍
• 4.例子回顾
• 5.B-树的应用

问题引入

我们知道，数据库查询是数据库最主要的功能之一，我们都希望查询数据的速度尽可能的快，如果数据库中数据量比较大的话，稍有经验的开发都会建议我们在数据库中增加索引来提高数据库的查询效率，那么为什么数据库建立索引为什么会加快查询速度呢？
MySQL官方对于索引的定义为：

索引是帮助MySQL高效获取数据的数据结构。

首先明白为什么索引会增加速度，DB在执行一条Sql语句的时候，默认的方式是根据搜索条件进行全表扫描，遇到匹配条件的就加入搜索结果集合。如果我们对某一字段增加索引，查询时就会先去索引列表中一次定位到特定值的行数，大大减少遍历匹配的行数，所以能明显增加查询的速度。
然而，我们需要考虑一个现实因素，索引本身很大，不可能全部存储在内存中，因此索引以索引表的形式存储在磁盘中。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，因此我们要找一种能够减少I/O操作的数据结构作为索引的数据结构

如果我们用二叉查找树作为数据库的索引结构，如下图，假设树的高度是4，查找的值是10，那么查找的情形会是怎么样子的呢？

二叉查找树的结构

第一次IO操作：

第二次IO操作：

第三次IO操作：

第四次IO操作：

从上面的操作中，我们可以看出：我们对磁盘的IO的操作次数是4，索引树的高度也是4，所以最坏的情况下，磁盘IO次数等于索引树的高度。那么为了减少磁盘IO的操作，如果我们把原本“瘦高”的树结构变的“矮胖”，那么就可以减少磁盘IO的操作，这也是B- 树的特征之一。

B树定义

B树读音：

B-树就是B树英文名字叫做B-tree，读的时候，不能读成B减树，而是B树。中间的短线是英文连接符，只是翻译的时候将短线翻译成了减号。
全称Balance-tree(平衡多路查找树)，平衡的意思是左边和右边分布均匀。多路的意思是相对于二叉树而言的，二叉树就是二路查找树，查找时只有两条路，而B-tree有多条路，即父节点有多个子节点。

B树的阶：

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

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

B树的定义：

1. 根节点至少有两个孩子
2. 每个非根节点有[ m/2，m ]个孩子
3. 每个非根节点有[ (m/2) -1，m-1 ]个关键字，并且以升序排序
4. key[i]和key[i+1]之间的孩子节点的值介于两者之间
5. 所有的叶子节点都在同一层

上面的条条框框看起来很复杂吧，我们先从B树的一个特例：2-3树作为切入点，来看看一个B树是如何构建和操作的。

2-3B树介绍

2-3树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（称为2结点）或三个孩子（称为3结点）。

它拥有如下属性：

• 一个2结点包含一个元素和两个孩子（或没有孩子），和二叉排序树一致，左子树包含的元素小于该元素，右子树包含的元素大于该元素。但是这个2结点要么有两个孩子，要么没有孩子，不能只有一个孩子。
• 一个3结点包含两个元素和三个孩子（或没有孩子），左子树、较小元素、中间子树、较大元素和右子树也按照从小到大排序。一个3结点要么有三个孩子，要么没有孩子。

• 2-3树的所有叶子结点都在同一层次上。
  根据上面的描述，我们先看一棵正确的2-3树，如下图：

  
  
  

  下面我们通过构造一棵2-3树来演示它的增删过程，假定初始数据为：{1, 7, 4, 9, 15, 13, 6, 5, 8, 10, 3, 12, 14, 2, 11}。

插入：

现在树为空，要把1插入进去只需要构建一个2结点即可，如下所示：

接下来插入元素7，只要把当前结点升级为3结点即可，如下所示：

接下来插入4，可以发现根结点已经是3结点了，因为必须是平衡的，所以只能把根结点拆开，变为3个2结点，如下所示：

插入9时，因为9比4大，所以插入到右侧，而7所在结点可以升级为3结点，所以插入结果如下所示：

接下来要插入15，因为9所在结点已经是3结点，但是它的父结点4是2结点，所以可以把4所在结点升级，因为3结点必须有三个孩子，所以7和9所在结点需要拆分，如下所示：

接下来插入13和6时，对应节点都可以升级，所以插入结果如下：

接下来插入元素5时，发现6所在结点已经是3结点，而父结点，也就是根结点也是3结点了，这时只能再次拆分。首先，5、6、7中间的数是6，我们把它提出来，它应该位于4和9中间，如下所示：

因为3结点只能有两个元素，所以根结点也必须拆分，结果如下：

可以发现，根结点拆分后使得树的高度增加了。接下来插入8，10，3也是重复步骤，结果如下：

至此，再插入元素12、14、2时也变得十分简单了，结果如下：

最后插入11，可以发现它在10和12之间，而父结点也是3结点，所以10和12要拆分，9和13也要拆分，11应该和6一起升级为3结点，结果如下：

整个插入过程完成，构建成了一颗完整的2-3树，接下来我们看一下删除的过程

删除

首先删除元素1，因为1是2结点，删除后会影响平衡，但是我们发现它的父结点是一个3结点，所以可以把父结点拆开，2和3合并成一个3结点，结果如下：

现在，要删除7，因为7是叶节点也是3结点，直接删除就可以，结果如下：

删除结点4，因为它的左孩子是3结点，只要把它拆开就可以了，结果如下：

删除9时比较复杂，因为它的左右孩子都是2结点，首先把它的两个孩子合并为3结点并代替它，结果如下：

此时树是不平衡的，此时发现左侧3和6可以合并为3结点，结果如下：

接下来删除15，直接删除即可，结果如下：

删除13也比较复杂，首先需要把它的两个孩子合并，然后以11为根结点，做类似右旋的操作，具体做法是6的右孩子成为11的左孩子，然后6成为11的父结点，这和AVL树等的右旋操作是一致的，结果如下：

接下来要删除的元素6是根结点，做法是先找到它的前驱（第一个比它小的元素）5代替它，此时2、3结点需要合并，合并后左右子树不再平衡，所以还需要5和11合并，结果如下：

其余的删除操作其实和前面的都类似，这里不再演示了

这里介绍的2-3树是B树的一个特例，B树就是把2-3树的阶扩展到了m，它的每个结点特性和2-3树一致，除叶结点外每个结点的指针域和数据域都必须填充。

我们在回到刚开始数据库索引的例子中，如果把二叉树换成B-树，那么索引结构将是什么样子呢？如下图

同样，我们再查找10，树的层数为3，只需要做三次IO操作就好了。但是对于查询中比较的次数并不比二叉查找树少，尤其是当单一节点中元素数量很多时，可是相比磁盘IO的速度，内存中的比较耗时几乎是可以忽略的。所以只要树的高度足够低(矮胖)，IO 次数足够少，就可以提高查找性能。

B-树的应用

B-树主要应用于文件系统以及部分数据库索引，比如常见的非关系型数据库MongoDB。而大部分关系型数据库，如Mysql，则使用B+树作为索引。

参考：

• 漫画，什么是B-树
• B-树（B树）
• 数据结构之B树与B+树