mysql 节点查根_数据结构与算法之美——B-树和B+树

一、前言

mysql索引基于什么结构？ hash表或者B+树。B+树的实现细节是什么？B-树和B+树有什么区别？联合索引在B+树中如何存储？B-树和B+树都是很基础的概念。要明白什么是B+树，要先了解什么是B-树。需要注意的是B-树就是B树，中间的横线并不是减号。

数据库索引为什么要使用树存储？①树的查询效率高，②维持相对顺序。那为什么没有使用二叉查找树来实现呢？二叉查找树查询的时间复杂度是O(logN)，性能已经很高了，莫非B树比它更快？其实从算法逻辑上将，二叉查找树的查询次数和比较次数都是最小的。但是我们要考虑磁盘IO。

数据库索引是存储在磁盘上的，当数据量比较大时索引的大小可能有几个G甚至更多。当我们利用索引查询的时候，显然不能把整个索引全部加载到内存中。能做的只有逐一加载每一个磁盘块，这里的磁盘块对应 索引树的节点。

一颗100万的节点的平衡二叉查找树，树高是20。一次查询可能访问20个数据块，在机械硬盘时代，从磁盘随机读一个数据块需要10ms左右的寻址时间。也就是说对于1个100万行的表，如果使用二叉树来存储，单独访问一行可能需要20个10ms的时间。

为了提升读磁盘的效率，就必须访问尽量少的数据块。那么就不能使用二叉树这种“瘦高”的树。而应该使用“矮胖”的N叉树。这就是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

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

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

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

三、B树查询

演示一下B树的查询过程。假如我们要查询的数值是5。

第一次磁盘IO

在内存中定位(和9比较)：

第2次磁盘IO：

在内存中定位(和2，6比较)：

在内存中定位(和3，5比较)：

通过流程可以看出，B树在查询过程中比较次数其实不比二叉树少。尤其是当单一节点元素数量很多时。相比于磁盘IO的速度，内存中的比较耗时几乎可以忽略。所以只要树的高度足够低，IO次数足够少，就可以提升查询性能。

四、B树插入删除

B树插入新节点的过程比较复杂，而且分成很多种情况，在此只举最经典的例子。假如我们要插入的值是4。自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间。

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

为了插入1个元素，整个B树的多个节点发生了改变。也正因如此，让B树始终能维持多路平衡。这也是b树的一大优势：自平衡。

接下来说一下B树的删除。同样只举1个典型例子，删除元素11。自顶向下查找元素11的节点位置。

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

三、B+树

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

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

1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素)，每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大(或最小)元素。

举例来看下B+树的结构。

这种树不但节点之间含有重复元素，而且叶子节点还用指针连在一起。你说的这种就是B+树的几个特点。首先每一个父节点的元素都出现在子节点中，并且是子节点的最大(或最小)元素。

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

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

至于叶子节点，由于父节点的所有元素都出现在子节点，因此所有叶子节点包含了全量元素信息。 并且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。

B+树还具有1个特点，这个特点是在索引之外，却是至关重要的特点。那就是“卫星数据”的位置。所谓卫星数据，是指索引元素所执行的数据记录，比如数据库中的某一行在B-树中无论是中间节点还是叶子节点，都带有卫星数据。

B-树中的卫星数据：

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

B+树中的卫星数据：

四、B+树查询

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

1、单元素查询

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

第一次IO：

第二次IO：

第三次IO：

查询流程看起来和B-树差不多。但又2点不同。首先B+树的中间节点没有卫星数据，所以同样大小的磁盘块可以容纳更多的节点元素。这就意味着数据量相同的情况下B+树的结构比B-树更加“矮胖”，因此查询时IO次数也更少。其次B+树的查询必须找到叶子节点，而B-树只要找到匹配元素即可。无论是叶子节点还是中间节点。因此B-树的查找性能并不稳定(最好情况是只查根节点，最坏情况是查到叶子节点)。而B+树的每一次查找都是稳定的。

2、范围查询

B-树如何做范围查询呢？只能依靠中序遍历，比如我们要查找范围3到11的元素。B-树的范围查找过程如下：

自顶向下，查找到范围的下限(3)

中序遍历到元素6：

中序遍历到元素8：

中序遍历到元素9：

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

B-树的范围查询很繁琐。

而B+树的查询，则要简单地多。只需要在链表上做遍历即可。

B+树的范围查找过程：

自顶向下，查找到范围的下限(3)：

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

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

综上所述，B+树相比B-树的优点有3个：

①单一磁盘块存储更多的元素，使得查询的IO次数更少。

②所有查询都要查找到叶子节点，性能更稳定

③所有叶子节点形成有序链表，范围查找简便。