05. 索引

空灵大约 18 分钟

学习重点

理解索引是什么，为什么需要索引
掌握索引的数据结构，其他结构为什么不行
MySQL中索引的实现，MyISAM和InnoDB的主键索引和非主键索引
理解什么是回表，什么是覆盖索引

索引

面试的重点。

索引（Index）是数据库中一种特殊的数据结构，它用于提高数据库查询的效率和速度。在数据库中，索引类似于书籍中的目录，可以根据关键字快速定位到数据所在的位置，从而加速查询操作。

索引通常包括一个或多个列，每个列包含一个唯一的值，用于标识数据行。当查询语句包含一个或多个索引列时，数据库可以使用索引来快速定位符合条件的数据行，而不必扫描整个数据表。这可以大大提高查询速度，特别是对于大型数据表和复杂查询语句的情况下。

在数据库中，常用的索引类型包括主键索引、唯一索引、普通索引等。不同的索引类型适用于不同的查询场景，开发人员需要根据实际需求选择合适的索引类型。

需要注意的是，索引虽然可以提高查询效率，但也会占用一定的存储空间。因此，在设计数据库时需要仔细考虑索引的使用，避免过度使用索引导致数据库性能下降。同时，索引的维护也需要一定的时间和资源，因此需要根据实际情况定期进行索引优化和维护。

介绍

什么是索引呢？索引其实就是一种可以帮助我们提高查询速度的数据结构。

索引类似于一部字典开头的目录，可以帮助MySQL提高查询语句的效率。

索引的数据结构

我们说索引是一个可以帮助我们高效获取数据的数据结构，那么索引采用的是什么样的数据结构呢？

去探讨一个数据结构适不适合当索引主要有以下三个考察指标：

查询单个值

select * from user where id=10;

select * from user where name="zhangsan";

查询范围值

select * from user where id between 1 and 10;
select * from user where age < 18;

-- 索引是不是只能是int的值

插入数据

insert into user(name,age) values ("zhangsan", 20);

常见的数据结构

数组，链表，有序数组，二叉搜索树，B树，B+树，Hash表

数组：

查找单个值，速度慢。因为要比较所有的数据

查找范围值，速度慢，因为要比较所有数据

插入值，速度快。

链表：

查找单个值，速度慢。因为要比较所有的数据

查找范围值，速度慢，因为要比较所有数据

插入值，速度快。

有序数组

查询单个值：速度快。采用二分法
查询范围值：速度快。因为是有序的，先查找一个边界，然后再顺着走。
插入数据：速度慢。因为插入一条数据，需要挪动数据。

有序数组，一般不用来做索引。数据不要频繁插入和删除。历史数据。

有序数组，不适合用来做普通的索引，有没有什么场景可以用它来做索引。历史数据。2016年的淘宝订单。

**二叉搜索树：**左小右大。

定义：

它或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。

优点：查找单个数据方便，查找范围值不方便。

缺点：只有两个孩子。当数据量增大的时候，树的高度会升高，这个时候查询的次数就会变多。随着数据量的增大，会影响查询速度。

左子树的所有值，小于根节点的值。右子树的所有值，大于根节点。

查找单个值，速度快。查找范围值，速度中等，因为要在父节点和子节点之间反复跳转。

插入数据，速度快。

特殊的二叉搜索树。红黑树。

查找单个值，速度快。查找范围值，速度慢，因为要在父节点和子节点之间反复跳转。

插入数据，速度快。

存储信息的密度，高不高。

存储100w大小的表。log2(100w)。树的高度是20。

关系型数据库，数据都是放在磁盘里面。一层就要读一次磁盘。

100w条数据。select * from user where id=50301;

10ms * 20次 = 200ms = 0.2s

搜索树(B树、B+树)
- B树
  - 查询单个值比数组和链表要方便很多，比二叉树高度降低了，查询的效率也变高了
  - 查询范围值查询范围值需要在父子节点之前反复查找，其实不太方便
  - 插入数据：速度快
  image-20230217094430276
  B树对比红黑树和二叉树最大的进步：树的高度降低了，查询效率变高了。
  为什么说树的高度降低了之后，查询效率会变高：
  这个主要是和磁盘的读取策略以及数据库的设计策略有关系。
  结论：数据库在读取数据的时候，每一层会经过一次磁盘IO。假如数据的高度比较高，那么就需要经过多次的磁盘IO才能找到对应的数据，树的高度降低了之后，磁盘IO的次数会减少，那么这个时候查询速度增高。
