MySQL索引：B+树原理揭秘与索引优缺点分析

一、索引介绍

1、索引定义

索引是存储引擎中，用于快速找到记录的一种数据结构。索引能够帮助存储引擎快速获取数据，形象的说就是索引是数据的目录。

所谓的存储引擎，通俗的来说就是如何存储数据、如何为存储的数据建立索引和如何更新、查询数据等
技术的实现方法。

MySQL存储引擎有MyISAM、InnoDB、Memory，其中InnoDB是在MySQL 5.5之后成为默认的存
储引擎。

在实际场景中，索引对于良好的性能起到非常关键的作用。或许在数据量小且负载较低时，索引的不恰当使用可能对性能的影响可能不会太明显，但是当表中的数据量越来越大的时候，索引对性能的影响就愈发重要，不恰当的索引会让性能急剧的下降。

2、索引的查找方式

在MySQL的InnoDB存储引擎中

若没有索引的情况下进行数据查询

a) 在一个数据页中查询

当表中的记录比较少时，所有记录可以存放到一个数据页中。当查询记录时，根据搜索条件的不同查询分为两种情况：

• 以主键为搜索条件：在一个数据页内的记录会根据主键值的大小从小到大的顺序组成一个单向链表。每个数据页都会为存储在它里面的记录生成一个页目录。通过主键查询某条记录可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组的记录，即可快速找到指定的记录。

• 以其他列作为搜索条件：对于非主键列的查找，由于没有为非主键列建立对应的目录页，即未创建索引。无法用二分法快速定位相应的槽，只能从Infimum记录开始依次遍历单向链表中的每条记录，然后对比每条记录是否符合搜索条件，即全表扫描，因此效率非常低。

b) 在多个数据页中查询

在很多情况下，表中存放的记录是非常多的，需要查询到的数据可能分布在多个数据页中，在多个页中查找记录可以分为两个步骤：

• 定位到记录所在的页

• 从所在的页内查找相应的记录

在没有索引的情况下，无论是根据主键列还是其他列的值查找，都不能快速定位到记录所在的页，因此只能从第一页沿着双向链表一直往下找，因而非常耗时。

若存在索引的情况下进行数据查询

在创建索引的情况下，每个数据页都会为存储在它里面的记录生成一个目录项，在通过索引查找某条记录时可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录，快速找到指定的记录，确定记录后，即可向下寻找当前记录对应的下一个页节点，直到寻找到存在目标记录的叶子结点。

二、索引分类

1、按数据结构分类

Hash索引

哈希表是一种以键-值（key-value）存储数据的结构，输入待查找的键，即key，就可以找到其对应的值，即value。

哈希的思路很简单，把值放在数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置。

不可避免地，多个key值经过哈希函数的换算，会出现同一个值的情况，即哈希碰撞，处理这种情况的一种方法是，拉出一个链表。

但是，在哈希表中，数据的存储不是按顺序存放的，所以哈希索引做区间查询的速度是很慢的。

所以，哈希表这种结构适用于只有等值查询的场景，比如Memcached及其他一些NoSQL引擎。

有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀。

在查找数据方面，有序数组可以通过二分查找的方式快速找到，时间复杂度是 O(log(N))。

同样，有序数组的索引结构支持范围查询，通过二分法找到需要查找的范围的首元素，然后向后遍历，直到找到第一个不满足条件的元素为止。

如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

所以，有序数组索引一般适用于静态存储引擎。

B+树（InnoDB索引结构）

在MySQL 5.5之后，InnoDB成为默认的MySQL存储引擎，B+Tree索引类型也是MySQL存储引擎采用最多的索引类型。

在InnoDB数据页中，各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表。

在介绍B+树时，我们以主键索引为例，来看看InnoDB是如何构建主键索引的B+树。其他字段所建立的索引与主键索引相似，只是将主键字段替换成指定的索引字段来构建B+树。

主键策略

在创建表时，InnoDB存储引擎会根据不同的场景选择不同的列作为主键索引：

• 如果有指定主键，默认会使用主键作为聚簇索引的索引键
• 如果没有指定主键，则选择第一个不包含NULL值的唯一列作为聚簇索引的索引键
• 在上面两个都没有的情况下，InnoDB将自动生成一个隐式自增id列作为聚簇索引的索引键

