MySQL索引算法B树、B+树小结

MySQL逻辑架构图：

MySQL整体逻辑架构图可以分为Server层和存储引擎层。

Server层：

Server层涵盖了MySQL的大多数核心服务功能，以及所有的内置函数（如日期、时间、数学和加密函数passwd等），以及存储过程、触发器、视图等跨存储引擎的实现也在这一层来实现。

连接器：负责跟客户端建立连接、获取权限、维持和管理连接。
分析器：SQL词法分析，SQL语法分析
优化器：索引选择，选择一个执行效率高的，生成执行计划
执行器：操作引擎，返回执行结果
...
查询缓存：执行SQL语句之前，先查缓存，缓存结果可能是以key-value对方式存储的，key 是查询的语句，value 是查询的结果。

存储引擎层：

负责数据的存储和提取，是一种插件式的架构方式。

支持 InnoDB、MyISAM、Memory 等多个存储引擎。

MySQL 5.5.5版本开始默认存储引擎是 InnoDB，也是目前常用的存储引擎。

今天我们来看下详细看下优化器里的执行计划如何分析，要分析一个 SQL 的执行效率，就要会看执行计划，根据执行计划优化 SQL，使其能达到高效查询的目的。

一条查询语句需要经过 MySQL 查询优化器的各种基于成本和规则，优化后会生成一个所谓的执行计划。

那么这个执行计划主要展示具体执行查询的方式，比如多表连接的顺序是多少，表里包含多个索引，每个表采用什么访问方法来具体执行查询等。

而设计 MySQL 的大佬是非常贴心的，知道开发的朋友们都是亲自写 SQL 的，但是写出 SQL 容易，想写出性能高的 SQL 可不简单。

所以，大佬提供了 Explain 语句来帮我们查询某个查询语句的具体执行计划。

MySQL 存储引擎

查看MySQL 存储引擎的命令：show engines;

