B+树索引及其原理

?MySQL索引的底层结构是B+树，为什么它会选择这个结构？联合索引是怎么实现的？最左侧匹配原则的原理是什么？本文将一一解答这些疑惑。

1 前置知识

在学习B+树之前，我们先了解下其他的树形结构：二叉树、平衡二叉树及B-树。将以循序渐进的方式来学习它们并比较它们的优缺点。

下面我们将在不同的树形结构上按顺序分别插入数字：5，9，6，33，14，7，8，10，22。

1.1 二叉树

性质：左子树的键值小于根的键值，右子树的键值大等于根的键值。

图 二叉树按照不同顺序插入数字后的形态

插入算法：自根向下插入，将会与根节点比较，如果大等于根节点则插入到右子树，否则插入到左子树。二叉树插入算法非常简单。

从上图，我们发现如果按照不同顺序插入数字，二叉树到形态会不一样的；同时，会发现上图右边两个二叉树的查询效率会比较低，因为它们“失衡”了，左子树和右子树高度不一致，将导致查询效率降低。

1.2 平衡二叉树

简称AVL Tree。自平衡二叉树。本质上还是一棵二叉树，其特点是：每个节点的左右子树高度差的绝对值（平衡因子）最多为1。

平衡二叉树的关键点是维持平衡。分为两步施行：

1）确定失衡姿态。先找到最小不平衡子树，从最小不平衡子树的根向插入节点数两步，即可确定。有四种失衡姿态：

LL	Left Left,左左。根节点的左子树的左子树的非空节点，导致根节点的左子树高度比右子树高2。
RR	Right Right,右右。插入或删除一个节点，根节点的右子树的右子树的非空节点，导致根节点的右子树的高度比左子树高2。
LR	Left Right,左右。根节点的左子树的右子树的非空节点，导致根节点的左子树的高度比右子树高2。
RL	Right Left,右左。根节点的右子树的左子树的非空节点，导致根节点的右子树的高度比左子树高2。

表 平衡二叉树失衡的四种姿态

图 平衡二叉树失衡的四种姿态

2）根据失衡姿态做相应调整来维持平衡。

LL	右单旋。	RR	左单旋。
LR	先左旋，使其成为LL姿态，然后再右旋。	RL	先右旋，使其成为RR姿态，然后再左旋。

表 平衡二叉树不同失衡姿态下的平衡策略

图 LR姿态调整到平衡状态的过程

缺陷：1）平衡二叉树在插入和删除过程中很容易失衡，因此需要频繁的重新保持平衡。2）当插入到平衡二叉树的数字极多时，二叉树将非常的高。而查询效率和树的高度成反比。

1.3 B-树

首先，这个读B树，不是读B减树。全名为平衡多路查找树。M阶B树表示其最多可以有M个子树（实际应用中，M的值非常大，这样的好处就是即使存储大量的数据，B树的高度仍然比较小）。

1.3.1 磁盘预读

数据库的数据是存储在磁盘上的，要提高查询效率，就需要减少系统与磁盘交互的次数。

系统从磁盘读取数据到内存时是以磁盘块为基本单位，位于同一磁盘块中的数据会被一起读取。InnoDB中的页是其磁盘管理的最小单位，默认大小是16KB（磁盘块往往没这么大）。InnoDB每次申请磁盘空间时都会是若干个连续地址的磁盘块来达到16KB（通常是整数倍）。

图 B树结构下的磁盘块逻辑图

在查询数据时，可以通过磁盘块中的信息连接到其他的磁盘块查找数据。当一个磁盘块下的子树越多，意味着系统访问的磁盘块数量越少。

1.3.2 B-树的性质

M阶B树有有以下性质：

1）根节点最少拥有两棵子树。

2）非根节点关键字个数n满足：ceil(m/2) -1<= n <= m-1; (ceil表示向上取整)。

3）有n棵子树的分支节点则一定存在n-1个关键字。关键字按照递增顺序进行排序。（n>0）

4）所有的叶子节点都在同一层。

B树的节点上存储了数值及指向子树的指针。

1.3.3 B树的插入与删除

B树在插入与删除过程中，需要保持一直它的性质。在这过程中破坏B树结构的主要因素是：节点的关键字数量不符合要求。

插入时先插入，后调整。

