MySQL索引是怎么支撑千万级表的快速查找？

前言

在 MySQL 官方提到，改善操作性能的最佳方法 [SELECT](https://dev.mysql.com/doc/refman/5.7/en/select.html)在查询中测试的一个或多个列上创建索引。索引条目的作用类似于指向表行的指针，从而使查询可以快速确定哪些行与WHERE子句中的条件匹配，并检索这些行的其他列值。所有MySQL数据类型都可以建立索引。

尽管可能会为查询中使用的每个可能的列创建索引，但不必要的索引会浪费空间和时间，使MySQL难以确定要使用的索引。索引还会增加插入，更新和删除的成本，因为必须更新每个索引。您必须找到适当的平衡，才能使用最佳索引集来实现快速查询。

那么，索引到底是什么？透过现象看本质：

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。索引的本质：索引是数据结构。

另外，阿里巴巴《Java 开发手册》提出单表行数超过 500 万行或者单表容量超过 2GB，才推荐进行分库分表。对此，有阿里的黄金铁律支撑，所以，很多人设计大数据存储时，多会以此为标准，进行分表操作。

以及，阿里巴巴《Java 开发手册》补充到：如果预计三年后的数据量根本达不到这个级别，请不要在创建表时就分库分表。

为了更深入理解索引的本质，这里我们先了解一下磁盘相关知识。

外存储器-磁盘

计算机一般有两种存储的方式：内存储器(main memory)和外存储器(external memory)

• 内存:读写速度非常快，但是容量很小，而且造价非常贵，在不通电的情况下会数据会丢失，不能长期存储数据；
• 外存：磁盘是相对常见的外存储设备，它是以存取时间变化不大为特征的。可以直接存取任何字符组，且容量大、速度较其它外存设备更快。

磁盘的构造

磁盘是一个扁平的圆盘(与电唱机的唱片类似)。盘面上有许多称为磁道的圆圈，数据就记录在这些磁道上。磁盘可以是单片的，也可以是由若干盘片组成的盘组，每一盘片上有两个面。

红黑树

定义：

• 性质1. 节点是红色或黑色。
• 性质2. 根节点是黑色。
• 性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

缺点：数据量大会导致树层数比较多，这样就会造成查找数据慢。

Hash数据结构

定义：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 对目标值进行hash运算得到hash值和数据磁盘指针地址保存到hash表，这样就达到快速定位数据位置。

缺点：精确查找十分快速，但范围查找就碰壁了。

BTree

定义：

• 一个节点可以存储多个数据，这样可以避免黑红树的缺点，树的层数很变小；
• 叶节点具有相同的深度，叶节点的指针为空；
• 所有索引元素不重复；
• 节点中的数据索引从左到右递增排列。

缺点：节点里面数组数据：每个数据的结构=索引数据+数据记录（即叶子节点存储键值和数据记录）。

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。

模拟查找关键字29的过程：

1. 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2. 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4. 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
5. 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
6. 在磁盘块8中的关键字列表中找到关键字29。

分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的关键字是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B-Tree查找效率的决定因素。B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

B+Tree

定义：B+Tree是在B-Tree基础上的一种优化。节点里面数组数据：每个数据只存储键信息，这样不存数据可以腾出空间放更多的键信息，让树层数越小

• 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能

将上一节中的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为 INT（占用4个字节）或 BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值。（因为是估值，为方便计算，这里的K取值为〖10〗^{3）。也就是说一个深度为3的B+Tree索引可以维护10}3 * 10^3 * 10^3 = 10亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2_{4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1}3次磁盘I/O操作。

数据库中的B+Tree索引可以分为聚集索引（clustered index）和 辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。

辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

查看mysql文件页大小（16K）：SHOW GLOBAL STATUS like 'Innodb_page_size’;

MySQL存储引擎

什么是存储引擎？

数据库存储引擎是数据库底层软件组件，数据库管理系统使用数据引擎进行创建、查询、更新和删除数据操作。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能，使用不同的存储引擎还可以获得特定的功能。

现在许多数据库管理系统都支持多种不同的存储引擎。MySQL 的核心就是存储引擎。

• InnoDB 事务型数据库的首选引擎，支持事务安全表（ACID），支持行锁定和外键。MySQL 5.5.5 之后，InnoDB 作为默认存储引擎。
• MyISAM 是基于 ISAM 的存储引擎，并对其进行扩展，是在 Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM 拥有较高的插入、查询速度，但不支持事务。
• MEMORY 存储引擎将表中的数据存储到内存中，为查询和引用其他数据提供快速访问。

MySQL 5.7 支持的存储引擎

MySQL 支持多种类型的数据库引擎，可分别根据各个引擎的功能和特性为不同的数据库处理任务提供各自不同的适应性和灵活性。在 MySQL 中，可以利用 SHOW ENGINES 语句来显示可用的数据库引擎和默认引擎。

MySQL 提供了多个不同的存储引擎，包括处理事务安全表的引擎和处理非事务安全表的引擎。在 MySQL 中，不需要在整个服务器中使用同一种存储引擎，针对具体的要求，可以对每一个表使用不同的存储引擎。

MySQL 5.7 支持的存储引擎有 InnoDB、MyISAM、Memory、Merge、Archive、Federated、CSV、BLACKHOLE 等。

可以使用SHOW ENGINES语句查看系统所支持的引擎类型，结果如图所示。

如何选择 MySQL 存储引擎

不同的存储引擎都有各自的特点，以适应不同的需求，如表所示。为了做出选择，首先要考虑每一个存储引擎提供了哪些不同的功能。

功能	MylSAM	MEMORY	InnoDB	Archive
存储限制	256TB	RAM	64TB	None
支持事务	No	No	Yes	No
支持全文索引	Yes	No	No	No
支持树索引	Yes	Yes	Yes	No
支持哈希索引	No	Yes	No	No
支持数据缓存	No	N/A	Yes	No
支持外键	No	No	Yes	No

可以根据以下的原则来选择 MySQL 存储引擎：

• 如果要提供提交、回滚和恢复的事务安全（ACID 兼容）能力，并要求实现并发控制，InnoDB 是一个很好的选择。
• 如果数据表主要用来插入和查询记录，则 MyISAM 引擎提供较高的处理效率。
• 如果只是临时存放数据，数据量不大，并且不需要较高的数据安全性，可以选择将数据保存在内存的 MEMORY 引擎中，MySQL 中使用该引擎作为临时表，存放查询的中间结果。
• 如果只有 INSERT 和 SELECT 操作，可以选择Archive 引擎，Archive 存储引擎支持高并发的插入操作，但是本身并不是事务安全的。Archive 存储引擎非常适合存储归档数据，如记录日志信息可以使用 Archive 引擎。

提示：使用哪一种引擎要根据需要灵活选择，一个数据库中多个表可以使用不同的引擎以满足各种性能和实际需求。使用合适的存储引擎将会提高整个数据库的性能。

使用下面的语句可以修改数据库临时的默认存储引擎
SET default_storage_engine=< 存储引擎名 >
注意：将 MySQL 数据库的临时默认存储引擎修改为 其他的存储引擎时 ，但是当再次重启客户端时，默认存储引擎仍然是 InnoDB。

MyISAM存储引擎

数据存储形式

MyISAM采用的是索引与数据分离的形式，将数据保存在三个文件中.frm 、.MYD、.MYI。

• .frm : 存储表结构
• .MYD ： 存储表数据
• .MYI ：存储表索引

锁的粒度

MyISAM不支持行锁，所以读取时对表加上共享锁，在写入是对表加上排他锁。由于是对整张表加锁，相比InnoDB，在并发写入时效率很低。

事务

MyISAM不支持事务。

数据的存储特点

MyISAM是基于非聚簇索引进行存储的。

索引实现

MyISAM索引文件和数据文件是分离的(非聚集)

其他

MyISAM提供了大量的特性，包括全文索引，压缩，空间函数，延迟更新索引键等。

• 进行压缩后的表是不能进行修改的，但是压缩表可以极大减少磁盘占用空间，因此也可以减少磁盘IO，从而提供查询性能。

• 全文索引，是一种基于分词创建的索引，可以支持复杂的查询。

• 延迟更新索引键，不会将更新的索引数据立即写入到磁盘，而是会写到内存中的缓冲区中，只有在清除缓冲区时候才会将对应的索引写入磁盘，这种方式大大提升了写入性能。

InnoDB存储引擎

数据存储形式

使用InnoDB时，会将数据表分为.frm 和 .ibd 两个文件进行存储。

• .frm : 存储表结构
• .ibd : 存储表数据和索引

innodb的所有数据文件（后缀为ibd的文件），他的大小始终都是16384（16k）的整数倍。

锁的粒度

InnoDB采用MVCC(多版本并发控制)来支持高并发，InnoDB实现了四个隔离级别，默认级别是REPETABLE READ，并通过间隙锁策略防止幻读的出现。它的锁粒度是行锁。【MVCC在稍后会进行介绍】

事务

InnoDB是典型的事务型存储引擎，并且通过一些机制和工具，支持真正的热备份。

数据的存储特点

InnoDB表是基于聚簇索引建立的，聚簇索引对主键的查询有很高的性能，不过他的二级索引（非主键索引）必须包含主键列，索引其他的索引会很大。

索引实现

InnoDB索引实现(聚簇)

• 表数据文件本身就是按B+Tree组织的一个索引结构文件
• 聚簇索引-叶节点包含了完整的数据记录
• 为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
• 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

联合索引

联合索引的底层存储结构长什么样？

比较相等时，先比较第一列的值，如果相等，再继续比较第二列，以此类推。

最左前缀原理

使用联合索引时，索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引（a,b,c），mysql会从最左边的列优先匹配，如果最左边的带头大哥没有使用到，在未使用覆盖索引的情况下，就只能全表扫描。
联合底层数据结构思考，mysql会优先以联合索引第一列匹配，此后才会匹配下一列，如果不指定第一列匹配的值，也就无法得知下一步查询哪个节点。
另外还有一种情况，如果遇到 > < between等这样的范围查询，那B+树中也就无法对下一列进行等值匹配了。

浅谈MVCC

MySQL大多数事务型存储引擎实现的都不是简单的行锁。基于提升并发性能的考虑，他们一般都同时实现了多版本并发控制(MVCC)。

可以认为MVCC是行级锁的一个变种，它能在大多数情况下避免加锁操作，因此开销更低。无论怎样实现，它们大都实现了非阻塞的读操作，写操作也只锁定制定的行。

MVCC是通过保存数据在某一个时间点的快照来实现的，也就是说无论事务执行多久，每个事务看到的数据都是一致的。InnoDB的MVCC，是通过在每行记录后面保存两个隐藏的列来实现，这两个列一个保存了行的创建时间，一个保存了行的过期时间(或删除时间)，当然，并非存储的是时间，而是系统版本号。每开启一个事务，版本号都会递增，事务开始时刻的系统版本号会作为事务的版本号。

id	name	创建时间（行版本号）	删除时间(删除版本号)
1	Mary	1	null
2	Jann	1	null

以InnoDB存储引擎的的REPEATABLE READ隔离级别来说：

SELECT

• 只查询创建时间版本号小于当前事务版本号的数据行（保证事务读取的行要么在事务开始之前就存在，要么是事务本身插入的行）
• 行的删除版本号要么未定义，要么大于当前事务版本号，这样可以确保事务读取到的行，在开始事务之前未被删除

只有复合上诉两个条件的记录才会作为结果返回

INSERT

为插入的数据保存当前系统版本号作为行版本号

DELETE

保存当前系统版本号作为删除行版本号

UPDATE

插入一行数据，并将当前系统版本号赋予行版本号；同时保存当前系统版本号到原来的行作为删除版本号。

注：MVCC只在REPEATABLE和READ COMMITTED两个隔离级别下才能正常工作。

问题总结

InnoDB一棵B+树可以存放多少行数据？

这个问题的简单回答是：约2千万。为什么是这么多呢？因为这是可以算出来的，要搞清楚这个问题，我们先从InnoDB索引数据结构、数据组织方式说起。

我们都知道计算机在存储数据的时候，有最小存储单元，这就好比我们今天进行现金的流通最小单位是一毛。在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）他的最小单元是块，一个块的大小是4k，而对于我们的InnoDB存储引擎也有自己的最小储存单元——页（Page），一个页的大小是16K。

下面几张图可以帮你理解最小存储单元：

文件系统中一个文件大小只有1个字节，但不得不占磁盘上4KB的空间。

innodb的所有数据文件（后缀为ibd的文件），他的大小始终都是16384（16k）的整数倍。

磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。

在MySQL中我们的InnoDB页的大小默认是16k，当然也可以通过参数设置：

mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name    | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)

