【金三银四】深入理解Mysql索引底层数据结构解密

2020-01-06 1,186 阅读3分钟

【MySql系列】文章导航

【金三银四】深入理解MySql索引底层数据结构解密 juejin.im/post/684490…

【金三银四】MySql执行计划EXPLAIN详解 juejin.im/post/684490…

【金三银四】MySql执行计划EXPLAIN最佳实践 juejin.im/post/684490…

【金三银四】MySql索引优化实战 juejin.im/post/684490…

开始

2B哥从Mysql面试题开始说起吧。

案例

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());

分析以下几条sql的索引使用情况

SELECT * FROM employees WHERE name= 'LiLei';
SELECT * FROM employees WHERE name= 'LiLei' AND age = 22 AND position ='manager';
SELECT * FROM employees WHERE age = 22 AND position = 'manager';
SELECT * FROM employees WHERE name= 'LiLei' AND age > 22 AND position = 'manager';
SELECT * FROM employees WHERE name != 'LiLei';

Mysql的索引分析

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

索引的本质：索引是数据结构，而且是实现了高级查找算法的数据结构

索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作

磁盘存取原理

寻道时间(速度慢，费时)
旋转时间(速度较快) 预读：长度为页的整倍数（主存和磁盘以页为单位交换数据，一页4K）

什么是索引

索引是用来快速检索出具有特定值的记录。 MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构

论索引重要性

在比如我们生活中去图书馆找书，我们要找到图中的葵花宝典实在是太难了（从一楼到三楼全部都要看一遍书名）但也有这种一眼去可以找到的情况，如图找PHP这本书（Java是世界上最好的语言）所示：

根据找书的规则我们可以得出两个结论：

1、书的数量

2、书的位置

这两个条件决定了找到这本书的速度。那跟我们索引有什么关系了？看这个图

索引重要吗？如图所示，没有用到索引和用到索引速度对比。

索引的结构

二叉树
红黑树
HASH
BTREE

更多数据结构动画演示：数据结构教学网站

索引底层数据结构与算法

Hash索引

如果是等值查询，哈希索引明显有绝对优势，前提：键值唯一

哈希索引没办法完成范围查询检索

哈希索引也没办法利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询

哈希索引也不支持多列联合索引的

在有大量重复键值情况下，哈希索引的效率也最左前缀原则是极低的，因为存在哈希碰撞问题

B-Tree

度(Degree)-节点的数据存储个数
叶子节点具有相同的深度
叶子节点的指针为空
节点中的数据key从左到右递增排列

B+Tree

非叶子节点不存储data，只存储key，可以增大度
叶子节点不存储指针
顺序访问指针，提高区间访问的性能

MyISAM索引实现(非聚集)

MyISAM索引文件和数据文件是分离的

InnoDB索引实现(聚集)

数据文件本身就是索引文件
表数据文件本身就是按B+Tree组成的一个索引结构文件
聚集索引-叶节点包含了完整的数据记录
为什么InnoDB表要求有主键，并且推荐使用整型的自增主键？

没有主键：dev.mysql.com/doc/refman/…

为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

福利

赠送一份mysql知识图谱，高清版本关注公众号：java2b

友情链接：