B-树和B+树

思考并回答以下问题：

• 数据库索引为什么要使用树结构存储呢？
• 为什么索引没有使用二叉查找树来实现呢？
• B+树的实现细节是什么样？B-树和B+树有什么区别？
• 联合索引在B+树中如何存储？
• 卫星数据，指的是索引元素所指向的数据记录，比如数据库中的某一行。怎么理解？
• B+树的非叶子节点是没有卫星数据的，非叶子节点只起到索引的作用。是什么意思？

索引

MySQL的索引主要是基于Hash表和B+树。

要弄明白B+树，先要了解什么是B-树。需要注意的是，B-树就是B树，中间的横线并不是减号（不要读成B减树）。

二叉查找树

数据库索引为什么要使用树结构存储呢？

因为树的查询效率高，而且可以保持有序。

既然这样，为什么索引没有使用二叉查找树来实现呢？

其实从算法逻辑上来讲，二叉查找树的查找速度和比较次数都是最小的。但是，我们不得不考虑一个现实问题：磁盘IO。

数据库索引是存储在磁盘上的。当数据量比较大的时候，索引的大小可能有几个G甚至更多。

当我们利用索引查询的时候，能把整个索引全部加载到内存吗？显然不可能。能做的只有逐一加载每一个磁盘页，这里的磁盘页对应着索引树的节点。

如果我们利用二叉查找树作为索引结构，情形是什么样呢？假设树的高度是4，查找的值是10，那么流程如下:

二叉查找树的结构：

第1次磁盘IO：

第2次磁盘IO：

第3次磁盘IO：

第4次磁盘IO：

有没有从中看出，磁盘IO的次数是由什么决定？

磁盘IO的次数是4次，索引树的高度也是4。所以最坏情况下，磁盘IO次数等于索引树的高度。为了减少磁盘IO次数，我们就需要把原本“瘦高”的树结构变得“矮胖”，这就是B-树的特征之一。

二叉查找树的查找效率是最高的，如果内存能装下完整的树，最好使用二叉查找树，B树是退而求其次的方式。

B树

B树索引可以理解成是主要存储于磁盘中的数据结构。

B树是一种多路平衡查找树，它的每一个节点最多包含k个孩子，k被称为B树的阶。k的大小取决于磁盘页的大小。

下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：

• 1.根结点至少有两个子女。
• 2.每个中间节点都包含k-1个元素和k个孩子，其中m/2 <= k <= m。
• 3.每一个叶子节点都包含k-1个元素，其中m/2 <= k <= m（B-树叶子节点的元素数量最多可以是阶数-1。比如一颗4阶的B-树，每个节点最多包含有4个孩子、3个元素；最少包含有2个孩子，1个元素）。
• 4.所有的叶子结点都位于同一层。
• 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

我们以一个3阶B-树为例，来看看B-树的具体结构。树中的具体元素和刚才的二叉查找树是一样的。

这棵树中，重点来看(2，6)节点。该节点有两个元素2和6，又有三个孩子1，(3，5)，8。其中1小于元素2，(3，5)在元素2，6之间，8大于(3，5)，正好符合刚刚所列的几条特征。

查询

假如要查询的数值是5。

第1次磁盘IO：

在内存中定位（和9比较）：

第2次磁盘IO：

在内存中定位（和2，6比较）：

第3次磁盘IO：

在内存中定位（和3，5比较）：

通过整个流程我们可以看出，B-树在查询中的比较次数其实不比二叉查找树少，尤其当单一节点中的元素数量很多时。

可是相比磁盘IO的速度，内存中的比较耗时几乎可以忽略。所以只要树的高度足够低，IO次数足够少，就可以提升查找性能。

相比之下节点内部元素多一些也没有关系。仅仅是多了几次内存交互，只要不超过磁盘页的大小即可。这就是B-树的优势之一。

插入

B-树插入新节点的过程比较复杂，而且分成很多种情况。我们只举一个最典型的例子，假如我们要插入的值是4。

