深入理解MySQL索引底层实现原理丨技术干货

转载：

https://zhuanlan.zhihu.com/p/77383599

一、索引的本质

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。

我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

看一个例子：

上图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，原因会在下文介绍。

二、二叉排序树

在介绍B树之前，先来看另一颗神奇的树——二叉排序树（Binary Sort Tree）。关于这棵树大家已经很熟悉了，我不多说了，看原文吧。

若左子树不空，则左子树上所有节点的值均小于它的根节点的值
若右子树不空，则右字数上所有节点的值均大于它的根节点的值
它的左、右子树也分别为二叉排序数（递归定义）

从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）。

所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）

三、B树

还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2)，我们称之为m阶B树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树。博主棒。

总的来说，m阶B树满足以下条件：

每个节点至多可以拥有m棵子树
根节点，至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，既是根，也是叶，也是树）。
非根非叶的节点至少有Ceil(m/2)个子树（Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉）。
非叶子节点中的信息包括[n, A0, K1, A1, K2, A2, ..., Kn, An]，其中n表示该节点中保存的关键字个数，K为关键字且Ki<Ki+1，A为指向子树根节点的指针。
从根到叶子的每一条路径都有相同的长度，也就是说，叶子节点在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空。
B树的查询过程和二查排序树比较类似，从根节点依次比较每个节点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快的找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针。

例如查询图中字母表中的K：

从根节点P开始，K的位置在P之前，进入左侧指针
左子树中，依次比较C、F、J、M，发现K在J和M之间。
沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值。

B树搜索的简单伪代码如下：

BTree_Search(node, key) {
    if(node == null) return null;
    foreach(node.key)
    {
        if(node.key[i] == key) return node.data[i];
        if(node.key[i] > key) return BTree_Search(point[i]->node, key);
    }
    return BTree_Search(point[i+1]->node, key);
}
data = BTree_Search(root, my_key);

B树的特点可以总结为如下：

关键字集合分布在整颗树中
任何一个关键字出现且只出现在一个节点中
搜索有可能在非叶子节点结束
其搜索性能等价于在关键字集合内做一次二分查找
B树的插入删除新的数据记录会破坏B-Tree的性质，因为在插入删除时，需要对树进行分裂、合并、转移等操作以保持B-Tree的性质。

四、Plus版-B+树

作为B树的加强版，B+树与B树的差异在于

有n棵子树的节点含有n个关键字（也有人认为是n-1个关键字）。

所有的关键字全部存储在叶子节点上，且叶子节点本身根据关键字自小而大顺序连接。

非叶子节点可以看成索引部分，节点中仅包含有其子树（根节点）中的最大（最小）关键字。

B+树的查找过程，与B树类似，只不过查找时，如果在非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针直到叶子节点位置。因此在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径。

B+树的特性如下：

所有关键字都存储在叶子节点上，且链表中的关键字恰好是有序的
不可能非叶子节点命中返回
非叶子节点相当于叶子节点的索引，叶子节点相当于是存储（关键字）数据的数据层。
更适合文件索引系统

五、带有顺序访问指针的B+Tree

一般在数据库系统或文件系统中使用的B+Tree结构都在进店B+Tree的基础上进行了优化，增加了顺序访问指针，

如上图所示，在B+Tree的每个叶子节点增加一个指向相邻子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提高了取件查找效率。

六、MySQL为什么使用B树（B+树）

红黑树等数据结构也可以用来实现索引，但是文件系统以及数据库系统普遍采用B树或者B+树，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。

太长了，后面我总结一下

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
B-Tree巧妙地利用磁盘预读原理，将一个节点的大小设为等于一个页。每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。