【MySQL】1-深入理解MySQL的索引机制

小咪咪 2022-12-29 04:37 300阅读 0赞

> 这一节主要阐述MySQL的各种索引及底层结构的演变

### 文章目录 ###

*  MySQL索引
 *   *  数据库索引的全面认识
     *   *  哈希表
         *  B树索引
         *   *  普通二叉树
             *  AVL（平衡二叉树）
             *  B树（多路平衡二叉树）
             *   *  B树是怎么保持平衡的呢？
                 *  B树是怎么样搜索的呢？
             *  B+树
             *   *  为什么要搞个B+树呢【B+树的优点】
     *  索引机制的落地
     *   *  Myisam
         *  Innodb 索引的落地
         *   *  聚集索引【主键索引】
             *  联合索引
             *   *  索引列的离散性
             *  覆盖索引
             *  三星索引
             *  索引的打油诗

# MySQL索引 #

**正确**的创建**合适**的索引是数据库性能优化的**基础**

## 数据库索引的全面认识 ##

数据库索引是一种为了加速数据表中行记录检索的数据结构

数据库的索引存储在**磁盘**中  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

### 哈希表 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]  
特征总结：**等值匹配是非常快、范围查询不支持**

Innodb：可以创建哈希索引也可以不创建哈希索引，不支持用户级别去创建哈希索引

### B树索引 ###

#### 普通二叉树 ####

*  左小右大（通过关键字一分为二）
 *  递归的二分查找，查找效率 **Olog(N）**
 *  当完全递增时，就会退化成一个线性链表，时间复杂度为 **O(N)**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 2]

#### AVL（平衡二叉树） ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 3]

*  左子树和右子树的高度差不能大于1
 *  如何保证树的相对平衡：自旋、右旋、左旋
 *  节点包括：关键字、数据区、子节点的引用
    
     *  关键字：类似 ID
     *  数据区：数据的指针或者行记录数据的所有内容
     *  子节点的引用：向下搜索的树
 *  每次进行加载都需要和磁盘进行IO操作，操作系统与磁盘进行IO的操作过于缓慢，不如内存级的IO操作
 *  搜索过程：
    
     *  在几层查找，就需要几次IO操作（树高导致IO操作频繁）
     *  操作系统与磁盘的交互单位：页 一页 = 4KB （读一次就会读取4KB，关键字 + 数据区 + 子节点引用不足4KB，IO利用率太低）

#### B树（多路平衡二叉树） ####

*  针对 AVL 树的缺点，提出来了B树，通过一次IO操作加载多个关键字，能够填满其4KB内存，一页数据库 = 16KB
 *  关键字个数变多【关键字的个数 = 子岔路 - 1】（**空间换时间**）
 *  一次操作系统与磁盘进行IO操作，将多个关键字加载到内存中，**在内存中进行比较**，这样不需要进行频繁的IO操作  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 4]

##### B树是怎么保持平衡的呢？ #####

*  结点包括太多的关键字时，进行分列处理
 *  **在数据的插入删除进行逻辑判断，对于字段经常变动的，不宜创建索引**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 5]

##### B树是怎么样搜索的呢？ #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 6]  
假设我现在需要查询21这个关键字

*  利用IO操作，将我们的磁盘块1的内容加载到内存中，进行比较，得出结果：p2
 *  利用IO操作，将我们的磁盘块3的内容加载到内存中，进行比较，得出结果：p1
 *  利用IO操作，将我们的磁盘块3的内容加载到内存中，进行比较，得出结果：21
 *  找到我们的数据区，获取我们的所有数据

#### B+树 ####

*  根节点和支节点不保存数据区
 *  数据区在叶子结点上
 *  匹配规则，采用的左闭合方式
 *  叶子节点关键字形成天然的双向链表  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 7]

##### 为什么要搞个B+树呢【B+树的优点】 #####

