monodb 集聚索引 聚集索引的作用

一、什么是索引

索引（index）是帮助mysql高效获取数据的排好序的数据结构。

就像书的目录，用于快速定位书中内容的页码。

百度百科中定义：在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。

二、索引名词

聚集索引与非聚集索引

根据索引结构与数据是否存放在一起，可以划分为：聚集索引、非聚集索引。

聚集索引：也叫聚簇索引，是索引结构和数据一起存放的索引，即索引和数据都存放在叶子节点。其中主键索引就是聚集索引。

非聚集索引：也叫非聚簇索引,是索引结构和数据分开存放的索引，即索引叶子节点只存放索引以及主键id，而不存放具体的数据。因此，当使用非聚集索引查询数据时，查询字段不全部都是索引树中可以查找到的字段，则需要回表，通过主键id走聚集索引，取出对应的数据，当查询字段全部都是索引树中的数据时，不需要再次回表，可以直接取出数据返回给客户端，这种查询方式也叫“覆盖索引”。

一级索引和二级索引

一级索引：索引和数据存储在一起，也是直接存储在索引树的叶子节点上。一般主键索引都是一级索引，一级索引也是聚集索引。

二级索引：二级索引树的叶子节点存储的是主键而不是数据。也就是说，在找到索引后，得到对应的主键，再回到一级索引中找主键对应的数据记录。

组合索引：又叫“复合索引”、“联合索引”，在单个列上创建的索引，我们成为单列索引，在2个以上的列创建的索引叫组合索引。

hash索引：是将索引建的hash值和对应的磁盘指针信息，存放到一个bucket当中的，起到索引的作用，如图：

覆盖索引：是一种查询方式，就前文所说，执行sql查询时，如果一个索引包含（或者说覆盖）所有需要查询的字段的值，称之为“覆盖索引”。

三、索引底层数据结构

MySQL索引底层数据结构，采用的是B+树结构，是一种有序的数据结构，下图是聚集索引B+树结构：

对于索引的数据结构，可以采用二叉树、红黑树、Hash表、B-Tree，但是为什么没有用这些数据结构，而是使用B+树呢？

1. 二叉树：无法适应单边增长的情形，当索引树是单边的时候，查找叶子节点，就是一次全表扫描
2. 红黑树，红黑树是一种平衡二叉树，但是其高度是不可控的，当数据量较大时，查找叶子节点数据，每次都需要从根节点出发，当树的层次结构有4层时，每次查叶子节点数据，都需要查4次，数据量再大点，那么层级又会更高。
3. hash：只能根据索引建的hash值查找数据，只支持“=”、“in”的操作。当然MySQL中依旧可以选择建立hash数据结构的索引，因为hash索引的查询速度比B+树高，毕竟只需要计算一次hash值即可定位到数据的存储位置。
4. B-Tree，通过拓宽索引的存储空间，将原来一个节点存储一个索引变为多个索引，从而降低整颗索引树的高度，对比B+树，其主要不足有两点：
5. 节点中存放索引的同时，也存放了数据，而索引占用空间比数据少，而B+树叶子节点不存放数据，导致B-Tree在相同索引空间大小时，存储的索引数量就更少
6. B+树，叶子节点块之间有指针指向连接，可以方便的进行范围查找，而B-Tree，对于非当前叶子节点块中的数据，需要重新从根节点开始便利数据，导致范围查找的效率更低。
7. B-Tree的结构如下图：

对于组合索引，其数据结构如下图，是根据组合索引字段的顺序排列：

四、常见的索引性能优化方式

4.1 正确使用索引

通过前文，我们知道索引底层是一种排好序的数据结构，那么我们就需要知道一些索引生效或者失效的场景：

下文中，出现的索引，是以组合索引(name,age,position)来举例。

1. 最左前缀法则：查询时，从索引的最左前列开始并且不跳过索引中的列，如果跳过了前面的列，那么对于后续索引列来说，数据是无序的，就需要扫描当前范围条件下的所有数据。
2. 如：当执行如下sql时，只有name才会走索引，因为:在name=“12”的范围下，postion是无序的，可能在不同的age下，都有“中国”，所以需要扫描当前name=“12”的范围下的所有数据

select * from employees where name ="12" and postion="中国"

2. 不在索引列上做任何操作：如计算、函数、类型转换（自动or手动）
3. 因为索引树中，保存的是具体的索引值，而不是经过计算、函数计算等之后的值，所以使用了这些操作之后，在索引树中，是没法保证有序的。
4. 不能使用索引范围条件右边的列：即使用范围查找是，对于右边的数据，是无序的，如下面sql，对于age进行了范围匹配，那么position就是无序的

select * from employees where name =“12” and age>18 and position="中国"