- B+树（Btree）
  - B+树其实就是在B树的基础之上进行了优化。
    - 叶子节点之间维护一个指针，方便了范围查找
    - 所有的非叶子节点，都在叶子节点中冗余一份
    - 所以的非叶子节点，只存储key，不存储data，会降低树的高度，进一步提高查询的效率。
  - 查询单个值比较方便，速度快
  - 查询范围值比较方便（因为叶子节点之间维护了一个指针，指向下一个叶子节点）
  - 插入值：方便
  - B+树其实也是MySQL官方推荐我们使用的数据结构。Btree
  - MySQL对标准的B+树做了一些优化。主要就是增加了回去的指针。

Hash表
hash索引。在MySQL中，也有一种索引类型，叫做Hash索引，底层使用的是Hash表。
image-20220516155810313
- 查询单个值很方便，对比B+树来说要方便一些
- 查询范围值很不方便，需要一个一个查。
- 插入值：方便
Hash索引是MySQL内部使用的一种索引，没有开放给用户使用。

我们选来做索引的就是B+树。

问题1：索引的结构为什么选B+树。为啥不选红黑树做索引。

问题2：为什么索引结构是B+树？

先分析一些显而易见的不适合用来做索引的（数组链表有序数组）。再对比分析，为什么红黑树和二叉搜索树不行，主要的问题，是存储信息的密度太低。

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

索引的实现

索引的实现其实就是去介绍一下，数据库中数据到底是怎样存储的。在介绍这个之前，我们需要先了解一下数据库的组成结构。

了解了MySQL的结构之后，那我们就可以知道，数据的存储和存储引擎息息相关。不同的存储引擎存储数据的方式是不一样的。

MySQL底层的存储引擎是作为一个插件存在。

存储引擎就是MySQL底层怎样组织这些数据。（这些数据最终都是在磁盘上的），也就是在磁盘上怎样组织这些数据。

在MySQL中，有很多种存储引擎

InnoDB（5.1之后默认的存储引擎），这个存储引擎其实一开始是以插件的形式存在的，在5.1之后，MySQL官方团队把InnoDB当成了默认的存储引擎。
MyISAM（5.1之前默认的存储引擎），这个存储引擎是由MySQL的官方团队开发的。亲儿子。
Memory（基本不用）

MyISAM

C:\ProgramData\MySQL\MySQL Server 5.7\Data

首先，来看一下MyISAM这种存储引擎是怎样存储数据的。

MyISAM的表都有三个文件：

.frm
表结构定义文件.定义表结构，表里面有哪些列，列的类型。
.MYD
数据文件，其实也就是这个表中的数据都存储到这个文件中
.MYI
索引文件，这个表中的所有的索引树都是存储在这个文件中

mysql> create table t_myisam (
  ID int primary key,
  k int NOT NULL DEFAULT 0, 
  s varchar(16) NOT NULL DEFAULT '',
    -- index关键词 表明我想创建一个索引
    -- k 索引的名字
    -- (k) 索引列
  index k_name(k)
) engine=MyISAM;

insert into t_myisam values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

key就是主键。data存储的就是数据的地址（指向MYD文件中。）

MyISAM的索引分为两种类型，一种叫做主键索引，一种叫做非主键索引。

对于MyiSAM来说，MYI文件里面存储的是索引，MYD文件里面存储的data。

对于它的主键索引，key是主键值，data是地址值。

对于它的非主键索引，key是索引值，data是地址。

主键索引

主键索引是指MyISAM默认会根据主键这一列的值，去建立一个B+树，这个B+树就叫做主键索引树。

key：主键值
data：主键这一行数据对应的地址值

非主键索引

MyISAM中的非主键索引，是指我们可以把其他的非主键列声明为索引列，那么这样MyISAM就可以帮助我们根据这一列的值去建立一个索引树。意味着一个表可以有多个索引树。

key：索引列的值
data：索引列这一行数据对应的地址值

对于MyISAM中的索引来说，数据和索引是分开存储的，这种索引叫做 非聚集索引。

InnoDB

InnoDB的索引分为两种类型，一种叫做主键索引，一种叫做非主键索引。

每一个InnoDB表都有两个文件：

.frm
表结构定义文件
.ibd
数据和索引文件：这个文件中存储了数据和索引。

mysql> create table t_innodb (
  ID int primary key,
  k int NOT NULL DEFAULT 0, 
  s varchar(16) NOT NULL DEFAULT '',
  index k_name(k)
) engine=InnoDB;

insert into t_innodb values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

主键索引

key：主键值

data：主键这一行对应的其他列的数据

