一张表有 500 万条数据，在没有索引的 name 字段上执行一条 where 查询：
select * from user_innodb where name ='蔡徐坤';如果 name 字段上面有索引呢？在 name 字段上面创建一个索引，再来执行一下相同的查询。
ALTER TABLE user_innodb DROP INDEX idx_name; ALTER TABLE user_innodb ADD INDEX idx_name (name);有索引的查询和没有索引的查询相比，效率相差几十倍。
通过这个案例可以说明，索引对于数据检索的性能改善是非常大的。
那么索引到底是什么呢？为什么可以对我们的查询产生这么大的影响？创建索引的时候发生了什么事情？
维基百科对数据库索引的定义：
数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速查询、更新数据库表中数据。
看图： 数据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址。
如果没有索引的话，我们要从 500 万行数据里面检索一条数据，只能依次遍历这张表的全部数据，直到找到这条数据。
但是我们有了索引之后，只需要在索引里面去检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到数据了。
在 InnoDB 里面，索引类型有三种，普通索引、唯一索引、全文索引。
普通索引（INDEX）：也叫非唯一索引，是最普通的索引，没有任何的限制。
唯一索引（UNIQUE）：索引列的所有值都只能出现一次，即必须唯一。 另外需要注意的是，主键索引（PRIMAY KEY）是一种特殊的唯一索引，它还多了一个限制条件，要求键值不能为空。
全文索引（FULLTEXT）：针对比较大的数据，比如我们存放的是消息内容，有几 KB 的数据，如果要解决 like 查询效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如 char、varchar、text。
索引是一种数据结构，那么它到底应该选择一种什么数据结构，才能实现数据的高效检索呢？我们一起来推导一下。
(1) 使用 ALTER TABLE语句创建索引，应用于表创建完毕之后再添加。
ALTER TABLE 表名 ADD 索引类型 （unique,primary key,fulltext,index）[索引名]（字段名） 普通索引 alter table table_name add index index_name (column_list) ; 唯一索引 alter table table_name add unique (column_list) ; 主键索引 alter table table_name add primary key (column_list) ;ALTER TABLE可用于创建普通索引、唯一索引和主键索引这3种索引，table_name是要增加索引的表名，column_list指出对哪些列进行索引，多列时各列之间用逗号分隔。
索引名index_name可选，缺省时，MySQL将根据第一个索引列赋一个名称。
另外，ALTER TABLE允许在单个语句中更改多个表，因此可以同时创建多个索引。
(2) 使用 CREATE INDEX 语句对表增加索引。
CREATE INDEX可用于对表增加普通索引或唯一索引，可用于建表时创建索引。
CREATE 索引类型 index_name ON table_name(username(length));如果是CHAR，VARCHAR类型，length可以小于字段实际长度；如果是BLOB和TEXT类型，必须指定 length。
create只能添加这两种索引;
CREATE INDEX index_name ON table_name (column_list) CREATE UNIQUE index_name ON table_name (column_list)table_name、index_name和column_list具有与ALTER TABLE语句中相同的含义，索引名不可选。另外，不能用CREATE INDEX语句创建主键索引。
删除索引可以使用 ALTER TABLE 或 DROP INDEX 语句来实现。 DROP INDEX可以在ALTER TABLE内部作为一条语句处理，其格式如下：
drop index index_name on table_name ; alter table table_name drop index index_name ; alter table table_name drop primary key ;其中，在前面的两条语句中，都删除了table_name中的索引index_name。而在最后一条语句中，只在删除PRIMARY KEY索引中使用，因为一个表只可能有一个PRIMARY KEY索引，因此不需要指定索引名。如果没有创建PRIMARY KEY索引，但表具有一个或多个UNIQUE索引，则MySQL将删除第一个UNIQUE索引。
如果从表中删除某列，则索引会受影响。对于多列组合的索引，如果删除其中的某列，则该列也会从索引中删除。如果删除组成索引的所有列，则整个索引将被删除。
双十一过去之后，你女朋友跟你玩了一个猜数字的游戏。
猜猜我昨天买了多少钱，给你五次机会。 10000？低了。30000？高了。接下来你会猜多少？ 20000。为什么你不猜 11000，也不猜 29000 呢？
这就是二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。
所以首先，我们可以考虑用有序数组作为索引的数据结构。
有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变 index），所以只适合存储静态的数据。
为了支持频繁的修改，比如插入数据，我们需要采用链表 。链表的话，如果是单链表，它的查找效率还是不够高。
所以，有没有可以使用二分查找的链表呢？ 为了解决这个问题，BST（Binary Search Tree）也就是我二叉查找树诞生了。
二叉查找树的特点：左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。
二叉查找树既能够实现快速查找，又能够实现快速插入。
但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。
什么情况是最坏的情况呢？
还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、6、11、13、17、22。
这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。
造成它倾斜的原因是什么呢？
因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。
所以，有没有左右子树深度相差不是那么大，更加平衡的树呢？
有，就是平衡二叉树，或者 AVL 树（AVL 是发明这个数据结构的人的名字）。
AVL Trees (Balanced binary search trees)
平衡二叉树的定义：左右子树深度差绝对值不能超过 1。
比如左子树的深度是 2，右子树的深度只能是 1 或者 3。
这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。
那 AVL 树的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？
插入 1、2、3。
当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，
这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。
那应该怎么办呢？因为它是右节点下面接一个右节点，称为：右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。
同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。
所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。
平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？
在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？
它应该存储三部分的内容：
第一，是索引的键值。比如我们在 id 列上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。
第二，是数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
第三，因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。
如果是这样存储数据的话，我们来看一下会有什么问题。
当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。
访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384字节)。那么，一个树的节点就是 16K 的大小。
如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到 16K 的容量，所以访问一个树节点，进行一次 IO 的时候，浪费了大量的空间。
所以如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问更多的节点，意味着跟磁盘交互次数就会过多。
如果是机械硬盘时代，每次从磁盘读取数据需要 10ms 左右的寻址时间，交互次数越多，消耗的时间就越多。
比如上面这张图，我们一张表里面有 6 条数据，当我们查询 id=37 的时候，要查询两个子节点，就需要跟磁盘交互 3 次，如果我们有几百万的数据呢？这个时间更加难以估计。
所以我们的解决方案是什么呢？ 第一，就是让每个节点存储更多的数据。 第二，节点上的关键字的数量越多，我们的指针数也越多，也就是意味着可以有更多的分叉（我们把它叫做“路数”）。 因为分叉数越多，树的深度就会减少。
这样，我们的树是不是从原来的高瘦高瘦的样子，变成了矮胖矮胖的样子？ 这个时候，我们的树就不再是二叉了，而是多叉，或者叫做多路。
（Balanced Tree） 这个就是我们的多路平衡查找树，叫做 B Tree（B 代表平衡）。
跟 AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。
它有一个特点：分叉数（路数）永远比关键字数多 1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。
B Tree 的查找规则是什么样的呢？
比如我们要在这张表里面查找 15。 因为 15 小于 17，走左边。 因为 15 大于 12，走右边。 在磁盘块 7 里面就找到了 15，只花费了 3 次 IO。
B Tree是不是比 AVL 树效率更高呢？ 那 B Tree 又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟 AVL 树有什么区别？
比如 Max Degree（路数）是 3 的时候，我们插入数据 1、2、3，在插入 3 的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有 4 个指针，子节点会变成 4 路，所以这个时候必须进行分裂（其实就是 B+Tree）。把中间的数据 2提上去，把 1 和 3 变成 2 的子节点。 如果删除节点，会有相反的合并的操作。 注意这里是分裂和合并，跟 AVL 树的左旋和右旋是不一样的。 我们继续插入 4 和 5，B Tree 又会出现分裂和合并的操作。
因此，在更新索引的时候会有大量的索引的结构的调整，所以解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。
节点的分裂和合并，其实就是 InnoDB 页（page）的分裂和合并。
B Tree 的效率已经很高了，为什么 MySQL 还要对 B Tree 进行改良，最终使用了 B+Tree 呢？ 总体上来说，这个 B 树的改良版本解决的问题比 B Tree 更全面。 我们来看一下 InnoDB 里面的 B+树的存储结构： MySQL 中的 B+Tree 有几个特点：
1、它的关键字的数量是跟路数相等的；2、B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。搜索到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索 id=28，虽然在第一层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜索，一直到叶子节点。假设一条记录是 1K，一个叶子节点（一页）可以存储 16 条记录。 非叶子节点可以存储多少个指针？
假设索引字段是 bigint 类型，长度为 8 字节。指针大小在 InnoDB 源码中设置为6 字节，这样一共 14 字节。非叶子节点（一页）可以存储 16384/14=1170 个这样的单元（键值+指针），代表有 1170 个指针。
树 深 度 为 2 的 时 候 ， 有 1170^2 个 叶 子 节 点 ， 可 以 存 储 的 数 据 为1170117016=21902400。 在查找数据时一次页的查找代表一次 IO，也就是说，一张 2000 万左右的表，查询数据最多需要访问 3 次磁盘。 所以在 InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。
3、B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。4、它是根据左闭右开的区间 [ )来检索数据。1）比如我们要查找 28，在根节点就找到了键值，但是因为它不是叶子节点，所以会继续往下搜寻，28 是[28,66)的左闭右开的区间的临界值，所以会走中间的子节点，然后继续搜索，它又是[28,34)的左闭右开的区间的临界值，所以会走左边的子节点，最后在叶子节点上找到了需要的数据。
2）如果是范围查询，比如要查询从 22 到 60 的数据，当找到 22 之后，只需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点，这样就极大地提高了区间查询效率（不需要返回上层父节点重复遍历查找）。
总结一下，InnoDB 中的 B+Tree 的特点：
它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。B Tree 解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵 B+Tree 拿到所有的数据）
B+Tree 的磁盘读写能力相对于 B Tree 来说更强（根节点和枝节点不保存数据，所以一个节点可以保存更多的关键字，一次磁盘IO加载的关键字更多）
排序能力更强（因为叶子节点上有下一个数据区的指针）
效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）
我们知道不同的存储引擎，文件不一样：
show VARIABLES LIKE 'datadir';每 张 InnoDB 的 表 有 两 个 文 件 （ .frm 和 .ibd ） ， MyISAM 的 表 有 三 个 文 件 （.frm、.MYD、.MYI）。
有一个是相同的文件，.frm。
.frm 是 MySQL 里面表结构定义的文件，不管你建表的时候选用任何一个存储引擎都会生成，我们就不看了。
我们主要看一下其他两个文件是怎么实现 MySQL 不同的存储引擎的索引的。
我们先来看下 MyISAM。
在 MyISAM 里面，另外有两个文件：
一个是.MYD 文件，D 代表 Data，是 MyISAM 的 数据文件 ，存放数据记录，比如我们的 user_myisam 表的所有的表数据。
一个是.MYI 文件，I 代表 Index，是 MyISAM 的 索引文件 ，存放索引，比如我们在id 字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面。
也就是说，在 MyISAM 里面，索引和数据是两个独立的文件。那我们怎么根据索引找到数据呢？
MyISAM 的 B+Tree 里，叶子节点存储的是数据文件对应的磁盘地址。 所以从索引文件.MYI 中找到键值后，会到数据文件.MYD 中获取相应的数据记录。（见下图） 这里画的是主键索引，如果是辅助索引，有什么不一样呢？
ALTER TABLE user_innodb DROP INDEX index_user_name; ALTER TABLE user_innodb ADD INDEX index_user_name (name);在 MyISAM 里面，辅助索引也在这个.MYI 文件里面。
辅助索引跟主键索引存储和检索数据的方式是没有任何区别的，一样是在索引文件里面找到磁盘地址，然后到数据文件里面获取数据。
InnoDB 只有一个文件（.ibd 文件），那索引放在哪里呢？ InnoDB是以主键为索引来组织数据的存储的，所以索引文件和数据文件是同一个文件，都在.ibd 文件里面。
在 InnoDB 的主键索引的叶子节点上，它直接存储了我们的数据。
什么叫做 聚集索引（聚簇索引）？
就是索引键值的逻辑顺序，跟表数据行的物理存储顺序是一致的。（比如字典的目录是按拼音排序的，内容也是按拼音排序的，按拼音排序的这种目录就叫聚集索引）。如果我们查询id比较靠后的数据，那么这行数据的地址在磁盘中的物理地址也会比较靠后。
在 InnoDB 里面，它组织数据的方式叫（聚集）索引组织表（clustered index organize table），所以 主键索引是聚集索引，非主键都是非聚集索引 。
主键之外的索引，比如我们在 name 字段上面建的普通索引（辅助索引），又是怎么存储和检索数据的呢？
InnoDB 中，主键索引和辅助索引是有一个主次之分的。
辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终取得数据。
比如我们用 name 索引查询 name= ‘青山’，它会在叶子节点找到主键值，也就是id=1，然后再到主键索引的叶子节点拿到数据。
另一个问题，如果一张表没有主键怎么办？
如果我们定义了主键(PRIMARY KEY)，那么 InnoDB 会选择主键作为聚集索引。如果没有显式定义主键，则 InnoDB 会选择第一个不包含有 NULL 值的唯一索引 作为主键索引。如果也没有这样的唯一索引，则 InnoDB 会选择内置 6 字节长的 ROWID 作为隐 藏的聚集索引，它会随着行记录的写入而主键递增。 select _rowid name from t2;我们容易有一个误区，就是在经常使用的查询条件上都建立索引，索引越多越好，到底是不是这样呢？
首先要考虑的是列的离散度 ，我们先来看一下列的离散度的公式： count(distinct(column_name)) : count(*)， 也就是列的全部不同值和所有数据行的比例。
数据行数相同的情况下，不同的值越多，分子越大，列的离散度就越高。
了解了离散度的概念之后，我们再来思考一个问题，我们在 name 上面建立索引和在 gender（性别） 上面建立索引有什么区别。
当我们用在 gender 上建立的索引去检索数据的时候，由于重复值太多，需要扫描的行数就更多。例如，我们现在在 gender 列上面创建一个索引，然后看一下执行计划。
ALTER TABLE user_innodb DROP INDEX idx_user_gender; ALTER TABLE user_innodb ADD INDEX idx_user_gender (gender); -- 耗时比较久 EXPLAIN SELECT * FROM `user_innodb` WHERE gender = 0;预估需要扫描将近50w行。 而 name 的离散度更高，比如“青山”的这名字，只需要扫描一行。
ALTER TABLE user_innodb DROP INDEX idx_user_name; ALTER TABLE user_innodb ADD INDEX idx_user_name (name); EXPLAIN SELECT * FROM `user_innodb` WHERE name = '青山';如果在 B+Tree 里面的重复值太多，MySQL 的优化器发现使用索引跟使用全表扫描差不了多少的时候，就算建了索引，也不一定会走索引。
建立索引，要使用离散度（选择度）更高的字段。
前面我们说的都是针对单列创建的索引，但有的时候我们的多条件查询的时候，也会建立联合索引（组合索引）。单列索引可以看成是特殊的联合索引。
比如我们在 user 表上面，给 name 和 phone 建立了一个联合索引。
ALTER TABLE user_innodb DROP INDEX comidx_name_phone; ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);联合索引在 B+Tree 中是复合的数据结构，它是按照从左到右的顺序来建立搜索树的（name 在左边，phone 在右边）。
从这张图可以看出来，name 是有序的，phone 是无序的。当 name 相等的时候，phone 才是有序的。
这个时候我们使用 where name=‘青山’ and phone = '136xx '去查询数据的时候，B+Tree 会优先比较name 来确定下一步应该搜索的方向，往左还是往右。如果 name相同的时候再比较 phone。但是如果查询条件没有 name，就不知道第一步应该查哪个节点，因为建立搜索树的时候 name 是第一个比较因子，所以用不到索引。
所以， 我们在建立联合索引的时候，一定要把最常用的列放在最左边。
比如下面的三条语句，大家觉得用到联合索引了吗？
使用两个字段，能用到联合索引： EXPLAIN SELECT * FROM user_innodb WHERE name= '权亮' AND phone = '15204661800'; 使用左边的 name 字段，能用到联合索引： EXPLAIN SELECT * FROM user_innodb WHERE name= '权亮' 使用右边的 phone 字段，无法使用索引，全表扫描： EXPLAIN SELECT * FROM user_innodb WHERE phone = '15204661800'回表： 非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查出索引里面没有的数据，它比基于主键索引的查询多扫描了一棵索引树，这个过程就叫回表。
例如：
select * from user_innodb where name = '青山';在辅助索引里面，不管是单列索引还是联合索引，如果 select 的数据列只用从索引中就能够取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引 ，这样就避免了回表。
我们先来创建一个联合索引：
-- 创建联合索引 ALTER TABLE user_innodb DROP INDEX comixd_name_phone; ALTER TABLE user_innodb add INDEX `comixd_name_phone` (`name`,`phone`);当发起一个被索引覆盖的查询(也叫作索引覆盖查询)时，在 EXPLAIN 的 Extra 列可以看到“Using index”的信息: 现在观察在这个联合索引存在的情况下，下面的哪些查询语句用到了覆盖索引：
EXPLAIN SELECT name,phone FROM user_innodb WHERE name= '青山' ; -- 可以 EXPLAIN SELECT name FROM user_innodb WHERE name= '青山' AND phone = '13666666666'; -- 可以 EXPLAIN SELECT name FROM user_innodb WHERE phone = '13666666666'; -- 可以 EXPLAIN SELECT * FROM user_innodb WHERE name= '青山' ; -- 不可以由于联合索引中，已经包含了name,phone这两个列的数据了，因此，如果要查询的列刚好在name,phone这两个中，就可以直接从联合索引取数据，而不需要到主键索引中去取了。 第四句中，所查询的列超出了范围，因此发生了回表。
很明显，因为覆盖索引减少了 IO 次数，减少了数据的访问量，可以大大地提升查询效率。
因为索引对于改善查询性能的作用是巨大的，所以我们的目标是尽量使用索引。
where 条件中 like abc%，like &73%，like