4. 尽量使用覆盖索引：当业务场景只需要查询索引列包含的列的时候，就不要使用select *了，可以选择使用覆盖索引，前文也说了，走覆盖索引，可以避免回表
5. 不使用 !=、<>、not in、not exists：大部分情况下，mysql会使用全表扫描；
6. is null、is not null一般情况也无法使用索引：主要原因依旧是mysql内部优化器会评估是否走索引。
7. 不能使用“左模糊”或者“全模糊”：即不能使用 like“%abc”或者 like “%abc%”，就是因为前缀无法判断，无法使用索引的顺序，就会走全表扫描。对于此场景，可以使用搜索引擎。
8. 少用 or 或 in：这个需要or和in的范围数据量，因为mysql优化器会进行整体评估，来确定是否使用索引。对于in，建议尽可能少，最好不要超过1000，当然越少越好
9. 对于范围查询，有时不会使用索引：对于<、>、<=、>=这些，mysq内部优化器对使用索引、不使用索引进行整体评估，计算代价值，具体情况具体分析，可以使用explain看看mysql执行计划。对于这种类型的优化，可以将大范围拆分为多个小范围。

4.2 索引优化

4.2.1 索引下推

索引下推：在索引遍历过程中，对索引中包含的所有字段先做判断，过滤掉不符合条件的记录之后再回表，以有效减少回表次数，看下面示例：

对于组合索引(name,age,position)，按最左前缀原则，下面这条sql，age、和position字段是不会走索引的，但是为什么会走索引呢？即为什么 like 'abc%'这种右模糊可以走索引？

explain SELECT * FROM employees WHERE name like 'LiLei%' AND age = 22 AND position ='manager'

1. 在MySQL5.6之前的版本，只能在组合索引里匹配到name是“LiLei”开头的索引，然后拿这些索引对应的主键逐个汇编，到主键索引上找出对应的记录，再不对age、position这两个字段的值是否符合条件；
2. 但是MySQL5.6版本，引入了索引下推优化，可以在索引遍历过程中，对索引中包含的所有字段先做判断，过滤掉不符合条件的记录之后再回表，以有效减少回表次数。
3. 备注：对于主键索引，因其叶子节点上保存的是全行数据，所以此时索引下推不会起到减少查询全行数据的效果。
4. 有时，右模糊不一定会走索引下推，但是绝大多数情况都是会使用的。

对于范围查找，MySQL没有使用索引下推？

个人认为：是MySQL认为范围查找过滤后的结果集过大，而like "abc%"在绝大多数情况下，过滤后的结果集比较小，可以使用索引下推优化。

4.2.2 Using filesort：文件排序

单路排序：循环查询数据并取出所有满足条件行的所有字段，放在sort_buffer中进行排序。读取聚集索引叶子节点数据，将索引的数据放到内存中排序。

示例：

SELECT * FROM employees  where name="abc"  order by position

第一步：从索引name找到第一个满足 name = ‘abc’ 条件的主键 id

第二步：根据主键 id 取出整行，取出所有字段的值，存入 sort_buffer 中

第三步：从索引name找到下一个满足 name = ‘abc’ 条件的主键 id

第四步：重复步骤 2、3 直到不满足 name = ‘abc'

第五步：对 sort_buffer 中的数据按照字段 position 进行排序

第六步：返回结果给客户端

双路排序（回表排序模式）：循环查询数据并取出所有满足条件行的排序字段以及主键id，放在sort_buffer中进行排序，排序玩之后，在回到原表取出所有需要返回给客户端的字段。读取聚集索引叶子节点数据，讲排序字段和id的数据放到内存中排序，排序玩之后再根据id回表查询数据。

第一步：从索引name找到第一个满足 name = ‘abc’ 条件的主键 id

第二步：根据主键 id 取出整行，把排序字段 position 和主键 id 这两个字段放到 sort buffer 中

第三步：从索引name找到下一个满足 name = ‘abc’ 条件的主键 id

第四步：重复步骤 2、3 直到不满足 name = ‘abc'

第五步：对 sort_buffer 中的字段 position 和主键 id 按照字段 position 进行排序

第六步：遍历排序好的 id 和字段 position，按照 id 的值回到原表中取出 所有字段的值返回给客户端

4.2.3 Order by 和Group by优化

Order by

Order by排序方式有两种：

1. 利用有序索引自动实现，即explain结果的Using index。因为索引时有序的，此时就不需要再排序了，速度比Using filesort快。
2. 筛选结果后，再排序，即explain结果的Using filesort。

因此，对于Order by的优化，就需要避免使用Using filesort。

使用Using index，需要满足两个条件：

1. order by 使用索引最左前缀
2. 使用where子句与order by子句条件列组合满足索引最左前列

即遵循索引建立是的最左前缀法则。

备注：能用覆盖索引，就是用覆盖索引；where高于order by，即索引优先满足where 子句。