数据表中的数据都是存储在页中的，所以一个页中能存储多少行数据呢？假设一行数据的大小是1k，那么一个页可以存放16行这样的数据。

如果数据库只按这样的方式存储，那么如何查找数据就成为一个问题，因为我们不知道要查找的数据存在哪个页中，也不可能把所有的页遍历一遍，那样太慢了。所以人们想了一个办法，用B+树的方式组织这些数据。如图所示：

我们先将数据记录按主键进行排序，分别存放在不同的页中（为了便于理解我们这里一个页中只存放3条记录，实际情况可以存放很多），除了存放数据的页以外，还有存放键值+指针的页，如图中page number=3的页，该页存放键值和指向数据页的指针，这样的页由N个键值+指针组成。当然它也是排好序的。这样的数据组织形式，我们称为索引组织表。现在来看下，要查找一条数据，怎么查？

如select * from user where id=5;

这里id是主键,我们通过这棵B+树来查找，首先找到根页，你怎么知道user表的根页在哪呢？其实每张表的根页位置在表空间文件中是固定的，即page number=3的页（这点我们下文还会进一步证明），找到根页后通过二分查找法，定位到id=5的数据应该在指针P5指向的页中，那么进一步去page number=5的页中查找，同样通过二分查询法即可找到id=5的记录.

