1. 什么是索引

索引是帮助数据库高效获取数据的数据结构。简而言之,索引是数据结构

2. 索引的底层数据结构

2.1 Hash索引

哈希表是键值对的集合，通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O（1））。

为何能够通过 key 快速取出 value呢？ 原因在于 哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到 value 对应的 index，找到了 index 也就找到了对应的 value。

index = hash % array.size()

但是！哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。

为什么MySQL 没有使用其作为索引的数据结构呢？

1. Hash 冲突问题 ：我们上面也提到过Hash 冲突了，不过对于数据库来说这还不算最大的缺点。
2. Hash 索引不支持顺序和范围查询(Hash 索引不支持顺序和范围查询是它最大的缺点： hash索引中存储的就是Hash码，hash 码彼此之间是没有规律的，且 Hash 操作并不能保证顺序性，所以值相近的两个数据，Hash值相差很远，被分到不同的桶中。

2.2 树

有很多树可以作为索引的数据结构，但mysql的InnoDB使用b+树

• B+ 树
  单来说就是一种为磁盘或者其他存储设备而设计的一种平衡二叉树,在B+tree中所有记录都按照key的大小存放在叶子结点上，各叶子结点直接用指针连接
• 二叉搜索树
  二叉搜索树的规则是父节点大于左孩子节点，小于右孩子节点
• 平衡二叉树
  首先是一个二叉搜索树，但是要求任意一个节点的左右孩子节点的高度差不大于1
• B树
  首先是一个平衡二叉树，但是又要求每个叶子节点到根节点的距离相等
  那么B树和B+树的区别是什么呢？
  • B+树的叶子节点可以包含一个指针，指向另一个叶子节点
  • B+树键值的拷贝存在非叶子节点；键值+记录存储在叶子节点

2.2.1 B 树& B+树

B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。

目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。

B 树& B+树两者有何异同呢？

• B 树的所有节点既存放键(key) 也存放 数据(data)，而B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
• B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
• B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。

2.2.2 为什么要用b+树?

数据库存储的数据实际上是存在磁盘中的，之所以选择b+树也和这个有关。

2.2.2.1 磁盘

下面我们简单了解一下磁盘是如何工作的。

磁盘大概长这个样子：

磁盘主要由磁盘盘片、传动手臂、读写磁头和马达组成。

为了存储容量,主轴像穿糖葫芦一样把多个磁盘片组成一个阵列。通过马达驱动主轴转动以及传动手臂移动，使读写磁头在磁盘片上读写数据。大概如下：

磁盘片由很多半径不等的同心圆组成，这些圆被称为磁道，数据就是写在这些磁道上。

每个磁道又划分成块称为扇区。

如果磁盘是一记事本，那么一张磁盘片就是本子的一页纸，而主轴就是本子的装订线；磁道就是纸页的行，而扇区可以看作是很宽的列。

如果在磁盘中存储一首诗,想象中大概这个样子。

磁盘的读 I/O 操作,需要找到数据所在的磁盘片，以及对应的磁道和扇区。这些操作类似于从一本书中找到数据所在的页，行，列。

因为每个磁盘片都对应一个磁头，所以性能的关键就在于找行和列，即寻道和磁盘旋转。寻道即通过磁头找到数据所在的磁道，相当于换行到数据所在行。由于磁头只能水平移动，即只能换行寻道，无法在指定磁道上移动，因此需要磁盘高速旋转移动到指定扇区，类似写春联时，笔不动，纸动。

综上所述，磁盘的读写是通过机械运动来定位数据所在位置，而 cpu 是通过电信号进行数字运算。粗略的认为，机械查询数据，与光速处理数据的性能完全不是在一个量级，总之一句话就是磁盘处理太慢太慢了。

虽然磁盘处理数据太慢了，但是它是目前相对廉价且稳定的存储设备，所以又不能舍弃不用，但大致可以通过以下方法进行优化。

• 尽量减少 I/O 次数，比如可以使用缓存
• 每次 I/O 尽量获取更多的数据
• 每次 I/O 尽量获取有用的数据，当然相应的也间接减少总 I/O 次数

2.2.2.2 为什么用b+树不是b树

上文为了解决磁盘处理数据太慢的问题，我们可以从：尽量减少 I/O 次数，比如可以使用缓存；每次 I/O 尽量获取更多的数据；每次 I/O 尽量获取有用的数据，当然相应的也间接减少总 I/O 次数；这三点出发。可以发现b树很符合磁盘处理，它加载一次节点，可以加载很多路径数据，同时把查询范围缩减到更小。大大减少了 I/O 次数或者寻道次数。

但是b树仍然有一个致命的缺陷，那就是它的索引数据与业务绑定在一块，而业务数据的大小很有可能远远超过了索引数据，这会大大减小一次 I/O 有用数据的获取，间接的增加 I/O 次数去获取有用的索引数据。

因为业务数据才是我们查询最终的目的，但是它又是在「二分」查找中途过程无用的数据，因此，如果只把业务数据存储在最终查询到的那个节点是不是就可以了？这其实就是b+树。

B+ 树中，非叶子节点只保存索引数据，叶子节点保存索引数据与业务数据。这样即保证了叶子节点的简约干净，数据量大大减小，又保证了最终能查到对应的业务数。既提高了单次 I/O 数据的有效性，又减少了 I/O 次数，还实现了业务。

2.2.3 不同引擎下B+树的区别

在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构，但是，两者的实现方式不太一样。（下面的内容整理自《Java 工程师修炼之道》）

MyISAM 引擎中，B+Tree 叶节点的 data 域存放的是数据记录的地址。在索引检索的时候，首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。这被称为“非聚簇索引”。

InnoDB 引擎中，其数据文件本身就是索引文件。相比 MyISAM，索引文件和数据文件是分离的，其表数据文件本身就是按 B+Tree 组织的一个索引结构，树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。这被称为“聚簇索引（或聚集索引）”，而其余的索引都作为辅助索引，辅助索引的 data 域存储相应记录主键的值而不是地址，这也是和 MyISAM 不同的地方。在根据主索引搜索时，直接找到 key 所在的节点即可取出数据；在根据辅助索引查找时，则需要先取出主键的值，在走一遍主索引。 因此，在设计表的时候，不建议使用过长的字段作为主键，也不建议使用非单调的字段作为主键，这样会造成主索引频繁分裂。

3. 索引的分类

3.1 根据应用区分

3.1.1 主键索引

数据表的主键列使用的就是主键索引。

一张数据表有只能有一个主键，并且主键不能为 null，不能重复。

在 MySQL 的 InnoDB 的表中，当没有显示的指定表的主键时，InnoDB 会自动先检查表中是否有唯一索引的字段，如果有，则选择该字段为默认的主键，否则 InnoDB 将会自动创建一个 6Byte 的自增主键。

3.1.2 二级索引(辅助索引)

二级索引又称为辅助索引，是因为二级索引的叶子节点存储的数据是主键。也就是说，通过二级索引，可以定位主键的位置。

唯一索引，普通索引，前缀索引等索引属于二级索引。

1. 唯一索引(Unique Key) ：唯一索引也是一种约束。唯一索引的属性列不能出现重复的数据，但是允许数据为 NULL，一张表允许创建多个唯一索引。建立唯一索引的目的大部分时候都是为了该属性列的数据的唯一性，而不是为了查询效率。
2. 普通索引(Index) ：普通索引的唯一作用就是为了快速查询数据，一张表允许创建多个普通索引，并允许数据重复和 NULL。
3. 前缀索引(Prefix) ：前缀索引只适用于字符串类型的数据。前缀索引是对文本的前几个字符创建索引，相比普通索引建立的数据更小， 因为只取前几个字符。
4. 全文索引(Full Text) ：全文索引主要是为了检索大文本数据中的关键字的信息，是目前搜索引擎数据库使用的一种技术。Mysql5.6 之前只有 MYISAM 引擎支持全文索引，5.6 之后 InnoDB 也支持了全文索引。

3.2 根据索引和数据是否分开区分

3.2.1 聚簇索引

聚簇索引即索引结构和数据一起存放的索引。主键索引属于聚簇索引。

如果表设置了主键，则主键就是聚簇索引
如果表没有主键，则会默认第一个NOT NULL，且唯一（UNIQUE）的列作为聚簇索引
以上都没有，则会默认创建一个隐藏的row_id作为聚簇索引

聚簇索引的优点

聚簇索引的查询速度非常的快，因为整个 B+树本身就是一颗多叉平衡树，叶子节点也都是有序的，定位到索引的节点，就相当于定位到了数据。

聚簇索引的缺点

1. 依赖于有序的数据 ：因为 B+树是多路平衡树，如果索引的数据不是有序的，那么就需要在插入时排序，如果数据是整型还好，否则类似于字符串或 UUID 这种又长又难比较的数据，插入或查找的速度肯定比较慢。
2. 更新代价大 ： 如果对索引列的数据被修改时，那么对应的索引也将会被修改， 而且况聚簇索引的叶子节点还存放着数据，修改代价肯定是较大的， 所以对于主键索引来说，主键一般都是不可被修改的。

3.2.2 非聚簇索引

非聚簇索引即索引结构和数据分开存放的索引。二级索引属于非聚簇索引。

非聚簇索引的优点

更新代价比聚簇索引要小 。非聚簇索引的更新代价就没有聚簇索引那么大了，非聚簇索引的叶子节点是不存放数据的

非聚簇索引的缺点

跟聚簇索引一样，非聚簇索引也依赖于有序的数据
可能会二次查询(回表) :这应该是非聚簇索引最大的缺点了。 当查到索引对应的指针或主键后，可能还需要根据指针或主键再到数据文件或表中查询。

如果还不清楚聚簇索引和非聚簇索引。看了下面回表和覆盖索引就知道了。

4. 回表查询和覆盖索引

4.1 什么是回表查询

第一次先通过非聚簇索引搜索得到主键，然后再通过主键去搜索取得所需要的数据，进行了两次搜索所以叫回表。理解不了看一下下面的例子就知道了。

示例

建表

id 字段是主键索引，属于聚簇索引，age 字段是普通索引（二级索引）

mysql> create table user(
    -> id int(10) auto_increment,
    -> name varchar(30),
    -> age tinyint(4),
    -> primary key (id),
    -> index idx_age (age)
    -> )engine=innodb charset=utf8mb4;

填充数据

insert into user(name,age) values('张三',30);
insert into user(name,age) values('李四',20);
insert into user(name,age) values('王五',40);
insert into user(name,age) values('刘八',10);

mysql> select * from user;
+----+--------+------+
| id | name  | age |
+----+--------+------+
| 1 | 张三  |  30 |
| 2 | 李四  |  20 |
| 3 | 王五  |  40 |
| 4 | 刘八  |  10 |
+----+--------+------+

索引存储结构

id 是主键，所以是聚簇索引，其叶子节点存储的是对应行记录的数据

聚簇索引（ClusteredIndex）

聚簇索引即索引结构和数据一起存放的索引。对于 InnoDB 引擎表来说，该表的索引(B+树)的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据。

普通索引（secondaryIndex）

age 是普通索引（二级索引），非聚簇索引，其叶子节点存储的是聚簇索引的的值

索引查找过程

聚簇索引查找过程

如果查询条件为主键（聚簇索引），则只需扫描一次B+树即可通过聚簇索引定位到要查找的行记录数据。

如：select * from user where id = 1;

普通索引查找过程

如果查询条件为普通索引（非聚簇索引），需要扫描两次B+树，第一次扫描通过普通索引定位到聚簇索引的值，然后第二次扫描通过聚簇索引的值定位到要查找的行记录数据。

如：select * from user where age = 30;

1. 先通过普通索引 age=30 定位到主键值 id=1
2. 再通过聚集索引 id=1 定位到行记录数据

4.2 覆盖索引

4.2.1 什么是覆盖索引

只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表，速度更快。覆盖索引是一种优化手段。

示例

select id,age from user where age = 10;

还是之前的搜索过程，但是通过普通索引 age=30 定位到主键值 id=1时已经是所需的所有列数据了，因此无需回表

4.2.2 如何实现覆盖索引

将被查询的字段，建立到联合索引里去

select id,age from user where age = 10;

explain分析：因为age是普通索引，使用到了age索引，通过一次扫描B+树即可查询到相应的结果，这样就实现了覆盖索引

创建联合索引

select id,age,name from user where age = 10;

explain分析：age是普通索引，但name列不在索引树上，所以通过age索引在查询到id和age的值后，需要进行回表再查询name的值。此时的Extra列的NULL表示进行了回表查询。

这个时候可以创建组合索引

drop index idx_age on user;
create index idx_age_name on user(`age`,`name`);

explain分析：此时字段age和name是组合索引idx_age_name，查询的字段id、age、name的值刚刚都在索引树上，只需扫描一次组合索引B+树即可，这就是实现了索引覆盖，此时的Extra字段为Using index表示使用了索引覆盖。

4.2.3 什么时候使用覆盖索引

全表count查询优化

mysql> create table user(
    -> id int(10) auto_increment,
    -> name varchar(30),
    -> age tinyint(4),
    -> primary key (id),
    -> )engine=innodb charset=utf8mb4;

此时

select count(age) from user;

使用索引覆盖优化：创建age字段索引

create index idx_age on user(age);

列查询回表优化

前文在描述索引覆盖使用的例子就是

例如：select id,age,name from user where age = 10;

使用索引覆盖：建组合索引idx_age_name(age,name)即可

分页查询

例如：select id,age,name from user order by age limit 100,2;

因为name字段不是索引，所以在分页查询需要进行回表查询，此时Extra为Using filesort文件排序，查询性能低下。

使用索引覆盖：建组合索引idx_age_name(age,name)

5. Mysql如何操作索引

1.添加 PRIMARY KEY（主键索引）

ALTER TABLE `table_name` ADD PRIMARY KEY ( `column` )

2.添加 UNIQUE(唯一索引)

ALTER TABLE `table_name` ADD UNIQUE ( `column` )

3.添加 INDEX(普通索引)

ALTER TABLE `table_name` ADD INDEX index_name ( `column` )

4.添加 FULLTEXT(全文索引)

ALTER TABLE `table_name` ADD FULLTEXT ( `column`)

5.添加多列索引

ALTER TABLE `table_name` ADD INDEX index_name ( `column1`, `column2`, `column3` )

6.查看索引

show index from `table_name`;

7.删除索引

drop index `index_name` on `table_name`;

8.强制走索引的一种方式

select * from `table_name` force index(`index_name`) where xxx

6. 索引使用原则

6.1 索引使用规则-最左匹配原则(重点)

最左匹配原则：最左优先，以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。

索引的底层是一颗B+树，那么联合索引当然还是一颗B+树，只不过联合索引的健值数量不是一个，而是多个。构建一颗B+树只能根据一个值来构建，因此数据库依据联合索引最左的字段来构建B+树。

假如创建一个（a,b)的联合索引，那么它的索引树是这样的

