一. 索引定义

索引是排好序的数据结构。

二. 索引的数据结构

mysql索引可选两种数据结构：B+树和hash。默认B+树。

索引为啥不用二叉树、红黑树？

二叉树和红黑树的节点只能存一个值，数据量大的时候树太高，检索的时候每个节点都需要进行一次io，io浪费性能。

B+树每个节点能存储16k（默认是16K，可以使用innodb_page_size参数修改），大概能存储1000多个值，能降低树高度，减少io次数。

指针大小大概占用6Byte

B+树B-树的区别

B-树：

B+树：

B+树的非叶子节点不存数据，叶子节点存数据；B-树在每个节点存了行数据的磁盘地址。

B+树把所有节点都放到叶子节点用链表连起来，方便范围查询（冗余叶子节点）；B-树没有冗余叶子节点。

hash索引

hash索引的数据结构和jdk1.7的hashMap类似，由数组和链表组成。把字段值换算成hash码存入数组，有hash冲突时改成链表。

hash索引的优点：查找快，只用一次hash计算就能在数组匹配到值。

缺点：不能范围查询，不能模糊查询。

三. 索引的分类（InnorDB引擎）

索引分为主键索引(又叫聚簇索引)和非主键索引。非主键索引包括：普通索引、唯一索引、组合索引。

1.主键索引

主键索引在非叶子节点中存储了主键的值，在叶子节点中保存了整行数据。查找的时候通过主键查找，找到在叶子节点找到整行数据。

非主键索引在非叶子节点中存储索引的值，查找的时候通过索引的值进行查找，找到最后的叶子节点，叶子节点存储了对应的主键ID，然后根据查到的主键ID，从主键索引的B+树进行查找，直到找到这一行的所有数据。通过非主键索引找到主键，再通过主键索引找到整行数据的过程，称为回表。

注意：每张表都有一个主键索引，当没设置主键的时候，mysql会把第一个不包含NULL值的唯一索引列作为主键索引。如果没有这样的列，就把行号作为主键索引。

2.组合索引

2.1最左前缀

全值匹配查询：查询条件全符合组合索引字段。

最左前缀查找：查找条件符合组合索引的最左边几项，索引就会生效。最左前缀可以是组合索引的最左边n个字段，也可以是字符串索引的最左边n个字符（例：like \’abc%\’）。

2.2 索引下推

例：建name，age 组合索引

select * from user where name like \”B%\” and age = 30;

mysql会以名字为“B”开头的数据开始遍历，然后判断年龄是否为30。

但是最左前缀有一个非常重要的原则：MySQL会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配。

所以此时这里的查询age索引用不上。

在mysql5.6之前，只要找到了符合以“B”开头的名字这个条件，就会通过这个数据的主键ID，进行回表的操作，然后查找这个数据的年龄是否为30。

而MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。也就是说，直到找到了以“B”开头的名字并且年龄为30，才会进行回表。

此外，在回表之前，如果使用了Multi-Range Read (MRR)这个策略，在取出主键后，回表之前，会再对所有获取到的主键排序。

3.3 覆盖索引

查询字段已经被包含在了索引字段里，这样就不用回表。例如把name,age建了索引，查询字段只包含name，age字段。

3.唯一索引与普通索引

唯一索引和普通索引在叶子节点存储索引值和主键值。

唯一索引与普通索引区别：    

1.普通索引找到数据后继续往后遍历查找，直到找不到为止。唯一索引找到数据立刻返回。

2.唯一索引insert数据的时候会检验一次有没有重复，普通索引不会检验。

建议：业务上具有唯一特性的字段，即使是组合字段，也必须建成唯一索引。不要以为唯一索引影响了insert速度，这个速度损耗可以忽略，但提高查找速度是明显的；另外，即使在应用层做了非常完善的校验控制，只要没有唯一索引，根据墨菲定律，必然有脏数据产生。

四. InnorDB索引和MyISam索引的区别

注意数据库引擎是用来修饰表的，不是用来修饰数据库的。

上面有说到InnorDB的主键索引和非主键索引，都是在非叶子节点存储索引值，叶子节点存储索引值和数据，主键索引的数据是整行数据，非主键索引的数据是主键索引值。

这里介绍MyIsam引擎的索引。

MyIsam也是使用B+Tree作为索引结构，但是没有主键索引。非叶子节点存储索引值，叶子节点存储索引值和数据，数据保存的是数据文件的磁盘地址指针。

五. 索引是怎么找到数据的

MyIsam和InnorDb两种引擎用索引找数据的方式不一样。

1.MyIsam

MyIsam引擎的B+树每个节点存储了索引值和行数据的磁盘地址，找到索引后，用磁盘地址去磁盘文件找到数据。

数据以文件的形式存储在磁盘，例如磁盘目录：mysql/data/tablename

mysql/data/tablename/

*.frm    frm是frame的简写，存储的是表结构。

*.MYD    MYIsam Data的缩写，存储数据。

*.MYI    MYIsam Index的缩写，存储索引。

2.InnorDB

整行数据存储在聚簇索引的叶子节点上，通过聚簇索引，找到叶子节点就能找到整行数据。

六. 为什么建议把索引建成整形自增的

1.索引需要排序，如果是字符串，需要把字符串的每个字符转成ASCII码逐个比较进行排序。

2.整形自增的添加到索引树的时候只用在索引树后面追加即可，可以避免索引树自动调整。