《高性能MySQL》读后感——B-Tree索引

当人们谈论索引的时候，如果没有特别指明类型，多半说的是B-Tree索引，它使用B-Tree数据结构来存储数据。实际上很多存储引擎使用的是B+Tree，即每个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历。
常用的存储引擎以不同的方式使用B-Tree索引，性能也各有不同，各有优劣。MyISAM和InnoDB都使用B+Tree。例如：

MyISAM使用前缀压缩技术使得索引更小，InnoDB则按照原数据格式进行存储。
MyISAM索引通过数据的物理位置引用被索引的行，InnoDB则根据主键引用被索引的行。

B-Tree通常意味着所有的值都是按顺序存储的，井且每一个叶子页到根的距离相同。下面图1、图2展示了B-Tree索引的抽象表示，大致反映了InnoDB索引是如何工作的。MyISAM使用的结构有所不同，但基本思想是类似的。

图1 建立在B-Tree结构（技术上是B+Tree）上的索引

图2 建立在B-Tree结构（技术上是B+Tree）上的索引

B-Tree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点（图示并未画出）开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。
叶子节点比较特别，它们的指针指向的是被索引的数据，而不是其他的节点页（不同引擎的“指针”类型不同）。图1和图2中仅绘制了一个节点和其对应的叶子节点，其实在根节点和叶子节点之间可能有很多层节点页。树的深度和表的大小直接相关。
B-Tree对索引列是顺序组织存储的，所以很适合查找范围数据。例如，在一个基于文本域的索引树上，按字母顺序传递连续的值进行查找是非常合适的，所以像“找出所有以I到K开头的名字”这样的查找效率会非常高。
假设有如下数据表：

CREATE TABLE `People` (
  `last_name` varchar(32) NOT NULL,
  `first_name` varchar(32) NOT NULL,
  `dob` date NOT NULL,
  `gender` enum('m','f') NOT NULL,
  KEY `last_name` (`last_name`,`first_name`,`dob`)
)

对于表中的每一行数据，索引中包含了last_name、first_name和dob列的值，下图显示了该索引是如何组织数据的存储的。

建立在B-Tree结构（技术上是B+Tree）索引树中的部分条目示例

请注意，索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。看一下最后两个条目，两个人的姓和名都一样，则根据他们的出生日期来排列顺序。B-Tree索引适用于全键值、键值范围或键前缀查找。其中键前缀查找只适用于根据最左前缀的查找。

全值匹配

全值匹配指的是和索引中的所有列进行匹配，例如前面提到的索引可用于查找姓名为Cuba Allen、出生于1960-01-01的人。

匹配最左前缀

前面提到的索引可用于查找所有姓为Allen的人，即只使用索引的第一列。匹配列前缀也可以只匹配第一列值的开头部分。例如前面提到的索引可用于查找所有以A开头的姓的人。

mysql> explain select * from People where last_name = 'Allen';
+----+-------------+--------+------+---------------+-----------+---------+-------+------+-------------+
| id | select_type | table  | type | possible_keys | key       | key_len | ref   | rows | Extra       |
+----+-------------+--------+------+---------------+-----------+---------+-------+------+-------------+
|  1 | SIMPLE      | People | ref  | last_name     | last_name | 98      | const |    1 | Using where |
+----+-------------+--------+------+---------------+-----------+---------+-------+------+-------------+

mysql> explain select * from People where last_name like 'A%';
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key       | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
|  1 | SIMPLE      | People | range | last_name     | last_name | 98      | NULL |    1 | Using where |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+

如下例子，匹配列前缀不是第一列值的开头部分，不会用到索引。

mysql> explain select * from People where last_name like '%ll%';
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | People | ALL  | NULL          | NULL | NULL    | NULL |    4 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+

如下例子，当使用中间列first_name查询时，不会用到索引。

mysql> explain select * from People where first_name = 'Cuba';
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | People | ALL  | NULL          | NULL | NULL    | NULL |    4 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+

匹配范围值

例如前面提到的索引可用于查找姓在Allen和Barrymore之间的人，这里也只使用了索引的第一列。其实也是匹配最左前缀。

精确匹配到某一列并范围匹配另外一列

前面提到的索引也可用于查找所有姓为Allen，并且名字是字母C开头（比如Cuba、Carl等）的人。即第一列last_name全匹配，第二列first_name范围匹配。

mysql> explain select * from People where last_name = 'Allen' and first_name like 'C%';
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key       | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
|  1 | SIMPLE      | People | range | last_name     | last_name | 196     | NULL |    1 | Using where |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+