可以看到a的值是有顺序的，1，1，2，2，3，3，而b的值是没有顺序的1，2，1，4，1，2。所以b = 2这种查询条件没有办法利用索引，因为联合索引首先是按a排序的，b是无序的。

同时我们还可以发现在a值相等的情况下，b值又是按顺序排列的，但是这种顺序是相对的。所以最左匹配原则遇上范围查询就会停止，剩下的字段都无法使用索引。例如a = 1 and b = 2 a,b字段都可以使用索引，因为在a值确定的情况下b是相对有序的，而a>1and b=2，a字段可以匹配上索引，但b值不可以，因为a的值是一个范围，在这个范围中b是无序的。

6.1.1 全值匹配查询时

select * from table_name where a = '1' and b = '2' and c = '3' 
select * from table_name where b = '2' and a = '1' and c = '3' 
select * from table_name where c = '3' and b = '2' and a = '1' 

用到了索引

where子句几个搜索条件顺序调换不影响查询结果，因为Mysql中有查询优化器，会自动优化查询顺序。
=、in会自动优化顺序

6.1.2 匹配左边的列时

select * from table_name where a = '1' 
select * from table_name where a = '1' and b = '2'  
select * from table_name where a = '1' and b = '2' and c = '3'

都从最左边开始连续匹配，用到了索引

