Mysql索引底层数据结构

朴灿烈づ我的快乐病毒、 2022-11-19 01:26 313阅读 0赞

# Mysql系列文章目录 #

提示：mysql是关系型数据库，被好多公司广泛使用

--------------------

提示：索引是帮助MySQL高效获取数据的排好序的数据结构，接下来跟我学习mysql数据库索引吧

### 文章目录 ###

*  Mysql系列文章目录
 *  前言
 *  一、数据的存储IO Buffer
 *  二、MYSQL索引
 *   *  B+Tree Innodb
     *  InnoDB索引实现(聚集)
     *  MyISAM索引(非聚集)
     *  联合索引的底层存储结构

--------------------

# 前言 #

提示：如果有说的不对的地方请批评指正

--------------------

# 一、数据的存储IO Buffer #

> 首先我们想读取文件，是不是需要IO流？  
> Buffer存在一个成本问题，磁盘有磁道和扇区，每个扇区有多少字节？每次扇区有512个字节，如果我们想访问这个硬盘的硬件，这个硬盘的大小大概1个T，都是最小力度每个扇区进行查找，我的数据在那个扇区放着？这样的话我们查找，是不是成本变大，索引变大，1T里面很多512，那么操作系统中是不是需要索引，这个索引大小是不是我们就不确定多少字节了，他需要一个很大的数据区间，才能获取扇区，所以成本越大，索引越大，我们的磁盘格式化的时候会有4k对齐，也就是真正用到硬件的时候，并不是按照扇区的读写量，他会变得大一些，如果自己读的话是512个字节，读取到1K就给硬盘了，硬盘都是默认4k格式化的，无论读多少都是最少4k从磁盘拿的，文件如果从几M到几个G查询的速度变慢了，如果访问的话硬盘是否收到影响？也就是IO读取的速度，换言而知，我们如果把这些数据放入数据库中是不是，查找速度变快了，如果咱们在数据库建一张表，里面有很多行，存到磁盘的时候，他其实在物理存的时候，用到了4K这个小格子概念，这个4K和咱们格式化的时候和我们的磁盘对的上，所以数据库准备很多这样的4K，也就是曾经数据是线性在一个文件里面，他的底层是4K，所以文件混在一起，4k连起开不能把他们分割，如果我在自己的软件里定义一个4k这4K的数据他都有不同的ID号，0号丶1号。。。。，我要查找4K里面的某个数据，正好符合我的磁盘IO，自己也可以变小，变小的话是不是变慢了？磁盘IO一次读取的是4k，我要查找数据的时候调用对某个位置，一下就可以拿出来了，如果我定义小了，对资源是一种浪费，为什么浪费如果定义1k但是底层也会按照4K走，定义大了无所谓，可以往大了调，因为IO读取会从第一个数据读取到内存，然后挨个去找，他走的还是全亮的IO，查找的时候和前面的复杂度，几乎一样  
> 数据库的数据是存在磁盘上的！！！！！

# 二、MYSQL索引 #

> 众所周知Mysql的数据存储在磁盘上的，那他的存储结构是什么样的那？存储的文件是什么样的？接下来慢慢的跟我一起学习

**索引**是帮助MySQL高效获取数据的**排好序**的**数据结构**  
**B-Tree** Mysql 采用的B+Tree 但是为什么我要说一下B-Tree因为我曾经看过一道面试题，到现在才明白！！！！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70]  
如上图：B-Tree的数据结构图，叶节点具有相同的深度，叶节点的指针为空。他和B+tree的比较，先说B-tree因为B+tree根据他改编的，咱们看到的，他的根节点存着数据，但是我们想一下，有什么坏处？  
根节点  
咱们先看一下页大小 16k 根节点单行长度计算公式 page大小（16\*1024=16384）那咱们的表字段能存多少？咱们算一下  
那么以三层高度的B树来说，这也是日常生活中最常碰到树的高度了。对于一棵三层高度的B树计算最多存储记录数非常好计算，无非就是根节点最大存储记录数N1中间节点最大存储记录数N2叶子节点最大存储记录数N3得到N，这个N就是当前数据存储结构下的三层高度B树的最大存储记录数。

> 首先我们计算一个节点可保存的数据量：假设我们长度为8个字节的bigint类型为id的类型，每个数据包含6字节的指针，那么不考虑除叶子节点保存的数据。那么在一层和二层的节点中，可以大概保存16*1024/(8+6)约为1,170。那么一二层的节点数最多可保存1,170*1,170的列数据信息  
> ，也就是136万节点。

那么咱们在想一下 如果节点上携带者数据那这样存储的叶子节点变得更少，树的高度是不是也要提高，树的高度提高我们的检索是不是时间也要加长，也增加IO的次数，因为读取验证是不是我们要的数据还得继续检索到下一个叶子节点，所以Mysql没有采用B-tree，在B-Tree上做了改进，B+Tree

SHOW GLOBAL STATUS like 'Innodb_page_size';
    结果：
    16384	Innodb_page_size

**叶节点具有相同的深度，叶节点的指针为空** 为什么说没有指针，因为mysql是排好序的，不像是B+树，前后节点都会有指针，例如我寻找一个<5的第一次扫到6然后在回到根节点再去往下扫  
**所有索引元素不重复** 索引元素不可重复唯一索引  
**节点中的数据索引从左到右递增排列**

