MySQL索引原理

索引概念

索引（Index）是帮助MySQL高效获取数据的数据结构。索引是对表中一列或多列的值进行排序的一种存储结构。
索引也是表的组成部分，建立太多的索引将会影响更新和插入的速度，因为它需要同样更新每个索引项结构。

在数据之外，数据库系统还维护着满足特定查找算法的数据结构。这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构就是索引。

数据写入到mysql的时候，每行数据按照过来的先后顺序，顺序写入到磁盘。如果没有任何索引，我们查找某个值的时候，需要遍历整个磁盘进行查找，对于那些经常用于查找的列，我们可以为其创建索引，例如简单的二叉树。二叉树的节点的值是该列的值，同时有一个指针指向该值对应的磁盘的位置，通过二叉树很快定位到要查找的值，获取到磁盘上的对应的行的位置，从而很快取出这一行，比遍历整个磁盘要快得多。

创建索引的优势：

提高数据的检索速度，降低数据库IO成本：使用索引的意义就是通过缩小需要查询的记录的数目从而加快搜索的速度。
降低数据排序的成本，降低CPU消耗：索引之所以查的快，是因为先将数据排好序，若该字段正好需要排序，则真好降低了排序的成本。

创建索引的劣势：

占用存储空间：索引实际上也是一张表，记录了主键与索引字段，一般以索引文件的形式存储在磁盘上。
降低更新表的速度：表的数据发生了变化，对应的索引也需要一起变更，从而降低的更新速度。否则索引指向的物理数据可能不对，这也是索引失效的原因之一。
优质索引创建难：索引的创建并非一日之功，也并非一直不变。需要频繁根据用户的行为和具体的业务逻辑去创建最佳的索引。

为什么MySQL索引要用Hash、B+Tree，而不用二叉树、红黑树、BTree

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。
这样的话，索引查找过程中就要产生磁盘I/O消耗。索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

不用二叉树、红黑树的原因

首先二叉树不是自平衡的，插入新节点时，二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后），为O(n)。而红黑树恰恰优化了二叉树的缺点，使插入、删除节点时能自平衡。但红黑树还是有些问题：那就是数据量大的话，红黑树的深度会很深，也就是说深度不可控，而造成磁盘IO读写过于频繁，另外由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，IO读写次数就更多了，这样一来查找数据还是会很耗时。

红黑树多用在内部排序，即全部在内存中的，C++的STL中map和set的内部实现就是红黑树，Java集合框架里TreeMap也是使用红黑树实现，
B树多用在内存里放不下，大部分数据存储在外存上时。因为B树层数少，因此可以确保每次操作，读取磁盘的次数尽可能的少。

使用hash

相比较于红黑树，hash可以固定“深度”，且映射到磁盘存储引用，这样查找数据直接告诉磁盘数据在哪，查找数据也挺快的，但是 hash 还是有些不足：那就是不能范围查找。

memory引擎就是使用hash索引。

不用BTree的原因

根据B-Tree的定义，可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

综上所述，用B-Tree作为索引结构效率是非常高的。

但B+Tree更适合外存索引，原因和内节点出度d有关。从上面分析可以看到，d越大索引的性能越好，而出度的上限取决于节点内key和data的大小。

B+树相对B树的优点：

1、B+树的所有Data域在叶子节点，所有关键字查询的路径长度相同，也让B+-tree的查询效率更加稳定。另外叶子节点增加一个指向相邻叶子节点的指针，遍历叶子节点就能获取全部数据，提高区间访问性能。

2、非叶子节点不存储数据，一个页所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
结论：B+Tree 既减少查询次数又提供了很好的范围查询

Mysql 索引实现

聚集索引：索引和数据文件为同一个文件。
非聚集索引：索引和数据文件分开的索引。
MyISAM 、 InnoDB 都使用B+Tree索引结构。但是底层索引存储不同，MyISAM 采用非聚集索引，而InnoDB采用聚集索引。
每个索引一个B+树，一个B+树节点 = 一个物理Page（16K）

MyISAM索引实现(非聚集)

原理：采用非聚集索引，索引文件(.myi)和数据文件(.myd)分离。索引文件仅保存数据记录的指针地址，叶子节点data域存储指向数据记录的指针地址。