除主键索引外，其它索引都属于辅助索引（Secondary Index），也被称为二级索引或非聚簇索引。创建的主键索引和二级索引默认使用的是B+Tree索引。

建立B+树索引的条件

条件一：下一个数据页中记录的主键值必须大于上一个数据页中记录的主键值

我们知道，在MySQL中，新分配的数据页编号可能并不是连续的，即这些数据页在磁盘上并非紧挨着存储。需要通过维护上一下和下一页的编号，因此，在InnoDB中，每个数据页组成了一个双向链表来维护每个数据页之间的上下关系。

为什么构建B+树需要满足条件一呢？

原因在于为了提高范围查询的效率，B+树要求叶子节点中的数据记录按照主键值的顺序进行排列。

当进行范围查询时，如果叶子节点中的数据记录不按照主键值的顺序排列，就会增加查找的复杂度。如果下一个数据页中记录的主键值小于上一个数据页中记录的主键值，那么在进行范围查询时就需要在不同的叶子节点之间来回跳转，这样会增加IO操作次数和查询时间。

因此，为了保证范围查询的效率，B+树要求叶子节点中记录的主键值必须按照顺序排列，即下一个数据页中记录的主键值必须大于上一个数据页中记录的主键值。这样可以确保在进行范围查询时可以顺利地按照主键值的顺序进行遍历，提高查询效率，同样MySQL中的预加载页功能也可以减少IO操作次数。

在InnoDB中，在对页中的记录进行增删改操作时，必须通过一些记录移动的操作来始终保证：下一个数据页中用户的记录的主键值必须大于上一个页中用户记录的主键值，则这个过程也成为页分裂操作，即在一个数据页中插入记录，而该数据页在插入之前已经满了，则需要申请一个新的数据页，然后挪动部分数据过去。

条件二：需要给所有的数据页建立一个目录页

由于每个数据页的编号可能并不连续，因此需要为这些数据页建立一个目录。

比如当我们看一本书的时候，书的目录可以帮助我们快速定位到我们想看的内容，而目录标题对应的页号可以比作每个数据页的页号，通过书的目录我们可以快速定位到我们想看的内容，同样的道理，通过为数据页建立目录，在目录中存储数据页的编号，即可通过目录快速定位到相应的数据页。

目录页可以包括两个内容：

• 数据页的记录中最小的主键值，用key表示
• 数据页页编号，用page_no表示

为了方便说明，我们可以定义一个数据表：