1	根据要插入的key值，找到叶子节点并插入。
2	判断当前节点的关键字个数是否满足要求，满足则操作结束，否则进行下一步。
3	以节点中间的key为中心分裂成左右两部分，然后将中间的key插入到父节点中，这个key的左子树指向分裂后的左部分，右子树指向分裂后的右部分。如果key所在的节点关键字不符合要求，则在这个节点上继续执行这一步。

表 B树的插入步骤

图 3阶级B树插入9

删除时分为两步：

1）查找并确定位置，并删除关键字，这一步有两种情况。

a）是叶子节点，则直接删除。

b）非叶子节点，需要用该关键字的后继关键字来填充该关键字，转化为在叶子节点删除一个关键字。后继关键字是其左子树最大的键值或右子树最小的键值。

2）调整B树以维持B树性质。

a）如果缺少节点的右邻兄弟存在且拥有多余的键，则左旋。

b）如果缺少节点的左邻兄弟存在且拥有多余的键，则右旋。

c）左右都没有多余的键，则将它与一个相邻兄弟节点以及父节点中它们的分隔值合并。如果B树失衡，则重新平衡父节点。

图 3阶B树删除14（删除阶段非叶子节点，9和22是后继节点）

图 3阶B树删除9（缺少节点的右邻兄弟存在多余键）

图 3阶B树删除14（合并节点后B树失衡）

1.3.4 B树的优缺点

优点：B树可以不要像平衡树那样频繁的重新保持平衡，同时树的高度远远低于平衡树，这样查询效率就能提高。

缺点：B树可能会没有完全填充，会浪费一些空间。B树也不适合范围查询（比如要查询6-12之间的值）。

2 B+树

对，这个读作B加树。M阶B+树有以下的性质：

1）根节点至少有一个关键字。

2）非根节点关键字数量n满足 ceil(m/2) <= n <= m。

3）有n个关键字必须有n个子女。

4）所有叶子节点在同一层，并且不包含任何信息（可看成是外部节点或查找失败的节点）。

5）关键字自小到大排列。

B+树的节点类型有两种，即内部节点（也叫索引节点）和叶子节点。内部节点不保存数据，只用于索引。

2.1 B+树的插入

插入操作全部在叶子节点上进行，且不能破坏关键字自小到大的顺序。B树的插入分四种情况：

1）被插入关键字所在节点，其关键字数目小于m，并且被插入值小等于该节点最大值，则直接插入。

2）被插入关键字所在节点，其关键字数目小于m，但是被插入值大于该节点最大值，则修正从根节点到当前节点到所有索引值，然后再进行插入。

3）被插入关键字所在节点，其关键字数目等于m,则将此节点分裂为左右两部分，中间的关键字放到父节点中。放入后如果父节点关键字数量小等于m，则操作完成，否则继续分离父节点。

图 3阶B+树插入55的过程

2.2 B+树的删除

B+树的删除与B树的删除算法有些类似。分为两种情况：

1）删除后节点关键字个数>=ceil(m/2)。

a) 如果被删除元素非索引值，则直接删除。

b）是索引值，则将该节点的索引值替换成被删除元素前一个元素，然后再删除。

2）删除后节点关键字个数<ceil(m/2)。

a）相邻兄弟节点有多余关键字，则删除后从其兄弟节点借一个关键字。

b）相邻兄弟节点没有多余关键字，则被删除其他痛其兄弟节点进行合并。（合并后如果破坏了B+树结构，则需要按B+树的性质进行修正。）

图 3阶B+树删除8的过程

2.3 B+树的优缺点

优点：与B 树一样不要频繁的维护其平衡，非常便于范围查找。

缺点：在插入及删除元素的过程中，所做的操作比较多。同时其叶子节点存储了相关的指针，也加大了整个的内存。

3 B+树索引

3.1 联合索引

mysql建立联合索引只会建立一棵B+树。与单值索引，其关键字多了几列（索引项）。排序时，先按照第一列排序，如果相等则按照下一列排序…依此类推。

3.2 MongoDB为什么使用B树作为底层结构

作为非关系型数据库，它对于遍历数据单需求没那么强，它追求的是查询单个记录的性能。

多数使用场景是读多写少。在MongoDB中单个数据查询需求比变量数据更常见。由于B树的非叶子节点也可以存储数据，所以查询一条数据所需的平均随机I/O次数也会比B+树少。这样查询速度也会更快。