自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间。

节点3，5已经是两元素节点，无法再增加。父亲节点2，6也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。

就为了插入一个元素，让整个B树的那么多节点都发生了连锁改变。确实有些麻烦，但也正因为如此，让B-树能够始终维持多路平衡。这也是B-树的一大优势：自平衡。

删除

同样只举一个典型例子，删除元素11。

自顶向下查找元素11的节点位置。

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

应用

B-树主要应用于文件系统以及部分数据库索引，比如著名的非关系型数据库MongoDB。

B-树的好处是，虽然查询性能不稳定，但平均的查询速度快一些（不用每次都查找到叶子节点为止）。

而大部分关系型数据库，比如MySQL，则使用B+树作为索引。

B+树

B+树是基于B-树的一种变体，有着比B-树更高的查询性能。

先回顾一下B-树的几大特征。一个m阶的B树具有如下几个特征：

• 1.根结点至少有两个子女。
• 2.每个中间节点都包含k-1个元素和k个孩子，其中m/2 <= k <= m。
• 3.每一个叶子节点都包含k-1个元素，其中m/2 <= k <= m。
• 4.所有的叶子结点都位于同一层。
• 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B+树和B-树有一些共同点，但是B+树也具备一些新的特征。

一个m阶的B+树具有如下几个特征：

• 1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
• 2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

具体例子

这是什么怪树？不但节点之间含有重复元素，而且叶子节点还用指针连在一起。

这些正是B+树的特点。首先，每一个父节点的元素都出现在子节点中，是子节点的最大（或最小）元素。

在上面这棵树中，根节点元素8是子节点2，5，8的最大元素，也是叶子节点6，8的最大元素。

根节点元素15是子节点11，15的最大元素，也是叶子节点13，15的最大元素。

需要注意的是，根节点的最大元素（这里是15），也就等同于整个B+树的最大元素。以后无论插入删除多少元素，始终要保持最大元素在根节点当中。

至于叶子节点，由于父节点的元素都出现在子节点，因此所有叶子节点包含了全量元素信息。

并且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。

这是以空间换时间，因为子节点都包含父节点的元素。树的层数和一个节点被重复存储成线性关系。父节点元素在子节点重复出现，增加了少量空间，换来的是范围查询的便利。

B+树还具有一个特点，这个特点是在索引之外，却是至关重要的特点。那就是[卫星数据]的位置。

所谓卫星数据，指的是索引元素所指向的数据记录，比如数据库中的某一行。在B-树中，无论中间节点还是叶子节点都带有卫星数据。

B-树中的卫星数据（Satellite Information）：

而在B+树当中，只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联。

B+树中的卫星数据（Satellite Information）：

需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。

B+树设计成这样子究竟有什么好处呢？

B+树的好处主要体现在查询性能上。下面我们分别通过单行查询和范围查询来做分析。

在单元素查询的时候，B+树会自顶向下逐层查找节点，最终找到匹配的叶子节点。比如我们要查找的是元素3。

第一次磁盘IO：

第二次磁盘IO：

第三次磁盘IO：

查询流程看起来跟B-树差不多。但其实有两点不同。首先，B+树的中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素。

这就意味着，数据量相同的情况下，B+树的结构比B-树更加“矮胖”，因此查询时IO次数也更少。

其次，B+树的查询必须最终查找到叶子节点，而B-树只要找到匹配元素即可，无论匹配元素处于中间节点还是叶子节点。

因此，B-树的查找性能并不稳定（最好情况是只查根节点，最坏情况是查到叶子节点）。而B+树的每一次查找都是稳定的。

B+树的查询每次都查到叶子节点，所以IO次数稳定。试想一个数据库的查询，有时候执行10毫秒，有时候执行100毫秒，肯定是不太合适的。还不如每次都执行30毫秒。

B-树的范围查找过程