现在我们清楚了InnoDB中主键索引B+树是如何组织数据、查询数据的，总结一下：

1. InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存放键值+指针，在B+树中叶子节点存放数据，非叶子节点存放键值+指针。
2. 索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而在去数据页中查找到需要的数据；

那么回到我们开始的问题，通常一棵B+树可以存放多少行数据？

这里我们先假设B+树高为2，即存在一个根节点和若干个叶子节点，那么这棵B+树的存放总记录数为：根节点指针数单个叶子节点记录行数*。

上文我们已经说明单个叶子节点（页）中的记录数=16K/1K=16。（这里假设一行记录的数据大小为1k，实际上现在很多互联网业务数据记录大小通常就是1K左右）。

那么现在我们需要计算出非叶子节点能存放多少指针，其实这也很好算，我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节，我们一个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。那么可以算出一棵高度为2的B+树，能存放1170*16=18720条这样的数据记录。

根据同样的原理我们可以算出一个高度为3的B+树可以存放：1170*1170*16=21902400条这样的记录。所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

怎么得到InnoDB主键索引B+树的高度？

上面我们通过推断得出B+树的高度通常是1-3，下面我们从另外一个侧面证明这个结论。在InnoDB的表空间文件中，约定page number为3的代表主键索引的根页，而在根页偏移量为64的地方存放了该B+树的page level。如果page level为1，树高为2，page level为2，则树高为3。即B+树的高度=page level+1；下面我们将从实际环境中尝试找到这个page level。

