关于程序员:万字详解-阿里面试真题请你说说索引的原理

前言

置信每个 IT 界大佬，简历上少不了 Mysql 索引这个关键字，但如果被问起来，你能说出多少干货呢？先看上面几个问题测试一下吧：

• 索引是怎么进步查问效率的？能够为了进步查问效率减少索引么？
• mysql 索引零碎采纳的数据结构是什么？
• 为什么要应用 B + 树？
• 汇集索引绝对于非汇集索引的区别？
• 什么是回表？
• 什么是索引笼罩？
• 什么是最左匹配准则？
• 索引生效场景有哪些，如何防止？

这些问题说不明确？不要慌！请带着问题向下看。

​

1 索引原理探索

什么是数据库索引？先来个官网一些的定义吧。

在关系数据库中，索引是一种独自的、物理的数对数据库表中一列或多列的值进行排序的一种存储构造，它是某个表中一列或若干列值的汇合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

这段话有点绕，其实把索引了解为图书目录，就十分好了解了。

如果咱们想在图书中查找特定内容，在没有目录的状况下只能逐页翻找。与此相似，当执行上面这样一条 SQL 语句时，如果没有索引，数据库如何查找到绝对应的记录呢？

SELECT * FROM student WHERE name='叶良辰'

搜索引擎只能扫描整个表的每一行，并顺次比照判断 name 的值是否等于“叶良辰”。咱们晓得，单纯的内存运算是很快的，但从磁盘中取数据到内存中是绝对慢的，当表中有大量数据时，内存与磁盘交互次数大大增加，这就导致了查问效率低下。

1.1 B 树与 B + 树

绝对于 cpu 和内存操作，磁盘 IO 开销很大，非常容易成为零碎的性能瓶颈，因而计算机操作系统做了一些优化：

当一次 IO 时，将相邻的数据也都读取到内存缓冲区内，而不是仅仅读取以后磁盘地址的数据。因为部分预读性原理通知咱们，当计算机拜访一个地址的数据的时候，与其相邻的数据也会很快被拜访到。每一次 IO 读取的数据咱们称之为一页(page)。具体一页有多大数据跟操作系统无关，个别为 4k 或 8k，也就是咱们读取一页内的数据时候，实际上才产生了一次 IO，这个实践对于索引的数据结构设计十分有帮忙。

为什么索引能晋升数据库查问效率呢？根本原因就在于索引缩小了查问过程中的 IO 次数。那么它是如何做到的呢？应用 B + 树。上面先简略理解一下 B 树和 B + 树。

B 树，即均衡多路查找树（B-Tree），是为磁盘等外存储设备设计的一种均衡查找树。

B 树简略示意图：

​

察看上图可见 B 树的两个特点：

1. 树内的每个节点都存储数据
2. 叶子节点之间无指针连贯

B+ 树简略示意图：

​

再看 B + 树绝对于 B 树的两个特点：

1. 数据只呈现在叶子节点
2. 所有叶子节点减少了一个链指针

叶子结点是离散数学中的概念。一棵树当中没有子结点（即度为 0）的结点称为叶子结点，简称“叶子”。叶子是指出度为 0 的结点，又称为终端结点。

然而，为什么是 B + 树而不是 B 树呢？起因有两点：

1. B 树每个节点中不仅蕴含数据的 key 值，还有 data 值。而每一个页的存储空间是无限的，如果 data 数据较大时将会导致每个节点能存储的 key 的数量很小，要保留同样多的 key，就须要减少树的高度。树的高度每减少一层，查问时的磁盘 I / O 次数就减少一次，进而影响查问效率。而在 B +Tree 中，所有数据记录节点都是依照键值大小程序寄存在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样能够大大加大每个节点存储的 key 值数量，升高 B + 树的高度。
2. B+ 树的叶子节点上有指针进行相连，因而在做数据遍历的时候，只须要对叶子节点进行遍历即可，这个个性使得 B + 树非常适合做范畴查问。

1.2 聚簇索引与非聚簇索引

首先，为了不便了解，咱们先理解一下汇集索引（clustered index）和非汇集索引（secondary index，也称辅助索引或一般索引）。这两种索引是按存储形式进行辨别的。

汇集索引（clustered）也称聚簇索引，这种索引中，数据库表行中数据的物理程序与键值的逻辑（索引）程序雷同。一个表的物理程序只有一种状况，因而对应的汇集索引只能有一个。如果某索引不是汇集索引，则表中的行物理程序与索引程序不匹配，与非汇集索引相比，汇集索引有着更快的检索速度。

