MySQL详解：索引的介绍和原理分析( 二 ) _MySQL详解

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

文章插图

同理，在平衡二叉树进行插入或删除节点，也可能导致AVL树失去平衡，这种失去平衡的二叉树可以有四种状态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。
看下图示：

文章插图

我们来逐一看下这几种状态。
LL（LeftLeft），即左左。是指插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树比右子树高度>1，AVL树失去平衡。
RR（RightRight），即右右。是指插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树比左子树高度>1，AVL树失去平衡。
LR（LeftRight），即左右。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树比右子树高度>1，AVL树失去平衡。
RL（RightLeft），即右左。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树比左子树高度>1，AVL树失去平衡。
失去平衡的AVL树，可以通过旋转来修复，旋转的本质是将树的节点进行调整，达到恢复平衡的目的。下面逐一来看下。
LL的旋转： LL失去平衡的情况下，可以通过一次旋转让AVL树恢复平衡。步骤如下：
1、将根节点的左孩子作为新根节点。
2、将新根节点的右孩子作为原根节点的左孩子。
3、将原根节点作为新根节点的右孩子。
如下图所示：

文章插图

RR的旋转： RR失去平衡的情况下，旋转方法与LL旋转相反，步骤如下：
1、将根节点的右孩子作为新根节点。
2、将新根节点的左孩子作为原根节点的右孩子。
3、将原根节点作为新根节点的左孩子。
如下图所示：

文章插图

LR的旋转： LR失去平衡的情况下，需要进行两次旋转，步骤如下：
1、围绕根节点的左孩子进行RR旋转。
2、围绕根节点进行LL旋转。
如下图所示，它转了两次，最后恢复成一棵AVL树：

文章插图

RL的旋转： RL失去平衡的情况下也需要进行两次旋转，旋转方法与LR旋转相反，步骤如下：
1、围绕根节点的右孩子进行LL旋转。
2、围绕根节点进行RR旋转。
如下图所示，它转了两次，最后恢复成一棵AVL树：

文章插图

平衡多路查找树（B-Tree）我们知道，磁盘这种存储设备是以磁盘块（block）为基本单位的，而B-树也是基于这种存储方式设计的平衡查找树。
所以当我们从系统磁盘读取数据时，以磁盘块（block）为基本单位映射到内存中，位于同一个磁盘块中的数据会被一次性读取出来，而不是只取需要的数据。InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，我们可以在命令窗口输入以下脚本查看：

1 mysql> show variables like 'innodb_page_size';2 +------------------+-------+3 | Variable_name | Value |4 +------------------+-------+5 | innodb_page_size | 16384 |6 +------------------+-------+7 1 row in set

而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB 。
InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，
这将会减少磁盘I/O次数，提高查询效率。
B-Tree结构的数据可以让系统高效地找到数据所在的磁盘块。为了描述B-Tree，首先定义一条记录为一个二元组[key, data]，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。