mysql索引底层数据结构和算法

我就是我 2023-09-29 13:47 12阅读 0赞

**分析以下几条 sql 根据索引使用情况**

1. SELECT \* FROM titles WHERE emp\_no='10001' AND title='Senior Engineer' AND

from\_date='1986-06-26';

2. SELECT \* FROM titles WHERE title='Senior Engineer' ;

3. SELECT \* FROM titles WHERE emp\_no > ‘10001';

4. SELECT \* FROM titles WHERE emp\_no > ‘10001' and title='Senior Engineer';

5. SELECT \* FROM titles WHERE emp\_no > ‘10001' order BY title;

![34ea90daf8f27e357e65111cb60cd519.png][]

## 索引到底是什么 ##

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

## 索引存储在文件里； ##

## 索引结构； ##

![934195adc88db0414171af8ffe6de7af.png][]

## 二叉： ##

一个节点的左键点小于该节点，右节点大于该节点，但是如果插入二叉树的数据是有序的，就会形成二叉树的极端情况，形成链表，我们知道树的查询复杂度跟树的高度有关，树越高，那么查询事件复杂度就越高，并且需要更多的磁盘IO,所以需要通过某种约束来保证树的平衡,所以MySQL不用二叉存储索引；

二叉结构存储数据的示意图：

![8d3ac50d776ee752ae2ac14838ac5fd3.png][]

## 红黑树： ##

那么红黑树就是平衡二叉树中的一种，它通过一系列的规则来保证树的平衡。但是在大规模数据存储的时候，红黑树常常会因为树的深度过高而导致磁盘IO读写过于频繁，导致效率底下，为什么会形成这种情况呢，我们知道要获取磁盘上的数据，必须通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后进行读写，这种涉及到物理操作情况下，性能自然会很低下。MySQL不用红黑树存储索引；

红黑树存储的数据示意图：

![2aaa4cbd0c55ca8ceabb5eec419e6d9f.png][]

## HASH： ##

如果不是范围查找用hash效率也是很高的，hash索引查询单条确实比较快，但是他是无序的，查询多条或者排序的话性能就比较低了；

## BTREE： ##

B树也就是B-树，B树是一个多路搜索树，也就是每个节点可以有多个子节点，这样是为了降低树的高度，减少磁盘IO次数;

B+树是B树的优化，他的子节点只存储键而不存储数据，数据全部存在叶子节点，并且叶子节点间通过指针进行连接，这样因为子节点不存储数据，那么磁盘可以一次读取更多的子节点，减少IO次数，并且叶子节点想通，如果想查询10-100的数据只需要找到头尾就可以了。

B-Trees示意图：

![e5946b6292fdba511ba6125ef2960d8a.png][]

B+Trees示意图:

![2e1a80ec1a1feaaf77016332e00b3597.png][]

## 数据结构网站： ##

到此为止，我们知道了Mysql为什么使用B+树了，因为我们平常的业务查询一般可能不是查询一条，而是查询多条，hash索引查询单条确实比较快，但是他是无序的，查询多条或者排序的话性能就比较低了，并且在内存资源紧张的情况下，树索引可以分批装入内存进行计算。红黑树因为大数据存储下，树的高度很高，这样可能会导致多次IO，查询效率比较低。而B+树可以一次性装入更多的叶子节点到内存，并且树的高度可以控制到很低，叶子节点存储数据并且形成链表可以避免跨层查询。

## 索引概述 ##

## 磁盘存取原理（一般使用磁盘I/O次数评价索引结构的优劣，一次磁盘io指指令一般是通知磁盘开始扇区位置，然后给出需要从这个初始扇区往后读取的连续扇区个数，所以树的层级越深磁盘io读取越频繁） ##

寻道时间 ( 速度慢，费时 )

旋转时间 ( 速度较快 )

![d7e14b2281902941caa6aa8a5a7203cb.png][]

不同面上的磁道编号则组成了一个圆柱面

![fa813a8766486e0c45f92e602f2e8a52.png][]

## 磁盘IO为什么慢 ##

先温习下知识点：磁盘IO时间 = 寻道 + 磁盘旋转 + 数据传输时间

从磁盘读取数据时，系统会将逻辑地址发给磁盘，磁盘将逻辑地址转换为物理地址（哪个磁道，哪个扇区）。 磁头进行机械运动，先找到相应磁道，再找该磁道的对应扇区，扇区是磁盘的最小存储单元（见图1-1）。

![a13fe1e6a56bc87f52d21718bae89839.png][]

图1-1 磁盘物理结构

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

## 索引底层数据结构与算法 ##

![a86ee61a56a0239afbd6c62356cb263f.png][]

![faab92fa4fd9fdcbff44c00224f3c202.png][]

![802ce33b31d5fdcefd3362295c03b25d.png][]

![1e717bfd469a8ff28af1962671b20fe9.png][]

**主键索引和辅助索引的区别？**

逐渐索引：逐渐索引当做分叶子节点的值，行的记录被放到叶子节点上，索引和数据放到一起了。

辅助索引:辅助索引的value是主键索引的key，辅助索引通过b+tree找到主键索引，然后通过主键索引找到对应的行的记录；

**为啥InnoDB必须有主键，并且推荐使用整型的自增主键？**