在InnoDB的主键索引中，索引和数据是存储在同一个数据页中，也就是索引和数据是存储在一起的，这种叫做聚集索引。

在InnoDB中，数据是依附于主键索引树来存储的，假如没有主键的话，那么就不存在主键索引树，那么数据也没办法存储。
所以对于InnoDB的表来说，必须得有一个主键。
对于InnoDB的表来说，如果用户在建表的时候，没有设置主键，那么InnoDB会维护一个隐藏的列来当做主键。

1.myisam使用索引存储。主键索引和非主键索引，其实存储的都是地址。都需要去数据文件中找这个数据

2.innodb使用索引存储，主键索引，直接存储的是数据。非主键索引，存储的是主键的值。

select * from t where k=3;

非主键索引

非主键索引是指根据其他的列建立的索引。

key：索引列的值

data：这一行数据对应的主键值

在InnoDB的非主键索引中，索引只和主键存储在到了一起，实际上没有和数据存储在一起，其实也是非聚集索引。

对于MyISAM来说，主键索引和非主键索引，都是怎么存的？

都是存的B+树，然后key是索引的值，data都是存的地址。这个地址是指向MYD文件里面的。

对于InnoDB来说，主键索引和非主键索引。

主键索引，存的B+树，key是主键的值，value是这一行的其他值。

（100,1，‘aa'）

对于非主键索引，key存的是索引的值，value是主键的值。

MyISAM 与InnoDB的区别

存储的文件不一样，MyISAM有三个文件(frm MYD MYI)、InnoDB只有两个文件(frm ibd)。
InnoDB支持事务、MyISAM不支持事务
既然MyISAM不支持事务，那么MyISAM还有没有用呢？
什么样的表不需要事务呢？存储什么样的数据才不需要事务呢？什么样的数据不需要使用增删改呢？历史数据。普通的日志数据。
InnoDB支持外键，MyISAM不支持外键
InnoDB支持表锁和行锁，MyISAM只支持表锁
image-20220516173955741

Innodb举例

还是使用之前的数据。

mysql> create table T (
  ID int primary key,
  k int NOT NULL DEFAULT 0, 
  s varchar(16) NOT NULL DEFAULT '',
  index k(k)
) engine=Innodb;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

如果现在查询一条SQL，经历怎样的过程？

如果查询的SQL是这样的： select * from T where id=500;

回表

select * from T where k =3;

在k索引树上找到k=3的记录，取得ID=300
再到ID索引树查到ID=300对应的行
再到主键索引树上找到k=5的记录，发现不符合条件。

在这个过程中，回到主键索引树搜索的过程，我们称为回表。可以看到，这个查询过程读了 k 索引树的 2 条记录（步骤 1、3 ），回表了一次（步骤 2 ）。在这个例子中，由于查询结果所需要的数据只在主键索引上有，所以不得不回表。那么，有没有可能经过索引优化，避免回表过程呢？

如果我们写得SQL是这样： select id from T where k=3;

后续，需要什么字段，拿什么字段，不要直接写*。有可能会造成不必要的回表。

select * from T where k between 3 and 5;

这个SQL，会经历怎样的过程？

select * from T where k between 3 and 5;

去k索引树上找，k=3。拿到id=300
回主键索引树，取得这一行的数据。
去k索引树，往后拿5，拿到id=500
回主键索引树，取得这一行的数据。拿id=500的数据
再往后拿，拿到k=6. 不符合条件，结束。

这个过程，我们在k索引树上读了三条记录（3 5 6）。回表了两次(300 500)

覆盖索引

select ID from T where k =3

如果执行的语句是这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

今后建议大家，不要写 select * from T where k=3; 需要哪些列，你就把这些列，全部写出来。

索引的语法

我们给一个列声明为主键，默认主键这一列就会是主键索引（主键这一列会默认创建一个主键索引树）

-- 查询索引
show index from innodb_user;

drop table if exists student1;
-- 建立索引
create table student1(
	id int PRIMARY KEY,
	name varchar(20),
	age int(10),
	gender varchar(10),
    -- index  索引的名字(列名)
    -- index 索引的名字(列名1, 列名2)  联合索引
	index idx_name(name) using BTREE
)ENGINE=InnoDB ;

select * from student1;

show index from student;

-- 删除索引
-- alter table TABLE_NAME drop index INDEX_NAME;
alter table student1 drop index idx_name;

-- 添加索引
alter table student add index idx_age(age);

alter table student add index idx_name_age(name,age);

有时候发现，有一条SQL，特别慢，怎么办？

