面试系列-索引及检索过程

如果需要查询id=14的数据，只需要在左边的主键索引中检索就可以了。
如果需要搜索name='Ellison'的数据，需要2步：
1. 先在辅助索引中检索到name='Ellison'的数据，获取id为14
2. 再到主键索引中检索id为14的记录
辅助索引这个查询过程在mysql中叫做回表。

1. 在索引中找到对应的关键字，获取关键字对应的记录的地址
2. 通过记录的地址查找到对应的数据记录
我们⽤的最多的是innodb存储引擎，所以此处主要说⼀下innodb索引的情况，innodb中
最好是采⽤主键查询，这样只需要⼀次索引，如果使⽤辅助索引检索，涉及到回表操作，
⽐主键查询要耗时⼀些。

表中的数据发⽣变更的时候，会影响其他记录地址的变化，如果辅助索引中记录数据的地
址，此时会受影响，⽽主键的值⼀般是很少更新的，当页中的记录发⽣地址变更的时候，
对辅助索引是没有影响的。

聚集索引（主键索引）、⾮聚集索引（辅助索引）、单列索引、多列索引（⼜称复合索引）、唯⼀索引

如上图，所有的数据都是唯⼀的，查询105的记录，过程如下：
    1. 将P1页加载到内存
    2. 在内存中采⽤⼆分法查找，可以确定105位于[100,150)中间，所以我们需要去加载
    100关联P4页
    3. 将P4加载到内存中，采⽤⼆分法找到105的记录后退出

如上图，查询105的所有记录，过程如下：
    1. 将P1页加载到内存
    2. 在内存中采⽤⼆分法查找，可以确定105位于[100,150)中间，100关联P4页
    3. 将P4加载到内存中，采⽤⼆分法找到最有⼀个⼩于105的记录，即100，然后通过链
    表从100开始向后访问，找到所有的105记录，直到遇到第⼀个⼤于100的值为⽌

查询[55,150]所有记录，由于页和页之间是双向链表升序结构，页内部的数
据是单项升序链表结构，所以只⽤找到范围的起始值所在的位置，然后通过依靠链表访问
两个位置之间所有的数据即可，过程如下：
    1. 将P1页加载到内存
    2. 内存中采⽤⼆分法找到55位于50关联的P3页中，150位于P5页中
    3. 将P3加载到内存中，采⽤⼆分法找到第⼀个55的记录，然后通过链表结构继续向后
    访问P3中的60、67，当P3访问完毕之后，通过P3的nextpage指针访问下⼀页P4中所
    有记录，继续遍历P4中的所有记录，直到访问到P5中的150为⽌。

查询以 f 开头的所有记录
    1. 将P1数据加载到内存中
    2. 在P1页的记录中采⽤⼆分法找到最后⼀个⼩于等于f的值，这个值是f，以及第⼀个⼤
    于f的，这个值是z，f指向叶节点P3，z指向叶节点P6，此时可以断定以f开头的记录
    可能存在于[P3,P6)这个范围的页内，即P3、P4、P5这三个页中
    3. 加载P3这个页，在内部以⼆分法找到第⼀条f开头的记录，然后以链表⽅式继续向后
    访问P4、P5中的记录，即可以找到所有已f开头的数据

查询包含 f 的记录
    包含的查询在sql中的写法是 %f% ，通过索引我们还可以快速定位所在的页么？
    可以看⼀下上⾯的数据，f在每个页中都存在，我们通过P1页中的记录是⽆法判断包含f的
    记录在那些页的，只能通过io的⽅式加载所有叶⼦节点，并且遍历所有记录进⾏过滤，才
    可以找到包含f的记录。
    所以如果使⽤了 %值% 这种⽅式，索引对查询是⽆效的。

查询a=1的记录，由于页中的记录是以 a asc,b asc,c asc 这种排序⽅式存储的，所以a字段是有序的，可
以通过⼆分法快速检索到，过程如下：
    1. 将P1加载到内存中
    2. 在内存中对P1中的记录采⽤⼆分法找，可以确定a=1的记录位于{1,1,1}和{1,5,1}关联
    的范围内，这两个值⼦节点分别是P2、P4
    3. 加载叶⼦节点P2，在P2中采⽤⼆分法快速找到第⼀条a=1的记录，然后通过链表向下
    ⼀条及下⼀页开始检索，直到在P4中找到第⼀个不满⾜a=1的记录为⽌

查询a=1 and b=5的记录
    ⽅法和上⾯的⼀样，可以确定a=1 and b=5的记录位于{1,1,1}和{1,5,1}关联的范围内，查找
过程和a=1查找步骤类似。

查询b=1的记录
    这种情况通过P1页中的记录，是⽆法判断b=1的记录在那些页中的，只能加锁索引树所有
叶⼦节点，对所有记录进⾏遍历，然后进⾏过滤，此时索引是⽆效的。

按照c的值查询
    这种情况和查询b=1也⼀样，也只能扫描所有叶⼦节点，此时索引也⽆效了。

按照b和c⼀起查
    这种也是⽆法利⽤索引的，也只能对所有数据进⾏扫描，⼀条条判断了，此时索引⽆效。

