Mysql实现排序有两种方法

  • 通过索引生成有效的排序
  • 通过文件排序

InnoDB 索引实现

InnoDB存储引擎以B+树作为索引的底层实现，B+树的叶子节点存储着所有数据页而内部节点不存放数据信息，这棵树的叶点data 域保存了完整的数据记录。这个索引的 key 是数据表的主键,因此 InnoDB 表数据文件本身就是主索引。并且所有叶子节点形成一个(双向)链表。MySQL会直接遍历引的叶子节点链表，不需要进行额外的排序操作。这就是用索引扫描来排序。

索引扫描排序执行过程分析

对于一张表的查询 一次只能使用一个索引也就是说当WHERE子句与ORDER BY子句要使用的索引不一致时，MySQL只能使用其中一个索引(B+树)。也就是说，一个既有WHERE又有ORDER BY的SQL中，使用索引有三个可能的场景:

  • 只用于WHERE子句 筛选出满足条件的数据
  • 只用于ORDER BY子句 返回排序后的结果
  • 既用于WHERE又用于ORDER BY，筛选出满足条件的数据并返回排序后的结果

举个例子：我们创建一张user_account表 记录每一笔充值记录的userid(用户id)、money(用户充值金额)、create_time(充值时间)，主键是自增id：

CREATE TABLE `user_recharge` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `user_id` int(11) NOT NULL,
  `money` float NOT NULL,
  `create_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`id`),
  KEY `user_id` (`user_id`),
  KEY `create_time` (`create_time`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

插入100W条测试数据

SELECT COUNT(*) FROM user_recharge;
+----------+
| COUNT(*) |
+----------+
|  1000000 |
+----------+

SELECT * FROM order_detail LIMIT 5;
+----+--------+-------+---------------------+
| id | userid | money | create_time         |
+----+--------+-------+---------------------+
|  1 | 1000001 |  3000 | 2019-01-01 07:40:38 |
|  2 | 1000002 |  1235 | 2019-01-01 07:40:42 |
|  3 | 1000003 |  8909 | 2019-01-01 07:40:46 |
|  4 | 1000004 |  4307 | 2019-01-01 07:40:55 |
|  5 | 1000005 |  1912 | 2019-01-01 07:40:58 |
+----+--------+-------+---------------------+

场景一 索引只用于WHERE子句

我们现在取一条用户的查询信息，例如user_id = 1000001,并以充值时间排序，分析一下SQL

EXPLAIN SELECT * FROM user_recharge WHERE user_id = 1000001 ORDER BY create_time;

+----+-------------+---------------+------+---------------+---------+---------+-------+------+-----------------------------+
| id | select_type | table         | type | possible_keys | key     | key_len | ref   | rows | Extra                       |
+----+-------------+---------------+------+---------------+---------+---------+-------+------+-----------------------------+
|  1 | SIMPLE      | user_recharge | ref  | user_id       | user_id | 4       | const |    1 | Using where; Using filesort |
+----+-------------+---------------+------+---------------+---------+---------+-------+------+-----------------------------+
1 row in set (0.00 sec)

整体执行流程如下

  • 先通过user_id索引找到所有满足WHERE条件的主键id（注:从b+树根节点往下找叶子节点，时间复杂度为O(logN))
  • 再根据这些主键id去主键索引(聚簇索引))找到这几行的数据，生成一张临时表放入排序缓冲区（时间复杂度为O(M*logN)，M是临时表缓冲区里的行数）
  • 对临时表缓冲区里的数据进行排序，时间复杂度为O(MlogM),M为缓冲区内的行数

场景二 索引只用于Order By

我们可以继续使用上文的SQL，通过FORCE INDEX子句强制Optimizer使用ORDER BY子句的索引create_time:

EXPLAIN SELECT * FROM user_recharge  FORCE INDEX (create_time) WHERE user_id = 1000001 ORDER BY create_time;

+----+-------------+---------------+-------+---------------+-------------+---------+------+-----------+-------------+
| id | select_type | table         | type  | possible_keys | key         | key_len | ref  |    rows   | Extra       |
+----+-------------+---------------+-------+---------------+-------------+---------+------+-----------+-------------+
|  1 | SIMPLE      | user_recharge | index | NULL          | create_time | 4       | NULL |   990900 | Using where |
+----+-------------+---------------+-------+---------------+-------------+---------+------+-----------+-------------+
1 row in set (0.00 sec)

可以看到Extra字段里的Using filesort已经没了，但是扫过的rows大概有990900行(准确的值应该是1000000行，InnoDB这一列只是估值)。这是因为索引用于ORDER BY子句时，会直接遍历该索引的叶子节点链表，而不像第一种场景那样从B+树的根节点出发 往下查找。执行流程如下:

  • 从create_time索引的第一个叶子节点出发，按顺序扫描所有叶子节点
  • 根据每个叶子节点记录的主键id去主键索引(聚簇索引))找到真实的行数据，判断行数据是否满足WHERE子句的user_id条件，若满足，则取出并返回 整个时间复杂度是O(M*logN)，M是主键id的总数，N是聚簇索引叶子节点的个数(数据页的个数)

本例中M的值为1000000，所以整个执行过程比第一种场景花了更多时间，同一台机器上耗时1.34 sec 上述两个例子恰好说明了另一个道理：在某些场景下使用filesort比不使用filesort 效率更高。

场景三 索引WHERE 又用于Order By

第三种情况发生在WHERE子句与ORDER BY子句能使用相同的索引时（如: WHERE userid > xxx ORDER BY userid），这样就能省去第二种情况的回表查询操作了。