MySQL索引原理

编程之心

发布于 2021-07-14 16:43:41

4150

发布于 2021-07-14 16:43:41

文章被收录于专栏：编程之禅编程之禅

MySQL索引原理

MySQL 的索引

概述

索引是数据库中一个排序的数据结构，用来协助快速查询和更新数据库表中的数据；数据是以文件的形式存放在磁盘上的，每一行数据都有它的磁盘地址；当没有索引时，比如从 **500w** 条数据中检索出一条数据，只能依次遍历这张表的全部数据，直到找到这条数据。但是有了索引后，只需要在索引里去检索这条数据就可以了，因为它是一种专门进行数据检索特殊的数据结构，在找到数据存放的磁盘地址后就可以拿到数据。在 **InnoDB** 存储引擎中，索引有三类：
- 普通（**normal**）：非唯一索引，没有任何限制；
- 唯一（**unique**）：唯一索引要求键值不能重复；主键索引是一种特殊的唯一索引，还多了一个条件限制，要求键值不能为空；
- 全文（**fulltext**）：主要针对比较大的数据；例存放 **n KB** 的消息内容，当要解决 **like** 查询效率低的问题时就可以创建全文索引。只有文本类型字段才可以创建全文索引（**cahr、varchar、text**）。在 **MySQL** 中的 **InnoDB & MyISAM** 存储引擎都支持全文索引。

索引存储模型

二分查找算法

二分查找有时也被称为折半查找，当数据已经排序完后，把候选数据缩小一半，这种方式效率比较高。所以可以使用有序数组来作为索引的数据结构，有序数组的等值和比较查询效率都很好，但更新数据时可能会移动大量的数据，所以只是适合存储静态数据。为了支持频繁地修改，可以采用链表，但是他的查询效率就不高了。针对该问题就出现了二叉查找树。

二叉查找树

二叉查找树（**BST Binary Search Trees**）的特点是左子树所有的节点都小于父节点，右子树所有的节点都大于父节点，其实就是个有序的线性表。二叉查找树能实现快速查找和插入；

但二叉查找树的查找耗时和树的深度相关的，在最坏的情况下时间复杂度会退化成 **O(n)**，比如把刚刚的数据按照有序插入后会变成链表（斜树），在这种情况下不能达到快速检索的效率，与顺序查找效率是等价的。造成它倾斜的原因是左右子树深度差别太大，这个树的左子树没有节点，就就是说不够平衡。所以为了解决该问题就出现了平衡二叉树。

平衡二叉树

平衡二叉树（**Balanced Binary Search Trees**）是指左右子树的深度差绝对值不能超过 **1**；比如左子树的深度是 **2**，右子树的深度只能是 **1 | 3**；在这时按照顺序插入 **1、2、3、4、5、6** 就不会变成一颗斜树；可以通过平衡二叉树测试看到在插入 **1、2** 后，如果按照二叉查找树的定义，**3** 是会插入在 **2** 的右边的。但是在平衡二叉树中的根节点 **1** 的右节点深度就会变成 **2**，而左节点的深度是 **0**，因为根节点 **1** 没有左子节点，所以就会违反平衡二叉树的定义。所以在操作的过程中可以看到它的右节点是右-右型的，在这时就需要把 **2** 提上去，这个操作称为左旋。同样，再以 **7、6、5** 的顺序插入就会变成左左形，就会发生右旋操作，把 **6** 提上去。所以为了保持平衡，**AVL** 树在插入和更新数据时执行了一系列的计算和调整操作。解决了平衡的问题后，就需要解决 **AVL** 树作为索引是怎么查询数据的问题。在平衡二叉树中，一个节点的大小是一个固定的单位，作为索引应该存储三块内容：
- 索引的键值：例如在 **id** 上创建了一个索引，在使用 **where id = 1** 的条件进行查询时就会找到索引里面的 **id** 的这个键值；
- 数据的磁盘地址：因为索引的作用就是去查找数据存放的地址；
- 节点的引用：因为是二叉树，它必须还需要有左子节点和右子节点的引用，这样才能找到下一个节点。

