首先补充一点，标题中的"B-树"就是“B树”，它们都是B-Tree的翻译，里面不是减号-，是连接符-。因为有人把B-Tree读成"B-树"，让人误以为“B树”和"B-树"是两种树，实际上两者都是同一种树。还有，大家在读的时候千万不要读成“B减树”，读成“B树”就行了，不然就外行了。
下面开始今天正文，我们依然从数据库的检索开始，我们知道数据库的索引是使用树结构来实现的，是因为树的查询效率高，而且还可以保持有序的状态。上篇中讲到的二叉查找树效率就很高，但是为什么没有使用二叉查找树来实现索引呢？其实从算法逻辑上讲，二叉查找树的查找次数和比较次数都是最小的，但是我们必须还要考虑一个现实问题：磁盘的IO（磁盘读写）。
数据库的索引是存储在磁盘上的，当数据量非常大的时候，索引的大小可能有几个G甚至更多，当我们利用索引查询的时候显然不可能将整个索引全部加载到内存，正常的操作都是逐一加载每一个磁盘页，这里的磁盘页就对应着索引树的节点。
索引树和磁盘页
我们如果利用二叉查找树做索引结构，查找情形是什么样子的呢？假设树的高度是4，要查找的值是10。
以此二叉查找树为例查10
这是第1次和第2次磁盘IO的结果
这是第3次和第4次磁盘IO的结果
磁盘IO的次是4次，即树的高度，最坏的情况就是磁盘IO的次数等于索引树的高度。既然如此，为了减少磁盘IO的次数，我们就需要把原来的“瘦高”树结构变得“矮胖”，这就是本文所要说的B-树的特征之一。
B-树（以下都称作B树）是一种多路平衡查找树，它的每个节点最多包含k个孩子，其中，k被称为B数的阶，k的大小取决于磁盘页的大小。
一个m阶的B树具备如下几个特征：
1、根节点至少有两个子女；
2、每个中间节点都包含k-1个元素和k个孩子，其中m/2<=k<=m；
3、每个叶子节点都包含k-1个元素，其中m/2<=k<=m；
4、所有的叶子节点都位于同一层；
5、每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分。
我们以一个3阶B树为例来看一下B树的结构，树中的具体元素和上面的二叉查找树是一样的。
3阶B树
我们来看（2，6）节点，该节点有两个元素2和6，又有三个孩子1，（3，5），8。其中1小于元素2，（3，5）在元素2，6之间，8大于元素6，符合上面的几条规则。
（2，6）分支
接下来我们来看一下B树的查询过程，看看会带来什么效果，假如我们要查询的数值是5
第1次磁盘IO
在内存中定位（和9比较）
第2次磁盘IO
在内存中定位（和2，6比较）
第三次磁盘IO
在内存中定位（和3，5比较）
从上面我们看出，其实B树在查询中的比较次数并不比二叉查找树少，尤其当单一节点中的元素数量很多时。可是相对磁盘IO的速度，在内存中比较耗时几乎可以忽略，所以只要树的高度足够低，磁盘IO次数足够少，就可以提高查询性能。就算单个节点内元素多一点也没关系，仅仅是多了几次内存中的交互，可以忽略用时。其实说白了B树的优势和高效就是因为B树将一部分的IO负担到内存中来了，用内存的高效和强大提升了查询性能。
下面我们来看一下B树的插入和删除
B树插入新节点的过程比较复杂，分好多种情况，此处举一个最典型的例子，还使用上面的B树，假如我们要插入的值是4，自顶向下查找4的位置，发下4应当插入到节点元素3，5之间，
插入4
可是节点3，5已经是两节点元素，无法再增加，父节点2，6也是两节点元素，无法再增加。倒是根节点9是单元素节点，可以升级为两元素节点，于是拆分节点2，6和节点3，5，让根节点9升级为两元素节点4，9，节点6独立为根节点的第二个孩子。
插入4后的B树
由此看出，插入一个节点，会让B树的那么多节点发生连锁改变。也正是如此，保证了B树始终维持多路平衡，这就是B树的一大优势，也是B树英语Balance-Tree中Balance的体现。
下面再看看B树的删除机制，以上面插入4后的B树为例，删除元素11，首先自顶向下找出11的位置
自顶向下找出11的位置
删除11后，节点12只有一个孩子，不符合B树规范，因此找出12，13，15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（此过程称为“左旋”）
删除11
左旋完成
以上便是B树的查询，新增和删除的机制，B树主要应用于文件系统（FS）以及部分数据库索引，比如著名的非关系型数据库MongoDB。但是绝大多数关系型数据库，比如MySQL，都使用B+树作索引
网友评论