*  因为形成了天然的双向链表的结构，排序时间复杂度低
 *  IO利用率更高【在我们的B树中，我们每次进行IO时，加载到内存的数据，大部分是我们不需要的数据区，导致空间的浪费】
 *  基于索引的数据扫描，B+树更好，执行计划 **type = index(索引扫描) all(全表扫描)**
 *  查询稳定性【对于B树来说，可能第一次IO操作命中，返回，也可能第二次IO操作命中返回，但对于B+树来说，无论如何，都必须进行IO操作至叶子节点】

## 索引机制的落地 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 8]

*  Myisam：User.MYI、User.MYD（索引和数据区是分开存储的）
 *  Innodb：索引和数据区是一起进行存储的

### Myisam ###

*  在我们的Myisam引擎中，是没有主键索引这个概念的，相应的，也没有回表这个概念
 *  索引和数据是分开存储的【先去索引进行遍历，在叶子结点找到指针，再由指针到我们的数据存储文件中找到相对应的数据】
 *  在我们的 Myisam 中，type = index\_merge --------> 索引合并
 *  一条SQL语句可以使用2条索引嘛？
    
     *  Innodb不能
     *  Myisam可以（比如下图：我们先根据 name 和 id 查询出来磁盘的地址，再进行合并）  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 9]

### Innodb 索引的落地 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 10]

#### 聚集索引【主键索引】 ####

*  聚集索引：数据库表行中数据的物理顺序与键值的逻辑（索引）顺序相同
    
     *  在 Innidb 引擎中，只有主键索引才是聚集索引，其他索引都是非聚集索引
     *  **基于主键来进行查询，不创建会自动创建一个自适应索引**
 *  回表
    
     *  数据存储在主键索引，我们先去辅助索引查询找主键，在根据主键索引查询所有的数据
 *  为什么建议大家使用递增的序列作为索引？
    
     *  根据B+树的底层原理，如果不采取递增的序列，会导致树不断的进行调整，时间复杂度的增高
 *  为什么我们的辅助索引不直接存储所有的数据？
    
     *  为了保持树的绝对平衡，地址可能会随时进行改变
     *  这时候，如果我们的辅助索引也使用地址，会频繁的进行改变，导致时间复杂度的增高

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 11]

#### 联合索引 ####

##### 索引列的离散性 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 12]

*  计算公式：count（distinct col） : count(col)，比值越高离散性越好
 *  若列的离散性越好，列的选择性就越好
 *  选择性好的列作为索引更适合
 *  离散性很差的列作为索引可能适得其反

如果使用性别来做索引：会造成索引的持久命中，造成时间复杂度的降低  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 13]

*  联合索引是多个索引嘛？【一个索引】
 *  联合索引的使用为什么要遵循最左前置原则？
    
     *  最左前置原则：最常用列 > 离散度高 > 最少空间
     *  前面的东西不匹配，后面的无法匹配
 *  索引列的离散性
 *  单列索引是一种特殊的联合索引![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 14]

#### 覆盖索引 ####

*  主要是为了防止回表，回表造成了一定的时间损耗
 *  通过索引项的信息可直接返回所需的查询列，则该索引称之为查询SQL的覆盖索引
 *  禁止使用 `select *`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 15]

#### 三星索引 ####

*  第一颗星：WHERE 字句中条件匹配的索引关键字中列越多扫描的数据越少
 *  第二颗星：避免再次排序【select \* from user\_innodb where id > 1234123 order by name desc; 本来是按照 id 进行查询，排序后，需要物化文件，再根据 name 排序】
 *  第三颗星：尽可能运用到覆盖索引进行数据的扫描，减少回表的IO操作

#### 索引的打油诗 ####

*  全值匹配我最爱，最左前缀要遵守
 *  带头大哥不能死，中间兄弟不能断
 *  索引列上少计算，范围之后全失效
 *  Like百分写最右，覆盖索引不写星
 *  不等空值还有or，索引失效要少用

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20221120/eaccc17e985445c4a3af68e695e15117.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020121921524825.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201219215506403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201219215546922.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201219215933277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201219220651830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201219220710596.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201219220843639.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20201219221326793.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20201219221458494.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2020121922174754.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20201219221843973.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20210228162832605.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20210228162854747.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/2020121922363585.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 15]: https://img-blog.csdnimg.cn/20201219230655384.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70