MyISAM索引按照B+Tree搜索，如果指定的Key存在，则取出其data域的值，然后以data域值-数据指针地址去读取相应数据记录。
辅助索引和主索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如下图在col1上建立主索引，在col2上建立辅助索引。

采用MyISAM引擎创建的表产生3个文件： frm-表定义文件、 myi-索引文件、 myd-数据文件

InnoDB索引实现(聚集)

原理：采用聚集索引，数据和索引文件为一个idb文件，表数据文件本身就是主索引，相邻的索引临近存储。

叶节点data域保存了完整的数据记录（除主键id外其他列data）。

采用InnoDB引擎创建的表产生2个文件：frm -表定义、 idb: innoDB数据&索引文件

在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

与MyISAM索引的不同

1、InnoDB的数据文件本身就是索引文件
2、InnoDB的辅助索引data域存储相应记录主键的值而不是数据记录的指针地址

索引查询实例流程

1、索引精确查找:

确定定位条件, 找到根节点Page No, 根节点读到内存, 逐层向下查找, 读取叶子节点Page,通过二分查找找到记录或未命中。
（select * from user_info where id = 23）

2.索引范围查找：

读取根节点至内存, 确定索引定位条件id=18, 找到满足条件第一个叶节点, 顺序扫描所有结果, 直到终止条件满足id < 22。
（select * from user_info where id >= 18 and id < 22）

3、全表扫描：
直接读取叶节点头结点，顺序扫描，返回符合条件记录，到最终节点结束
（select * from user_info where name = ‘abc’）