如果不好了解，请看上面这个表：

​

表中 id 和物理地址是保持一致程序的，id 较大的行，其物理地址也比拟靠后。因为汇集索引的个性，它的建设有肯定的特殊要求：

1. 在 Innodb 中，聚簇索引默认就是主键索引。
2. 如果表中没有定义主键，那么该表的第一个惟一非空索引被作为汇集索引。
3. 如果没有主键也没有适合的惟一索引，那么 innodb 外部会生成一个暗藏的主键作为汇集索引，这个暗藏的主键是一个 6 个字节的列，改列的值会随着数据的插入自增。

大家还记得，自增主键和 uuid 作为主键的区别么？因为主键应用了汇集索引，如果主键是自增 id，那么对应的数据肯定也是相邻地寄存在磁盘上的，写入性能比拟高。如果是 uuid 的模式，频繁的插入会使 innodb 频繁地挪动磁盘块，写入性能就比拟低了。

1.3 索引原理图示

上面用一个通过主键索引查找数据的案例演示一下索引的原理。如果有 student 表如下，id 上建设了汇集索引，name 上建设非汇集索引：

idnamescore2 叶良辰 784 龙傲天 8810 赵日天 5611 徐胜虎 77

1.3.1 聚簇索引

当咱们执行上面的语句时，

SELECT name FROM student WHERE id=2

查问过程如下图所示：

​

用语言形容一下，是这样的：

1. 先找到根节点所在磁盘块，读入内存。（第 1 次磁盘 I / O 操作）
2. 在内存中判断 id= 3 所在区间(0,8)，找到该区间对应的指针 1（第 1 次内存查找）
3. 依据指针 1 记录的磁盘地址，找到磁盘块 2 并读入内存（第 2 次磁盘 I / O 操作）
4. 在内存中判断 id= 3 所在区间(0,4)，找到该区间对应的指针 2（第 2 次内存查找）
5. 依据指针 2 记录的磁盘地址，找到磁盘块 4 并读入内存（第 3 次磁盘 I / O 操作）
6. 在内存中查找到 id= 2 对应的数据行记录（第 3 次内存查找）

咱们晓得，磁盘 I / O 绝对于内存运算（尤其内存中的主键是有序排列的，利用二分查找等算法效率十分高）耗时高得多，因而在数据库查问中，缩小磁盘拜访时数据库的性能优化的次要伎俩。

而剖析下面过程，发现整个查问只须要 3 次磁盘 I / O 操作（其实 InnoDB 引擎是将根节点常驻内存的，第 1 次磁盘 I / O 操作并不存在）和 3 次内存查找操作。绝对于不应用索引的遍历式查找，大大减少了对磁盘的拜访，因而查找效率大幅提高。然而，因为索引树要与表中数据保持一致，因而当表产生数据增删改时，索引树也要相应批改，导致写数据比没有索引时开销大一些。

1.3.2 非聚簇索引

好，汇集索引看完后，再看非汇集索引。

​

如上图，多加一个索引，就会多生成一颗非聚簇索引树。因而，索引不能随便减少。在做写库操作的时候，须要同时保护这几颗树的变动，导致效率升高！

另外，仔细观察的人肯定会发现，不同于汇集索引，非汇集索引叶子节点上不再是实在数据，而是存储了索引字段本身值和主键索引。因而，当咱们执行以下 SQL 语句时：

SELECT id,name FROM student WHERE name='叶良辰';

整个查问过程与汇集索引的过程一样，只须要扫描一次索引树（n 次磁盘 I / O 和内存查问），即可拿到想要的数据。

然而，如果查问 name 索引树没有的数据时，状况就不一样了：

SELECT score FROM student WHERE name='叶良辰';

​

留神看上图中的红色箭头，因为扫描完 name 索引后，Mysql 只能获取到对应的 id 和 name，而后用 id 的值再去汇集索引中去查问 score 的值。这个过程绝对于汇集索引查问的效率降落，能够了解了吧。

这就是通常所说的回表或者二次查问：应用汇集索引查问能够间接定位到记录，而一般索引通常须要扫描两遍索引树，即先通过一般索引定位到主键值，在通过汇集索引定位到行记录，这就是所谓的回表查问，它的性能比扫描一遍索引树低。

既然一般索引会导致回表二次查问，那么有什么方法能够应答呢？建设联结索引！

1.3.3 联结索引

所谓联结索引，也称多列所谓，就是建设在多个字段上的索引，这个概念是跟单列索引绝对的。联结索引仍然是 B + 树，但联结索引的健值数量不是一个，而是多个。构建一颗 B + 树只能依据一个值来构建，因而数据库根据联结索引最左的字段来构建 B + 树。

