搞懂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)次就能查到所需要的数据。因此，建立索引的目的就是加快对表中记录的查找或排序。

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

索引的分类

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

索引底层原理

哈希表

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索引使用策略

Mysql索引使用原则

什么字段适合创建索引？

来源：https://www.cnblogs.com/yrxing/p/14557150.html
图文来源于网络，如有侵权请联系删除。