05 -06| 深入浅出索引

索引可以提高数据的查询效率，就像书的目录。其中索引设计到一部分数据结构和算法的内容，想要深入理解索引的概念那正要补补数据结构和算法了。

涉及数据结构

• 哈希表
• 有序数组
• 搜索树

优缺点

数据模型|优点|缺点
:-:|:-:|:-:|:-:|
哈希表|插入和查找在没退化成链表情况下O(1)|不适合范围查找
有序数组|等值范围都适合O(long(N))|写入性能成本高
搜索树(N叉树)|读写操作O(long(N))|写入最坏时间复杂度O(n)

InnoDB主键（聚簇）索引 和非主键索引的区别

主键索引的叶子节点放的整行数据，非主键索引放的主键的值，也就是说使用非主键索引时需要再查询次主键索引树，这种方式称为回表

eg

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

select * from T where k betwee 3 and 5 需要执行几次树的检索

1. 在k索引树上找到k=3,获得 id = 300
2. 到ID索引树上找 id = 300 取全部值

如此往复，那么怎么优化第2部的消耗能？

索引覆盖

覆盖索引对innodb表特别有用,上面讲到二级索引的值是主键索引的值所以用了覆盖索引可以减少回表查询的次数。由此可见上面的查询可改为

select id from T where k betwee 3 and 5

依稀记得刚开始写代码的时候老师傅书过 * 性能不如每行写出要查的值吗，当时很懵逼问了老师傅，得到的解释是查出来的内容少了网络开销也会小（糟老头子误人子弟），其实覆盖索引减少的回表次数才是主要原因

最左原则

最左原则是建立在联合索引上的，联合索引有个好处就是减少回表，但是因为B+树的数据结构形式还是会有些限制的由此有了最左原则

假设上面是一个联合索引（'name',number） ID为索引保存的值，当要找到 name = abc的时候可以快速定位到位置并且遍历出所有内容，如果是 where name like ‘%a’也可以用到这个联合索引。由此可得，最左可以是最左索引中的最左N个字段，也可以是字符串索引的最左N个字符。

小技巧

• （a,b）的联合索引，不需要单独给a加上索引。
• 如果同时需要（a,b） 联合查询，又需要单独查询，建议以ab两个字段的大小决定先后顺序

索引下推

索引下推是 Mysql5.6后的特性，拿上面例子举例如果完成下面这条语句sql查询

mysql> select * from name like '%a' and number = 140

5.6之前的执行步骤

1. 在联合索引的树上找到a开头的主键ID
2. 通过主键ID找到 number 值
3. 对比是否满足 number = 140
   …

5.6之后的执行步骤

1. 在联合索引的树上找到a开头的主键ID
2. 和联合索引中的ID 对比是否满足 number = 140
   …

如何建立高效的主键索引

主键索引是基于B+数的数据结构，在数据写入时如果非顺序写入会存在插入一个节点而移动后面节点的情况。为了避免这种情况，我们一般会使用自增保证数据的顺序写入。而且非主键索引的值是主键索引的值，创建主键索引时应尽量保证索引的短小