MariaDB [wordpress]> show engines;
+--------------------+---------+----------------------------------------------------------------------------------+--------------+------+------------+
| Engine             | Support | Comment                                                                          | Transactions | XA   | Savepoints |
+--------------------+---------+----------------------------------------------------------------------------------+--------------+------+------------+
| ROCKSDB            | YES     | RocksDB storage engine                                                           | YES          | YES  | YES        |
| MRG_MyISAM         | YES     | Collection of identical MyISAM tables                                            | NO           | NO   | NO         |
| CSV                | YES     | Stores tables as CSV files                                                       | NO           | NO   | NO         |
| MEMORY             | YES     | Hash based, stored in memory, useful for temporary tables                        | NO           | NO   | NO         |
| MyISAM             | YES     | Non-transactional engine with good performance and small data footprint          | NO           | NO   | NO         |
| Aria               | YES     | Crash-safe tables with MyISAM heritage                                           | NO           | NO   | NO         |
| InnoDB             | DEFAULT | Supports transactions, row-level locking, foreign keys and encryption for tables | YES          | YES  | YES        |
| PERFORMANCE_SCHEMA | YES     | Performance Schema                                                               | NO           | NO   | NO         |
| SEQUENCE           | YES     | Generated tables filled with sequential values                                   | YES          | NO   | YES        |
| OQGRAPH            | YES     | Open Query Graph Computation Engine (http://openquery.com/graph)                 | NO           | NO   | NO         |
| CONNECT            | YES     | Management of External Data (SQL/NOSQL/MED), including many file formats         | NO           | NO   | NO         |
+--------------------+---------+----------------------------------------------------------------------------------+--------------+------+------------+
11 rows in set (0.007 sec)

MyISAM 是MySQL 5.0 之前的默认数据库引擎，最为常用。拥有较高的插入，查询速度，但不支持事务

InnoDB 是事务型数据库的首选引擎，支持ACID事务，支持行级锁定, MySQL 5.5 起成为默认数据库引擎

BDB源自 Berkeley DB，事务型数据库的另一种选择，支持Commit 和Rollback 等其他事务特性

Memory所有数据置于内存的存储引擎，拥有极高的插入，更新和查询效率。但是会占用和数据量成正比的内存空间。并且其内容会在 MySQL 重新启动时丢失

Merge将一定数量的 MyISAM 表联合而成一个整体，在超大规模数据存储时很有用

Archive非常适合存储大量的独立的，作为历史记录的数据。因为它们不经常被读取。Archive 拥有高效的插入速度，但其对查询的支持相对较差

Federated将不同的 MySQL 服务器联合起来，逻辑上组成一个完整的数据库。非常适合分布式应用

Cluster/NDB高冗余的存储引擎，用多台数据机器联合提供服务以提高整体性能和安全性。适合数据量大，安全和性能要求高的应用

CSV：逻辑上由逗号分割数据的存储引擎。它会在数据库子目录里为每个数据表创建一个 .csv 文件。这是一种普通文本文件，每个数据行占用一个文本行。CSV 存储引擎不支持索引。

BlackHole：黑洞引擎，写入的任何数据都会消失，一般用于记录 binlog 做复制的中继

EXAMPLE 存储引擎是一个不做任何事情的存根引擎。它的目的是作为 MySQL 源代码中的一个例子，用来演示如何开始编写一个新存储引擎。同样，它的主要兴趣是对开发者。EXAMPLE 存储引擎不支持编索引。

另外，MySQL 的存储引擎接口定义良好，有兴趣的开发者可以通过阅读文档编写自己的存储引擎

什么是索引

索引是一种数据结构，其作用就是用来提高数据查询效率。

比较常用的比喻就是将索引类比为书籍的目录。通过目录可以精确的找到某一章节的内容所在页。

在数据量较小的时候使用索引其实也没有什么意义，即使没有索引需要一条一条遍历数据对于计算机来说也并不需要太多时间。而一旦数据量较大，要保证我们能正常的对外提供服务，保证用户使用体验那么索引就是必要的了。

索引类型

索引是一种数据结构，为了应对不同的场景会有多种实现。

在MySQL中主要就是 Hash索引和 B+Tree

Hash索引

hash相信大家应该都很熟悉，hash是一种key-value形式的数据结构。

实现一般是数组+链表的结构，例如Java HashMap数据结构，通过hash函数计算出key在数组中的位置，然后如果出现hash冲突就通过链表来解决(拉链法)。

当然还有其他的解决hash冲突的方法，请见米扑博客：哈希表算法原理

hash这种数据结构是很常用的，比如我们系统使用HashMap来构建热点数据缓存，存取效率很好。

hash结构存数据首先通过计算key的hash值来确定其在数组中的位置，如果有冲突就在该数组位置建一个链表。这样很明显有几个问题：

1）即使是具有相同特征的key计算出来的位置可能相隔很远，连续查询效率低下，即不支持范围查询。

2）hash索引存储的是计算得到的hash值和行指针，而不存储具体的行值，所以通过hash索引查询数据需要进行两次查询(首先查询行的位置，然后找到具体的数据)

3）hash索引查询数据的前提就是计算hash值，也就是要求key为一个能准确指向一条数据的key，所以对于like等一类的匹配查询是不支持的。

所以，我们可以知道的是hash索引适用于快速选取某一行的数据。

MyISAM 和 InnoDB 的索引均采用B+树数据结构，所以接下来先介绍一下B树与B+树。

B+Tree结构

从名字上看这明显是一种树结构，在大学期间数据结构的课本上，树结构是必讲的。

树结构是一种特别重要的数据结构，在很多地方都会使用到。

上面我们说到hash索引无法进行范围查询，在树结构中也有一种方便进行有序查询的结构--二叉搜索树。

二叉搜索树的结构中，要求父节点的值大于左孩子节点，并且小于右孩子节点。

而在MySQL索引中虽然也使用了树结构，但是并不是使用的二叉树。因为在数据库中数据最终都是存放在磁盘上的，而如果树的节点过多的话，那么在节点之间转移会花费较多的时间。在MySQL的实现中选择将更多内容放在同一个节点，对同一个节点的操作转入在内存中完成，减少在外存中节点之间转移的次数，以达到提高效率的目的。这就是B+Tree，在B+Tree的实现中一个三层的树结构就基本上可以满足我们几乎所有的需求了。

B-Tree（B树）

B-Tree是一种平衡树，这里的B指的是Balance而不是Binary，更确切的说B-Tree是一种多路平衡搜索树。

特别提示：B-tree、B-树、B树，三者是同一个数据结构，因为英语翻译后，有些人误解了以为是多种树。

B树是一种多路搜索树。

定义任意非叶子结点最多只有M个儿子，且M>2。
根结点的儿子数为[2, M]。
除根结点以外的非叶子结点的儿子数为[M/2, M]。
每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）。
非叶子结点的关键字个数=指向儿子的指针个数-1。
非叶子结点的关键字：K[1], K[2], …, K[M-1]，且K[i] < = K[i+1]。
非叶子结点的指针：P[1], P[2], …,P[M]（其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树）。
所有叶子结点位于同一层。

下图是一个M=4阶的B树。

B树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的是叶子结点。

查找文件29的过程：

根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。（磁盘IO操作1次）

此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。

根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。（磁盘IO操作2次）

此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。

根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。（磁盘IO操作3次）

此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。

下面的动画是4阶B树插入的过程。

（因为动图时间过长，微信无法显示。请查看原文阅读博客，可以正常显示动图）

B树的特性：

关键字分布在整颗树的所有节点。

任何一个关键字出现且只出现在一个结点中。

搜索有可能在非叶子结点结束。

其搜索性能等价于在关键字全集内做一次二分查找。

这是一种2-3树，意思就是每个节点存有两个值，同时每个节点分支数为3，从上图中可以看出来着中结构很适合查询数据。每个节点的左子树的值都是小于当前节点中最小的值，中间的子树的值全都是在当前节点两个值的中间，而右子树的值全都大于当前节点的最大值。

比如我们要查找24这个值：

（1）首先从根节点判断24在根节点(15,25)之间，所以左右子树排除，从中间查找。

（2）然后找到中间子树的根节点(18,22)，比较发现24大于该节点最大值，排除左子树和中间子树。

（3）找到右子树，判断节点大值刚好等于24，查询结束。

基于上面的流程可以总结B树的搜索：

（1）从根结点开始，对结点内的关键字（有序）序列进行二分查找。

（2）如果命中则结束，否则进入查询关键字所属范围的子结点；

（3）重复上面的流程，直到所对应的子节点为空，或已经是叶子结点；

可以看出其搜索性能相当于在关键字集合内做一次二分查找。从这里看来好像B-Tree没有什么问题，但是需要注意到的是在B-Tree中每一个节点都是存储索引关键字以及其代表的具体行数据。而在MySQL中数据库加载数据是以页为单位加载，每一页的大小是固定的(默认16k)。如果每一个节点都存储所有的值，那么一页中能存下的节点就会很少，一次查询可能就会进行多次从内存中去加载数据，导致性能降低。

B+Tree

B+Tree是对B-Tree（B树）的一个变种，让其更加适应于进行外部存储文件索引。

两者之前最大的不同就在于B-Tree的每个节点都存储所有的数据，而B+Tree需要存储的数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都有指向下一个相邻的叶子节点的地址。这样的结构保证了在一个内存页中可以存下更多的索引节点，并且更加适合进行范围查询。

因为存储引擎负责实现索引，所以接下来讨论索引都是基于MySQL的InnoDB引擎。

聚簇索引

聚簇的意思是表示数据行和相邻的键值聚簇的存储在一起。一些数据库允许选择具体的某一个索引作为聚簇索引，而在InnoDB的实现中直接将主键索引指定为聚簇索引。如果没有定义主键，InnoDB 会选择一个唯一的非空索引来代替主键索引。如果同样没有定义这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引(row_id)。

非聚簇索引索引

在InnoDB中除主键索引外其他都是非聚簇索引，所以也叫非主键索引。

非主键索引的叶节点并不是存储一行的值，而是存储具体行的主键值。不满足聚簇的定义。

聚簇索引和非聚簇索引在查询时的差异

由上面的两种索引实例图就可以看出来，在查询时如果是通过主键索引查询的话直接查询到数据行然后返回。但是如果是通过非主键索引查询的话首先需要通过该索引确定主键，然后通过得到的主键从主键索引中查到具体行的数据，后面的通过得到的主键从主键索引中获取数据的过程被称为回表。

回表的过程使得通过普通索引查询较主键索引查询多了一步，在很多情况下效率相对较低。所以在我们的查询过程中如果能够仅通过主键确定数据那最好就是直接使用主键进行查询。

覆盖索引

上面介绍了通过非主键查询会有一个回表的过程，但是需要注意的是并不是每一个查询都存在回表这一步，对于一个普通索引来说其叶节点存储的是主键的值，那么假设我现在需要的数据也仅仅就是主键的值呢？通过普通索引取到主键的值后就并不需要再到主键索引中查，那么也就不存在回表这一过程了。

上面例子中该非主键索引已经存在了我们所需要的值，所以该索引也被称为覆盖索引。覆盖索引并不是一个固定的结构，可以使单索引(一个字段的索引)，也可以使复合索引，凡是能够直接提供查询结果而不需要进行回表过程的都可以被称为覆盖索引。

很多时候我们不可能仅仅通过主键来确定数据，使用普通索引可能会导致低效，所以覆盖索引在日常开发过程中也是一个很常用的性能优化的手段。

当然覆盖索引页并不都是好的，比如我现在建立了一个索引index(a,b)。由a，b两个字段来建立索引，好处已经说过了就是查询ab字段时不会回表，但是如果仅仅通过b字段来查询就无法走这个索引了。建立的索引的索引项是按照索引定义里面出现的字段顺序排序的。

最左前缀原则