在平时的工作当中，感觉很多人经常都会碰到慢sql的情况，也就是说执行一条sql语句可能需要几十秒甚至更长时间，那么这种情况出现，其实大家就可以考虑sql优化的问题的，关于sql 优化，相信大部分人首先想到的就是索引，那么关于索引的使用为什么能提高数据的检索速度？索引的一些原理是什么？加了索引后索引有没有失效？等一些问题可能很多人都不明白，其实关于数据库优化，不仅是工作当中我们经常需要考虑到的问题，包括换工作在面试的时候也是一个会经常被问到的。当然数据优化不仅仅是加索引的问题，关于大家可以自行百度，这篇文章主要讲索引底层数据结构相关原理及区别。
假如现在有一张学生学习表student_info ，包含主键，名称，学号，年龄 字段
索引的本质
索引是帮助MySQL高效获取数据的
排好序
的
数据结构
。另外在学习索引的时候，都知道索引是占实际内存的，也就是说索引不是说建的越多越好。为什么说索引是排好序的数据结构，使用索引和不使用索引有什么区别：
例如 现在使用age字段作为索引查询年龄等于19岁的学生信息，select * from student_info where age = 19;
没有使用索引的情况先，sql是全表检索，从第一条开始，逐条开始判断，然后返回满足条件的记录数据，就拿学生信息表来说，需要检索4次。如果是使用索引，数据结构来检索呢？可以看到下图二叉树的一个数据结构，检索的因为19大于18直接走右边，那么其实只要检索3次就能找到年龄等于19岁的记录。
可想而知，如果表的数据比较大的时候，全表逐条数据检索就需要耗时比较长，这个大家就可以明显感觉出使用和不使用索引的区别（当然索引的数据结构不是二叉树，这里只是那二叉树来讲个例子，其实索引的数据结构是B+树，下面关于为什么是B+树，不是其他数据结构也有介绍）。
索引数据结构二叉树、红黑树、B+树详解
二叉树：
二叉树特点
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。 4）二叉树的右边的数一定大于左边的数。
上面在使用二叉树描述使用索引和不使用索引的区别已经讲了二叉树的原理，那么为什么二叉树不是MySQL索引的数据结构的？因为二叉树存在斜树的情况（如下图 ），比如，学生信息表，使用主键作为索引去查找数据，select * from where id = 7， 根据上图分析，大家可以发现，二叉树斜树的情况下查询数据和不使用检索的效果都是一样的，都是检索7次，这也就是二叉树的弊端。
红黑树：
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
注意：
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
如上图，统一是主键id，使用红黑树的数据结构存储图，根据和二叉树数斜树的情况分析，可以明显看得出和二叉树的区别，前面有介绍到MySQL的索引是B+树，不是二叉树也不是红黑树，大家可以想想红黑树又有什么弊端？
现在我们介绍的学生信息表，数据只有几条，假如表单数据有成千上百万条数据，如果数据量比较大的时候，因为红黑树每个节点只能有两个叶子节点，那么也就是说会导致树的高度比较大。因为索引的存储在磁盘中，每次检索都要和磁盘进行一次IO操作，如果需要查找的数据刚好是最小叶子节点，当树比较高的时候也就是说检索的次数也会比较多，再加上io的操作是比较消耗性能的，所以某个程度上来讲，索引使用红黑树的数据结构也是不合理的。红黑树不适用大数据量场景。
B-树与 B+树
基于红黑数据不适用大数据量的场景情况，对红黑树进行改，比如说现在红黑树的高度是20，那有没有什么方法说可以控制树的高度不能大于5呢？同样大的数据量，只要能控制树的高度不大于5，那么sql在进行数据检索的时候就减少的磁盘的IO操作，从这个角度来说也就提高了数据检索的速度。其实基于对红黑树的这个改造也就是B 树的数据结构（对单节点进行了扩容，是单个节点不再只是存储一条数据）。下图大家可以看出每个节点 不在只是存储一个索引，而是存储多个。
B+树是B树的一个升级改造版，最只要的区别是：B+树的非叶子节点只存储索引不存储数据
B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间（
非子节点不存储数据，只存储索引，这样就可以更好的利用节点空间，存放更多的索引
），让查询
速度
更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别
（1）B+跟B树不同B+树的
非叶子
节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个
非叶子
节点所能保存的关键字大大增加；
（2）B+树
叶子
节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
（4）非叶子节点的子节点数=关键字数。
（以上对红黑树的改造，有人可能会有疑问，既然说要控制数的高度，那干嘛不直接都放在一个节点上，这样就可以只进行一次磁盘IO操作，有个疑问的朋友可以想想，数据量特别大的时候，一次性把所有的数据放在一个节点上是很占用存储内存的，也就是说欲速则不达，所以关于B+树和B树的节点有一个合理的大小，
SHOW GLOBAL STATUS LIKE ‘innodb_page_size’;
可以使用这个命令来查看非叶子节点的大小，可以看到非叶子节点大小为16384个字节，相当于16KB，为什么设置这个大小大家可以自行百度，
因为非叶子节点的大小是固定的，所以说B+树的非叶子节点不存储数据可以节省更多的存储空间，存放更多的索引
）
通常在
B+Tree
上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的
范围查找
和
分页查找
，另一种是从根节点开始，进行
随机查找
。
可能上面例子中只有22条数据记录，看不出B+Tree的优点，下面做一个推算：
InnoDB存储引擎中页的大小为16KB，一般表的主键类型为
INT
（占用4个字节）或
BIGINT
（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值。（因为是估值，为方便计算，这里的K取值为〖10〗3）。也就是说一个深度为3的B+Tree索引可以维护103 * 10^3 * 10^3 = 10亿 条记录。
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在24层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要13次磁盘I/O操作。
数据库中的B+Tree索引可以分为聚集索引（clustered index）和 辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为
聚集索引
，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。
辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。
查看mysql文件页大小（16K）：SHOW GLOBAL STATUS like ‘Innodb_page_size’;
Hash数据结构
定义
：
散列表
（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的
数据结构
。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做
散列函数
，存放记录的
数组
叫做
散列表
。 对目标值进行hash运算得到hash值和数据磁盘指针地址保存到hash表，这样就达到快速定位数据位置。
缺点
：精确查找十分快速，但范围查找就碰壁了。
以上简单讲解了索引的概念以及索引相关的数据存储结构，接下来简单介绍以下索引在表不同的存储引擎中数据是如何存储的？
MySQL存储引擎
什么是存储引擎？
数据库存储引擎是数据库底层软件组件，数据库管理系统使用数据引擎进行创建、查询、更新和删除数据操作。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能，使用不同的存储引擎还可以获得特定的功能。（
注意，MySQL的存储引擎是表级的，同一个数据库的不同表可以使用不同的引擎
）
现在许多数据库管理系统都支持多种不同的存储引擎。MySQL 的核心就是存储引擎。
- InnoDB 事务型数据库的首选引擎，支持事务安全表（ACID），支持行锁定和外键。MySQL 5.5.5 之后，InnoDB 作为默认存储引擎。
- MyISAM 是基于 ISAM 的存储引擎，并对其进行扩展，是在 Web、数据仓储和其他应用环境下最常使用的存储引擎之一。MyISAM 拥有较高的插入、查询速度，但不支持事务。
- MEMORY 存储引擎将表中的数据存储到内存中，为查询和引用其他数据提供快速访问。
MySQL
支持多种类型的数据库引擎，可分别根据各个引擎的功能和特性为不同的数据库处理任务提供各自不同的适应性和灵活性。在 MySQL 中，可以利用
SHOW ENGINES
语句来显示可用的数据库引擎和默认引擎。
可以使用
SHOW ENGINES
语句查看系统所支持的引擎类型，结果如图所示。
如何选择 MySQL 存储引擎
不同的存储引擎都有各自的特点，以适应不同的需求，如表所示。为了做出选择，首先要考虑每一个存储引擎提供了哪些不同的功能。
|
功能 |
MylSAM |
MEMORY |
InnoDB |
Archive |
|---|---|---|---|---|
| 存储限制 | 256TB | RAM | 64TB | None |
| 支持事务 | No | No | Yes | No |
| 支持全文索引 | Yes | No | No | No |
| 支持树索引 | Yes | Yes | Yes | No |
| 支持哈希索引 | No | Yes | No | No |
| 支持数据缓存 | No | N/A | Yes | No |
| 支持外键 | No | No | Yes | No |
可以根据以下的原则来选择 MySQL 存储引擎：
- 如果要提供提交、回滚和恢复的事务安全（ACID 兼容）能力，并要求实现并发控制，InnoDB 是一个很好的选择。
- 如果数据表主要用来插入和查询记录，则 MyISAM 引擎提供较高的处理效率。
- 如果只是临时存放数据，数据量不大，并且不需要较高的数据安全性，可以选择将数据保存在内存的 MEMORY 引擎中，MySQL 中使用该引擎作为临时表，存放查询的中间结果。
- 如果只有 INSERT 和 SELECT 操作，可以选择Archive 引擎，Archive 存储引擎支持高并发的插入操作，但是本身并不是事务安全的。Archive 存储引擎非常适合存储归档数据，如记录日志信息可以使用 Archive 引擎。
提示
：使用哪一种引擎要根据需要灵活选择，一个数据库中多个表可以使用不同的引擎以满足各种性能和实际需求。使用合适的存储引擎将会提高整个数据库的性能。
使用下面的语句可以修改数据库临时的默认存储引擎
SET default_storage_engine=< 存储引擎名 >
注意：将 MySQL 数据库的临时默认存储引擎修改为 其他的存储引擎时 ，但是当再次重启客户端时，默认存储引擎仍然是 InnoDB。
MyISAM存储引擎
MyISAM采用的是索引与数据分离的形式，将数据保存在三个文件中
.frm
、
.MYD
、
.MYI
。
- .frm : 存储表结构
- .MYD ： 存储表数据
- .MYI ：存储表索引
MyISAM索引文件和数据文件是分离的(
非聚集
)
MyISAM提供了大量的特性，包括全文索引，压缩，空间函数，延迟更新索引键等。
-
进行压缩后的表是不能进行修改的，但是压缩表可以极大减少磁盘占用空间，因此也可以减少磁盘IO，从而提供查询性能。
-
全文索引，是一种基于分词创建的索引，可以支持复杂的查询。
-
延迟更新索引键，不会将更新的索引数据立即写入到磁盘，而是会写到内存中的缓冲区中，只有在清除缓冲区时候才会将对应的索引写入磁盘，这种方式大大提升了写入性能。
InnoDB存储引擎
使用InnoDB时，会将数据表分为
.frm
和
.ibd
两个文件进行存储。
- .frm : 存储表结构
- .ibd : 存储表数据和索引
innodb的所有数据文件（后缀为ibd的文件），他的大小始终都是16384（16k）的整数倍。
InnoDB索引实现(聚簇)
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚簇索引-叶节点包含了完整的数据记录
- 为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
- 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间，使用非主键索引检索数据需要检索两个树)
其他
由表文件结构就可以看出，InnoDB是支持聚集索引的，它的表数据文件和索引文件放在一起。
-
为什么InnoDB非聚集索引的辅助键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
因为如果InnoDB的辅助键也将行数据全部存到叶子节点，虽然能避免使用辅助键索引进行检索的时候需要检索两次才找到行数据，但是这样会造成冗余的存储数据（因为同一份数据在物理存储器中只能存放在同一个位置，如果像上面这样在非聚集索引中也将表数据存在叶子节点，就只能在存储器中冗余的存两份相同的表数据），同一份数据在硬盘中存储两次，就会造成数据浪费，还有一点就是同一份数据存在两个索引上，一旦对数据库的数据进行修改，还需要保证两颗索引树的数据一致性，这又是一个很麻烦的事情，所以辅助键索引树的叶子节点存储主键值，可以节约空间和保证数据一致性，修改行数据只需要修改主键索引中的行数据就可以了，不需要再对辅助索引进行修改。
-
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？不用UUID
由上面的辅助键索引的检索过程可以看出，辅助键索引必须依赖于主键索引才能查找到完整的行数据，表数据就存在主键索引树中，所以InnoDB引擎必须要有主键索引，如果自己不设置主键索引InnoDB也会自己选一列作为索引，如果自己建的表中没有合适的列作为索引，InnoDB也会自动创建一个隐藏列来作为主键。使用整型自增的主键是为了方便检索，很显然整型数据的比较效率要高于随机ASCII码字符串的比较。
-
如果InnoDB引擎的表自己不主动定义主键，那么MySQL会自己想办法创建主键，过程如下：
- 如果没有为表定义PRIMARY KEY，MySQL将找到第一个UNIQUE索引，其中所有键列都是NOT NULL，而InnoDB将它用作聚集索引。
- 如果表没有PRIMARY KEY或合适的UNIQUE索引，InnoDB会在包含行ID值的合成列内部生成名为GEN_CLUST_INDEX的隐藏聚集索引 。这些行按InnoDB分配给此类表中的行的ID排序。行ID是一个6字节的字段，在插入新行时会单调增加。因此，由行ID排序的行在物理上处于插入顺序。
-
之前一直有一个误区，认为主键索引就是聚集索引
纠正一下这个误区，因为MySQL的默认存储引擎是InnoDB,所以创建的主键索引就是聚集索引。其实主键索引和聚集索引并没有必然联系，非聚集索引也有主键索引。聚集索引只是一种数据存储的方式，不同的存储引擎有不同的实现。只是因为MySQL默认是InnoDB引擎，所以创建的主键也就默认是聚集索引。即主键是聚集索引还是非聚集索引取决于这个表的存储引擎是InnoDB还是MyISAM。
-
名词解释
Clustered Index
：聚集索引，又称聚簇索引。
Nonclustered indexes
：非聚集索引，又称非聚簇索引。
Secondary Key
：二级索引，因为聚集索引只能有一个，所有同一个表其他字段只能是二级索引也就是非聚集索引。
InnoDB
的
索引与
MyISAM
的索引
的区别
为了更形象说明这两种存储引擎中的索引的区别，我们假想一个表如下图存储了4行数据。其中Id作为主索引，Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。
我们重点关注聚簇索引，看上去InnoDB的效率明显要低于MyISAM，因为每次使用辅助索引检索都要经过两次B+树查找，而MyISAM的非聚集索引使用辅助键查询只需要一次就能找到一整行的元组数据。这不是多此一举吗？
聚簇索引的优势在哪？
1 由于行数据和叶子节点存储在一起，这样主键和行数据是一起被载入内存的，找到叶子节点就可以立刻将行数据返回了，而
不用再通过存储的地址再去硬盘中查询一次数据行
，如果按照主键Id来组织数据，获得数据更快。
2 辅助索引使用主键作为”指针” 而不是使用地址值作为指针的好处是，减少了当出现行移动或者数据页分裂时辅助索引的维护工作，使用主键值当作指针会让辅助索引占用更多的空间，换来的好处是InnoDB在移动行时无须更新辅助索引中的这个”指针”。也就是说
行的位置（实现中通过16K的Page来定位，详细可以看计算机操作系统分页管理相关章节）会随着数据库里数据的修改而发生变化（B+树节点分裂以及Page的分裂）
，使用InnoDB就可以保证不管这个主键B+树（聚集索引）的节点如何变化，辅助索引树（非聚集索引）都不受影响。
3 聚集索引的数据都是按顺序存放的，所以如果查询条件是主键，使用主键索引，那么聚集索引会非常快，因为相同范围段的数据都是连续存放在一起的。即聚集索引表记录的
物理排列顺序
与索引的
逻辑排列顺序
一致，优点是查询速度快，一旦符合条件的第一个索引值的纪录被找到，具有连续索引值的记录也一定物理的紧跟其后。聚集索引的主键索引的叶子节点中直接存储行数据，又因为B+树的叶子节点之间都会用过指针相连，所以直接就能很快将这个范围内的数据全部获取。但是非聚集索引的主键索引虽然在逻辑上相同范围的叶子节点是顺序存储在一起的，但是真实的行数据是在硬盘中散列存储的，要想获取数据还需要将存储在叶子节点中的地址取出，根据地址再去硬盘中获取数据，效率就慢了很多。这个是聚集索引的主键索引的优势，也是第一条优势的具体体现。根据
局部性原理
，这也会提高检索效率。
局部性原理是指
CPU
访问
存储器
时，无论是存取指令还是存取数据，所访问的
存储单元
都趋于聚集在一个较小的连续区域中。
聚集索引的劣势有哪些？
1 聚集索引的缺点是对表进行修改速度较慢，这是为了保持表中的记录的物理顺序与索引的顺序一致，而把记录插入到数据页的相应位置，必须在数据页中进行数据重排，降低了执行速度。插入数据时速度要慢(时间花费在“物理存储的排序”上，也就是首先要找到位置然后插入)。而非聚集索引指定了表中记录的逻辑顺序，但记录的物理顺序和索引的顺序不一致，聚集索引和非聚集索引都采用了B+树的结构，但非聚集索引的叶子层并不与实际的数据页相重叠，而采用叶子层包含一个指向表中的记录在数据页中的指针的方式（这个指针可能是真实的物理地址，也可能是对应的主键值，这根据不同的存储引擎对它实现是不同的）。非聚集索引比聚集索引层次多，添加记录不会引起数据顺序的重组。
总的来说，聚集索引查询数据速度快，插入数据速度慢;非聚集索引反之。他们各自优缺点就是相反的。所以非聚集索引的优缺点看上面聚集索引的优缺点就够了。
联合索引
比较相等时，先比较第一列的值，如果相等，再继续比较第二列，以此类推。
使用联合索引时，索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引（a,b,c），mysql会从最左边的列优先匹配，如果最左边的带头大哥没有使用到，在未使用覆盖索引的情况下，就只能全表扫描。
联合底层数据结构思考，mysql会优先以联合索引第一列匹配，此后才会匹配下一列，如果不指定第一列匹配的值，也就无法得知下一步查询哪个节点。
另外还有一种情况，如果遇到 > < between等这样的范围查询，那B+树中也就无法对下一列进行等值匹配了。
比如 上图中，select * from t where id=’10001′ and name = ‘assistant’; 会走联合索引，select * from t where name = ‘assistant’; 或者 select * from t where time=’2001-09-03′ ;则不走索引。原因：根据上图可以看出，10001-10003是按顺序排序的，也就是说联合索引是按最做变的字段进行一个排序，如果直接跳过id，直接使用name或者time ，因为是没有排序的，所以不走索引。