InnoDB 存储引擎的逻辑存储结构

**MySQL** 的存储结构分为：表空间、段、簇、页以及行

表空间（**Tablespace**）：表空间可以看做是 **InnoDB** 存储引擎逻辑结构的最高层，所有的数据都存放在表空间中；表空间又分为系统表空间、独占表空间、通用表空间、临时表空间以及 **Undo** 表空间；
段（**Segment**）：表空间是由各个段组成的，常见的段有数据段、索引段、回滚段等，段是一个逻辑的概念。一个 **ibd** 文件（独立表空间文件）里是由很多个段组成。创建一个索引时会创建两个段：
- 索引段 **leaf node segment**：主要管理非叶子节点的数据
- 数据段：**non-leaf node segment**：主要管理叶子节点的数据
簇（**Extent**）：一个段又分为很多个区，每个区的大小都是 **1MB**（64 个连续的页）；每一个段至少有一个簇，一个段所管理的空间大小是无限的，可以一直扩展下去，但是扩展的最小单位就是簇。
页（**Page**）：为了高效管理物理攻击，对簇进行进一步的细分为页；每个簇都是由 **64** 个连续的页空间组成，每个页的大小是 **16 KB** 并且是 **InnoDB** 存储引擎的磁盘管理中的最小单位。这个页的大小是可以通过 **innodb_page_size** 进行设置；这些页在物理上和逻辑上都是连续的。所以说一个表空间最多拥有 **2** 个页，默认情况下一个页的大小为 **16KB**，也就是说一个表空间最多可以存储 **64TB** 的数据。

行（**Row**）：**InnoDB** 存储引擎是面向行的，意味着数据的存放按行进行存放。

AVL 树用于存储索引数据

索引的数据是存放在硬盘上的

-- 查看数据和索引的大小
SELECT
	CONCAT( ROUND( SUM( DATA_LENGTH / 1024 / 1024 ), 2 ), 'MB' ) AS data_len,
  CONCAT( ROUND( SUM( INDEX_LENGTH / 1024 / 1024 ), 2 ), 'MB' ) AS index_len 
FROM
	information_schema.TABLES 
WHERE
	table_schema = 'mybatis' 
	AND table_name = 'tb_user';

在使用树的数据结构来存储索引时，访问一个节点就需要与磁盘之间发生一个 **IO** 操作，**InnoDB** 操作磁盘的最小的单位是一页（磁盘块），大小是 **16KB（16384 bytes）**；那么一个树的节点就是 **16KB** 大小。当一个节点只存储一个键值、数据和引用（比如 **int** 类型的字段，可能只是用了十几个或几十个字节，它远远达不到 **16KB** 的容量）就访问一个树节点去进行一次 **I/O** 操作时，就会浪费大量的空间。所以当每个节点存储的数据太少，从索引中找到所需要的数据就需要访问更多的节点，也就意味着与磁盘的交互次数就会增多。如果只是使用机械硬盘，每次从磁盘读取数据就需要 **10ms** 左右的寻址时间，交互次数越多的情况下，消耗的时间也就越多。如下图，当查询 **id = 6** 时就需要查询两个子节点，要和磁盘交互 **3** 次；如果存储的数据是百万级以上，那么这个查询的时间就更加难以预测。为了解决该问题就需要让每个节点存储更多的数据，而节点上的关键字数量越多的情况下，指针数也越多，意味着有更多的分叉。当分叉越来越多时，随之树的深度就会减少；这时就称之为多路平很二叉树。

多路平衡二叉树

多路平衡二叉树也称为 **Balanced Tree（B Tree）**，它与 **AVL** 树一样，**B** 树在枝节点和叶子节点存储键值、数据地址和节点应用；其特点是分叉数量永远比关键字字数多 **1**；

