MySQL索引的底层结构

爱被打了一巴掌 2023-10-09 18:58 32阅读 0赞

#### mysql索引的底层结构 ####

*  MySQL中的索引
 *  索引的底层数据结构
 *  索引的类型
 *   *  普通索引
     *  主键索引
     *  唯一索引
     *  全文索引
     *  如何选择索引
     *   *  从表面的基本特性考虑
         *  性能和底层来分析
 *  覆盖索引的定义
 *   *  回表操作
 *  最左匹配原则

## MySQL中的索引 ##

本质是一种‘排好序的数据结构’，可以帮助快速查找数据。可以类比目录理解。

**不能全加上索引的原因：**  
虽然它查询使用优化隐藏器提高性能，但是也会相应占物理空间，从而导致降低增删改的速度，因为操作数据的同时也要‘维护索引文件’。

## 索引的底层数据结构 ##

常规的搜索引擎一般都是采用B树或者B+树来实现索引的存储。

常用的是B+树和Hash，常用的InnoDB引擎就是B+树实现的。

**不使用hash作为索引的原因：**  
hash底层是哈希表实现，等值查询，可以快速定位，一般情况效率很高，不稳定，无法用于排序分组，无法模糊查询。

**树的高度与磁盘之间的关系**  
![在这里插入图片描述][7af79dad29fe4b5eb75c21e98e8b6362.png]  
B树是一种**多路平衡树**，用这种存储结构来存储大量数据的情况，其**整体高度相比二叉树来说会矮很多**。

对于数据库来说，所有数据必然是存储在磁盘上的，而磁盘IO的效率实际上是很低的。特比是在随机磁盘IO的情况下，效率更低，所以**树的高度就能决定磁盘IO的次数**。磁盘IO次数越少，对性能提升就会越大。

但是，在MySQL的InnoDB存储引擎里面，它采用的是一种增强的B树结构，也就是B+树来作为索引和数据的一个存储结构。

![在这里插入图片描述][cef724c1620c4581a6b7629cc2325cdc.png]  
相比于B树，B+树做了几个方面的一个优化：

1.  B+树的所有数据都存储在叶子节点，非叶子节点只存储索引。
2.  叶子节点中的数据使用双向链表的方式进行关联的。

**选用B+树不使用B树的原因：**

1.  B+树只在叶子节点储存数据，**非叶子结点存索引**，而一个节点就是磁盘一个内存页，内存页大小固定。所以**每一层能够存储的索引数量会增加**。那么相比B树，这些便可以存更多的索引节点，出度更大，树高也就会更矮，这样查询次数少，**磁盘IO次数少**，性能也就更佳。
2.  叶子节点中的数据使用双向链表的方式进行关联的。MySQL中，**范围查询**是一个比较常用的操作，而B+树的所有存储在**叶子节点**的数据使用了**双向链表**来关联，所以在查询的时候只需查两个节点进行**遍历**就行，而**B树需要获取所有节点**，所以**B+树在范围查询上效率更高**。
3.  在**数据检索**方面，由于所有的数据都存储在叶子节点，所以B+树的**IO次数会更加稳定一些**。
4.  因为**叶子节点存储所有数据**，所以**B+树**的**全局扫描**能力**更强**一些，因为它只需要扫描叶子节点。但是**B树**需要**遍历整个树**。

另外，基于B+树这一个结构，如果采用自增的整型数据作为主键，还能够更好的去避免增加数据的时候带来的叶子节点分裂导致了大量运算的一个问题。

总的来说，技术方案的选择，更多的是去解决当前场景下的一些特定问题。并不一定B+树就是最好的选择。

就像**MongoDB中采用B树结构**，本质上来说是关系型数据库和非关系型数据库的一个差异。

## 索引的类型 ##

### 普通索引 ###

### 主键索引 ###

### 唯一索引 ###

### 全文索引 ###

### 如何选择索引 ###

#### 从表面的基本特性考虑 ####

普通索引可以重复，唯一索引只能是唯一一个，当然可以为空，而主键索引也是唯一的，不过它不能为空，因为它要作为聚簇索引排列，这就是为啥我们使用主键时不能为null。

#### 性能和底层来分析 ####

**查询**：以页为单位将数据页加载进内存，不需要一条记录一条记录读取磁盘。

然后唯一索引根据条件查询到记录时就返回结果，而普通索引查到第一条记录往后遍历直到不满足条件。

由于都在内存中，不需要磁盘读取那么大开销，带来的额外查询开销忽略不计，所以查询性能几乎一致。

因此，对于查询，选择普通索引、唯一索引都差不多。

**更新**：唯一索引由于更新时要检查唯一性，所以需要将数据页先加载进内存才能判断，此时直接操作内存，不需要操作`change buffer`。

普通索引若数据在内存中就直接在内存中更新，否则会将更新操作先记录到`change buffer`中，等下一次查询将数据读到内存中再进行`change buffer`里相关更新操作后将数据返回。

这样一来，在写多读少的情况下就减少了磁盘IO，若写完就马上查询，就大可不必用`change buffer`, 不但没提高多少效率还造成维护`change buffer`额外消耗。

因此，在写多读少的情况下，选用普通索引更好。

因为普通索引可以利用`change buffer`进行性能优化减少磁盘IO，将更新操作记到`change buffer`,等查询来了将数据读到内存再进行修改。

## 覆盖索引的定义 ##

其实‘覆盖索引’很好理解，就是索引字段覆盖了查询语句涉及的字段，直接通过索引文件就可以返回查询所需的数据，不必通过回表操作。

### 回表操作 ###

通过索引去找到主键，再根据主键ID去主键索引查，‘InnoDB’使用聚簇索引，它的二级索引就是这样一个模式。

## 最左匹配原则 ##

联合索引（a，b，c）

select \* from table\_xl where c = ‘1’ and b = ‘2’ and a = ‘3’ 会走索引吗？  
这是全值匹配查询，查询优化器会自动优化查询顺序。

select \* from table\_xl where a = 1 and b > 3 会走索引吗？  
a = 1的情况下b是有序的，进行范围查找走的是联合索引，会走a b 索引。

**参考资料：**

1.  [【大厂面试】终于上岸了，没想到MySQL索引会这样问][MySQL]
2.  [【Java最新面试题】阿里一面：Mysql为什么使用B+树作为索引结构？][Java_Mysql_B]

[7af79dad29fe4b5eb75c21e98e8b6362.png]: https://img-blog.csdnimg.cn/7af79dad29fe4b5eb75c21e98e8b6362.png
[cef724c1620c4581a6b7629cc2325cdc.png]: https://img-blog.csdnimg.cn/cef724c1620c4581a6b7629cc2325cdc.png
[MySQL]: https://www.bilibili.com/video/BV1XF411V72b/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb
[Java_Mysql_B]: https://www.bilibili.com/video/BV1HT411W7Qo/?spm_id_from=333.337.search-card.all.click&vd_source=a1af903e57688df870625021f7f3a7eb