1、如果设置了主键，那么InnoDB会选择主键作为聚集索引、如果没有显式定义主键，则InnoDB会选择第一个不包含有NULL值的唯一索引作为主键索引、如果也没有这样的唯一索引，则InnoDB会选择内置6字节长的ROWID作为隐含的聚集索引(ROWID随着行记录的写入而主键递增)。

2、如果表使用自增主键  
那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，主键的顺序按照数据记录的插入顺序排列，自动有序。当一页写满，就会自动开辟一个新的页,充分利用空间；

3、如果使用非自增主键（如果身份证号或学号或者uuid等）  
由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页的中间某个位置，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。字符串长查询效率低，浪费空间，增加磁盘io

## 联合索引结构 ##

![d8c51acbcf7c2f433670f5feeadb8d4f.png][]

## 索引最左前缀原理？ ##

![c6f31b0b3def24b01df25a6278a4fff5.png][]

![e2b00930363fe9fb1526fd617e82fd39.png][]

按照最左前缀原理只有第三个sql走索引了

EXPLAIN SELECT \* FROM employees WHERE NAME = 'LiLei' AND age = 22 AND POSITION ='manager';

EXPLAIN SELECT \* FROM employees WHERE NAME = 'LiLei' AND POSITION ='manager' AND age = 22 ;

这两个都用到索引了，如果索引列都用到mysql会自动排序索引的

EXPLAIN SELECT \* FROM employees WHERE NAME = 'LiLei' AND POSITION ='manager' AND age > 22 ;

这个是用到索引的

![a5361be9a4112a93c082934ac1877093.png][]

有没有走索引的依据是type类型在all之前

依次从最优到最差分别为：system > const > eq\_ref > ref > range > index > ALL

一般来说，得保证查询达到range级别，最好达到ref

![49f7f406c9624c43a17fba59d6a03c84.png][]

感谢大家阅读，本人见识有限，写的博客难免有错误或者疏忽的地方，还望各位大佬指点，在此表示感激不尽。文章持续更新中…....

[34ea90daf8f27e357e65111cb60cd519.png]: https://img-blog.csdnimg.cn/img_convert/34ea90daf8f27e357e65111cb60cd519.png
[934195adc88db0414171af8ffe6de7af.png]: https://img-blog.csdnimg.cn/img_convert/934195adc88db0414171af8ffe6de7af.png
[8d3ac50d776ee752ae2ac14838ac5fd3.png]: https://img-blog.csdnimg.cn/img_convert/8d3ac50d776ee752ae2ac14838ac5fd3.png
[2aaa4cbd0c55ca8ceabb5eec419e6d9f.png]: https://img-blog.csdnimg.cn/img_convert/2aaa4cbd0c55ca8ceabb5eec419e6d9f.png
[e5946b6292fdba511ba6125ef2960d8a.png]: https://img-blog.csdnimg.cn/img_convert/e5946b6292fdba511ba6125ef2960d8a.png
[2e1a80ec1a1feaaf77016332e00b3597.png]: https://img-blog.csdnimg.cn/img_convert/2e1a80ec1a1feaaf77016332e00b3597.png
[d7e14b2281902941caa6aa8a5a7203cb.png]: https://img-blog.csdnimg.cn/img_convert/d7e14b2281902941caa6aa8a5a7203cb.png
[fa813a8766486e0c45f92e602f2e8a52.png]: https://img-blog.csdnimg.cn/img_convert/fa813a8766486e0c45f92e602f2e8a52.png
[a13fe1e6a56bc87f52d21718bae89839.png]: https://img-blog.csdnimg.cn/img_convert/a13fe1e6a56bc87f52d21718bae89839.png
[a86ee61a56a0239afbd6c62356cb263f.png]: https://img-blog.csdnimg.cn/img_convert/a86ee61a56a0239afbd6c62356cb263f.png
[faab92fa4fd9fdcbff44c00224f3c202.png]: https://img-blog.csdnimg.cn/img_convert/faab92fa4fd9fdcbff44c00224f3c202.png
[802ce33b31d5fdcefd3362295c03b25d.png]: https://img-blog.csdnimg.cn/img_convert/802ce33b31d5fdcefd3362295c03b25d.png
[1e717bfd469a8ff28af1962671b20fe9.png]: https://img-blog.csdnimg.cn/img_convert/1e717bfd469a8ff28af1962671b20fe9.png
[d8c51acbcf7c2f433670f5feeadb8d4f.png]: https://img-blog.csdnimg.cn/img_convert/d8c51acbcf7c2f433670f5feeadb8d4f.png
[c6f31b0b3def24b01df25a6278a4fff5.png]: https://img-blog.csdnimg.cn/img_convert/c6f31b0b3def24b01df25a6278a4fff5.png
[e2b00930363fe9fb1526fd617e82fd39.png]: https://img-blog.csdnimg.cn/img_convert/e2b00930363fe9fb1526fd617e82fd39.png
[a5361be9a4112a93c082934ac1877093.png]: https://img-blog.csdnimg.cn/img_convert/a5361be9a4112a93c082934ac1877093.png
[49f7f406c9624c43a17fba59d6a03c84.png]: https://img-blog.csdnimg.cn/49f7f406c9624c43a17fba59d6a03c84.png