搞懂Mysql索引原理及应用，这一篇就够了！

什么是索引？

索引是对数据库表中一列或多列的值进行排序的一种数据结构，使用索引可以快速访问数据库表中的特定信息。

我们创建索引的时候是这样的：

create index index_name on table_name(column)

可以这样想：索引是取出了一列或者几个特殊的列，然后把他们重命名为index_name，然后存起来，存的方式是用特殊的数据结构，比如二叉树。

索引中包含了一个表中列的值和它的地址的值，并且这些值存储在一个数据结构中。索引的组织形式有二叉树、哈希、B-树、B+树。如果索引存的是一列就叫做单索引，多列就是复合索引。

索引一般以文件形式存在磁盘中（也可以存于内存），存储索引的原理大致概括为以空间换时间。

索引能干什么？

执行这样一条语句：

select name from student where stuno = "003"

在一张学生表里面找学号是003的学生，假如一共到100号学生。那么DBMS会生成一个类似指针的东西，从stuno ="001"一直到最后，进行全表扫描。那么为什么到stuno="003"不停止呢？因为数据库在未添加索引的时候默认执行的是全量搜索，select执行就就是全表扫描，即使扫描主键也一样。

如果我们在stuno字段上创建了一个索引，假如索引的底层存储结构是二叉树，那么只需要log2(100)次就能查到所需要的数据。因此，建立索引的目的就是加快对表中记录的查找或排序。

当然索引不是万能的，它的缺点有：创建和维护索引需要时间和空间成本，每次增删改索引都需要进行动态维护。

索引的分类

索引类型有：主键索引，普通索引，复合索引，全文索引，唯一索引

主键索引

--创建1crete table student(id int primary key auto_increment, name varchar(20) not null default)--创建2：先创建表，后创建indexalter table student add primary key(id)--在创建主键的时候，就会为我们创建好主键索引。

唯一索引

唯一索引和普通索引类似，主要区别在于，唯一索引限制列的值必须唯一，但允许存在空值（只能有一个）。主键索引不允许有空值。
全文索引

在执行模糊查询的时候，如
```
like "value%"
```
，这种情况下，需要考虑使用全文搜索的方式进行优化。全文搜索在MySQL中是一个FULLTEXT类型索引。全文索引主要用来查找文本中的关键字，而不是直接与索引中的值进行比较，它更像是一个搜索引擎，而不是简单的where语句的参数匹配。目前只有char/vachar/text列上可以创建全文索引，默认Mysql不支持中文全文搜索。Mysql全文搜索只是一个临时方案，对于全文搜索场景，更专业的做法是使用全文搜索引擎，如ElasticSearch。

索引底层原理

哈希表

select * from user where id=7;

哈希算法首先计算出id=7的无力地址addr=hash(7)=4213，而4213映射的物理地址是0x77，然后就可以找到我们想要的数据了。

从时间复杂度来看，哈希算法时间复杂度为o(1)，速度非常快，但是Mysql并没有采取哈希作为其底层算法。**因为考虑到数据检索有一个常用的手段就是范围查找，使用哈希就没有办法做到高效的范围查找。**比如：

select * from user where id>3

BST树

二叉查找树的时间复杂度是O(logn)，从检索效率上看是能做到高效检索，而二叉树所有左子树比根节点小，右子树比根节点大的特性使得它也支持范围查找。

但是二叉树有个致命缺点：极端情况下会退化为线性表。在数据库中，数据的自增是一个很常见的形式，比如主键id一般默认都是自增的，如果采取二叉树作为索引的底层数据结构，那上面介绍的不平衡状态导致的线形查找问题必然出现！！！因此，简单的二叉树不能直接用于实现Mysql底层索引的。

AVL树和红黑树

学过数据结构的都知道，解决二叉树不平衡导致的性能问题，就是二叉平衡树。通过调整树的结构，来达到高度的平衡状态，但是频繁的调整树的结构也是一种开销，而红黑树就是舍去一部分的平衡性来获得低的调整开销。但是红黑树也存在“右倾现象”，查找性能又会降低。因此在查找性能和调整树的开销之间很难找到一种平衡，也不适合作为Mysql底层索引结构。

有人会问：数据库查询数据的瓶颈在于磁盘IO，调整树的开销存在于增删，而查找不需要调整，为什么AVL树不适合呢？

答：AVL不是不适合，而是有更好的数据结构。我们知道磁盘IO有一个特点，就是从磁盘读取1B的数据和1KB的数据所消耗的时间基本是一样的，那我们的优化思路就可以改为：尽可能在一次磁盘 IO 中多读一点数据到内存。这个直接反映到树的结构就是，每个节点能存储的 key 可以适当增加，这就是B树、B+树的设计原理了。

B树和B+树

B树和B+树又被称为多路查找，一个节点存储了多个key来减少磁盘IO，从而提高检索速度。

B树和B+树有什么区别呢？

B树一个节点里面存的是（key&value），而B+树存储的是（key），所以B树里一个节点存不了很多（key&value），但是B+树一个节点能存储很多（key），B+树叶子节点存所有的数据。
B+树的叶子节点是（key&value，并用一个链表串联起来。

通过 B 树和 B+树的对比我们看出，B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。

Mysql存储引擎实现

Mysql底层数据引擎以插件形式设计，最常见的就是Innodb引擎和Myisam引擎，用户可以根据个人需求选择不同的引擎作为Mysql数据表的底层引擎。我们刚分析了，B+树作为 Mysql 的索引的数据结构非常合适，但是数据和索引到底怎么组织起来也是需要一番设计，设计理念的不同也导致了 Innodb 和 Myisam 的出现，各自呈现独特的性能。