只访问索引的查询

B-Tree通常可以支持“只访问索引的查询”，即查询只需要访问索引，而无须访问数据行。用Explain查看Extra可以看到Using index，如下所示。

mysql> explain select dob from People where last_name = "Allen" and first_name = 'Cu%';
+----+-------------+--------+------+---------------+-----------+---------+-------------+------+--------------------------+
| id | select_type | table  | type | possible_keys | key       | key_len | ref         | rows | Extra                    |
+----+-------------+--------+------+---------------+-----------+---------+-------------+------+--------------------------+
|  1 | SIMPLE      | People | ref  | last_name     | last_name | 196     | const,const |    1 | Using where; Using index |
+----+-------------+--------+------+---------------+-----------+---------+-------------+------+--------------------------+

因为索引树中的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的ORDER BY操作（按顺序查找）。如果B-Tree可以按照某种方式查找到值，那么也可以按照这种方式用于排序。所以，如果ORDER BY子句满足前面列出的几种查询类型，则这个索引也可以满足对应的排序需求。
以第一列last_name ORDER BY，可以使用索引，如下所示。

mysql> explain select dob from People order by last_name;
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key       | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+
|  1 | SIMPLE      | People | index | NULL          | last_name | 199     | NULL |    4 | Using index |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-------------+

以第一列first_name ORDER BY，出现Using filesort，重新到数据行获取first_name排序，如下所示。

mysql> explain select dob from People order by first_name;
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------------+
| id | select_type | table  | type  | possible_keys | key       | key_len | ref  | rows | Extra                       |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------------+
|  1 | SIMPLE      | People | index | NULL          | last_name | 199     | NULL |    4 | Using index; Using filesort |
+----+-------------+--------+-------+---------------+-----------+---------+------+------+-----------------------------+

下面是一些关于B-Tree索引的限制：

如果不是按照索引的最左列开始查找，则无法使用索引。例如上面例子中的索引不能用于查找名字为Bill的人，也无法查找某个特定生日的人，因为这两列都不是最左数据列。类似地，也无法查找姓氏以某个字母结尾的人。
不能跳过索引中的列。也就是说，前面所述的索引无法用于查找姓为Smith并且在某个特定日期出生的人。如果不指定名（first_name），则MySQL只能使用索引的第一列。
如果查询中有某个列的范围(like between > <都算范围查询)查询，则其右边所有列都无法使用索引优化查找。例如有查询WHERE last_name='Smith’AND first_name like '%J%'AND dob＝’1976-12-23'，这个查询只能使用索引的前两列，因为这里的like是一个范围条件（但是服务器可以把其余列用于其他目的），并且first_name不是最左开始查找，索引也不能用first_name。如果范围查询列值的数量有限，那么可以通过使用多个等于条件来代替范围条件。

所以前面提到的索引列的顺序是多么的重要：这些限制都和索引列的顺序有关。在优化性能的时候，可能需要使用相同的列但顺序不同的索引来满足不同类型的查询需求。

索引的优点

最常见的B-Tree索引，按照顺序存储数据，所以MySQL可以用来做ORDER BY和GROUP BY操作。因为数据是有序的，所以B-Tree也就会将相关的列值存储在一起。最后，因为索引中存储了实际的列值，所以某些查询只使用索引就能够完成全部查询。总结下来索引有如下三个优点：

索引大大减少了服务器需要扫描的数据量。
索引可以帮助服务器避免排序和临时表。
索引可以将随机I/O变为顺序I/O。

三星索引理论

Lahdenmaki和Leach的三星索引理论：

一星：索引将相关的记录放到一起。
二星：索引中的数据顺序和查找中的排列顺序一致。
三星：索引中的列包含了查询中需要的全部列。

表shop结构：

mysql> desc shop;
+----------+---------------+------+-----+---------+----------------+
| Field    | Type          | Null | Key | Default | Extra          |
+----------+---------------+------+-----+---------+----------------+
| id       | int(11)       | NO   | PRI | NULL    | auto_increment |
| shop_id  | int(11)       | NO   | MUL | NULL    |                |
| goods_id | int(11)       | NO   |     | NULL    |                |
| pay_type | tinyint(1)    | NO   | MUL | NULL    |                |
| price    | decimal(10,2) | NO   | MUL | NULL    |                |
| comment  | varchar(4000) | YES  | MUL | NULL    |                |
+----------+---------------+------+-----+---------+----------------+

查询下面的SQL：

select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price

没有创建任何索引之前，Explain结果：

explain select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: shop
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 20029
        Extra: Using where; Using filesort

