B+ 树概述

  1. 每一个索引都对应着一棵 B+ 树，B+ 树分为好多层，最下面一层是叶子节点，其余的是内节点。所有的用户记录都存储在 B+ 树的叶子节点，所有的目录项记录都存储在内节点
  2. InnoDB 存储引擎会自动为主键（如果没有会自动添加）建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录
  3. 我们可以为自己感兴趣的列创建二级索引，二级索引的叶子节点包含的用户记录由“索引列 + 主键列”组成，所以说想通过二级索引来查找完整的用户记录的话，需要通过回表操作，也就是在通过二级索引查找到主键之后，再回到聚簇索引中查找完整的用户记录
  4. B+ 树中每层节点都是按照索引列值从小到大的顺序组成了一个双向链表，而且每个页内的记录（无论是用户记录还是目录项记录）都是按照索引的值从小到大的顺序形成了一个单项链表，如果是联合索引的话，则页面和记录先按照联合索引前面的列进行排序，如果相同，再按照联合索引中后面一列的顺序排序，以此类推
  5. 通过索引查找记录是 B+ 树的根节点开始的，一层一层往下搜索，由于每个页面都是按照索引列的值建立了页目录，所以在这些页面中的查找非常的块。

索引的代价

空间上涨的代价

每建立一个索引，都要为他建立一棵 B+ 树，每一颗 B+ 树的每一个节点都是一个数据页，一个页默认占用 16 KB的存储空间，一棵很大的 B+ 树由很多页组成，那就是很大的一片存储空间。

时间上的代价

每次对表中的数据进行增、删、改操作时，都要去修改这棵 B+ 树，而且我们说过，B+ 树每层节点都是按照索引列的值从小到大的顺序而组成的双向链表，无论时叶子节点中的记录，还是内节点的记录（也就是无论时用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成的单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录位移，页面分裂，页面回收等操作来维护好节点和记录的排序，如果我们建立了许多索引，每个索引对应的 B+ 树都要进行相关的维护操作。


B+ 树索引实战

  1. CREATE INDEX idx_t1_bcd on t1(b, c, d);

匹配

全值匹配

  1. select * from t1 where b = 1 and c = 1 and d = 1;

MySQL 中有查询优化器，会分析这些搜索条件并且按照可以使用索引的列的顺序决定先使用哪个搜索条件

匹配左边列

  1. select * from t1 where b = 1;
  2. select * from t1 where b = 1 and c = 1;
  3. select * from t1 where c = 1; -- 用不到索引

因为 B+ 树的数据页和记录是先按照 b 列的值排序的，在 b 列的值不同的情况下才会使用 c 列进行排序，也就是说 b 列的值不同的记录中，c 列的值可能是无序的，而现在跳过 b 列，直接根据 c 列去查找，这样是做不到的

匹配列前缀

但是需要注意的是，如果只给出后缀或者中间某个字符串，比如：

  1. select * from t1 where b like '%101%'; -- 用不到索引

MySQL 无法快速定位记录位置，因为字符串中间有 101 的字符串并没有排好序，所以只能全表扫描了，有时候我们有一些匹配某些字符串后缀的需求，如某个表有很多 url

  1. www.baidu.com
  2. www.google.com
  3. www.qq.com

假设已经对该 url 列创建了索引，如果我们想查询以 com 为后缀的网址，可以写

  1. where url like '%com'; -- 用不到索引

但是这样无法使用该 url 列的索引，为了在查询时用到这个索引而不至于全表扫描，我们可以把后缀查询改成前缀查询，不过我们就得把表中的数据全部逆序存储一下，也就是说我们可以保存这样的 url 列的数据：

  1. moc.udiab.www
  2. moc.elgoog.www
  3. moc.qq.www

这样再查找 com 后缀的网址的搜索条件就可以这么写，就可以用到索引了

  1. where url like 'moc%';

匹配范围值


所有记录都是按照索引列的值从小到大排好序的，所以这极大的方便了我们查找索引的值在某个范围内的记录，比如：

  1. select * from t1 where b > 1 and b < 2000;

由于 B+ 树中的数据页和记录是先按 b 列排序的，所以上面的查询过程其实是这样的：

  1. 找到 b 值为 1 的记录
  2. 找到 b 值为 2000 的记录
  3. 由于所有记录都是由链表连起来的（记录直接单向链表，数据页之间双向链表），所以他们之间可以很容易的取出来
  4. 找到这些记录的主键值，再到聚簇索引中回表查找完整的记录

不过在使用联合进行范围查找的时候需要注意，如果对多个列同时进行范围查找的话，只有对索引最左边的那个列进行范围查找的时候才能用上 B+ 树索引，比如：

  1. select * from t1 where b > 1 and c > 1;

上面这个查询可以分为两部分：

  1. 通过条件 b > 1 来对 b 进行范围过滤，查找的结果可能有多条 b 值不同的记录
  2. 对这些 b 值不同的记录继续通过 c > 1 继续过滤

这样对于联合索引来说，只能用到 b 列的部分，而用不到 c 列的部分，因为只有 b 值相同的情况下，才能用到 c 列的值进行排序，而这个查询中通过 b 进行范围查找的记录中可能并不是按照 c 列的值进行排序的，所以再搜索条件中继续以 c 列进行查找时是用不到 B+ 树索引的

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