4、二级索引查找：
通过二级索引查出对应主键，拿主键回表查主键索引得到数据，二级索引可筛选掉大量无效记录，提高效率
Create table table_x(int id primary key, varchar(64) name,key sec_index(name)
Select * from table_x where name = “d”;

MySQL索引类型

mysql的索引分为单列索引(全文索引，主键索引，唯一索引，普通索引)和组合索引。
单列索引:一个索引只包含一个列，一个表可以有多个单列索引。
组合索引:一个组合索引包含两个或两个以上的列。

普通索引

建表时：INDEX IndexName(字段名(length))

建表后：CREATE INDEX IndexName ON TableName(字段名(length))

或ALTER TABLE TableName ADD INDEX IndexName(字段名(length))

注意：如果字段数据是CHAR，VARCHAR类型，可以指定length，其值小于字段的实际长度，如果是BLOB和TEXT类型就必须指定length。
这个length的用处是什么?

有时候需要在长文本字段上建立索引，但这种索引会增加索引的存储空间以及降低索引的效率，这时就可以用到length，创建索引时用到length的索引，我们叫做前缀索引，前缀索引是选择字段数据的前n个字符作为索引，这样可以大大节约索引空间，从而提高索引效率。

前缀索引是一种能使索引更小，更快的有效办法，但是MySql无法使用前缀索引做ORDER BY 和 GROUP BY以及使用前缀索引做覆盖扫描。

唯一索引

要求字段所有的值是唯一的，这一点和主键索引一样，但是允许有空值。
建表时：UNIQUE INDEX IndexName(字段名(length))

建表后：CREATE UNIQUE INDEX IndexName ON TableName(字段名(length))

或ALTER TABLE TableName ADD UNIQUE INDEX IndexName(字段名(length)）

主键索引

一般在建表的时候自动创建，主键一般会设为 int 而且是 AUTO_INCREMENT自增类型的

全文索引

假设字段的数据类型是长文本，文本字段上(text等)建立了普通索引，我们需要查找关键字的话，那么其条件只能是where column like ‘%xxxx%’ ，但是，这样做就会让索引失效，这时就需要全文索引了。
建表时：FULLTEXT INDEX IndexName(字段名(length))

建表后：CREATE FULLTEXT INDEX IndexName ON TableName(字段名(length))

或ALTER TABLE TableName ADD FULLTEXT INDEX IndexName(字段名(length)）

使用：
SELECT * FROM TableName
WHERE MATCH(column1， column2) AGAINST(‘xxx′， ‘sss′， ‘ddd′)
这条命令将把column1和column2字段里有xxx、sss和ddd的数据记录全部查询出来。

组合索引

假设字段a，b都有索引，我们的查询条件是a=1，b=2查询过程是mysql会先挑选出符合a=1的结果集，再在这些结果集中挑选b=2的结果集，但是mysql并不会在查询a，b时都用到索引，只会用其中一个，这和我们的预期不一样，所以，我们要使用组合索引

建表时：INDEX IndexName(字段名(length)，字段名(length)，……..)

建表后：CREATE INDEX IndexName ON TableName(字段名(length)，字段名(length)，……..)

或ALTER TABLE TableName ADD INDEX IndexName(字段名(length)，字段名(length)，……..)

在最左匹配原则中，有如下说明：

最左前缀匹配原则，非常重要的原则，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的顺序可以任意调整（按照索引列来检索匹配）。

=和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式

索引失效（or、like%、类型转换、函数、表达式）

如果条件中有or，即使其中有条件带索引也不会使用(这也是为什么尽量少用or的原因)。要想使用or，又想让索引生效，只能将or条件中的每个列都加上索引

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 c都可以使用到索引，只是最终c是一个范围值。
like查询以%开头
如果列类型是字符串，那一定要在条件中将数据使用引号引用起来,否则不使用索引，也是发生类型转换
如果mysql估计使用全表扫描要比使用索引快,则不使用索引
索引列不能是表达式的一部分，也不能作为函数的参数，否则无法使用索引查询。下面是例子：
1
2
SELECT * FROM user_test WHERE user_name = concat(user_name, 'fei');

order by使用索引

order by排序有两种排序方式：using filesort使用算法在内存中排序以及使用mysql的索引进行排序；我们在部分情况下希望的是使用索引。

如果ID是单列索引，则order by会使用索引，如：

1 2	select test_index where id = 3 order by id desc;

如果ID是单列索引，name不是索引或者name也是单列索引，则order by不会使用索引。

1 2	select test_index where id = 3 order by name desc;

因为Mysql的一次查询只会从众多索引中选择一个索引，而这次查询中使用的是ID列索引，而不是name列索引。在这种场景下，如果想让order by也使用索引的话，就建立联合索引（id，name），这里需要注意最左前缀原则，不要建立这样的联合索引（name，id）。

最后需要注意mysql对排序记录的大小有限制：max_length_for_sort_data 默认为1024；也就意味着如果需要排序的数据量大于1024，则order by不会使用索引，而是使用using filesort。

索引创建的几个原则

适合索引的列是出现在WHERE子句中的列
使用唯一索引
具有多个重复值的列，其索引效果最差，比如性别全是男的记录，对于MyISAM引擎来说，因为这时查找的时间就是T扫描整个索引表+T扫描整个表，那么耗时肯定过大了。对于InnoDB引擎来说，默认是有主键索引的，性别就相当于辅助索引了，这时每找到一个辅助索引节点就要去主键索引，也是相当于遍历辅助索引链表+整颗主键索引树。
使用短索引
如果对串列进行索引，应该指定一个前缀长度，只要有可能就应该这样做。例如，如果有一个CHAR(200) 列，如果在前10 个或20 个字符内，多数值是唯一的，那么就不要对整个列进行索引。对前10 个或20 个字符进行索引能够节省大量索引空间，也可能会使查询更快。较小的索引涉及的磁盘I/O 较少，较短的值比较起来更快。更为重要的是，对于较短的键值，索引高速缓存中的块能容纳更多的键值，因此，MySQL也可以在内存中容纳更多的值。这增加了找到行而不用读取索引中较多块的可能性
不要过度索引
每个额外的索引都要占用额外的磁盘空间，并降低写操作的性能。在修改表的内容时，索引必须进行更新，有时可能需要重构，因此，索引越多，所花的时间越长。
考虑在列上进行的比较类型
索引可用于“ <”、“ < = ”、“ = ”、“ > =”、“ > ”和BETWEEN 运算。
尽量选择区分度高的列作为索引，区分度的公式是 COUNT(DISTINCT col) / COUNT(*)，表示字段不重复的比率，比率越大我们扫描的记录数就越少。

什么时候不创建索引

1、表记录太少
如果一个表只有5条记录，采用索引去访问记录的话，那首先需访问索引表，再通过索引表访问数据表，一般索引表与数据表不在同一个数据块，这种情况下至少要往返读取数据块两次。而不用索引的情况下ORACLE会将所有的数据一次读出，处理速度显然会比用索引快。

2、唯一性太差的字段
如状态字段、类型字段。那些只存储固定几个值的字段，例如用户登录状态、消息的status等。
这个涉及到了索引扫描的特性。例如：通过索引查找键值为A和B的某些数据，通过A找到某条相符合的数据，这条数据在X页上面，然后继续扫描，又发现符合A的数据出现在了Y页上面，那么存储引擎就会丢弃X页面的数据，然后存储Y页面上的数据，一直到查找完所有对应A的数据，然后查找B字段，发现X页面上面又有对应B字段的数据，那么他就会再次扫描X页面，等于X页面就会被扫描2次甚至多次。以此类推，所以同一个数据页可能会被多次重复的读取，丢弃，在读取，这无疑给存储引擎极大地增加了IO的负担。

1	select * from tb where gender='男'

这种不仅需要扫描这个索引而且要去取有‘男’的数据块基本覆盖了整个表所涉及的数据块。

3、更新频繁的字段
当你为这个字段创建索引时候，当你再次更新这个字段数据时，数据库会自动更新它的索引，所以当这个字段更新太频繁的时候，那么就是不断的更新索引。如果一个字段同一个时间段内被更新多次，那么不能为他建立索引。

思考

InnoDB索引为什么不建议使用过长的字段作为主键

因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大

为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？

InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。

如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。

如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：

此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

为什么非主键索引结构叶子节点存储的是主键值？

1、节省空间
根据主键就可以找到主键索引中对应的叶子节点，不用再多存储一份相同的数据。

2、数据一致性
如果主键索引结构和非主键索引结构都含有相同的数据，那么在更新数据的时候，就要同时更新两个索引结构

什么时候用MyISAM，什么时候用Innodb?

主要区别：
1).MyISAM是非事务安全型的，而InnoDB是事务安全型的。
2).MyISAM锁的粒度是表级，而InnoDB支持行级锁定。
3).MyISAM支持全文类型索引，而InnoDB不支持全文索引。
4).MyISAM相对简单，所以在效率上要优于InnoDB，小型应用可以考虑使用MyISAM。
5).MyISAM表是保存成文件的形式，在跨平台的数据转移中使用MyISAM存储会省去不少的麻烦。
6).InnoDB表比MyISAM表更安全，可以在保证数据不会丢失的情况下，切换非事务表到事务表（alter table tablename type=innodb）。

