Mysql 学习day 2 深入理解Mysql索引底层数据结构

简介

索引是帮助MySQL高效获取数据的排好序的数据结构

索引是MySQL中用于快速定位和访问数据的一种机制。它通过特定的数据结构（如B+树）对数据进行组织和排序，帮助数据库引擎快速找到所需数据行，从而减少查询时间。索引并不存储完整数据，而是存储指向数据的引用或键值。在查询过程中，索引可以缩小扫描范围、支持排序等功能，显著提升数据库的查询效率。常见的索引类型包括普通索引、唯一索引、主键索引和全文索引等。

一行行查找，放磁盘，但是放进磁盘的顺序是混乱的
索引key放值，value放地址

可以用可视化图做例子

可用的数据结构

为什么数据结构不用二叉树，因为二叉树插入变成了链表，查找次数多，对查找效率没有提升
可以看这个链接，更详细

为什么不用红黑树
红黑树是平衡二叉树
因为数据量大的时候，红黑树层数会增多，查找效率会降低，高度不可控

为什么不用b树
1.叶节点具有相同的深度，叶节点的指针为空
2.所有索引元素不重复
3.节点中的数据索引从左到右递增排列

为什么用B+树

B+Tree(B-Tree变种)

1. 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
   MySQL的B+树中，非叶子节点存储的是键值范围的划分点，这些键值是从叶子节点中抽样出来的，用于快速引导查询路径，帮助构建树的层级结构，从而加速数据定位。这些划分点并不是实际存储的数据，而是中间引索，目的是指导查询快速找到目标数据所在的叶子节点。
2. 叶子节点包含所有索引字段
3. 叶子节点相邻之间用指针连接，最前端或者最尾端开辟了内存存储上一个和下一个的地址，提高区间访问的性能
   第二层其实是冗余节点

三层可以存多少数据

myisam和innoDB

myisam和innoDB区别

索引是存在磁盘上的data目录下面

例子

一个test表
用的myisam存储引擎，frm文件存放着是表结构信息，myd文件存放着是myisam表的记录，myi文件就是index表
myI里面得到索引记录，然后去myd文件里面得到数据，可以看做是非聚簇索引

InnoDB存储引擎的IBD文件就是所有数据放进去

InnoDB索引实现(聚集)

1. 表数据文件本身就是按B+Tree组织的一个索引结构文件

2. 聚集索引-叶节点包含了完整的数据记录

3. 为什么建议InnoDB表必须建主键？
   因为如果不建主键，他就会找从第一列选择一列索引建立和维护B+树
   如果选不到索引，会建立rowid隐藏列来组织B+树

4. 为什么推荐使用整型的自增主键
   因为整型比大小快，一般企业用固态硬盘，节约空间

什么是自增？
假设列设为哈希索引，对索引进行哈希，然后插入，mysql底层有自己的hash算法，另外一个需要自增的原因，如果是乱序插入，树会变成乱序，会分裂新的节点

	Hash
 1. 对索引的key进行一次hash计算就可以定位出数据存储的位置
 2. 很多时候Hash索引要比B+ 树索引更高效
 3. 仅能满足 “=”，“IN”，不支持范围查询，B+树范围查找是把一个范围的数据页都load出来
 4. hash冲突问题

工作中，一般不用哈希，比如果name>Alice，就需要全表扫描，所以一般是b+树

5. 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
   因为如果都放所有数据，如果有修改的时候两个表都需要修改数据，如果是其中一个放的是主键值，在MySQL中，利用主键值在聚集索引（主表）中查找完整数据行的过程如下：首先，通过主键值在B+树结构的聚集索引中逐层查找，直到定位到存储完整数据行的叶子节点。若数据所在的页未在内存中，则从磁盘加载该页到内存。最后，在内存中的数据页里找到对应的行并返回结果。整个过程通常只需一次I/O操作（若数据页已加载则无需I/O），效率较高，但回表操作的瓶颈可能在于磁盘I/O和数据页加载次数。

联合索引的底层存储结构长什么样？

如果不匹配最左侧原理，就会扫描所有表

联合索引可以使用的脚本

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';

关于最左前缀的补充
MySQL一定是遵循最左前缀匹配的，这句话在mysql8以前是正确的，没有任何毛病。但是在MySQL 8.0中，就不一定了。
索引跳跃扫描（Index Skip Scan）
参考：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;
这里f1和f2是联合索引

虽然我们的SQL中，没有遵循最左前缀原则，只使用了f2作为查询条件，但是经过MySQL 8.0的优化以后，还是通过索引跳跃扫描的方式用到了索引了。

索引跳跃扫描优化原理
mysql8.013后通过优化器帮我们加了联合索引，SQL执行过程如下：
1.获取 f1 字段第一个唯一值，也就是 f1 = 1
2.构造 f1 = 1 and f2 > 40，进行范围查询
3.获取 f1 字段第二个唯一值，也就是 f1 = 2
4.构造 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 不能为空。