第一步构建一星索引

根据where后面等值条件，或者范围条件来构建索引，即index(shop_id,goods_id) ，如下所示，用explain查看上面SQL使用这个索引。SQL优化一般都说索引是为了能以最快的速度定位到想要的数据，即用空间来换时间，快速定位想要的数据后，也就过滤掉了不必要的数据，所以一星索引的核心就是利用索引来尽可能的过滤不必要的数据，减少数据处理的规模，对于RDBMS来说是极为关键的，比如说shop表有1000000行，shop_id的过滤度是10%，goods_id的过滤度是0.1%，如果没有索引，数据库不得不把表里所有的一百万行数据都读出来，做处理，但是如果有了这个一星索引，需要处理的数据被极大的缩小，只需要根据索引找到符合条件的索引叶子节点的范围，读取0.1%10%1000000=100 rows就可以了，哪怕我们乐观的假定产生的都是逻辑IO，而不是物理IO，单次的差别就已经很明显，更别说是执行频率很高的时候，我们线上很多烂SQL对DB造成了影响，一看机器逻辑读都好几百万，基本上可以定位是SQL索引缺失，或者索引不合理造成的。

mysql> ALTER TABLE shop add index shop_id(`shop_id`, `goods_id`);

mysql> explain select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: shop
         type: ref
possible_keys: shop_id
          key: shop_id
      key_len: 8
          ref: const,const
         rows: 19
        Extra: Using where; Using filesort

第二步构建二星索引

针对上面的case，我们构建索引如下index(shop_id, goods_id, price)，用explain查看上面SQL已经没有Using filesort。基本的原理就是利用索引的有序性，把消除order by或者group by等需要排序的操作，因为大家都知道排序是非常消耗CPU资源的，大量的排序操作会把CPU搞得很高，即使CPU吃得消，如果数据量比较大，需要排序的数据放不下内存的sort buffer，只能悲剧的和外存换进换出，性能下降的就不是一点两点，这时候利用索引避免排序的优势就明显的体现出来了。

mysql> ALTER TABLE shop drop index shop_id;

mysql> ALTER TABLE shop add index shop_id(`shop_id`, `goods_id`, `price`);

mysql> explain select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: shop
         type: ref
possible_keys: shop_id
          key: shop_id
      key_len: 8
          ref: const,const
         rows: 19
        Extra: Using where

第三步构建三星索引

如下index(shop_id, goods_id, price,pay_type)，跟之前的二星索引的差别在于，在索引中额外添加了要查询的列pay_type，这就是所谓的索引覆盖，用explain查看上面SQL有Using index，即在索引的叶子节点就能够读到查询SQL所需要的所有信息，而不需要回原表去查询，在目前内存如此充足的情况下，很多时候，除了root节点和branch结构，甚至整个索引都是可以被放入内存的，这样能大概率的避免，至少是减少物理IO。

mysql> ALTER TABLE shop drop index shop_id;

mysql> ALTER TABLE shop add index shop_id(`shop_id`, `goods_id`, `price`, `pay_type`);

mysql> explain select pay_type, price from shop where shop_id = 2 and goods_id = 2 order by price\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: shop
         type: ref
possible_keys: shop_id
          key: shop_id
      key_len: 8
          ref: const,const
         rows: 19
        Extra: Using where; Using index

注意：索引是最好的解决方案吗？

索引并不总是最好的工具。索引其实是一种权衡，是一种拿空间来换时间的艺术。总的来说，只有当索引帮助存储引擎快速查找到记录带来的好处大于其带来的额外工作时，索引才是有效的。对于非常小的表，大部分情况下简单的全表扫描更高效。对于中到大表，索引就非常有效。但对于特大型的表，建立和使用索引的代价将随之增长。这种情况下，则需要一种技术可以直接区分出需要查询的一组数据，而不是一条记录一条记录的匹配。例如可以使用分区技术。
如果表的数量特别多，可以建立一个元数据信息表，用来查询需要用到的某些特性。例如执行那些需要聚合多个应用分布在多个表的数据的查询，则需要记录“哪个用户的信息存储在哪个表中”的元数据，这样在查询时就可以直接忽略那些不包含指定用户信息的表。

最后编辑于：2017.12.10 11:18:11

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 205,565评论 6赞 479
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,021评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,003评论 0赞 341
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,015评论 1赞 278
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,020评论 5赞 370
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,856评论 1赞 283
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,178评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,824评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,264评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,788评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,913评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,535评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,130评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,102评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,334评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,298评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,622评论 2赞 343