深入理解Mysql索引底层数据结构与算法

叁歲伎倆 2023-07-02 11:22 7阅读 0赞

### 深入理解Mysql索引底层数据结构与算法 ###

*   *  索引到底是什么
     *  B树
     *  索引实现

## 索引到底是什么 ##

1、**索引**是帮助MySQL高效获取数据的**排好序**的**数据结构**  
2、索引存储在**文件里**  
3、索引结构**B树**

## B树 ##

*  **B-Tree**

1.  度(Degree)-节点的数据存储个数
2.  叶节点具有相同的深度
3.  叶节点的指针为空
4.  节点中的数据key从左到右递增排列  
    ![在这里插入图片描述][20200129134639927.png]········································································

*  **B+Tree**(B-Tree变种)
 *  非叶子节点不存储data，只存储key，可以增大度
 *  叶子节点不存储指针
 *  顺序访问指针，提高区间访问的性能  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70]\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`\`

**B+Tree索引的性能分析**  
1.一般使用磁盘I/O次数评价索引结构的优劣  
2.预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存  
3.局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用  
B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O  
4.B+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)

## 索引实现 ##

**MyISAM索引实现(非聚集)**

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 2]

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

*  数据文件本身就是索引文件
 *  表数据文件本身就是按B+Tree组织的一个索引结构文件
 *  聚集索引-叶节点包含了完整的数据记录
 *  为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
 *  为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 3]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 4]  
    **联合索引的底层存储结构长什么样？**![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 5]

[20200129134639927.png]: https://img-blog.csdnimg.cn/20200129134639927.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200129135805587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020012914114734.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200129141157243.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200129140847752.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200129140914583.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200129141924639.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU4NDU0NQ==,size_16,color_FFFFFF,t_70