select * from table_name where  b = '2' 
select * from table_name where  c = '3'
select * from table_name where  b = '1' and c = '3' 

这些没有从最左边开始，最后查询没有用到索引，用的是全表扫描

select * from table_name where a = '1' and c = '3' 

如果不连续时，只用到了a列的索引，b列和c列都没有用到，无法跳过某个列使用后续索引列

6.1.3 匹配列前缀

如果列是字符型的话它的比较规则是先比较字符串的第一个字符，第一个字符小的哪个字符串就比较小，如果两个字符串第一个字符相通，那就再比较第二个字符，第二个字符比较小的那个字符串就比较小，依次类推，比较字符串。

如果a是字符类型，那么前缀匹配用的是索引，后缀和中缀只能全表扫描了

select * from table_name where a like 'As%'; //前缀都是排好序的，走索引查询
select * from table_name where  a like '%As'//全表查询
select * from table_name where  a like '%As%'//全表查询

6.1.4 匹配范围值

select * from table_name where  a > 1 and a < 3

可以对最左边的列进行范围查询

select * from table_name where  a > 1 and a < 3 and b > 1;

多个列同时进行范围查找时，只有对索引最左边的那个列进行范围查找才用到B+树索引，也就是只有a用到索引，在1<a<3的范围内b是无序的，不能用索引，找到1<a<3的记录后，只能根据条件 b > 1继续逐条过滤