应用场景：
1).MyISAM管理非事务表。它提供高速存储和检索，以及全文搜索能力。如果应用中需要执行大量的SELECT查询，那么MyISAM是更好的选择。
2).InnoDB用于事务处理应用程序，具有众多特性，包括ACID事务支持。如果应用中需要执行大量的INSERT或UPDATE操作，则应该使用InnoDB，这样可以提高多用户并发操作的性能。

INNODB的行级锁是有条件的。在where条件没有使用主键时，照样会锁全表。

主索引和辅助索引

一个主文件仅有一个主索引，但可以有多个辅助索引

myisam 和 innodb中count(*)查询快慢原理

在myisam中count(*)查询,myisam引擎很容易获得总行数的统计。查询速度变得更快。因为myisam存储引擎已经存储了表的总行数。每次新增加一行,这个计数器就加1。也就是说，把表的总数缓存在索引中了。

注意:

myisam存储引擎的表，count()速度快的也仅仅是不带where条件的count。这个想想容易理解的，因为你带了where限制条件，原来所以中缓存的表总数能够直接返回用吗？不能用。这个查询引擎也是需要根据where条件去表中扫描数据，进行统计返回的。

针对Innodb表,尽量不执行 SELECT COUNT() 语句,因为Innodb表没有类似MyISAM那样的内部计数器来记录表记录总量,执行这个操作将会全表扫描,速度很慢。所以呢，表的行数越多，扫描的时间就越多。当你表行数还是小数量的时候体会不出速度差距。比如百万也感觉不出明显。上千万就会很明显速度差别了。

哪些列比较适合做索引

用于索引的最好的备选数据列是那些出现在WHERE子句、JOIN子句、ORDER BY或GROUP BY子句中的列，仅仅出现在SELECT关键字后面的输出数据列列表中的数据列不是很好的备选列。

在mysql中执行查询时，只能使用一个索引，如果我们在lname,fname,age上分别建索引,执行查询时，只能使用一个索引，mysql会选择一个最严格(获得结果集记录数最少)的索引。