## B+Tree Innodb ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70 1]  
如上图：  
**非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引**  
我们长度为8个字节的bigint类型为id的类型，每个数据包含6字节的指针，那么不考虑除叶子节点保存的数据。那么在一层和二层的节点中，可以大概保存16*1024/(8+6)约为1,170。那么一二层的节点数最多可保存1,170*1,170的列数据信息，data大小不超过16k，**1170 \* 1170 \* 16** 也就是2000多万 两层索引+data树也就是能存储那么多数据，树的高度才是3我们查找某个元素的时候，是不是IO三次就查到了？更高版本的数据库可能做了不一样的优化，据说会把所有的索引放入到内存中，磁盘上只放数据，这样的话是不是更快！！！  
**叶子节点包含所有索引字段**  
**叶子节点用指针连接，提高区间访问的性能**  
也就是咱们第三层看到的双向指针，例如18里面叶子上存储着20的地址，20存储着18的地址，双向的也就是咱们用范围查找的时候，查找的速度更快，因为他是排好序的mysql从左到右的顺序，这样区间的访问性能是很高的

## InnoDB索引实现(聚集) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70 2]  
**表数据文件本身就是按B+Tree组织的一个索引结构文件**  
**聚集索引-叶节点包含了完整的数据记录**  
如上图看二级索引，的叶子节点，存储着一级节点的索引，因为主键索引，包含着所有的数据，这么做是为了节省空间，方便二级索引查找的速度更加高效，虽然有一次回表操作，但是节省了空间  
**为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？**

> 咱们说InnoDB是用于表的还是用于数据库的？答是表的！！！！为什么需要设置主键，因为主键如果不设置主键的话，mysql底层算法，先去你的表中查找一列唯一且不重复的作为索引，如果没有找到怎么办？他会生成一个隐藏索引，类似于rowId  
> 行号，作为构建索引树，常常我们不设置主键索引，也可以建成表这就是原因，命名咱们手动能做的事情，为什么要耗费数据库的性能帮我们去做这个计算那？数据库的资源很宝贵的！！

> 为什么使用整形，你会说我们的库里用的UUID做的主键，为什么不推荐UUID那？因为你是字符类型的，他会按照asccll码表，将你的每一个字符进行计算进行排序，耗费一定的性能，然后在你查询的时候，例如你有a1，a2，a3，他会先进行拆分然后比大小，如果前面值相等，则判断第二位，因为还涉及到排序这个功能，存储的时候是排好序的，自增主键是从大到小，而且唯一，UUID完全可以作为二级索引！！！！切记

**为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)**  
因为如果我要修改某一个值，我直接修改主键索引里面的值不就好了，还能保证一致性，咱们想想，如果插入数据你插入到一个结构里面快还是插入两个，既浪费空间，又耗时，所以执行一次就行了，二级索引存的是一级索引的主键的值，直接定位到哪里，减少了IO，回表就是二级索引查找之后回到主键索引树里

## MyISAM索引(非聚集) ##

什么是快乐星球？这就是快乐星球  
![在这里插入图片描述][20210419131031785.png]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70 3]  
如上图，因为MyISAM索引文件和数据文件是分离的，frm是文件存储的结构，MYD是数据，MYI是索引文件这是三个文件的，例如我们查找，我们从上到下查到到18存储着地址然后我们去MYD文件中去找出来对应的某列数据， InnoDB我自己的数里就有，不用执行回表操作，看图就行了

## 联合索引的底层存储结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70 4]  
如上图，联合索引，个人感觉就把他看成三个索引联合在一块有执行顺序的先执行name，age，position  
name是字符类型的拆分成一个个的字符，首字母前缀进行比对，也就是咱们常说的最左前缀比对，如果，比对完毕之后前几位都相等一个的比对，进行排序，如果那么都一样，那就比对第二列的age，从小到大排列，从左到右排好序的  
接下来我出三个案例

SELECT * from user where name = 'zhangsan'  and age=40 and position= 'dev'
    SELECT * from user where age=40 and position= 'dev'
    SELECT * from user where position= 'dev'

如上代码哪个走了索引，还是全部走了索引

SELECT * from user where name = 'zhangsan'  and age=40 and position= 'dev'

这句话走了索引因为从左到右执行顺序，就是咱们上面说的，他不可能跳过第一个name索引去执行别的先会走name做比较 下面这俩完全不会走索引，因为是全表扫描，联合索引，个人觉得，满足第一个不？不满足我接着扫，ALL 如果第一个name索引能匹配到那就比对第二个 ，过滤筛选，如果查找一个不存在的name 也会扫描全表的

SELECT * from user where age=40 and position= 'dev'
    SELECT * from user where position= 'dev'

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70]: /images/20221022/9e52b7d3ffe9456caaaa34a3c360c7e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70 1]: /images/20221022/4553c88b006c43fa983166d766569273.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70 2]: /images/20221022/23f578bbc8374653942d5426b9206b6f.png
[20210419131031785.png]: /images/20221022/857f6161d07b45b2a11ec67b46a096ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70 3]: /images/20221022/3be36769520d45ee990353f65e1b87eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNzMxMzU4_size_16_color_FFFFFF_t_70 4]: /images/20221022/c7c9a5602176424ea70c9c5682e830ae.png