什么是索引
索引是存储引擎中一种数据结构，或者说数据的组织方式，又称之为键key，是存储引擎用于快速找到记录的一种数据结构。 为数据建立索引就好比是为书建目录，或者说是为字典创建音序表，如果要查某个字，如果不使用音序表，则需要从几百页中逐页去查
使用索引的好处
一般的应用系统，读写比例在9:1左右，而且插入操作和一般的更新操作很少出现性能问题，在生产环境中，我们遇到最多的、也是最容易出问题的，还是一些复杂的查询操作，因此对查询语句的优化显然是重中之重。说起加速查询，就不得不提到索引了。 索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高好几个数量级。
理解索引的储备知识
储备知识1：机械磁盘一次IO的时间
机械磁盘一次io的时间 = 寻道时间 + 旋转延迟 + 传输时间
# 寻道时间
寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下
# 旋转延迟
旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；
# 传输时间
传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计
所以访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右
这9ms对于人来说可能非常短，但对于计算机来可是非常长的一段时间，长到什么程度呢？
一台500 -MIPS（Million Instructions Per Second）的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行约450万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。
储备知识2：磁盘的预读
# 考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化：
当一次IO时，不光读当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。
储备知识3：索引原理精髓提炼
索引的目的在于提高查询效率，与我们查阅图书所用的目录是一个道理：先定位到章，然后定位到该章下的一个小节，然后找到页数。相似的例子还有：查字典，查火车车次，飞机航班等
本质都是：
-- 通过不断地缩小想要获取数据的范围来筛选出最终想要的结果，同时把随机的事件变成顺序的事件，也就是说，有了这种索引机制，我们可以总是用同一种查找方式来锁定数据。
数据库也是一样，但显然要复杂的多，因为不仅面临着等值查询，还有范围查询(>、<、between、in)、模糊查询(like)、并集查询(or)等等。数据库应该选择怎么样的方式来应对所有的问题呢？我们回想字典的例子，能不能把数据分成段，然后分段查询呢？最简单的如果1000条数据，1到100分成第一段，101到200分成第二段，201到300分成第三段......这样查第250条数据，只要找第三段就可以了，一下子去除了90%的无效数据。但如果是1千万的记录呢，分成几段比较好？稍有算法基础的同学会想到搜索树，其平均复杂度是lgN，具有不错的查询性能。但这里我们忽略了一个关键的问题，复杂度模型是基于每次相同的操作成本来考虑的。而数据库实现比较复杂，一方面数据是保存在磁盘上的，另外一方面为了提高性能，每次又可以把部分数据读入内存来计算，因为我们知道访问磁盘的成本大概是访问内存的十万倍左右，所以简单的搜索树难以满足复杂的应用场景。
索引分类
索引模型分为很多种类
#==== B+树索引（等值查询与范围查询都快）
二叉树->平衡二叉树->B树->B+树
#==== HASH索引(等值查询快，范围查询慢)
将数据打散再去查询
#==== FULLTEXT：全文索引 （只可以用在MyISAM引擎）
通过关键字的匹配来进行查询，类似于like的模糊匹配
like + %在文本比较少时是合适的
但是对于大量的文本数据检索会非常的慢
全文索引在大量的数据面前能比like快得多，但是准确度很低
百度在搜索文章的时候使用的就是全文索引，但更有可能是ES
#不同的存储引擎支持的索引类型也不一样
-- InnoDB存储引擎
支持事务，支持行级别锁定，支持 B-tree（默认）、Full-text 等索引，不支持 Hash 索引。
-- MyISAM存储引擎
不支持事务，支持表级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引。
-- Memory存储引擎
不支持事务，支持表级别锁定，支持 B-tree、Hash 等索引，不支持 Full-text 索引。
-- 因为mysql默认的存储引擎是innodb，而innodb存储引擎的索引模型/结构是B+树
索引的数据结构
常见的数据结构有4种：二叉查找树、平衡二叉树、B树以及B+树
1.二叉查找树
-- 二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.任意节点的左、右子树也分别为二叉查找树。
4.没有键值相等的节点（no duplicate nodes）。
有user表，我们以id字段值为基础创建索引。
**1、提取每一条记录的id值作为key值，value为本行完整记录，即：
| id | user |
|---|---|
| 10 | zs |
| 7 | ls |
| 13 | ww |
| 5 | zl |
| 8 | xw |
| 12 | xm |
| 17 | dy |
**2、以key值的大小为基础构建二叉树，如上图所示**
**二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。**
**顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。**
**如果我们需要查找id=12的用户信息**
```sql
select * from user where id=12;
利用我们创建的二叉查找树索引，查找流程如下：
1.将根节点作为当前节点，把12与当前节点的键值10比较，12大于10，接下来我们把当前节点>的右子节点作为当前节点。
2.继续把12和当前节点的键值13比较，发现12小于13，把当前节点的左子节点作为当前节点。
3.把12和当前节点的键值12对比，12等于12，满足条件，我们从当前节点中取出data，即id=1>2,name=xm。
利用二叉查找树我们只需要3次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要6次才能找到。
2.平衡二叉树
基于5.1所示的二叉树，我们确实可以快速地找到数据。但是让我们回到二叉查找树地特点上，只论二叉查找树，它的特点只是：任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。 所以，依据二叉查找树的特点，二叉树可以是这样构造的，如图
**这个时候可以看到我们的二叉查找树变成了一个链表。如果我们需要查找id=17的用户信息，我们需要查找7次，也就相当于全表扫描了。 导致这个现象的原因其实是二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。**
**为了解决这个问题，我们需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树了。平衡二叉树又称AVL树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度不能超过1。 下面是平衡二叉树和非平衡二叉树的对比：**
**由平衡二叉树的构造我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。平衡二叉树保证了树的构造是平衡的，当我们插入或删除数据导致不满足平衡二叉树不平衡时，平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。**
**那么是不是说基于平衡二叉树构建索引的结构就可以了呢？答案是否！**
3.B树
那么直接用平衡二叉树这种数据结构来构建索引有什么问题？
首先，因为内存的易失性。一般情况下，我们都会选择将user表中的数据和索引存储在磁盘这种外围设备中。但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。 如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。所以，如果我们单纯用平衡二叉树这种数据结构作为索引的数据结构，即每个磁盘块只放一个节点，每个节点中只存放一组键值对，此时如果数据量过大，二叉树的节点则会非常多，树的高度也随即变高，我们查找数据的也会进行很多次磁盘IO，查找数据的效率也会变得极低！
综上，如果我们能够在平衡二叉的树的基础上，把更多的节点放入一个磁盘块中，那么平衡二叉树的弊端也就解决了。即构建一个单节点可以存储多个键值对的平衡树，这就是B树。
注意：
1、图中的p节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。
2、图中的每个节点里面放入了多组键值对，一个节点也称为一页，一页即一个磁盘块，在mysql中数据读取的基本单位都是页，即一次io读取一个页的数据，所以我们这里叫做页更符合mysql中索引的底层数据结构。
从上图可以看出，B树相对于平衡二叉树，每个节点存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会很低。 基于这个特性，B树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。 假如我们要查找id=28的用户信息，那么我们在上图B树中查找的流程如下：
1）先找到根节点也就是页1，判断28在键值17和35之间，我们那么我们根据页1中的指针p2找到页3。
2）将28和页3中的键值相比较，28在26和30之间，我们根据页3中的指针p2找到页8。
3）将28和页8中的键值相比较，发现有匹配的键值28，键值28对应的用户信息为(28,bv)。
注意：
1）B树的构造是有一些规定的，但这不是本文的关注点，有兴趣的同学可以令行了解。
2）B树也是平衡的，当增加或删除数据而导致B树不平衡时，也是需要进行节点调整的。
那么B树是否就是索引的最终结构了呢？答案是no，B树只擅长做等值查询，而对于范围查询（范围查询的本质就是n次等值查询），或者说排序操作，B树也帮不了我们
select * from user where id=3; -- 擅长
select * from user where id>3; -- 不擅长
4.B+树
B+树是对B树的进一步优化。让我们先来看下B+树的结构图：
根据上图我们来看下B+树和B树有什么不同。
1.B+树非叶子节点non-leaf node上是不存储数据的，仅存储键，而B树的非叶子节点中不仅存储键，也会存储数据。B+树之所以这么做的意义在于：树一个节点就是一个页，而数据库中页的大小是固定的，innodb存储引擎默认一页为16KB，所以在页大小固定的前提下，能往一个页中放入更多的节点，相应的树的阶数（节点的子节点树）就会更大，那么树的高度必然更矮更胖，如此一来我们查找数据进行磁盘的IO次数有会再次减少，数据查询的效率也会更快。
2.B+树的阶数是等于键的数量的，例如上图，我们的B+树中每个节点可以存储3个键，3层B+树存可以存储333=27个数据。所以如果我们的B+树一个节点可以存储1000个 键值，那么3层B+树可以存储1000×1000×1000=10亿个数据。而一般根节点是常驻内存的，所以一般我们查找10亿数据，只需要2次磁盘IO，真是屌炸天的设计。
3.因为B+树索引的所有数据均存储在叶子节点leaf node，而且数据是按照顺序排列的。那么B+树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而B树因为数据分散在各个节点，要实现这一点是很不容易的。 而且B+树中各个页之间也是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。其实上面的B树我们也可以对各个节点加上链表。其实这些不是它们之前的区别，是因为在mysql的innodb存储引擎中，索引就是这样存储的。也就是说上图中的B+树索引就是innodb中B+树索引真正的实现方式，准确的说应该是聚集索引（聚集索引和非聚集索引下面会讲到）。
通过上图可以看到，在innodb中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。
索引管理
1.索引的功能就是加速查找
2.mysql中的primary key，unique，联合唯一也都是索引，这些索引除了加速查找以外，还有约束的功能
1.MySQL常用的索引分类
我们可以在创建上述索引的时候，为其指定索引类型，主要有以下几类
#===========B+树索引（innodb存储引擎默认）
-- 聚集索引：即主键索引，PRIMARY KEY
用途：
1、加速查找
2、约束（不为空、不能重复）
-- 唯一索引：UNIQUE
用途：
1、加速查找
2、约束（不能重复）
-- 普通索引INDEX：
用途：
1、加速查找
-- 联合索引：
PRIMARY KEY(id,name):联合主键索引
UNIQUE(id,name):联合唯一索引
INDEX(id,name):联合普通索引
#===========HASH索引(查询单条快，范围查询慢)
将数据打散再去查询
Innodb和Myisam都不支持，设置完还是Btree
memery存储引擎支持
#===========FULLTEXT：全文索引 （只可以用在MyISAM引擎）
通过关键字的匹配来进行查询，类似于like的模糊匹配
like + %在文本比较少时是合适的
但是对于大量的文本数据检索会非常的慢
全文索引在大量的数据面前能比like快得多，但是准确度很低
百度在搜索文章的时候使用的就是全文索引，但更有可能是ES
#===========RTREE：R树索引
RTREE在mysql很少使用，仅支持geometry数据类型
geometry数据类型一般填写经纬度那样的数据
支持该类型的存储引擎只有MyISAM、BDb、InnoDb、NDb、Archive几种。
RTREE范围查找很强，但Btree也不弱.
#不同的存储引擎支持的索引类型也不一样
InnoDB 支持事务，支持行级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；
MyISAM 不支持事务，支持表级别锁定，支持 B-tree、Full-text 等索引，不支持 Hash 索引；
Memory 不支持事务，支持表级别锁定，支持 B-tree、Hash 等索引，不支持 Full-text 索引；
NDB 支持事务，支持行级别锁定，支持 Hash 索引，不支持 B-tree、Full-text 等索引；
Archive 不支持事务，支持表级别锁定，不支持 B-tree、Hash、Full-text 等索引；
2.创建索引的语法
#方法一：创建表时
CREATE TABLE 表名 (
字段名1 数据类型 [完整性约束条件…],
字段名2 数据类型 [完整性约束条件…],
[UNIQUE | FULLTEXT | SPATIAL ] INDEX | KEY
[索引名] (字段名[(长度)] [ASC |DESC])
);
-- 案例：
mysql> create table user(
-> id int primary key
-> );
Query OK, 0 rows affected (0.01 sec)
mysql> show create table userG
*************************** 1. row ***************************
Table: user
Create Table: CREATE TABLE `user` (
`id` int(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)
#方法二：CREATE INDEX可对表增加普通索引或UNIQUE索引。 不能用CREATE INDEX语句创建PRIMARY KEY索引。
CREATE [UNIQUE | FULLTEXT | SPATIAL ] INDEX 索引名
ON 表名 (字段名[(长度)] [ASC |DESC]) ;
CREATE INDEX 索引名 ON 表名(字段名)
CREATE UNIQUE INDEX 索引名 ON 表名(字段名)
-- 案例一：
mysql> create unique index grade on t1(id);
Query OK, 0 rows affected (0.32 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> show create table t1G
*************************** 1. row ***************************
Table: t1
Create Table: CREATE TABLE `t1` (
`id` int(11) DEFAULT NULL,
UNIQUE KEY `grade` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)
-- 案例二：
mysql> create index number on t2 (id);
Query OK, 0 rows affected (0.11 sec)
Records: 0 Duplicates: 0 Warnings: 0
#方法三：ALTER TABLE用来创建普通索引、UNIQUE索引或PRIMARY KEY索引。
ALTER TABLE 表名 ADD [UNIQUE | FULLTEXT | SPATIAL] INDEX
索引名(字段名[(长度)] [ASC |DESC]) ;
ALTER TABLE 表名 ADD PRIMARY KEY (字段名)
ALTER TABLE 表名 ADD UNIQUE 索引名(字段名)
ALTER TABLE 表名 ADD INDEX 索引名(字段名)
ALTER TABLE 表名 ADD FULLTEXT [index] 索引名(字段除id以外);
-- 案例一 添加主键：
mysql> alter table t2 add primary key(id);
Query OK, 0 rows affected (0.08 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> show create table t1G
*************************** 1. row ***************************
Table: t1
Create Table: CREATE TABLE `t1` (
`id` int(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)
-- 案例二 添加唯一索引： -- UNIQUE 后面不用跟INDEX
mysql> alter table t2 add unique grade(id);
Query OK, 0 rows affected (0.13 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> show create table t2G
*************************** 1. row ***************************
Table: t2
Create Table: CREATE TABLE `t2` (
`id` int(11) NOT NULL,
UNIQUE KEY `grade` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)
-- 案例三 添加普通索引：
mysql> alter table t2 add index number(id);
Query OK, 0 rows affected (0.01 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> show create table t2G
*************************** 1. row ***************************
Table: t2
Create Table: CREATE TABLE `t2` (
`id` int(11) NOT NULL,
KEY `number` (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)
-- 案例四 添加全文索引：
mysql> alter table t2 add fulltext (name);
Query OK, 0 rows affected, 1 warning (0.25 sec)
Records: 0 Duplicates: 0 Warnings: 1
mysql> show create table t2G
*************************** 1. row ***************************
Table: t2
Create Table: CREATE TABLE `t2` (
`id` int(11) NOT NULL,
`name` varchar(20) DEFAULT NULL,
FULLTEXT KEY `name` (`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)
#该语句指定了索引为 FULLTEXT ，用于全文索引。不能用在id
3.删除索引
#使用DROP语句删除：
DROP INDEX 索引名 ON 表名字;
-- 案例：
mysql> drop index number on t2;
Query OK, 0 rows affected (0.01 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> show create table t2G
*************************** 1. row ***************************
Table: t2
Create Table: CREATE TABLE `t2` (
`id` int(11) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)
#使用ALTER语句删除：
ALTER TABLE <表名> DROP index 索引名;
ALTER TABLE table_name DROP PRIMARY KEY; #删除主键
-- 案例一：
mysql> alter table t1 drop index grade;
Query OK, 0 rows affected (0.01 sec)
Records: 0 Duplicates: 0 Warnings: 0
mysql> show create table t1G
*************************** 1. row ***************************
Table: t1
Create Table: CREATE TABLE `t1` (
`id` int(11) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)
-- 案例二： 删除主键
mysql> alter table t2 drop primary key;
Query OK, 0 rows affected (0.15 sec)
Records: 0 Duplicates: 0 Warnings: 0
# 因为一个表只可能有一个PRIMARY KEY索引，因此不需要指定索引名。如果没有创建PRIMARY KEY索引，但表具有一个或多个UNIQUE索引，则MySQL将删除第一个UNIQUE索引。
4.查看索引
-- 方法一：
mysql> desc t1;
+-----+
| Key |
+-----+
| PRI | 主键索引
| MUL | 普通索引
| UNI | 唯一键索引
+-----+
-- 方法二：
mysql> show index from t1G
*************************** 1. row ***************************
Table: t1 #表的名称。
Non_unique: 0 #如果索引不能包括重复词，则为0。如果可以，则为1。
Key_name: number #索引的名称。
Seq_in_index: 1 #索引中的列序列号，从1开始。
Column_name: id #列名称
Collation: A #列以什么方式存储在索引中。在MySQL中，有值‘A’（升序）或NULL（无分类）。
Cardinality: 0 #索引中唯一值的数目的估计值。通过运行ANALYZE TABLE或myisamchk -a可以更新。基数根据被存储为整数的统计数据来计数，所以即使对于小型表，该值也没有必要是精确的。基数越大，当进行联合时，MySQL使用该索引的机会就越大。
Sub_part: NULL #如果列只是被部分地编入索引，则为被编入索引的字符的数目。如果整列被编入索引，则为NULL。
Packed: NULL #指示关键字如何被压缩。如果没有被压缩，则为NULL。
Null: YES #如果列含有NULL，则含有YES。如果没有，则该列含有NO。
Index_type: BTREE #用过的索引方法（BTREE, FULLTEXT, HASH, RTREE）。
Comment:
Index_comment: #索引注释
1 row in set (0.00 sec)
-- 方法三：
mysql> show create table t1G
*************************** 1. row ***************************
Table: t1
Create Table: CREATE TABLE `t1` (
`id` int(11) NOT NULL,
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4
1 row in set (0.00 sec)