文章目录
- 一、索引的本质
- 1、索引是帮助MySQL高效获取数据的排好序的数据结构
- 2、索引的数据结构
- 3、数据结构可视化网站
- 二、常见数据结构介绍
- 1、B-Tree
- 2、B+Tree（B-Tree变种）
- 3、Hash结构
- 三、存储引擎的索引实现
- 1、MyISAM存储引擎索引实现
- MyISAM索引文件和数据文件是分离的（非聚集）。
- 2、InnoDB存储引擎索引实现
- InnoDB索引实现（聚集）：
- 四、联合索引
- 1、联合索引案例使用的脚本
- 2、索引最左前缀原理
- 3、关于最左前缀的补充
- 索引跳跃扫描（Index Skip Scan）
- 索引跳跃扫描优化原理
- 生效的限制条件
一、索引的本质
1、索引是帮助MySQL高效获取数据的排好序的数据结构
2、索引的数据结构
- 二叉树
- B-Tree
- Hash表
- 红黑树
3、数据结构可视化网站
为了更好的了解数据结构，直观的感受数据结构的变化，可以使用如下网站，进行可视化操作。
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
二、常见数据结构介绍
1、B-Tree
- 叶节点具有相同的深度，叶节点的指针为空。
- 所有索引元素不重复。
- 节点中的数据索引从左到右递增排列。
2、B+Tree（B-Tree变种）
- 非叶子节点不存储data，只存储索引（冗余），可以放更多的索引。
- 叶子节点包含所有索引字段。
- 叶子节点用指针连接，提高区间访问的性能。
3、Hash结构
- 对索引的key进行一次hash计算就可以定位出数据存储的位置。
- 很多时候Hash索引要比B+ 树索引更高效。
- 仅能满足 “=”，“IN”，不支持范围查询。
- hash冲突问题。
三、存储引擎的索引实现
1、MyISAM存储引擎索引实现
MyISAM索引文件和数据文件是分离的（非聚集）。
2、InnoDB存储引擎索引实现
InnoDB索引实现（聚集）：
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
- 为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？（方便排序提升查找效率）
- 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
四、联合索引
1、联合索引案例使用的脚本
CREATE TABLE `employees` (`id` int(11) NOT NULL AUTO_INCREMENT,`name` varchar(24) NOT NULL DEFAULT '' COMMENT '姓名',`age` int(11) NOT NULL DEFAULT '0' COMMENT '年龄',`position` varchar(20) NOT NULL DEFAULT '' COMMENT '职位',`hire_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '入职时间',PRIMARY KEY (`id`),KEY `idx_name_age_position` (`name`,`age`,`position`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=utf8 COMMENT='员工记录表';INSERT INTO employees(name,age,position,hire_time) VALUES('LiLei',22,'manager',NOW());
INSERT INTO employees(name,age,position,hire_time) VALUES('HanMeimei', 23,'dev',NOW());
INSERT INTO employees(name,age,position,hire_time) VALUES('Lucy',23,'dev',NOW());EXPLAIN SELECT * FROM employees WHERE name = 'Bill' and age = 31;
EXPLAIN SELECT * FROM employees WHERE age = 30 AND position = 'dev';
EXPLAIN SELECT * FROM employees WHERE position = 'manager';
2、索引最左前缀原理
在联合索引中，索引的数据结构如下，正常的索引是遵循B+树结构，索引项从左到右，从小到大排序，假设我们跳过name，直接使用联合索引中的age和position，由于在比较中，无法先确认第一项name，故无法对整个索引项进行排序，从而导致联合索引失效。
简单理解，其实索引的最左前缀原理就是根据索引中开始的索引字段，按顺序进行匹配排序，实现通过索引的高效查找的的一种规则。
3、关于最左前缀的补充
索引跳跃扫描（Index Skip Scan）
MySQL一定是遵循最左前缀匹配的，这句话在mysql8以前是正确的，没有任何毛病。但是在MySQL 8.0中，就不一定了。
参考：https://dev.mysql.com/doc/refman/8.0/en/range-optimization.html#range-access-skip-scan
官网示例：
CREATE TABLE t1 (f1 INT NOT NULL, f2 INT NOT NULL, PRIMARY KEY(f1, f2));
INSERT INTO t1 VALUES
(1,1), (1,2), (1,3), (1,4), (1,5),
(2,1), (2,2), (2,3), (2,4), (2,5);
INSERT INTO t1 SELECT f1, f2 + 5 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 10 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 20 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 40 FROM t1;
ANALYZE TABLE t1;EXPLAIN SELECT f1, f2 FROM t1 WHERE f2 > 40;
虽然我们的SQL中，没有遵循最左前缀原则，只使用了f2作为查询条件，但是经过MySQL 8.0的优化以后，还是通过索引跳跃扫描的方式用到了索引了。
索引跳跃扫描优化原理
mysql8.013后通过优化器帮我们加了联合索引，SQL执行过程如下：
- 获取 f1 字段第一个唯一值，也就是 f1 = 1
- 构造 f1 = 1 and f2 > 40，进行范围查询
- 获取 f1字段第二个唯一值，也就是 f1 = 2
- 构造 f1 = 2 and f2 > 40，进行范围查询
SELECT f1, f2 FROM t1 WHERE f2 > 40;-- 执行的最终SQL:
SELECT f1, f2 FROM t1 WHERE f1 =1 and f2 > 40
UNION
SELECT f1, f2 FROM t1 WHERE f1 =2 and f2 > 40;
所以对于f1值很少，区分度不高的情况索引跳跃扫描会快一些；反之查询效率慢些。
我们不能依赖这个优化，建立索引的时候，还是优先把区分度高的，查询频繁的字段放到联合索引的左边。
生效的限制条件
- 查询必须只能依赖一张表，不能多表JOIN。
- 查询中不能使用 GROUP BY 或 DISTINCT 语句。
- 查询的字段必须是索引中的列。
- 组合索引形式：([A_1, …, A_k,] B_1, …, B_m, C [, D_1, …, D_n])，A，D 可以为空，但是B ,C 不能为空。
![[OS] 3.Insert and Remove Kernel Module](/images/no-images.jpg)
