MYSQL索引B+tree详解

前言

二叉树、平衡树、B树做铺垫，来讲解B+tree。这里对于数据结构不做详细解释，只讲与本文有关的知识。

一、二叉树

首先，明确几个概念，每个树结构，只有一个根节点。最下一层，没有子节点的节点叫叶子节点，初根节点和叶子节点外的节点，叫非叶子节点。

二叉树，顾名思义，就是子节点最多有两个分支的树，如下图:

由二叉树定义以及图示分析得出二叉树有以下特点：
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二、平衡二叉树

左右子树的高度相差不超过 1 的树为平衡二叉树。平衡之意，如天平，即两边的分量大约相同。平衡二叉树的查找效率是最高的。
平衡二叉树看起来左右就平衡，比如:

而下面这几种，就不是平衡二叉树:

三、 B树

平时所说的B-tree，就是B树。
上面我们提到的二叉树，当数据量非常大时，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构。
举例说明:
二叉树查找:

假如查找10，那么磁盘IO情况是:
第1次磁盘IO：

第二次磁盘IO:

第3次磁盘IO：

第四次磁盘IO:

可见，二叉树的查找，IO次数是与树的高度有关系的。当数据量很高时，树的高度也高，那么磁盘IO就很频繁，极大影响了性能。B树就是要把这种"高瘦"的树，变成"矮胖"的树。

首先，B树不要和二叉树混淆，在计算机科学中，B树是一种自平衡树数据结构，它维护有序数据并允许以对数时间进行搜索，顺序访问，插入和删除。B树是二叉搜索树的一般化，因为节点可以有两个以上的子节点。
所谓自平衡的意思就是，当添加或者删除节点时，B树会发生裂变或旋转，维持B树左右平衡的机制。假如某个B树是m阶，那么当加入数据超过m阶时，B树会发生裂变，来维持其m阶的特性。
正是因为B树的节点可以多于两个，所以说B树可以降低树的高度。非常适合用于做数据库的索引。
下面我们举例讲解B树插入数据的过程:
首先需要明确，树的一个节点，包含两部分，数据和指针，如下图:

我们以一个5阶树(就是一个节点有5个子节点了就进行裂变，拆分)为例，演示其插入数据的过程:

在(1)节点中，我们插入数据8，则插入后如下图:

此时，(2)中已经是6阶了，要发生裂变，(真实情况是先发生裂变，再插入数据，这里为了方便理解)。裂变取中间元素作为父节点，裂变后结构如下图:

接着插入元素5，11，17，不需要裂变，如下图：

再插入13，如下图:

此时，右侧子节点需要裂变，同样，选择中间元素进行裂变，裂变完后如下图:

依次类推，这就是B树插入数据的过程。由此可知，B树里的数据都是按顺序排序好的，在增加数据和删除数据时，都需要对数据进行排序，还有可能发生裂变。所以说B树的增删操作是比较影响性能的。

四、磁盘IO与预读

计算机存储设备一般分为两种：内存储器(main memory)和外存储器(external memory)。
内存储器为内存，内存存取速度快，但容量小，价格昂贵，而且不能长期保存数据(在不通电情况下数据会消失)。
外存储器即为磁盘读取，磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。

五、B+tree

千呼万唤使出来，下面我们看看B+tree。
B+tree是对B树的优化，我们看B+tree的特点：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

下面我们看一个B+tree：

可以看到，父节点的数据都出现在了子节点中，是子节点中最大(或最小)的元素。

需要注意的是，根节点的最大元素(这里是15)，也等同于整个B+tree的最大元素，以后无论插入删除多少数据，始终保持最大数据在根节点。由于父节点的元素都出现在子节点中，所以所有的叶子节点包含了全量元素信息。
并且每个叶子节点都带有指向下一个节点的指针，形成一个有序链表。
需要注意的是，在B+tree中，非叶子节点只存索引信息，而其他信息，在叶子节点中保存。所以在B+tree索引中，必须查询到叶子节点，才能找到数据，比较稳定。
而在B-tree中，每个节点，都存了数据的详细信息，当在某个节点找到要找的数据后，就不会再往下查找了。这就造成B-tree的查询极不稳定。而且，B-tree中每个节点携带了详细信息，占用空间就会大，IO一次读取的节点数就少，而B+tree非叶子节点只存索引信息，空间小，一次IO读取节点多，所以B+tree比B-tree更矮胖。

对于范围查询，我们看B+tree是如何做的:通过范围的下限，去查找到B+tree的叶子节点。找到叶子节点后，再通过叶子节点的链表，进行范围查询，这样性能就很高。
(***疑问:B+tree的非叶子节点只存索引信息，不存其他信息，如何理解，和联合索引有何关系??***)

最后，总结一下B+tree的优势:
1.单一节点存储更多的元素，使得查询的IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。
3.所有叶子节点形成有序链表，便于范围查询。

参考文章:什么是B+tree
什么是B-tree