Group by

group by其实质是先排序，后分组，所以其也是遵循索引建立是的最左前缀法则。

备注：对于group by，如果不需要排序，可以加上order by null 禁止排序

4.2.4 分页查询优化

1. 根据自增且连续的主键排序进行分页优化：必须满足如下条件才可以使用：
2. 主键自增且连续
3. 数据的排序时按照主键来排序的

示例：

-- 正常分页
select * from employees limit 10000,10;
-- 优化：
select * from employees where id>10000 limit 10;

备注：特别注意，如果某条数据删除了，那么分页查询的数据和优化后数据会不一致

2. 根据非主键字段排序的分页查询：让排序时返回的字段尽可能少

示例：

-- 正常分页
select * from employees order by name limit 10000,10;
-- 优化后
select * from employees e inner join (select id from employees order by name limit 10000,5) ed on e.id = ed.id;

4.2.5 join关联查询优化

嵌套循环连接 Nested-Loop Join(NLJ) 算法

一次一行循环地从第一张表（称为驱动表）中读取行，在这行数据中取到关联字段，根据关联字段在另一张表（被驱动表）里取出满足条件的行，然后取出两张表的结果合集。

使用了 NLJ算法。一般 join 语句中，如果执行计划 Extra 中未出现 Using join buffer 则表示使用的 join 算法是 NLJ。

如果被驱动表的关联字段没索引，使用NLJ算法性能会比较低，mysql会选择Block Nested-Loop Join算法

示例：

EXPLAIN select * from t1 inner join t2 on t1.a= t2.a;

第1步：从表 t2 中读取一行数据（如果t2表有查询过滤条件的，会从过滤结果里取出一行数据）；

第2步：从第 1 步的数据中，取出关联字段 a，到表 t1 中查找；

第3步：取出表 t1 中满足条件的行，跟 t2 中获取到的结果合并，作为结果返回给客户端；

第4步：重复上面 3 步

整个过程会读取 t2 表的所有数据(扫描100行)，然后遍历这每行数据中字段 a 的值，根据 t2 表中 a 的值索引扫描 t1 表中的对应行(扫描100次 t1 表的索引（索引加载在内存，比查询数据时扫磁盘会快很多），1次扫描可以认为最终只扫描 t1 表一行完整数据，也就是总共 t1 表也扫描了100行)。因此整个过程扫描了 200 行。

驱动表是 t2，被驱动表是 t1。先执行的就是驱动表(执行计划结果的id如果一样则按从上到下顺序执行sql)；优化器一般会优先选择小表做驱动表。所以使用 inner join 时，排在前面的表并不一定就是驱动表

当使用left join时，左表是驱动表，右表是被驱动表，当使用right join时，右表时驱动表，左表是被驱动表，当使用join时，mysql会选择数据量比较小的表作为驱动表，大表作为被驱动表。

基于块的嵌套循环连接 Block Nested-Loop Join(BNL)算法

把驱动表的数据读入到 join_buffer 中，然后扫描被驱动表，把被驱动表每一行取出来跟 join_buffer 中的数据做对比。

示例：

EXPLAIN select * from t1 inner join t2 on t1.b= t2.b;

1. 把 t2 的所有数据放入到 join_buffer

2. 把表 t1 中每一行取出来，跟 join_buffer 中的数据做对比

3. 返回满足 join 条件的数据

整个过程对表 t1 和 t2 都做了一次全表扫描，因此扫描的总行数为10000(表 t1 的数据总量) + 100(表 t2 的数据总量) =10100。并且 join_buffer 里的数据是无序的，因此对表 t1 中的每一行，都要做 100 次判断（内存中比对），所以内存中的判断次数是100 * 10000= 100 万次

如果join_buffer 放不下怎么办呢？

join_buffer 的大小是由参数 join_buffer_size 设定的，默认值是 256k。如果放不下表 t2 的所有数据话，策略很简单，就是分段放。

比如 t2 表有1000行记录， join_buffer 一次只能放800行数据，那么执行过程就是先往 join_buffer 里放800行记录，然后从 t1 表里取数据跟 join_buffer 中数据对比得到部分结果，然后清空 join_buffer ，再放入 t2 表剩余200行记录，再次从 t1 表里取数据跟 join_buffer 中数据对比。所以就多扫了一次 t1 表。

即分段放时，扫描磁盘次数=800+10000+200+10000=21000，多扫描了一次大表，比对次数是800*10000+200*10000=1千万

被驱动表的关联字段没索引为什么要选择使用 BNL 算法而不使用 Nested-Loop Join 呢？

如果上面BNL算法示例的sql使用 Nested-Loop Join，那么扫描行数为 100 * 10000 = 100万次，这个是磁盘扫描，效率会特别低