例如在 a 和 b 字段上建设联结索引，索引构造将如下图所示：

​

高深莫测，当咱们再执行 SELECT score FROM student WHERE name=’ 叶良辰 ’; 时，能够间接通过扫描非汇集索引间接获取 score 的值，而不再须要到汇集索引上二次扫描了。

最左前缀匹配

联结索引中有一个重要的课题，就是最左前缀匹配。

最左前缀匹配准则：在 MySQL 建设联结索引时会恪守最左前缀匹配准则，即最左优先，在检索数据时从联结索引的最右边开始匹配。

这是为什么呢？咱们再仔细观察索引构造，能够看到索引 key 在排序上，首先按 a 排序，a 相等的节点中，再按 b 排序。因而，如果查问条件是 a 或 a 和 b 联查时，是能够利用到索引的。如果查问条件是独自应用 b，因为无奈确定 a 的值，因而无奈应用索引。

如果在 table 表的 a,b,c 三个列上建设联结索引，简要分类剖析下联结索引的最左前缀匹配。

首先看等值查问：

1、全值匹配查问时（where 子句搜寻条件程序调换不影响索引应用，因为查问优化器会主动优化查问程序），能够用到联结索引

SELECT * FROM table WHERE a=1 AND b=3 AND c=2
SELECT * FROM table WHERE b=3 AND c=4 AND a=2

2、匹配右边的列时，能够用到联结索引

SELECT * FROM table WHERE a=1
SELECT * FROM table WHERE a=1 AND b=3

3、未从最左列开始时，无奈用到联结索引

SELECT * FROM table WHERE b=1 AND b=3

4、查问列不间断时，无奈应用联结索引（会用到 a 列索引，但 c 排序依赖于 b，所以会先通过 a 列的索引筛选出 a = 1 的记录，再在这些记录中遍历筛选 c = 3 的值，是一种不齐全应用索引的状况）

SELECT * FROM table WHERE a=1 AND c=3

再看范畴查问：

1、范畴查问最左列，能够应用联结索引

SELECT * FROM table WHERE a>1 AND a<5;

2、准确匹配最左列并范畴匹配其右一列（a 值确定时，b 是有序的，因而能够应用联结索引）

SELECT * FROM table WHERE a=1 AND b>3;

3、准确匹配最左列并范畴匹配非右一列（a 值确定时，c 排序依赖 b，因而无奈应用联结索引，但会应用 a 列索引筛选出 a >2 的记录行，再在这些行中条件 c >3 逐条过滤）

SELECT * FROM table WHERE a>2 AND c>5;

索引的原理探索到此结束，这部分内容堪称最难啃的骨头。不过，能保持读下来的敌人，你的播种也肯定良多。接下来的内容就轻松愉悦多了。

​

2 索引的正确应用姿态

索引的长处如下：

• 通过创立惟一索引能够保障数据库表中每一行数据的唯一性。
• 能够大大放慢数据的查问速度，这是应用索引最次要的起因。
• 在实现数据的参考完整性方面能够减速表与表之间的连贯。
• 在应用分组和排序子句进行数据查问时也能够显著缩小查问中分组和排序的工夫。

既然索引这么好，那么咱们是不是纵情应用索引呢？非也，索引长处显著，但绝对应，也有毛病：

• 创立和保护索引组要消耗工夫，并且随着数据量的减少所消耗的工夫也会减少。
• 索引须要占磁盘空间，除了数据表占数据空间以外，每一个索引还要占肯定的物理空间。
• 当对表中的数据进行减少、删除和批改的时候，索引也要动静保护，这样就升高了数据的保护速度。

因而，应用索引时要兼顾索引的优缺点，寻找一个最无利的平衡点。

2.1 索引的类型辨别

以 InnoDB 引擎为例，Mysql 索引能够做如下辨别。

首先，索引能够分为汇集索引和非汇集索引，它们的区别和含意在前文有大幅介绍，此处不再赘述。

其次，从逻辑上，索引能够辨别为：

