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

周梦康
  • 8.9k

以 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 的顺序对数据排序返回?

回复
阅读 4.5k
2 个回答

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

user_mOpH8dAy
  • 2
新手上路,请多包涵

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

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