**B** 树的分裂与合并演示：例如当 Max.Degree = 3 时，插入 **1、2、3** 后，在插入 **3** 时应该在第一个磁盘块，但是如果一个节点有三个关键字时，意味着有 **4** 个指针；子节点会变成 **4** 路，所以这时需要进行分裂，把中间的数字 **2** 提为父节点，把 **1、3** 变为 **2** 的子节点。在删除时会有相反的合并操作，然后再继续看 **4、5** 的分裂与合并操作。在下面图中可以看到在更新索引时会有大量的索引的结构调整，所以这就是为什么不要在频繁更新的列上建立索引的原因，或者不要更新主键；节点的分裂和合并就是 **InnoDB** 存储引擎中的页的分裂与合并。

B+ 树

**B+ Tree** 是 **B Tree** 的改良版，比 **B Tree** 解决了更加全面的问题；它的特点是它的关键字的数量与路数相等，还有 **B+ Tree** 的根节点和枝节点中都不会存储数据，只有在叶子节点才存储数据。搜索到关键字不会直接返回，会到最后一层的叶子节点；例如搜索 **id = 29** 时，虽然在第一层直接命中，但是全部的数据还是在叶子节点上，所以还需要继续往下搜索，一直到叶子节点。

假如索引字段是 **bitint** 类型，长度为 **8** 个字节，指针的大小在 **InnoDB** 源码中设置为 **6** 个字节，加起来就一共有 **14** 个字节；假如一条记录是 **1KB**，一个叶子节点（一页）可以存储 **16** 条记录，而非叶子叶节点可以存储 **16384 / 14 = 1170** 个单元，也代表着有 **1170** 个指针。当树的深度为 **2** 时，有 **1170** 个叶子节点，可以存储 **1170 * 1170 * 16 = 21902400** 条数据。在查找数据时一次页的查找代表一次 **I/O**，也就是说一张 **2000w** 条记录的表，查询数据只需要与 **I/O** 进行 **3** 次交互。在 **InnoDB** 的 **B+ Tree** 的深度一般为 **1 - 3** 层就能满足千万级的数据存储。

**B+ Tree** 的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构；
它是根据左闭右开的区间 **[)** 来检索数据的。
**B+ Tree** 总结：
- 数据搜索过程：
  - 假如需要查找 **29**，在根节点就找到了对应的键值，但因为它不是叶子节点，所以会继续往下寻找。 **29** 是 **[29， 73)** 的左闭右开的区间的临界值，所以会走中间的子节点，然后继续搜索；它又是 **[29， 45)** 的左闭右开的区间的临界值，所以会走左边的子节点，最后在叶子节点上找到了需要的数据。
  - 当存在范围查询时，比如从 **35 - 86** 的数据，那么在找到 **35** 之后，只需要顺着节点和指针顺序遍历就可以一次性访问所有的数据节点，这样就极大地提高了区间查询效率（不需要返回上层父节点重新遍历查找）。
- 特点：
  - **B+ Tree** 是 **B Tree** 的加强版，**B Tree** 能解决的问题，它都能解决；**B Tree** 解决的两大问题是每个节点存储更多的关键字和路数更多；
  - 扫库与扫表更强；在需要对表进行全表扫表时，只需要遍历叶子节点就行，不用遍历整颗 **B+ Tree**** **拿到所有的数据；
  - **B+ Tree** 的磁盘读写能力比 **B Tree** 更强，因为根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字也就更多；
  - 排序能力更强，因为叶子节点上有下一个数据区的指针，数据形成了链表结构；
  - 效率更加稳定，因为 **B+ Tree** 永远是在叶子节点拿到数据，所以 **I/O** 次数是稳定的。

为什么不用红黑树

红黑树也是 BST，但不是严格的平衡二叉树，它必须满足 **5** 个约束：
- 节点分为红色或黑色；
- 根节点必须是黑色的；
- 叶子节点都是黑色的 **NULL** 节点；
- 红色节点的两个子节点都是黑色（不允许两个相邻的红色节点）；
- 从任意节点触发，到每个叶子节点的路径中包含相同数量的黑色节点；
基于红黑树的 **5** 个规则可以得出从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全部是黑色节点）的 **2** 倍。
而在 **InnoDB** 存储引擎中不使用红黑树的原因主要是只有两条路与不够平衡；红黑树一般情况下只是放在内存中使用。
插入数据 **60、56、68、45、64、58、72、43、49**