6.1.5 精确匹配某一列并范围匹配另外一列

如果左边的列是精确查找的，右边的列可以进行范围查找

select * from table_name where  a = 1 and b > 3;

a=1的情况下b是有序的，进行范围查找走的是联合索引

6.1.6 排序

一般情况下，我们只能把记录加载到内存中，再用一些排序算法，比如快速排序，归并排序等在内存中对这些记录进行排序，有时候查询的结果集太大不能在内存中进行排序的话，还可能暂时借助磁盘空间存放中间结果，排序操作完成后再把排好序的结果返回客户端。Mysql中把这种再内存中或磁盘上进行排序的方式统称为文件排序。文件排序非常慢，但如果order子句用到了索引列，就有可能省去文件排序的步骤

select * from table_name order by a,b,c limit 10;

因为b+树索引本身就是按照上述规则排序的，所以可以直接从索引中提取数据，然后进行回表操作取出该索引中不包含的列就好了

order by的子句后面的顺序也必须按照索引列的顺序给出，比如

select * from table_name order by b,c,a limit 10;

这种颠倒顺序的没有用到索引

select * from table_name order by a limit 10;
select * from table_name order by a,b limit 10;

这种用到部分索引

select * from table_name where a =1 order by b,c limit 10;

联合索引左边列为常量，后边的列排序可以用到索引