CREATE TABLE `index_demo` (
  `a` int NOT NULL,
  `b` int DEFAULT NULL,
  `c` char(1) DEFAULT NULL,
  PRIMARY KEY (`a`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci ROW_FORMAT=COMPACT;

上述表定义中，使用了COMPACT行格式来存储数据，COMPACT行格式的简化存储如下：

我们假设每个数据页最多只能存放2条记录（实际一个数据页非常大，可以存放许多的记录）

当为数据页编制其对应的目录页时，如图下所示：

我们以页10为例，为其编制的目录项为目录项1，该目录项包含了该页的页号10以及该页的数据记录中主键值最小的值1。当我们把这些目录项在物理存储器中连续存储，就可以实现根据主键快速查找某条记录的功能了。举个例子，当我们想查询主键值为100的记录时，具体的查询过程如下：

• 通过目录项，根据二分查找快速定位到主键值为100的记录在目录项3中（因为12 < 100 < 209），其对应的数据页页号为9
• 再根据上述聊到的在单个页中查询记录的方式，即可在页9中查询到主键值为100的记录。

B+树的结构

上述我们聊到构建B+树的条件，其核心是通过使用二分法的方式快速定位到具体的目录项，再通过目录项快速定位到我们所需要的数据页。

我们在聊到给数据页记录建立其对应的目录项时，数据页内的每条记录都会有record_type字段，它的各个取值代表意思如下：

• 0：普通数据记录，即我们插入的数据记录
• 2：Infimum记录，在B+树索引中，Infimum记录位于整个索引的最左边，用于表示没有更小值的情况。
• 3：Supermun记录，在B+树索引中，Supremum记录位于整个索引的最右边，用于表示没有更大值的情况。

你可能会好奇，取值有0、2、3，那取值1是什么意思呢？

我们注意到，在目录项中存储两个字段，分别是最小主键值以及对应的页号，事实上，存放目录项的页与实际存放数据的数据页并无区别，目录项中的两个字段（主键值以及页号）完全可以看作是存储的实际数据，因此，目录项中记录可以称作为目录项记录，即目录页，那InnoDB是如何区别实际数据记录与目录页记录呢，答案就是record_type字段的取值为1来表示目录页记录。

• 0：普通数据记录，即数据页记录
• 1: 目录项记录，即目录页记录
• 2：Infimum记录
• 3：Supermun记录

通过上图可以看到，我们使用页30来存放目录页记录，目录页记录与数据页记录的不同点在于：

• 目录页记录的record_type=1，而数据页记录的record_type=0
• 目录页记录只包含主键值(索引值)和页号，而数据页记录则可以由用户来自定义，可以包含很多列。

除此之外，两者并无实际的区别，在目录页中，同样可以通过二分法来快速定位到目录页记录，再通过目录页记录向下查询到其对应的数据页。

当然，当目录页中的记录过多，一个目录页难以容纳时，我们可以再多分配一个存储目录项的页即可。当同层存在多个目录项时，我们则可以向上再分配更高一级的目录项，即多级目录。

我们可以观察到，这样多级的目录，不就像一颗树的数据结构了呢？其实，这就是InnoDB的B+树结构。

B+树的特点

无论是存放实际数据的数据页，还是存放目录项记录的目录页，都可以把它们放到B+树当中，这些页称为B+树的节点。

其中，存放我们插入的实际数据的记录存放在B+树的最底层节点，这些节点称为叶子节点。其余非叶子节点则用来存放目录项记录。其中B+树最上层的节点称为根节点。

B+树的叶子节点之间是用「双向链表」进行连接，这样的好处是既能向右遍历，也能向左遍历。

2、按物理存储分类

聚簇索引（主键索引）

聚簇索引，又可以称为主键索引，在创建表时，InnoDB会默认为主键创建一棵B+树的主键索引。

聚簇索引的特点在于：

• 使用记录的主键值大小来对记录和页进行排序。

  • 页（包括叶子节点和非叶子节点）内的记录按照主键值的大小进行排序组成单向链表。页内的记录会被划分为若干的组，每个组中主键值最大的记录在页内的偏移量会被当做该组的槽放在页目录中，以便后续可以通过二分法来查找定位到需要查找的记录。
  • 存放实际数据的各个数据页（叶子节点）同样也根据主键大小排成双向链表。
  • 存放目录数据的各个目录页（非叶子节点）可以分为B+树的多个层级，在同一层级的目录页页根据也中存储的主键值大小来排序成一个双向链表。

• B+树的叶子节点存放的是完整的数据记录，即保存了该记录的所有列的值。

包含以上两个特点的B+树称为聚簇索引。

非聚簇索引（二级索引）

不同于聚簇索引，非聚簇索引存储的并不是完整的数据，非聚簇索引的叶子节点存放的是指定的索引列+主键值。非聚簇索引的目录页存储的记录中不再是主键+页号的搭配，而是指定的索引列+页号。

以非主键列的大小为排序规则而建立的B+树需要执行回表操作才可以定位到完整的用户记录，这种B+树也称为二级索引或辅助索引。

同样非聚簇索引的B+树的叶子节点也会按照索引列排序并组成双向链表，同一层级的目录页也会根据索引列的大小来排序组成双向链表。

回表

聚簇索引和非聚簇索引的查询有什么区别？

当使用二级索引进行查询定位到符合条件的记录时，当索引中并未存储我们需要查询的字段时（非聚簇索引值的叶子节点只存储主键值以及指定索引值，可能存在需要查询的字段并未存储在索引B+树中），需要根据二级索引中存储的主键值，回表到主键索引查询到对应的字段才能够返回。

根据该记录中的主键信息回到聚簇索引中查找到完整的用户记录。通过携带主键信息到聚簇索引中重新定位完整的用户记录的过程也成为回表。

在查询时，回表是有代价的，我们知道，在使用二级索引进行范围查询的时候，二级索引对应的主键值的大小是毫无规律的，每读取一条二级索引记录，就需要根据该二级索引记录的主键值到聚簇索引中执行回表操作，如果对应的聚簇索引记录所在的页面不在内存中，就需要将该页面从磁盘加载到内存中由于要读取很多主键值并不连续的聚簇索引记录，而这些聚簇索引记录分布在不同的数据页中，这些数据页的页号也毫无规律，因此会造成大量的随机I/O。

需要执行回表操作的记录越多，使用二级索引进行查询的性能就越低，因此在某些查询场景下，MySQL优化器宁愿使用全表扫描也不使用二级索引，而选择全表扫描，还是二级索引+回表，这就是查询优化器的工作了。

查询优化器会事先针对表中的记录计算一些统计数据，再利用这些统计数据或者访问表中的少量记录来计算回表操作的记录数，如果需要执行回表操作的记录数越多，就越倾向于使用全表扫描，反之则倾向于使用二级索引+回表。

既然回表有一定的代价，那为什么还需要进行回表呢？ 在创建索引时直接就完整的数据记录放入索引的叶子节点不就好了么？

如果完整的数据放入到每个索引建立的B+树的叶子节点中确实可以避免回表，但是取而代之的是需要更多的存储空间，太占地方，相当于每建立一棵B+树都需要将所有的完整数据复制一遍。

3、按字段特性分类

主键索引

主键索引，即聚簇索引，建立在主键字段上的索引，通常在创建表的时候一起创建，一张表最多只有一个主键索引，索引列的值不允许有空值。

在创建表时，创建主键索引的方式如下：

CREATE TABLE table_name (
    ...
    PRIMARY KEY (index_column_1) USING BTREE
);

唯一索引

唯一索引建立在UNIQUE字段上的索引，一张表可以有多个唯一索引，索引列的值必须唯一，但是允许有空值。

在创建表时，创建唯一索引的方式如下：

CREATE TABLE table_name (
    ....
    UNIQUE KEY(index_column_1,index_column_2,...)
);

建表后，如果要创建唯一索引，可以使用这面这条命令：

CREATE UNIQUE INDEX index_name ON table_name(index_column_1,index_column_2,...);

普通索引

普通索引就是建立在普通字段上的索引，既不要求字段为主键，也不要求字段为UNIQUE。

在创建表时，创建普通索引的方式如下：

CREATE TABLE table_name (
    ....
    INDEX(index_column_1,index_column_2,...)
);

建表后，如果要创建普通索引，可以使用这面这条命令：

CREATE INDEX index_name ON table_name(index_column_1,index_column_2,...);

前缀索引

前缀索引是指对字符类型字段的前几个字符建立的索引，而不是在整个字段上建立的索引。前缀索引可以建立在字段类型为char、varchar、binary、varbinary的列上。

使用前缀索引的目的是为了减少索引占用的存储空间，提升查询效率。

CREATE TABLE table_name(
    ....
    INDEX(column_name(length))
);

建表后，如果要创建前缀索引，可以使用这面这条命令：

CREATE INDEX index_name ON table_name(column_name(length));

4、按字段个数分类

单列索引

当创建索引时，指定某一个字段作为索引列，建立在单列上的索引称为单列索引，比如主键索引。

联合索引

联合索引顾名思义，即指定多个字段列来作为索引列，同时以多个列的大小作为排序规则，即同时为多个列建立索引。

例如建立联合索引(a,b)，则在创建的B+树中，记录的排序方式为：

• 先将各个记录和页按照a列进行排序
• 在记录的a列相同的情况下，再采用b列进行排序

在联合索引(a,b)的B+树中，存储的内容为：

• 非叶子节点中，每条目录项记录都有a列、b列、页号3个部分组成。各条记录先按照a列的值进行排序，如果记录的a列相同，则按照b列的值进行排序
• 叶子节点中，数据页记录由a列、b列和主键列三部分组成；

使用联合索引时，存在最左匹配原则，即按照最左优先的方式进行索引的匹配。

举个例子：

当我们创建联合索引（name, age）时，如果你要查的是所有名字第一个字是"张"的人，你的SQL语句的条件是where name like '张%'。这时这条SQL能够用上这个联合索引。

从上述的例子可以看出，在对name字段进行单列条件查询时，同样能够使用上该联合索引，即联合索引（name, age）可以等效于单列索引（name）。

因此，在建立联合索引的时候，如何安排索引内的字段顺序呢？

评估标准是索引的复用能力。如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的。例如上述的例子，通过联合索引（name，age）的顺序，可以让我们少维护一个单列索引（name）。当然age。

三、索引的优缺点

在了解了B+树的索引结构后，我们知道恰当的索引使用可以为我们带来极大的查询效率，提高性能。但是索引也并非没有缺点，了解好索引的优缺点，选择使用索引时，需要综合考虑索引的优点和缺点，才能让我们在实际使用索引的过程中得心应手。

1、优点

• 提高数据检索的效率，降低数据库的I/O成本，将随机I/O转变为顺序I/O，这是创建索引最主要的原因；

• 通过创建唯一索引，可以保证数据库表中每一行数据的唯一性；

• 由于索引中记录的存储顺序，在使用分组和排序子句进行数据查询时，可以显著减少查询中分组和排序的时间，即帮助服务器避免排序和临时表，降低了CPU的消耗。

• 可以加速表和表之间的连接，即对于有依赖关系的子表和父表联合查询时，可以提高多表查询的速度。

2、缺点

创建索引和维护索引要耗费时间 ，并且随着数据量的增加，所耗费的时间也会增加。

• 索引需要占磁盘空间

每个索引在创建后，需要占一定的物理空间存储在磁盘上，因为每建立一个索引，都要为它建立一棵B+树。每一棵B+树的每一个节点都是一个数据页。

一个数据页默认占用 16KB 的存储空间，而一棵很大的B+树由许多数据页组成，这将会占用很大的一片存储空间。

如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。

• 虽然索引大大提高了查询速度，同时却会降低更新表的速度

当对表中的数据进行增加、删除和修改的时候，索引也要动态地维护，即都需要修改各个B+树索引，这样就降低了数据的维护速度。

增删改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行页面分裂、页面回收等操作，以维护节点和记录的排序。

• 影响优化器执行效率

在执行查询语句前，首先要生成一个执行计划。

一般情况下，一条查询语句在执行过程中最多使用一个二级索引，在生成执行计划时需要计算使用不同索引执行查询时所需的成本，最后选取成本最低的那个索引执行查询，如果此时建了太多的索引，可能会导致成本分析过程耗时太多，从而影响查询语句的执行性能。

四、索引使用场景

索引最大的好处是提高查询速度，但是索引使用不当则会出现上述描述的缺点所带来的影响。因此，索引不是万能钥匙，它也是根据场景来使用的。

那么在什么情况下，我们该使用索引呢？

1、适用索引的场景

• 字段需要唯一性限制

当业务中某个字段需要唯一性限制时，除了在业务逻辑层面校验，最后一道防线则是通过唯一索引来限制字段唯一。

• 经常用于WHERE查询条件的字段

对经常用于WHERE查询条件的字段建立索引，能够提高整个表的查询速度，尤其是在数据量大的情况下，创建索引就可以大幅提升数据查询的效率。

• 经常用于GROUP BY和ORDER BY的字段

对于经常用于GROUP BY和ORDER BY的字段，建立索引，利用索引其按索引字段值顺序存储数据的特性，减少排序与临时表带来的损耗。

• 对DISTINCT字段创建索引

有时候需要对某个字段进行去重，使用DISTINCT，那么对这个字段创建索引，也会提升查询效率。因为当去重字段创建了索引后是按照顺序递增的，所以在去重的时候会快很多。

• 在多个字段都要创建索引的情况下，联合索引优于单值索引

2、不适用索引的场景

• WHERE条件、GROUP BY条件、ORDER BY条件中用不到的字段

索引的价值是快速定位，如果起不到定位的字段通常是不需要创建索引的，因为索引是会占用物理空间的。

• 表数据太少的时候，可以考虑不需要创建索引

• 经常更新的字段不用创建索引

经常更新的字段不用创建索引，比如不要用户余额建立索引，因为索引字段频繁修改，由于要维护 B+Tree的有序性，那么就需要频繁的重建索引，这个过程是会影响数据库性能的。