索引的使用规则

列的离散度

列的离散度指列的全部不同值和所有数据行的比例，数据行数相同的情况下，分子越大，列的离散度就越高。也就是说当列的重复值越多，离散度就越低；反之，离散度越高。比如给 **name | gender** 建立索引，根据字段 **name** 查询很快就能查询出来，但是根据 **gender** 查询，由于该字段的重复率太高，扫描的行数就越多。

联合索引的最左匹配

前面是针对单列创建的索引，但需要多条件查询时就要建立联合索引；单例索引也可以看成是特殊的联合索引。

ALTER TABLE user_innodb DROP INDEX comidx_name_address; 
-- 建立 name 和 address 的联合索引
ALTER TABLE user_innodb add INDEX comidx_name_address (name, address);

联合索引在 **B+ Tree** 中是复合的数据结构，是按照从左到右的顺序来建立搜索树的（name 在左边，**address** 在右边）。这时使用 **select * from person where name = 'John' and address = '广州'** 语句查询时，**B+ Tree** 会先比较 **name** 来确定应该搜索左子节点还是右子节点，当 **name** 相同时再比较 **address**；但是如果查询条件没有 **name** 就不确定查询哪个子节点，因为建立搜索树的时候 **name** 是第一个比较因子，所以用不到索引而进行全文检索。所以在建立联合索引时需要把最常用的列放在最左边

-- 建立 name 和 address 的联合索引，这里相当于建立了两个索引 (name)、(name, address)
CREATE INDEX idx_name_address on person(name, address);
-- 使用两个字段可以用到联合索引
EXPLAIN SELECT * FROM person WHERE name= 'John' AND address = '广州';
-- 使用左边的 name 字段可以用到联合索引
EXPLAIN SELECT * FROM person WHERE name= 'John';
-- 使用右边的 address 字段，无法使用到索引而导致全表扫描
EXPLAIN SELECT * FROM person WHERE address = '广州';

覆盖索引

回表：指非主键索引，先通过索引找到主键索引的键值，然后再通过主键值查出索引里没有的数据，它比基于主键索引的查询多扫描了一颗索引树，这个过程就称之为回表。

在辅助索引里，不管是单例索引还是联合索引，当 **select** 的数据列只用了从索引中就能取得，不用从数据区中读取，这个时候就叫做索引覆盖，这样就避免了回表。在使用查询计划查看 **Extra = Using index** 就表示使用了覆盖索引。而 **select *** 使用不到覆盖索引。

-- 删除联合索引 
ALTER TABLE person DROP INDEX comixd_name_address; 
-- 创建联合索引
ALTER TABLE person add INDEX `comixd_name_address` (`name`,`address`);
-- 下面三个查询都使用到了覆盖索引
EXPLAIN SELECT name, address FROM person WHERE name = 'John' AND address = '广州'; 
EXPLAIN SELECT name FROM person WHERE name = 'John' AND address = '广州'; 
EXPLAIN SELECT phone FROM person WHERE name = 'John' AND address = '广州';

索引下推

-- 创建员工表
CREATE TABLE `employees` (
	`emp_no` INT ( 11 ) NOT NULL,
	`birth_date` date NULL,
	`first_name` VARCHAR ( 14 ) NOT NULL,
	`last_name` VARCHAR ( 16 ) NOT NULL,
	`gender` enum ( 'M', 'F' ) NOT NULL,
	`hire_date` date NULL,
	PRIMARY KEY ( `emp_no` ) 
) ENGINE = INNODB DEFAULT CHARSET = latin1;

-- 建立 first_name 和 last_name 的联合索引
ALTER TABLE employees ADD INDEX idx_lastname_firstname ( last_name, first_name );

