当你有一张一百万数据的表且没有加索引优化的话，查询一条记录的速度为0.5秒
而当你加入索引后，查询一条记录的速度为0.024秒
速度相差了20倍，这是一条创建MySql索引的语法
ALTER TABLE <表名> ADD INDEX (<列名>);
在创建索引后，发生了什么？为什么添加索引后能产生这么大的变化?
1. 什么是索引？
要弄懂索引的查询为何如此之快，我们需要先知道索引是什么。
索引在MySql是帮助MySql高效获取数据的排好序的数据结构。而在程序中，包含了很多种的索引，比如二叉树，红黑树，B树，b+树
它为什么能产生如此高效的查询
1.1 那么在mysql中索引的数据结构是怎么样的？
1.1.2 二叉树排序树做索引
当让我们去设计一个存储数据的索引时，可以从最简单的二叉树排序树出发，利用它设计MySql的索引。
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。
若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树；
当我们往其中持续插入数据时，比如 {1，2，3，4，5，6，7}，产生的树形结构如下图
此时我们通过查询当中的某一个数值，比如5，那么将会执行5次才获取到数据，这样的查询效果并不令人满意，因为假如是链表也可以满足这个需求
1.1.3 红黑树做索引
换一种数据结构试试，比如红黑树，也是二叉平衡树，Java用它来实现TreeMap。
红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 结点是红色或黑色。
性质2. 根结点是黑色。
性质3. 所有叶子都是黑色。（叶子是NIL结点）
性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。
依然用我们之前的数据例子，{1，2，3，4，5，6，7}，得到的属性结构如图：
此时我们进行查询数据 5 的话，需要4步才能找到，比二叉排序树要好一些。
那么如果我们使用它作为MySql的索引会发生什么？
如果是100万的数据量，此时，通过公式 $[2^=1000000]$ ，其中n为树形结构产生的高度，当数据量是100万的时候，意味着$[n\approx 19.931569 ]$ ,而树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。那么查询一次的轮询也是非常耗时的。
更好的方案去存储索引，能不能将深度 n 控制在3-5 次之间，既要存储大量数据，又要控制深度，那么如果对红黑树进行改造一下呢？
在每个父节点的同级，增加横向节点，意味着产生的效果是这样的
而这就是B-Tree,
1.1.4 B-Tree做索引
B-tree（多路搜索树，并不是二叉的）是一种常见的数据结构。使用B-tree结构可以显著减少定位记录时所经历的中间过程，从而加快存取速度。
B-tree中，每个结点包含：
- 本结点所含关键字的个数；
- 指向父结点的指针；
- 关键字；
- 指向子结点的指针；
对于一棵m阶B-tree，每个结点至多可以拥有m个子结点。各结点的关键字和可以拥有的子结点数都有限制，规定m阶B-tree中，根结点至少有2个子结点，除非根结点为叶子节点，相应的，根结点中关键字的个数为1~m-1；非根结点至少有[m/2]（[]，向上取整）个子结点，相应的，关键字个数为[m/2]-1~m-1。
通过对B-Tree增加数据后，得到的效果是
这里要说一下B-Tree的特点
- 关键字集合分布在整棵树中；
- 任何一个关键字出现且只出现在一个结点中；
- 搜索有可能在非叶子结点结束；
- 其搜索性能等价于在关键字全集内做一次二分查找；
- 自动层次控制；
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最低搜索性能为：
其中，M为设定的非叶子结点最多子树个数，N为关键字总数；
所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题
由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；删除结点时，需将两个不足M/2的兄弟结点合并。
这看起来似乎已经满足了我们的要求，B-Tree搜索性能等价于在关键字全集内做一次二分查找，这样的搜索速度是相当快的，但是 B-Tree的每个节点都有data域（指针），这是什么意思呢？
也就是表示B-Tree的每个节点不仅包含了索引元素，而且存储了索引元素对应的数据，如图：
这无疑增加了节点大小，也就是增加了磁盘IO次数，而磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时。
MySql在此基础上进行了改变，使用B+Tree做索引
1.1.5 B+Tree做索引
B+Tree是B树的变种，有着比B树更高的查询性能，来看下m阶B+Tree特征：
- 有m个子树的节点包含有m个元素（B-Tree中是m-1）
- 根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。
- 所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。
- 叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小，从小到大顺序链接。
以上，当中有很重要的两个特征，
根节点和分支节点不保存数据，只用于索引，所有数据都保存在叶子节点中。
叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小，从小到大顺序链接
这便解决了B-Tree中data域的问题
当我们用数据插入的时候，得到的树形结构图是
对这张图进行解释说明一下
使用语法 show GLOBAL STATUS like 'Innodb_page_size'; 可以知道MySql中默认的页大小容量为多少
1.1.6 为什么B+Tree会这样进行存放？
以索引中的一个节点为例，索引元素占8个字节，而指向下一级索引的指针占4个字节，那么在这一层节点中，可以存储的元素数量有$\frac{16KB}{14B} = \frac{16*1024}{14} \approx 1170 $ ，假设树的高度是 n=3,满载情况下
$$
1170 \cdot 1170 \cdot 16 = 21902400
$$
这样经过3次磁盘IO就能找到2000万中的某一条数据
这样便解决了数据库中查询的问题。
当然，有经验的程序员都知道，在创建MySql索引的时候，我们还可以选择HASH，通过HASH去创建索引。
1.1.7 通过Hash表做索引
哈希算法时间复杂度为O(1)，且不只存在于索引中，每个数据库应用中都存在该数据结构。
哈希表也为散列表，又直接寻址改进而来。在哈希的方式下，一个元素k处于h(k)中，即利用哈希函数h，根据关键字k计算出槽的位置。函数h将关键字域映射到哈希表T[0...m-1]的槽位上。
Hash索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以Hash索引的查询效率要远高于B-Tree索引。
那么既然效率这么高，为什么不使用Hash索引而还要使用B+Tree索引呢？
当中的原因有：
- Hash索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。哈希索引只支持等值比较查询，包括**＝、 IN 、<=> ** (注意<>和＜＝＞是不同的操作）。 也不支持任何范围查询，例如WHERE price > 100。
由于Hash索引比较的是进行Hash运算之后的Hash值，所以它只能用于等值的过滤，不能用于基于范围的过滤
- Hash索引无法被用来避免数据的排序操作
- Hash索引不能利用部分索引键查询。对于组合索引，Hash索引在计算Hash值的时候是组合索引键合并后再一起计算Hash值，而不是单独计算Hash值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash索引也无法被利用。
- Hash索引在任何时候都不能避免表扫描。Hash索引是将索引键通过Hash运算之后，将 Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中，由于不同索引键存在相同Hash值，所以即使取满足某个Hash键值的数据的记录条数，也无法从Hash索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
- Hash索引遇到大量Hash值相等的情况（产生Hash冲突）后性能并不一定就会比BTree索引高。
对于选择性比较低的索引键，如果创建Hash索引，那么将会存在大量记录指针信息存于同一个Hash值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。
在基于上面的分析后，MySql的存储引擎索引实现并不完全就是这样
在mysql5之后，支持的存储引擎有十几个，但是常用的就那么几种，而且默认支持的也是InnoDB。我们可以通过命令 show ENGINES ; 知道当前MySql支持的存储引擎有哪些
| Engine | Support | Comment | Transacations | XA | Savepoints |
|---|
| MEMORY | YES | Hash based, stored in memory, useful for temporary tables | NO | NO | NO |
| MRG_MYISAM | YES | Collection of identical MyISAM tables | NO | NO | NO |
| CSV | YES | CSV storage engine | NO | NO | NO |
| FEDERATED | NO | Federated MySQL storage engine | | | |
| PERFORMANCE_SCHEMA | YES | Performance Schema | NO | NO | NO |
| MyISAM | YES | MyISAM storage engine | NO | NO | NO |
| InnoDB | DEFAULT | Supports transactions, row-level locking, and foreign keys | YES | YES | YES |
| BLACKHOLE | YES | /dev/null storage engine (anything you write to it disappears) | NO | NO | NO |
| ARCHIVE | YES | Archive storage engine | NO | NO | NO |
1.2 MyISAM存储引擎
首先这里需要提到的一点是：存储引擎是用来形容表的，而不是数据库的。可以对每一张表设计不一样的存储引擎。
1.2.1 锁的粒度
MyISAM不支持行锁，所以读取时对表加上共享锁，在写入是对表加上排他锁。由于是对整张表加锁，相比InnoDB，在并发写入时效率很低。
1.2.2 数据存储形式
MyISAM采用的是索引与数据分离的形式，将数据保存在三个文件中.frm.MYD,.MYIs。
1.2.3 事务
MyISAM不支持事务。
1.2.4 索引实现
MyISAM是基于非聚簇索引进行存储的。
这意味着，索引中存储的是磁盘文件指针，如下图中叶子节点 15下方的 0x07
1.2.5 其他
MyISAM提供了大量的特性，包括全文索引，压缩，空间函数，延迟更新索引键等。
进行压缩后的表是不能进行修改的，但是压缩表可以极大减少磁盘占用空间，因此也可以减少磁盘IO，从而提供查询性能。
全文索引，是一种基于分词创建的索引，可以支持复杂的查询。
延迟更新索引键，不会将更新的索引数据立即写入到磁盘，而是会写到内存中的缓冲区中，只有在清除缓冲区时候才会将对应的索引写入磁盘，这种方式大大提升了写入性能。
1.3 InnoDB存储引擎
1.3.1 数据存储形式
使用InnoDB时，会将数据表分为.frm 和 idb两个文件进行存储。
1.3.2 锁的粒度
InnoDB采用MVCC(多版本并发控制) 来支持高并发，InnoDB实现了四个隔离级别，默认级别是REPETABLE READ，并通过间隙锁策略防止幻读的出现。它的锁粒度是行锁。
1.3.3 事务
InnoDB是典型的事务型存储引擎，并且通过一些机制和工具，支持真正的热备份。
1.3.4 索引实现
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
聚集索引如下图
这里InnoDB涉及到的几个面试题
1.35 为什么InnoDB表必须要有主键？并且推荐整形的自增主键？
首先InnoDB中必须要有主键。B+Tree的索引设计使得表必须需要主键用来平衡B+Tree，如果自己没有设置主键，那么MySql会自行建立一列数据用作主键。
主键递增更适应B+Tree。自增的主键进行插入数据时，会在平衡后进行累加，而UUID因为不是自增，这个B+Tree会不停的进行平衡，消耗资源、时间。
1.3.6 UUID为什么不推荐被当作主键
这是因为UUID比较时会先转化为ASCII码，然后进行比较，这个转化加比较是费时的，而且UUID的字符表更长，更占用空间。
说完了两个MySql的存储引擎之后，还有一种辅助索引，用来告诉InnoDB哪里可以找到与索引相对应的行数据。
1.4 辅助索引（Secondary Index）
辅助索引说的是，叶子节点中存储主键值，每次查找数据时，根据索引找到叶子节点中的主键值，根据主键值再到聚簇索引中得到完整的一行记录。
辅助索引如下图
1.4.1 为什么要设计辅助索引(二级索引)？
InnoDB在移动行时，无需维护二级索引，因为叶子节点中存储的是主键值，而不是指针。
聚簇索引的叶子节点存储了一行完整的数据，而二级索引只存储了主键值，相比于聚簇索引，占用的空间要少。当我们需要为表建立多个索引时，如果都是聚簇索引，那将占用大量内存空间，所以InnoDB中主键所建立的是聚簇索引，而唯一索引、普通索引、前缀索引等都是二级索引。
也就是说，假如当进行插入数据，修改数据，需要维护主键索引，又要维护非主键索引，那么这对于大数据量的插入绝对是种灾难。所以辅助索引就是为了解决这个问题，插入和修改数据时，只要维护主键索引就行。
1.5 联合索引
联合索引是指对表上的多个列进行索引。
也就是说将多个字段放入叶节点进行索引排序，如下图演示
联合索引也是一棵B+树，其键值数量大于等于2。键值都是排序的，通过叶子节点可以逻辑上顺序的读出所有数据。
假设说创建联合索引
ALTER TABLE person ADD INDEX (`a`,`b`);
对于以下查询显然是可以使用（a，b）这个联合索引的
select * from table where a=xxx and b=xxx ;
select * from table where a=xxx;
参考文章:
算法可视化网站
如何计算B+树可以存放多少条数据
什么是B+Tree
mysql索引之哈希索引
浅谈MySQL存储引擎-InnoDB&MyISAM
聚集索引、辅助索引、覆盖索引、联合索引