Mysql B+数索引分析

         InnoDB存储引擎支持以下几种常见的索引：

•  B+树索引
• 全文索引
• 哈希索引

        B+数索引的构造类似于二叉树，根据 键值快熟查找数据，并且B+树中的B不代表二叉（Binary），而实代表平衡（balance），因为B+树是从最早的平衡二叉树演变而来的，但是B+树不是一个二叉树。B+树索引并不能找到一个键值的具体行，B+树索引找到的只是被查找数据行所在的页。然后数据库通过英把页读入内存，再在页中进行查找，最后找到要查找的数据。

       B+树索引是数据库中使用最频繁的一种索引。B+树是有平衡二叉树演化而来，所以在介绍B+树之前，先了解一下什么是二叉查找树和二叉平衡树。

       一.二叉查找树

       在二叉查找树中，左子树的键值总是小于根节点的键值，右子树的键值总是大于根节点的键值。

     该图就是二叉查找树，并且可以通过中序遍历得到键值的排序，为：235678.

     对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3) / 6 = 2.3次

    二叉查找树可以任意地构造，同样是2,3,5,6,7,8这六个数字，也可以按照下图的方式来构造：

     但是这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称AVL树。

   二.平衡二叉树

  平衡二叉树首先要满足二叉查找树的定义既：左子树的键值要小于根节点的键值，右子树的键值要大于根节点的键值，其次必须满足任意节点的两个子树的高度最大差为1。

  平衡二叉树的查询速度比较快，但是维护一颗平衡二叉树的代价非常大，对二叉树插入数据时需要左旋或者右旋来更新后树的平衡。

平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差<=1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1； 

如果在AVL树中进行插入或删除节点，可能导致AVL树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它们的示意图如下： 

这四种失去平衡的姿态都有各自的定义： 

LL：LeftLeft，也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。

RR：RightRight，也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。

LR：LeftRight，也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高2，AVL树失去平衡。

RL：RightLeft，也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高2，AVL树失去平衡。

AVL树失去平衡之后，可以通过旋转使其恢复平衡。下面分别介绍四种失去平衡的情况下对应的旋转方法。

LL的旋转。LL失去平衡的情况下，可以通过一次旋转让AVL树恢复平衡。步骤如下：

1. 将根节点的左孩子作为新根节点。
2. 将新根节点的右孩子作为原根节点的左孩子。
3. 将原根节点作为新根节点的右孩子。

LL旋转示意图如下： 

RR的旋转：RR失去平衡的情况下，旋转方法与LL旋转对称，步骤如下：

1. 将根节点的右孩子作为新根节点。
2. 将新根节点的左孩子作为原根节点的右孩子。
3. 将原根节点作为新根节点的左孩子。

RR旋转示意图如下： 

LR的旋转：LR失去平衡的情况下，需要进行两次旋转，步骤如下：

1. 围绕根节点的左孩子进行RR旋转。
2. 围绕根节点进行LL旋转。

LR的旋转示意图如下： 

RL的旋转：RL失去平衡的情况下也需要进行两次旋转，旋转方法与LR旋转对称，步骤如下：

1. 围绕根节点的右孩子进行LL旋转。
2. 围绕根节点进行RR旋转。

RL的旋转示意图如下： 

   三.B+树

   B+树和平衡二叉树，平衡二叉树一样。B+树是为了磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值对的大小顺序存放在同一层的叶子节点上，由各各叶子节点指针进行链接。

  1.B+树的插入操作

   B+树的插入必须保证插入后叶子节点中的记录依然排序，同时考虑插入到B+树的三种情况。

    在B+树中页会由旋转的功能，当叶子页已经满的时候，但是其的左右兄弟节点没有满的情况下。这时B+树不会急于去做拆分页的操作，而是将记录移到所在页的兄弟节点上，通常左兄弟会被首先检查用来做旋转操作。

   2.B+树的删除

B+树使用填充因子来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样必须满足删除后叶子节点中的记录依然排序，B+树的删除操作同样考虑以下三种情况。

   3.B+树索引

   B+树在数据中的高度一般都是2~4层。并且B+树索引可以分为聚集索引和辅助索引。聚类索引与辅助索引不同的是，叶子节点是否是一整行的信息。

   3.1.聚类索引

    聚集索引就是按照每一张表的主键构造一颗B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。聚集索引的这个特征决定了索引组织表中的数据是索引的一部分。同B+树的数据结构一样，每个数据页都是通过一个双向链表来进行链接的。

      由于实际的数据页只能按照一棵B+树的进行排序，因此每张表只能拥有一个聚集索引。

    3.2.辅助索引

    辅助索引叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含一个书签，该书签用于告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的书签就是相应行数据的聚集索引建。每张表可以有多个辅助索引。

文中的图片来源https://blog.csdn.net/ifollowrivers/article/details/73614549