-- 插入数据
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 1, NULL, '698', 'liu', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 2, NULL, 'd99', 'zheng', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 3, NULL, 'e08', 'huang', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 4, NULL, '59d', 'lu', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 5, NULL, '0dc', 'yu', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 6, NULL, '989', 'wang', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 7, NULL, 'e38', 'wang', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 8, NULL, '0zi', 'wang', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 9, NULL, 'dc9', 'xie', 'F', NULL );
INSERT INTO `employees` ( `emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date` )
VALUES ( 10, NULL, '5ba', 'zhou', 'F', NULL );

-- 关闭 ICP
set optimizer_switch='index_condition_pushdown=off';

-- 查看参数
show variables like 'optimizer_switch';

-- 查询所有姓王并且最后是以 zi 结尾的数据
select * from employees where last_name='wang' and first_name LIKE '%zi';

-- 使用执行计划查看 Extra 为 Using Where
explain select * from employees where last_name='wang' and first_name LIKE '%zi' ;

-- 开启 ICP
set optimizer_switch='index_condition_pushdown=on';

-- 再次使用执行计划查看 Extra 为 Using index condition
explain select * from employees where last_name='wang' and first_name LIKE '%zi' ;

在上面的案例中的 **SQL** 语句执行有两种方式
- 根据联合索引查出所有姓 **wang** 的二级索引数据，然后回表到主键索引上去查询全部符合条件的数据；接着返回给 **Server** 层去过滤出名字以 **zi** 结尾的员工；
- 根据联合索引查出所有姓 **wang** 的二级索引数据（**3** 个索引），然后从二级索引中筛选出 **first_name** 以 **zi** 结尾的索引（**1** 个索引），然后再回表到主键索引上查询符合条件的数据后再返回给 **Server** 层
在第二种方式中到主键索引查询的数据更少，在索引的比较是在存储引擎上进行的；数据记录的比较是在 **Server** 层进行的。当 **first_name** 的条件不能用于索引过滤时，**Server** 层不会把 **first_name** 的条件传递给存储引擎，所以读取了两条没有必要的记录。所以这时当满足 **last_name = 'wang'** 时的记录有 **10w** 条数据，那么就会有 **99999** 条没有必要读取的记录。
**Using Where & Using index condition**：
- **Using Where**：代表从 **InnoDB** 存储引擎取回的数据不是全部满足条件，需要在 **Server** 层进行过滤；先用 **last_name** 条件进行索引范围扫描，读取数据表记录，然后进行比较；检查是否符合 **first_name Like '%zi'** 的条件，此时 **3** 条中只有一条符合条件。
- 开启 **ICP** 后把 **first_name Like '%zi'** 条件下推给存储引擎后只会返回读取所需的 **1** 条记录，该功能是 **MySQL 5.6** 后完善的功能，只是适用于二级所用，**ICP** 的目标是减少访问表的完整行的读数据从而减少 **I/O** 操作。

索引的创建与注意事项

索引的创建：
- 在用 **where** 判断 **order** 排序和 **join** 的 **on** 字段上创建索引；
- 索引的个数不要太多，因为会浪费空间，更新时 **B+ Tree** 会变化导致性能差；
- 区分度低的字段不要建立索引（性别），因为离散度太低，导致扫描行数过多；
- 频繁更新的值不要作为主键或索引，因为会导致页分裂；
- 联合索引把散列性高的值放在前面
- 创建复合索引，而不是修改单列索引；
- 当字段比较长的时建立索引会消耗很多空间并且搜索也会很慢，可以通过截取字段的前面一部分内容建立索引，该方式称之为前缀索引。
索引的注意事项：
- 索引列上不要使用函数和表达式计算；
- 字符串需要加引号，否则会出现隐式转换；
- **like** 条件前不要带 %；
- 避免使用 **NOT LIKE**；
- 在某些情况下不要使用 **!= 、<>、NOT IN**
**SQL** 语句是否使用索引是根据数据库版本、数据量以及数据选择度有关；是否使用索引是优化器决定的，因为它是基于 **cost** 开销来进行优化的，哪种方式开销小就选择哪种。