在实际操作之前，你可以通过InnoDB元数据表确认主键索引根页的page number为3，你也可以从《InnoDB存储引擎》这本书中得到确认。

SELECT
b.name, a.name, index_id, type, a.space, a.PAGE_NO
FROM
information_schema.INNODB_SYS_INDEXES a,
information_schema.INNODB_SYS_TABLES b
WHERE
a.table_id = b.table_id AND a.space <> 0;

执行结果：

可以看出数据库approval_db下的sys_config表、sys_config表主键索引根页的page number均为3，而其他的二级索引page number为4。

聚簇索引和非聚簇索引的区别

• 聚簇索引：将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据
• 非聚簇索引：将数据与索引分开存储，索引结构的叶子节点指向了数据对应的位置

为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？

1. 如果设置了主键，那么InnoDB会选择主键作为聚集索引，如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。
2. 如果表使用自增主键

那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，主键的顺序按照数据记录的插入顺序排列，自动有序。当一页写满，就会自动开辟一个新的页

3. 如果使用非自增主键（如果身份证号或学号等）

由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

MySQL为什么用整型自增作为索引比较好。而UUID作为索引效率比较低？

聚簇索引的数据的物理存放顺序与索引顺序是一致的，即：只要索引是相邻的，那么对应的数据一定也是相邻地存放在磁盘上的。如果主键不是自增id，那么可以想象，它会干些什么，不断地调整数据的物理地址、分页，当然也有其他一些措施来减少这些操作，但却无法彻底避免。但，如果是自增的，那就简单了，它只需要一页一页地写，索引结构相对紧凑，磁盘碎片少，效率也高。

• 索引存储在磁盘，而且树的每个节点分配的空间有大小。整型占空间比较小，这样可以存放多个键值。反之然后UUID占空间比较大。
• 整型比较方便，UUID比较需要先转成ASCII在进行比较。

为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

1. 减少了出现行移动或者数据页分裂时二级索引的维护工作（当数据需要更新的时候，二级索引不需要修改，只需要修改聚簇索引，一个表只能有一个聚簇索引，其他的都是二级索引，这样只需要修改聚簇索引就可以了，不需要重新构建二级索引）；
2. 聚簇索引也称为主键索引，其索引树的叶子节点中存的是整行数据，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引。因为索引（目录）只能按照一种方法进行排序；
3. 非聚簇索引（普通索引）的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

部分图片来源于网络，版权归原作者，侵删。