对于同一个联合索引来说，虽然多个列都进行范围查找时，只能用到最左边的索引列，但是如果左边的列是精确查找，则右边的列可以进行范围查找，比如：

  1. select * from t1 where b = 1 and c > 1;

排序

我们在写查询语句的时候，经常需要对查询出来的记录通过 ORDER BY 子句按照某种规则进行排序，一般情况下，我们只能把记录都加载到内存中，再用一些排序算法，比如：快速排序，并归排序等等，在内存中对这些记录进行排序，有可能查询出来的结果集太大，以至于不能在内存中排序的话，还可能暂时借助磁盘的空间来存放中间结果，排序操作完成后，再把排序号的结果集返回到客户端。在 MySQL 中，把这种在内存或者磁盘上进行排序的方式统称为文件排序（filesort），这些排序操作非常慢，但是如果 ORDER BY 子句里使用到了我们的索引列，就有可能省去在内存或者文件中排序的步骤，比如：

  1. select * from t1 order by b, c, d;

这个查询的结果集，需要先按 b 值排序，如果记录的 b 值相同，则需要按照 c 值来排序，如果 c 值相同，则需要按 d 值进行排序，因为 B+ 树索引本身就是按照上述规则排序好的，索引直接从索引中提取数据就好，然后进行回表操作取出该索引中不包含的列就好了。


分组

  1. select b, c, d, count(*) from t1 group by b, c, d;

这个查询相当于做了 3 次分组操作：

  1. 先把记录按照 b 值进行分组，所有 b 值相同的记录划分为一组
  2. 将 b 值相同的记录，再按照 c 值进行分组，分成很多小组
  3. 将 c 值相同的记录，再按照 d 值进行分组，分成更小的组

然后对最后的更小的组进行统计，如果没有索引的话，这个分组过程将再内存实现，而有了索引的话，恰巧分组顺序又和 B+ 树的索引顺序一致的话，就可以直接使用 B+ 树进行分组。
和使用 B+ 树索引进行排序是一个道理，分组列的顺序也要和索引列的顺序一致。也可以只使用索引列的左边的列进行分组。


使用联合索引进行排序活分组的注意事项

对于联合索引有个问题需要注意，ORDER BY 的子句后边的列的顺序必须按照索引列的顺序给出，否则用不了 B+ 树索引的。同理，下图这种匹配索引左边列的形式可以使用部分 B+ 树索引。

  1. select * from t1 order by b;
  2. select * from t1 order by b, c;

当联合索引左边的列的值为常量的时候，也可以使用后边的列进行排序

  1. select * from t1 where b = 1 order by c, d

这种查询能使用到索引的原因是，b 列的值已经固定，查询出来的记录是按照 c、d 排序的


不可以使用进行排序或分组的几种情况

ASC、DESC 混用

对于使用联合索引进行排序的场景，我们要求各个排序列的排序规则是一致的，那就是说要么各个列都是按照 ASC 规则排序，要么都是 DESC 规则排序

  1. select * from t1 order by b ASC, c DESC; -- 这个查询用不到索引

如果建立索引

考虑索引的选择性

索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录的比值

  1. 选择性 = 基数 / 记录数

选择性的取值范围 (0, 1]，选择性越高的索引价值越大，如果选择性等于 1，就代表这个列的不重复值和表的记录数是一样的，那么对这个列建立索引是非常适合的，如果选择性非常小，那么就代表这个列的重复值很多，不适合建立索引

考虑前缀索引

用列的前缀代替整个列作为索引 key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引 key 变短而减少索引文件的大小和维护开销。

使用MySQL官网提供的示例数据库

https://dev.mysql.com/doc/employee/en/employees-installation.html

employees 表中只有一个索引 emp_no，那么如果想按名字搜索一个人，就只能用全表扫描了

  1. EXPLAIN select * from employees where first_name = 'Eric' and last_name = 'Anido';

那么可以对 或 建立索引，看下面两个索引的选择性

  1. select count(DISTINCT(first_name))/count(*) as selectivity 
  2. from employees; -- 0.0042
  4. select count(DISTINCT(CONCAT(first_name, last_name)))/count(*) as selectivity 
  5. from employees; -- 0.9313

显然选择性太低， 的选择性很好，但是 first_name 和 last_name 加起来长度为 30，有没有兼顾长度和选择性的办法呢？可以考虑 first_name 和 last_name 的前几个字符建立索引，例如：，在看看其选择性：

  1. select 
  2. count(DISTINCT(CONCAT(first_name, LEFT(last_name, 4))))/count(*) 
  3. as selectivity 
  4. from employees; -- 0.9007

这时选择性已经比较理想了，而整个索引长度只有 18，比 减少了接近一半，建立前缀索引的方式为：

  1. ALTER TABLE employees 
  2. ADD INDEX `first_name_last_name_prefix` (first_name, last_name(4));

前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于 ORDER BY 和 GROUP BY 操作，也不能用于覆盖索引

总结

  • 索引列的类型尽可能的小
  • 利用索引字符串值的前缀
  • 自增主键
  • 定位并删除表中的重复数据和冗余索引
  • 尽量使用覆盖索引进行查询，避免回表带来的性能损耗