很显然，用BNL磁盘扫描次数少很多，相比于磁盘扫描，BNL的内存计算会快得多。

因此MySQL对于被驱动表的关联字段没索引的关联查询，一般都会使用 BNL 算法。如果有索引一般选择 NLJ 算法，有索引的情况下 NLJ 算法比 BNL算法性能更高

优化原则：

1. 关联字段加索引，让mysql做join操作时尽量选择NLJ算法
2. 被驱动表一定要加索引，未加索引，可能使用BNL算法，但是BNL算法的效率肯定不如NLJ，毕竟BNL还需要在内存中逐条比对，而NLJ肯定直接通过内存中的索引信息直接筛选
3. 如果未加索引，但是mysql选择了NLJ算法，那么扫描磁盘的次数就是两张表的数量的乘积，效率更低
4. 小表驱动大表，写多表连接sql时如果明确知道哪张表是小表可以用straight_join写法固定连接驱动方式，省去mysql优化器自己判断的时间
5. 对于小表定义的明确:在决定哪个表做驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成之后，计算参与 join 的各个字段的总数据量，数据量小的那个表，就是“小表”，应该作为驱动表。
6. 对于BNL算法，大表则分段的数量更多，导致小表的扫描的数量也会变多，再内存中的比对次数更加疯狂增长
7. 备注：尽可能让优化器去判断，因为大部分情况下mysql优化器是比人要聪明的。使用straight_join一定要慎重，因为部分情况下人为指定的执行顺序并不一定会比优化引擎要靠谱

in 和exisits优化

in:当B表的数据集小于A表的数据集时，in优于exists：

示例：

select * from A where id in (select id from B);

#可以看做：
for(select id from B){
select * from A where A.id = B.id
 }

将主查询B的数据，放到子查询A中做条件验证，再查询出返回结果。

exists：当A表的数据集小于B表的数据集时，exists优于in：

示例：

select * from A where exists (select 1 from B where B.id = A.id);

#可以看做:
 for(select * from A){
 select * from B where B.id = A.id
 }
#A表与B表的ID字段应建立索引

将主查询A的数据，放到子查询B中做条件验证，根据验证结果（true或false）来决定主查询的数据是否保留。

4.2.6 count(*)优化

count(*)、count(1)、count(字段)、count(主键 id)的执行效率都差不多

1. 字段有索引：count(*)≈count(1)>count(字段)>count(主键 id)

字段有索引，count(字段)统计走二级索引，二级索引存储数据比主键索引少，所以count(字段)>count(主键 id)

2. 字段无索引：count(*)≈count(1)>count(主键 id)>count(字段)

字段没有索引count(字段)统计走不了索引，count(主键 id)还可以走主键索引，所以count(主键 id)>count(字段)

3. count(*)会统计值为NULL的行，而count(列名)不会统计此列为NULL值得行
4. count(1)跟count(字段)执行过程类似，不过count(1)不需要取出字段统计，就用常量1做统计，有索引值就直接计数，count(字段)还需要取出字段，存放到内容再计数，所以理论上count(1)比count(字段)会快一点
5. count(*) 是例外，mysql并不会把全部字段取出来，而是专门做了优化，不取值，按行累加，效率很高，所以不需要用count(列名)或count(常量)来替代 count(*)，并且“阿里巴巴手册”上写明：

【强制】不要使用count(列名)或count(常量)来替代count(*),count(*)是SQL92定义的标准统计行数的语法，跟数据库无关，跟NULL和非NULL无关

为什么对于count(id)，mysql最终选择辅助索引而不是主键聚集索引？

因为二级索引相对主键索引存储数据更少，检索性能应该更高，mysql内部做了点优化(应该是在5.7版本才优化)

常见优化方法：

1. 查询mysql自己维护的总行数
2. 对于myisam存储引擎的表做不带where条件的count查询性能是很高的，因为myisam存储引擎的表的总行数会被mysql存储在磁盘上，查询不需要计算
3. 对于innodb存储引擎的表mysql不会存储表的总记录行数(因为有MVCC机制)，查询count需要实时计算
4. show table status

如果只需要知道表总行数的估计值可以用如下sql查询，性能很高

3. 将总数维护到Redis里

插入或删除表数据行的时候同时维护redis里的表总行数key的计数值(用incr或decr命令)，但是这种方式可能不准，很难保证表操作和redis操作的事务一致性

4. 增加数据库计数表

插入或删除表数据行的时候同时维护计数表，让他们在同一个事务里操作

五、索引设计原则

1. 代码先行，索引后上：在完成主体代码之后，再创建索引
2. 组合索引尽量覆盖条件
3. 不要在小基数字段上建立索引
4. 长字符串需要采用前缀索引
5. where与order by冲突时，优先满足where 子句
6. 基于慢sql查询进行优化