下面我们再来看看范围查询。B-树如何做范围查询呢？只能依靠繁琐的中序遍历。比如我们要查询范围为3到11的元素：

自顶向下，查找到范围的下限（3）：

中序遍历到元素6：

中序遍历到元素8：

中序遍历到元素9：

中序遍历到元素11，遍历结束：

B-树的范围查询确实很繁琐。反观B+树的范围查询，则要简单得多，只需要在链表上做遍历即可：

B+树的范围查找过程

自顶向下，查找到范围的下限（3）：

通过链表指针，遍历到元素6，8：

通过链表指针，遍历到元素9，11，遍历结束：

比B-树的中序遍历要简单得多。

综合起来，B+树相比B-树的优势有三个：

• 1.IO次数更少；
• 2.查询性能稳定；
• 3.范围查询简便。

至于B+树的插入和删除，过程与B-树大同小异。

总结

联合索引就是把多个索引值拼接成一个字符串A，字符串A像普通索引一样保存在索引树中。

最后我们来总结一下， B+树的特征和优势：

B+树的特征：

• 1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
• 2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
• 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。一开始就要规定好，要么元素在子节点都是最大的要么都是最小的，不能有的是最大的，有的是最小的。

B+树的优势：

• 1.单一节点存储更多的元素，使得查询的IO次数更少。
• 2.所有查询都要查找到叶子节点，查询性能稳定。
• 3.所有叶子节点形成有序链表，便于范围查询。

在节点占用空间恒定的情况下，B+树单个节点的元素更多。比如同样节点大小，B树的每个节点有100个元素，B+树的每个节点就可以装下1000个元素。这样的好处就是树的高度降低了。

为什么MongoDB索引选择B-树，而MySQL选择B+树

一、B-树和B+树的区别

很明显，我们要想弄清楚原因就要知道B-树和B+树的区别。

1、B-树

B-树是一种自平衡的搜索树，形式很简单：

这就是一颗B-树。针对我们这个问题的最核心的特点如下：

• （1）多路，非二叉树。
• （2）每个节点既保存索引，又保存数据。
• （3）搜索时相当于二分查找。

2、B+树

B+树是B-树的变种。

最核心的特点如下：

• （1）多路非二叉
• （2）只有叶子节点保存数据
• （3）搜索时相当于二分查找
• （4）增加了相邻接点的指向指针。

从上面我们可以看出最核心的区别主要有俩，一个是数据的保存位置，一个是相邻节点的指向。就是这俩造成了MongoDB和MySQL的差别。为什么呢？

3、B-树和B+树的区别

（1）B+树查询时间复杂度固定是logn，B-树查询复杂度最好是O(1)。

（2）B+树相邻接点的指针可以大大增加区间访问性，可使用在范围查询等，而B-树每个节点key和data在一起，则无法区间查找。

（3）B+树更适合外部存储，也就是磁盘存储。由于内节点无data域，每个节点能索引的范围更大更精确。

（4）注意这个区别相当重要，是基于（1）（2）（3）的，B-树每个节点即保存数据又保存索引，所以磁盘IO的次数很少，B+树只有叶子节点保存，磁盘IO多，但是区间访问比较好。

有了他们的区别之后，现在我们再来解释这个原因就好多了。

二、原因解释

想要解释原因，我们还必须要了解一下MongoDB和MySQL的基本概念。

1、MongoDB

MongoDB是文档型的数据库，是一种NoSQL，它使用类Json格式保存数据。比如之前我们的表可能有用户表、订单表、购物篮表等等，还要建立他们之间的外键关联关系。但是类Json就不一样了。

我们可以看到这种形式更简单，通俗易懂。那为什么MongoDB使用B-树呢？

MongoDB使用B-树，所有节点都有Data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于MySQL。

2、MySQL

MySQL作为一个关系型数据库，数据的关联性是非常强的，区间访问是常见的一种情况，B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历。

这俩区别的核心如果你能看懂B-树和B+树的区别就很容易理解。