• 一般索引：一般索引是 MySQL 中最根本的索引类型，它没有任何限度，惟一工作就是放慢系统对数据的访问速度。一般索引容许在定义索引的列中插入反复值和空值。
• 惟一索引：惟一索引与一般索引相似，不同的是创立唯一性索引的目标不是为了进步访问速度，而是为了防止数据呈现反复。惟一索引列的值必须惟一，容许有空值。如果是组合索引，则列值的组合必须惟一。创立惟一索引通常应用 UNIQUE 关键字。例如在 student 表中的 id 字段上建设名为 index_id 的索引 CREATE UNIQUE INDEX index_id ON tb_student(id);
• 主键索引：主键索引就是专门为主键字段创立的索引，也属于索引的一种。主键索引是一种非凡的惟一索引，不允许值反复或者值为空。创立主键索引通常应用 PRIMARY KEY 关键字。不能应用 CREATE INDEX 语句创立主键索引。
• 空间索引：空间索引是对空间数据类型的字段建设的索引，空间索引次要用于天文空间数据类型，很少用到。
• 全文索引：全文索引次要用来查找文本中的关键字，只能在 CHAR、VARCHAR 或 TEXT 类型的列上创立。在 MySQL 中只有 MyISAM 存储引擎反对全文索引。全文索引容许在索引列中插入反复值和空值。

索引在理论应用上分为单列索引和多列索引。

单列索引：单列索引就是索引只蕴含原表的一个列。在表中的单个字段上创立索引，单列索引只依据该字段进行索引。

例如在 student 表中的 address 字段上建设名为 index_addr 的单列索引，address 字段的数据类型为 VARCHAR(20)，索引的数据类型为 CHAR(4)。SQL 语句如下：

CREATE INDEX index_addr ON student(address(4)); 

这样，查问时能够只查问 address 字段的前 4 个字符，而不须要全副查问。

多列索引也称为复合索引或组合索引。绝对于单列索引来说，组合索引是将原表的多个列独特组成一个索引。

多列索引是在表的多个字段上创立一个索引。该索引指向创立时对应的多个字段，能够通过这几个字段进行查问。然而，只有查问条件中应用了这些字段中第一个字段时，索引才会被应用。

上面在 student 表中的 name 和 address 字段上建设名为 index_na 的索引，SQL 语句如下：

CREATE INDEX index_na ON tb_student(name,address); 

该索引创立好了当前，查问条件中必须有 name 字段能力应用索引。

一个表能够有多个单列索引，但这些索引不是组合索引。一个组合索引本质上为表的查问提供了多个索引，以此来放慢查问速度。比方，在一个表中创立了一个组合索引 (c1，c2，c3)，在理论查问中，零碎用来理论减速的索引有三个：单个索引(c1)、双列索引(c1，c2) 和多列索引(c1，c2，c3)。

2.2 索引的查看

查看索引的语法格局如下：

SHOW INDEX FROM < 表名 >

查问后果阐明如下：

​

2.3 索引的创立

创立索引有 3 种形式：

1、CREATE INDEX 间接创立：

能够应用专门用于创立索引的 CREATE INDEX 语句在一个已有的表上创立索引，但该语句不能创立主键。

CREATE < 索引名 > ON < 表名 > (< 列名 > [< 长度 >] [ASC | DESC])

语法阐明如下：

• < 索引名 >：指定索引名。一个表能够创立多个索引，但每个索引在该表中的名称是惟一的。
• < 表名 >：指定要创立索引的表名。
• < 列名 >：指定要创立索引的列名。通常能够思考将查问语句中在 JOIN 子句和 WHERE 子句里经常出现的列作为索引列。
• < 长度 >：可选项。指定应用列前的 length 个字符来创立索引。应用列的一部分创立索引有利于减小索引文件的大小，节俭索引列所占的空间。在某些状况下，只能对列的前缀进行索引。索引列的长度有一个最大下限 255 个字节（MyISAM 和 InnoDB 表的最大下限为 1000 个字节），如果索引列的长度超过了这个下限，就只能用列的前缀进行索引。另外，BLOB 或 TEXT 类型的列也必须应用前缀索引。
• ASC|DESC：可选项。ASC 指定索引依照升序来排列，DESC 指定索引依照降序来排列，默认为 ASC。

例如，在 student 表 name 字段上创立索引：

• 一般索引：CREATE INDEX index_name ON student (name)
• 惟一索引：CREATE UNIQUE index_name ON student (name)

创立一般索引应用的关键字，例如在 student 表 name 字段上创立一个一般索引 index_name

• 建表创立：CREATE TABLE student(id INT NOT NULL,name CHAR(45) DEFAULT NULL,INDEX(name));
• ALTER TABLE：ALTER student ADD INDEX index_name (name)

2、CREATE TABLE 时创立

索引也能够在创立表（CREATE TABLE）的同时创立。在 CREATE TABLE 语句中增加以下语句。例如创立 student 表时在 name 字段增加索引：

