【深入浅出】——MySQL索引B+Tree

待我称王封你为后i 2022-09-02 00:54 167阅读 0赞

**索引**存在的意义是帮助我们提高查询速度，那么为什么创建了索引，MySQL的查询速度就可以提高呢？为什么MySQL单表的数据达到千万后就开始建议分库分表？基于这些未知的问题，开始本文篇文章的内容。

## 何为索引 ##

**索引**是帮助MySQL高效获取数据的**排好序**的**数据结构**。划重点，排好序，数据结构，所以索引是真实存在的，不仅仅是一个虚无的概念。  
        索引提升查询的效率的原因是因为将排序的过程前置，当需要查找的时候，直接可以定位到具体数据，省去全表遍历的过程，从而提升查询效率。所以好的索引，要避免数据变成链表，减少需要比对数据，从而达到预期效果。

## 索引数据结构 ##

*  二叉树  
    二叉树在一定程度上缓解链表的查询效率问题，但是随着数据增加，二叉树存在演变成链表的可能，故存在影响查询效率的可能
 *  红黑树  
    红黑树又称平衡二叉树，相比二叉树可能存在变成链表的风险，会在查询好很多，但是依旧无法解决层高过高的问题，层高过高，则证明比对数据比较多，会影响查询效率  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]
 *  Hash表  
    对索引的key进行一次hash计算就可以定位出数据存储的位置，很多时候Hash索引要比B+ 树索引更高效，但仅能满足 “=”，“IN”，不支持范围查询，还会存在hash冲突问题  
    面对范围查找Hash表则只能变成全局扫描，仅符合部分特征  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]
 *  B-Tree  
    B-Tree一层中可以存储更多的数据节点，而且可以保证节点元素从左到右依次递增，相比二叉树、红黑树同样的层高可以存储元素更多，查询效果更好。B-Tree存储特点，每个节点存储来索引以及具体数据，而MySQL页容量大约为16KB，当单表数据集过大时，树的高度同样会比较高，影响查询效率。而且B-Tree每个叶子结点是不会连的，无法支持范围查找  
    PS：查看mysql文件页大小（16K）：SHOW GLOBAL STATUS like 'Innodb\_page\_size’;  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]  
    那么问题来了MySQL的索引到底用的什么数据结构，才能解决上述这些乱七八糟的问题？

## B+Tree ##

解决MySQL查询效率问题，必须解决以下几类问题  
    1.树高低且支持数据量要大  
     2.支持范围查询  
    从上述分析的数据结构可以得知，暂时B-Tree是最好，那么解决B-Tree的不足之处，它就能变成好用的，故B+Tree（B-Tree）的变形应运而生。

**B+Tree特点**

*  非叶子结点不存储data，只存储索引（冗余），但是可以存放更多的索引
 *  叶子结点包含所有的索引字段
 *  叶子结点之间用指针相连（双向指针），提高区域访问性能  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]  
    那么这种数据结构，树高为3能存储多少数据呢？  
    假设主键是bigint类型，长度8B，指针大小在Innodb源码中为6B，一共14B，那么一页能存储16K/14B=1170个（主键+指针），叶子结点存在数据假设为1k，则一颗高度为3的B+Tree能存储数据为：1170 \* 1170 \* 16=21902400（千万级条）

看到这里回答下文章开头的问题

**1、为什么索引可以提升查询效率？**  
    索引将数据有序的排列，查询数据时减少了比较IO操作，从而提高查询效率，而且索引的根结点通常是常驻内存的，所以正确的索引可以提升查询效率  
**2、为什么MySQL单表的数据达到千万后就开始建议分库分表？**  
    随着单表数据的增长，索引的数高也会增大，会增大比较次数，降低查询效率

## 从索引看存储引擎实现 ##

MySQL存在多种数据存储引擎，而且在使用时真正生效的存储引擎其实还是table上的设置的存储引擎，接下来只介绍日常工作中经常MyISAM和InnoDB的索引实现方案。从data存储方式，MySQL的安装目录data文件夹下，有每个数据库的具体存储内容，看到table维度，可以发现MyISAM有三个存储文件frm(表结构)、MyD(数据)、MyI(索引),而InnoDB有两个frm(表结构)，idb(数据+索引)，所以通过存储方式可以看出两种存储引擎实现不同。