首先，需要看一下这个SQL。SQL是否写得有问题： select * from t where s = 'ee';

其次，如果条件没有办法动。尝试建索引。

explain。下去可以看下。可以看查询的过程，查询中，是否走了索引。

select * from t where k=5 and s = 'ee';

面试题

索引采用的是什么数据结构？为什么采用这种数据结构
B+树。列举一下其他的数据结构，对比一下。
数据库为什么推荐使用自定义主键，并且在MySQL中使用推荐使用主键自增的策略？
- 自定义主键：MySQL默认的使用的是InnoDB存储引擎，那么InnoDB存储引擎的数据和主键索引树是绑定在一起的，假如没有主键索引树，那么数据没有办法存储。假如没有给表指定主键的话，那么InnoDB会创建一个隐藏的列来当做主键，并建立主键索引树。假如使用了隐藏的列来当做的主键的话，那么我么查询的时候，就会浪费主键索引索引树带来的索引性能，所以推荐自己定义主键。
- 自增的策略：
  因为自增的策略，在插入的时候，永远只会插入到索引树的右侧，那么这样就能保证树的结构不会发生比较大的改变，而结构改变是需要消耗时间的，所以这样就能保证插入的效率会比较稳定。
```
create table student1(
	id int primary key auto_increment,
    name varchar(255),
    
    create_time timestamp default current_timestamp,
    update_time timestamp default current_timestamp on update current_timestamp
)
```
InnoDB和MyISAM有什么区别？什么情况下使用MyISAM？

什么是回表？如何避免回表？

create table ts(
	id int PRIMARY KEY,
	name varchar(20),
	age int,
	index idx_name(name,age) using BTREE
)character set utf8;


select * from ts where id = 1;  -- 查询主键索引树、查询速度快

select * from ts where name='zhangsan';  --  会先去 idx_name索引树上找。 回表。

select * from ts where age = 20;  -- 遍历整个主键索引树、查询速度很慢

-- 先查询index_name 整个索引的索引树，查询到的结果是主键
-- 再根据查询到的主键值 去主键索引树查询 对应的数据
select id,name,age from ts where name = '张三'; 


-- 最左匹配元素
-- 索引的生效范围是最左开始的。   (name,age,address )
-- 查询中，写什么，能走到索引？
-- select * from ts where name='zhangsan';  -- 光走age不行。
-- select * from ts where name='zhangsan' and age=20;

-- (a, b, c, d)   用哪些作为查询条件，可以走这颗索引树   a       a,b     a,b,c    a,b,c,d

回表：在一次查询中，假如需要先根据非主键索引树查询主键值，然后再根据主键值查询主键索引树，这种查询了两遍索引树的情况，叫做回表。
在实际的工作中，应该要尽量避免回表的情况出现，如何避免呢？
尽量使用主键查询
尽量避免写 select *
可以考虑使用联合索引.多个列创建一个索引。

索引性能这么好，是不是一个表建立的索引越多越好？
不是。
1. 声明一个索引列，需要建立一个索引树，需要占用空间
2. 假如声明的索引变多了之后，对应的索引树也会变多，查询的效率固然会提升，但是增删改的时候要去改变数据，改变数据势必会改变索引树的结构，维护这些索引树的成本也就提升了，增删改的效率也就降低了。
那么一般针对一个表，建立几个索引比较合适呢？通常默认为一个表建立的索引不要超过5个。
什么样的列适合当索引？
- 数据不重复出现的
- 值尽量不为空的（null）
- 业务场景中查询条件比较多的
- 这一列的值不经常变化的

三层可以存多少数据？

B+树和二叉搜索树的效率。

对于Innodb的B+树来说，节点大小是16k。

id bigint ，还有引用，在MySQL中大概占6字节。bigint 8个字节。总共14个字节。

16 * 1024 / 14 = 1170个数据

底下层1k一行。所以最终三层可以存储1170*1170*16 = 2KW

最终，让第一层常驻内存，也就是我只用读两次磁盘，就可以获取我想要的数据。

05. 索引

# 索引

# 介绍

# 索引的数据结构

# 索引的实现

# MyISAM

# 主键索引

# 非主键索引

# InnoDB

# 主键索引

# 非主键索引

# MyISAM 与InnoDB的区别

# Innodb举例

# 回表

# 覆盖索引

# 索引的语法

# 面试题

索引

介绍

索引的数据结构

索引的实现

MyISAM

主键索引

非主键索引

InnoDB

主键索引

非主键索引

MyISAM 与InnoDB的区别

Innodb举例

回表

覆盖索引

索引的语法

面试题