• 主键索引：CREATE TABLE student(name CHAR(45) PRIMARY KEY);
• 惟一索引：CREATE TABLE student(id INT NOT NULL,name CHAR(45) DEFAULT NULL,UNIQUE INDEX(name));
• 一般索引：CREATE TABLE student(id INT NOT NULL,name CHAR(45) DEFAULT NULL,INDEX(name));

3、ALTER TABLE 时创立

ALTER TABLE 语句也能够在一个已有的表上创立索引。例如在 student 表 name 字段上创立一个一般索引 index_name：

• 主键索引：ALTER TABLE student ADD PRIMARY KEY (name);
• 惟一索引：ALTER TABLE student ADD UNIQUE INDEX index_name(name);
• 一般索引：ALTER TABLE student ADD INDEX index_name(name);

2.4 索引生效场景

创立了索引并不意味着居安思危，在很多场景下，索引会生效。上面列举了一些导致索引生效的情景，是咱们写 SQL 语句时应尽量避免的。

1、条件字段起因

• 单字段有索引，WHERE 条件应用多字段（含带索引的字段），例如 SELECT * FROM student WHERE name =’ 张三 ’ AND addr = ‘ 北京市 ’ 语句，如果 name 有索引而 addr 没索引，那么 SQL 语句不会应用索引。
• 多字段索引，违反最佳左前缀准则。例如，student 表如果建设了 (name,addr,age) 这样的索引，WHERE 后的第一个查问条件肯定要是 name，索引才会失效。

2、<>、NOT、in、not exists

当查问条件为 等值或范畴查问 时，索引能够依据查问条件去找对应的条目。否则，索引定位艰难（联合咱们查字典的例子去了解），执行打算此时可能更偏向于全表扫描，这类的查问条件有：<>、NOT、in、not exists

3、查问条件中应用 OR

如果条件中有 or，即便其中有条件带索引也不会应用(因而 SQL 语句中要尽量避免应用 OR)。要想应用 OR，又想让索引失效，只能将 OR 条件中的每个列都加上索引。

4、查问条件应用 LIKE 通配符

SQL 语句中，应用后置通配符会走索引，例如查问姓张的学生（SELECT FROM student WHERE name LIKE ‘ 张 %’），而前置通配符 (SELECT FROM student WHERE name LIKE ‘% 东 ’) 会导致索引生效而进行全表扫描。

5、索引列上做操作（计算，函数，（主动或者手动）类型 装换）

有以下几种例子：

• 在索引列上应用函数：例如 select from student where upper(name)=’ZHANGFEI’; 会导致索引生效，而 select from student where name=upper(‘ZHANGFEI’); 是会应用索引的。
• 在索引列上计算：例如 select * from student where age-1=17;

6、在索引列上应用 mysql 的内置函数，索引生效

例如，SELECT * FROM student WHERE create_time

7、索引列数据类型不匹配

例如，如果 age 字段有索引且类型为字符串（个别不会这么定义，此处只是举例）但条件值为非字符串，索引生效，例如 SELECT * FROM student WHERE age=18 会导致索引生效。

8、索引列应用 IS NOT NULL 或者 IS NULL 可能会导致无奈应用索引

B-tree 索引 IS NULL 不会应用索引，IS NOT NULL 会应用，位图索引 IS NULL、IS NOT NULL 都会应用索引。

最初，对索引的应用做一个总结吧：

1. 索引有利于查问，但不能随便加索引，因为索引不仅会占空间，而且须要在写库时进行保护。
2. 如果多个字段经常须要一起查问，那么在这几个字段上建设联结索引是个好方法，同时留神最左匹配准则。
3. 不要在反复度很高的字段上加索引，例如性别。
4. 防止查问语句导致索引生效

举荐浏览

** 为什么阿里巴巴的程序员成长速度这么快，看完他们的内部资料我懂了
**

从事开发一年的程序员能拿到多少钱？

字节跳动总结的设计模式 PDF 火了，完整版凋谢下载

刷 Github 时发现了一本阿里大神的算法笔记！标星 70.5K

程序员 50W 年薪的常识体系与成长路线。

对于【暴力递归算法】你所不晓得的思路

开拓鸿蒙，谁做零碎，聊聊华为微内核

 
=

看完三件事❤️

如果你感觉这篇内容对你还蛮有帮忙，我想邀请你帮我三个小忙：

点赞，转发，有你们的『点赞和评论』，才是我发明的能源。

关注公众号『Java 斗帝』，不定期分享原创常识。

同时能够期待后续文章 ing????