### MyISAM ###

MyISAM索引文件和数据文件是分离的(非聚集)  
![非聚集索引][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]

### InnoDB ###

InnoDB索引文件和数据文件是存储在一起的(聚集)，表数据文件本身就是按B+Tree组织的一个索引结构文件。聚集索引-叶节点包含了完整的数据记录，在InooDB中仅有主键索引是聚集索引而其他索引都是非聚集索引  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 5]  
此时引出两个概念**聚集索引**和**非聚集索引**，通过两种存储引擎的比较方式可以得知，聚集索引，将索引和具体数据存储在一起，而非聚集索引则索引和数据分开存储故查询查询效率会低一些。  
其他索引的数据结构  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 6]

## 从面试看B+Tree ##

**设计分库分表方案时有几种拆分方式？为什么这样拆分？**

*  两种拆分方式，水平拆分和垂直拆分。
 *  水平拆分解决单表数据过大，造成索引的树高增加，增加查询IO次数，从而影响查询效率。
 *  垂直拆分解决单条数据过大，造成叶子结点每页存储的数据减少，增大存储空间，在范围查询时涉及数据页过多，IO次数增加，影响查询效率。

**为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？**

*  因为InnoDB的存储方式是基于聚集索引构建的，如果没有设定主键，那么MySQL就在当前表结构中寻找不重复的一列作为索引来构建，而如果找不到符合条件的列，则会设置隐藏列来完成这一过程。MySQL的资源很宝贵，没有必要浪费资源做这样的运算仅为完成数据的构建。
 *  索引是有序的，用整型比较是最方便的直接比大小即可，而使用其他类型还需要计算ascii码，变相资源浪费。
 *  索引是排好序的数据结构，乱序的主键，每次插入都需要B+Tree重新调整平衡，而自增只有叶子结点会上移，成本肯定是小于调整平衡。

**为什么非主键索引结构叶子节点存储的是主键值？**

*  数据存储多份，一致性的保证会增加额外的成本
 *  仅存储主键值，这样会节约大量数据存储空间（主要原因）

**为什么B+Tree可以支持范围查找？**

*  B+Tree的叶子节点的指针是相互指向张彼此的，这样在范围查找的，找到起始叶子节点不用再回溯到上层非叶子节点，通过叶子节点之间的指针即可完成。

**为什么MySQL索引仅支持左前缀原则呢？**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 7]

*  索引是排好序的数据结构，联合索引的存储方式，和普通索引基本无差别，就是在非叶子节点的时候，是按照联合索引的定义的顺序字段排序的，即每个字段都是有序的，如果打破顺序，从第二个字段开始匹配，因为不知道前置字段，故第二个字段起始位置无法确定，只能从最左侧开始匹配。

## 总结 ##

MySQL使用B+Tree作为索引，主要原因是B+Tree的非叶子节点仅存储索引值，使每页可以存储的索引数据增加，从而减少树高，同时叶子节点之间的双向指针，减少范围查找的回溯次数，这两个角度都是减少查找的IO操作，从而提高查询效率。关于MySQL存储引擎，InnoDB使用聚集索引，将数据和主键进行聚集，使得通过主键可以直接获取数据详细，无需二次查找。

**PS：本文如有理解偏颇之处，肯定各位大神不惜赐教，不胜感激**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/ea0c5dc0aa894fd2958407a305052eec.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220829/f3f6f3248b14455d93f1e6a917b24ae4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 2]: /images/20220829/454808722d884125bd8ef0e4d84312fa.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 3]: /images/20220829/0eccd076431343e8aebd47146f361de4.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 4]: /images/20220829/d3b1fdf4ddaa41e987f5e71c0da21165.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 5]: /images/20220829/8639086e980b49dda439424085f27fd5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 6]: /images/20220829/8ac00252356443c48d8b67aea0a1ae7e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATWFuZHlfaQ_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 7]: /images/20220829/148533d6c1184be48808aa7dda3d0819.png