按照[a,c]两个字段查询
    这种只能利⽤到索引中的a字段了，通过a确定索引范围，然后加载a关联的所有记录，再
对c的值进⾏过滤。

查询a=1 and b>=0 and c=1的记录
    这种情况只能先确定a=1 and b>=0所在页的范围，然后对这个范围的所有页进⾏遍历，c
字段在这个查询的过程中，是⽆法确定c的数据在哪些页的，此时我们称c是不⾛索引的，
只有a、b能够有效的确定索引页的范围。

类似这种的还有>、<、between and，多字段索引的情况下，mysql会⼀直向右匹配直到
遇到范围查询(>、<、between、like)就停⽌匹配。

上⾯这种查询叫做最左匹配原则。

[1,2,3,4,5,6,7,8,8,9,10]
[1,1,1,1,1,8,8,8,8,8]
采⽤上⾯这种⽅法找到8的记录，第⼀个数组中更快的⼀些。因为第⼆个数组中含有8的
⽐例更多的，需要访问以及匹配的次数更多⼀些。

索引区分度 = count(distint 记录) / count(记录) 
创建索引的时候，尽量选择区分度⾼的列作为索引

/*准备数据*/
DROP PROCEDURE IF EXISTS proc1;
DELIMITER $
CREATE PROCEDURE proc1()
  BEGIN
    DECLARE i INT DEFAULT 1;
    START TRANSACTION;
    WHILE i <= 4000000 DO
    INSERT INTO test1 (id, name, sex, email) VALUES
    (i,concat('javacode',i),if(mod(i,2),1,2),concat('javacode',i,'@163.com
                                                    '));
           SET i = i + 1;
           if i%10000=0 THEN
              COMMIT;
              START TRANSACTION;
           END IF;
             END WHILE;
              COMMIT;
  END $
    DELIMITER ;
    CALL proc1();

name、sex两个字段上分别建个索引
select id,name from test1 where name='javacode3500000';
name对应idx1索引，id为主键，所以idx1索引树叶⼦节点中包含了name、id的
值，这个查询只⽤⾛idx1这⼀个索引就可以了，如果select后⾯使⽤ * ，还需要⼀
次回表获取sex、email的值。
所以写sql的时候，尽量避免使⽤ * ， * 可能会多⼀次回表操作，需要看⼀下是否
可以使⽤索引覆盖来实现，效率更⾼⼀些。

需要查询name以 javacode35 开头的，性别为1的记录数，sql如下：
mysql> select count(id) from test1 a where name like 'javacode35%' and
sex = 1;
+-----------+
| count(id) |
+-----------+
| 55556 |
+-----------+
1 row in set (0.19 sec)
  过程：
  1. ⾛name索引检索出以javacode35的第⼀条记录，得到记录的id
  2. 利⽤id去主键索引中查询出这条记录R1
  3. 判断R1中的sex是否为1，然后重复上⾯的操作，直到找到所有记录为⽌。
上⾯的过程中需要⾛name索引以及需要回表操作。
如果采⽤ICP的⽅式，我们可以这么做，创建⼀个(name,sex)的组合索引，查询过程如下：
  1. ⾛(name,sex)索引检索出以javacode35的第⼀条记录，可以得到(name,sex,id)，
  记做R1
  2. 判断R1.sex是否为1，然后重复上⾯的操作，知道找到所有记录为⽌这个过程中不需要
  回表操作了，通过索引的数据就可以完成整个条件的过滤，速度⽐上⾯的更快⼀些。

1. 数字使字符串类索引失效-类型转换
    select * from test1 where id = '4000000';
2. 函数使索引⽆效-索引字段使⽤函数查询使索引⽆效
    select * from test1 a where concat(a.name,'1') = 'javacode11';
3. 运算符使索引⽆效
    select * from test1 a where id+1 = 2;

1. 在区分度⾼的字段上⾯建⽴索引可以有效的使⽤索引，区分度太低，⽆法有效的利⽤
   索引，可能需要扫描所有数据页，此时和不使⽤索引差不多
2. 联合索引注意最左匹配原则：必须按照从左到右的顺序匹配，mysql会⼀直向右匹配
   直到遇到范围查询(>、<、between、like)就停⽌匹配，⽐如a = 1 and b = 2 and c > 3
   and d = 4 如果建⽴(a,b,c,d)顺序的索引，d是⽤不到索引的，如果建⽴(a,b,d,c)的索引
   则都可以⽤到，a,b,d的顺序可以任意调整
3. 查询记录的时候，少使⽤*，尽量去利⽤索引覆盖，可以减少回表操作，提升效率
4. 有些查询可以采⽤联合索引，进⽽使⽤到索引下推（IPC），也可以减少回表操作，提升效率
5. 禁⽌对索引字段使⽤函数、运算符操作，会使索引失效
6. 字符串字段和数字⽐较的时候会使索引⽆效
7. 模糊查询'%值%'会使索引⽆效，变为全表扫描，但是'值%'这种可以有效利⽤索引
8. 排序中尽量使⽤到索引字段，这样可以减少排序，提升查询效率