MyISAM 虽然数据查找性能极佳，但是不支持事务处理。Innodb 最大的特色就是支持了 ACID 兼容的事务功能，而且他支持行级锁。Mysql 建立表的时候就可以指定引擎，比如下面的例子，就是分别指定了 Myisam 和 Innodb 作为 user 表和 user2 表的数据引擎。

create table \'user\' (\'id\' int not null default \'0\') engine=myisam default charset=utf8

Innodb创建表后生成的文件有：

frm：创建表的语句
idb：表里面的数据+索引文件

Myisam创建表后生成的文件有：

frm：创建表的语句
MYD：表里面的数据文件
MYI：表里面的索引文件

从生成的文件看来，这两个引擎底层数据和索引的组织方式并不一样，MyISAM 引擎把数据和索引分开了，一人一个文件，这叫做非聚集索引方式；Innodb 引擎把数据和索引放在同一个文件里了，这叫做聚集索引方式。下面将从底层实现角度分析这两个引擎是怎么依靠 B+树这个数据结构来组织引擎实现的。

MyISAM引擎的底层实现（非聚集索引方式）

MyISAM 用的是非聚集索引方式，即数据和索引落在不同的两个文件上。MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树，树的叶子节点存的是对应数据的物理地址。我们拿到这个物理地址后，就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。

当我们为某个字段添加索引时，我们同样会生成对应字段的索引树，该字段的索引树的叶子节点同样是记录了对应数据的物理地址，然后也是拿着这个物理地址去数据文件里定位到具体的数据记录。

Innodb引擎的底层实现（聚集索引方式）

InnoDB 是聚集索引方式，因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树，如左下图所示，而 B+树的叶子节点存储的是主键 ID 对应的数据，比如在执行 select * from user_info where id=15 这个语句时，InnoDB 就会查询这颗主键 ID 索引 B+树，找到对应的 user_name=\’Bob\’。

这是建表的时候 InnoDB 就会自动建立好主键 ID 索引树，这也是为什么 Mysql 在建表时要求必须指定主键的原因。当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢？比如我们要给 user_name 这个字段加索引，那么 InnoDB 就会建立 user_name 索引 B+树，节点里存的是 user_name 这个 KEY，叶子节点存储的数据的是主键 KEY。注意，叶子存储的是主键 KEY！拿到主键 KEY 后，InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。

问题来了，为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据，但是其他索引树却不存具体数据呢，而要多此一举先找到主键，再在主键索引树找到对应的数据呢?

其实很简单，因为 InnoDB 需要节省存储空间。一个表里可能有很多个索引，InnoDB 都会给每个加了索引的字段生成索引树，如果每个字段的索引树都存储了具体数据，那么这个表的索引数据文件就变得非常巨大（数据极度冗余了）。从节约磁盘空间的角度来说，真的没有必要每个字段索引树都存具体数据，通过这种看似“多此一举”的步骤，在牺牲较少查询的性能下节省了巨大的磁盘空间，这是非常有值得的。

两种存储引擎对比

在进行 InnoDB 和 MyISAM 特点对比时谈到，MyISAM 查询性能更好，从上面索引文件数据文件的设计来看也可以看出原因：MyISAM 直接找到物理地址后就可以直接定位到数据记录，但是 InnoDB 查询到叶子节点后，还需要再查询一次主键索引树，才可以定位到具体数据。等于 MyISAM 一步就查到了数据，但是 InnoDB 要两步，那当然 MyISAM 查询性能更高。

使用索引的注意事项！！！！

Mysql索引使用策略

最好全值匹配–索引怎么建我怎么用。
最佳左前缀法则–如果是多列复合索引，要遵守最左前缀法则。指的是查询要从索引的最左前列开始并且不跳过索引中的列。
不在索引列上做任何操作（计算，函数，（自动或者手动）类型装换），会导致索引失效而导致全表扫描。
存储引擎不能使用索引中范围条件右边的列。–范围之后索引失效（< ,>,between and）
尽量使用覆盖索引–索引和查询列一致，减少select *。–按需取数据用多少取多少
在MYSQL使用不等于（<,>,!=）的时候无法使用索引，会导致索引失效
is null或者is not null 也会导致无法使用索引
like以通配符开头（\’%abc…\’）MYSQL索引失效会变成全表扫描的操作。–覆盖索引
隐式转换索引失效：字符串不加单引号
where条件少用or，用它来连接时索引会失效

Mysql索引使用原则

复合索引：选择索引列的顺序

1)尽量把字段长度小的列放在联合索引的最左侧（因为字段长度越小，一页能存储的数据量越大，IO性能也就越好）2)区分度最高的放在联合索引的最左侧（区分度=列中不同值的数量/列的总行数）3)使用最频繁的列放到联合索引的左侧（这样可以比较少的建立一些索引）

表关联查询

1)类型和大小要相同，可以使用索引。VARCHAR(10)和 CHAR(10)大小相同，但 VARCHAR(10)与 CHAR(15)不相同。2)字符串列之间比较，两列应使用相同的字符集。例如，将utf8列与 latin1列进行比较会不使用索引。3)将字符串列与时间或数字列进行比较时，在没有转换情况下,不使用索引。

什么字段适合创建索引？

较为频繁的作为查询条件的字段应该创建索引
唯一性太差的字段不适合单独创建索引，即使该字段频繁作为查询条件
更新非常频繁的字段不适合创建索引