6.2 创建索引的注意事项

1. 选择合适的字段创建索引：
   • 不为 NULL 的字段 ：索引字段的数据应该尽量不为 NULL，因为对于数据为 NULL 的字段，数据库较难优化。如果字段频繁被查询，但又避免不了为 NULL，建议使用 0,1,true,false 这样语义较为清晰的短值或短字符作为替代。
   • 被频繁查询的字段 ：我们创建索引的字段应该是查询操作非常频繁的字段。
   • 被作为条件查询的字段 ：被作为 WHERE 条件查询的字段，应该被考虑建立索引。
   • 频繁需要排序的字段 ：索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。
   • 被经常频繁用于连接的字段 ：经常用于连接的字段可能是一些外键列，对于外键列并不一定要建立外键，只是说该列涉及到表与表的关系。对于频繁被连接查询的字段，可以考虑建立索引，提高多表连接查询的效率。
2. 被频繁更新的字段应该慎重建立索引。
   虽然索引能带来查询上的效率，但是维护索引的成本也是不小的。 如果一个字段不被经常查询，反而被经常修改，那么就更不应该在这种字段上建立索引了。
3. 尽可能的考虑建立联合索引而不是单列索引。
   因为索引是需要占用磁盘空间的，可以简单理解为每个索引都对应着一颗 B+树。如果一个表的字段过多，索引过多，那么当这个表的数据达到一个体量后，索引占用的空间也是很多的，且修改索引时，耗费的时间也是较多的。如果是联合索引，多个字段在一个索引上，那么将会节约很大磁盘空间，且修改数据的操作效率也会提升。
4. 注意避免冗余索引。
   冗余索引指的是索引的功能相同，能够命中索引(a, b)就肯定能命中索引(a) ，那么索引(a)就是冗余索引。如（name,city ）和（name ）这两个索引就是冗余索引，能够命中前者的查询肯定是能够命中后者的。 在大多数情况下，都应该尽量扩展已有的索引而不是创建新索引。
5. 考虑在字符串类型的字段上使用前缀索引代替普通索引。
   前缀索引仅限于字符串类型，较普通索引会占用更小的空间，所以可以考虑使用前缀索引带替普通索引。

6.3 索引的优缺点

6.3.1 优点

• 使用索引可以大大加快 数据的检索速度（大大减少检索的数据量）, 这也是创建索引的最主要的原因。
• 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
• 避免全表扫描（当走不到索引时，就只能一个一个的去匹配；如果走索引，则可以根据B树来定位）
• 使用索引可以帮助服务器避免排序或者临时表 （叶子节点上的指针，可以有效的支持范围查询；此外叶子节点本身就是根据key进行排序的）
• 索引将随机IO变成顺序IO

6.3.2 缺点

• 创建索引和维护索引需要耗费许多时间。当对表中的数据进行增删改的时候，如果数据有索引，那么索引也需要动态的修改，会降低 SQL 执行效率。
• 索引需要使用物理文件存储，也会耗费一定空间。

参考搬运

1. https://github.com/Snailclimb/JavaGuide/blob/master/docs/database/mysql/MySQL%E6%95%B0%E6%8D%AE%E5%BA%93%E7%B4%A2%E5%BC%95.md
2. https://juejin.cn/post/6844904062329028621
3. https://juejin.cn/post/6844903581548544014#heading-34
4. https://juejin.cn/post/6844903645125820424#heading-9
5. https://blog.csdn.net/sinat_41917109/article/details/88944290
6. https://mp.weixin.qq.com/s/KxSlNnXQSaMemYdqyRCMOg