mysql 非主键做范围查找实现原理的一点困惑

Question

以 innodb 为例。

下面很多图都截图来自于 http://blog.codinglabs.org/ar...

CREATE TABLE `test` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `age` int(11) unsigned NOT NULL,
  `name` varchar(30) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  KEY `idx_name` (`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

插入下列数据

mysql> select * from test;
+----+-----+-------+
| id | age | name  |
+----+-----+-------+
| 15 |  34 | Bob   |
| 18 |  77 | Alice |
| 20 |   5 | Jim   |
| 30 |  91 | Eric  |
| 49 |  22 | Tom   |
| 50 |  89 | Rose  |
+----+-----+-------+
6 rows in set (0.00 sec)

因为主键是单调递增的，所以这里会以主键聚集，如图

这样如果我做范围查找

mysql> explain select * from test where id>16\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
   partitions: NULL
         type: range
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 5
     filtered: 100.00
        Extra: Using where
1 row in set, 1 warning (0.00 sec)

查找的过程比较清晰，查询到 B+树最左端的叶子节点，然后 mysql 对 B+ 树做了优化，各个叶子节点之间多了指针串连。

因为 Innodb 的特性，数据和聚簇索引都在一起了，就是上图的截图

当使用 name 做精确查找的时候，比较清晰，根据索引找到主键，然后再通过主键再去查询。

mysql> explain select * from test where name='Bob'\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
   partitions: NULL
         type: ref
possible_keys: idx_name
          key: idx_name
      key_len: 92
          ref: const
         rows: 1
     filtered: 100.00
        Extra: NULL
1 row in set, 1 warning (0.00 sec)

新增一个索引

ALTER TABLE `test` ADD INDEX `idx_age` (`age`);

mysql> explain select * from test FORCE INDEX(idx_age) where age>20\G;
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
   partitions: NULL
         type: range
possible_keys: idx_age
          key: idx_age
      key_len: 4
          ref: NULL
         rows: 5
     filtered: 100.00
        Extra: Using index condition
1 row in set, 1 warning (0.00 sec)

我的困惑，根据idx_age索引找到了各个叶子页的数据，但是叶子页上只是有对应主键的指针，后面根据idx_age所有查询的主键，再去聚簇索引中查询的过程是怎样的。

• 假如对应的主键的数据都不在一页上，那是不是有多少行，就要多少次从聚簇索引顶端到叶子页的查询；

• 还是先查询出所有的主键了，先根据主键排序，然后查询到最小的主键，然后依次往后找其他主键数据，最后再按照 age 的顺序对数据排序返回？

Answer 1

根据个人理解以及看书是拿到主键id，然后根据id去逐条回表随机访问。一般的索引建立，都会带上主键。
比如你上面的age，其实你的索引是(age,id)。按照你的理解来说，既然都查询到了所有的主键，然后排序花费nLog(n)的复杂度，接着还是逐条回表随机访问，有啥区别？

Answer 2

我想是多个id就多次从根节点开始先序遍历，如果先排好序时间复杂度不说，再对聚簇索引的叶子节点进行遍历，那就相当于只扫描叶子节点，从eq_ref退化到了range查找