InnoDB 存储引擎架构与索引的实现

逃离我推掉我的手 2021-11-05 08:01 559阅读 0赞

### 文章目录 ###

*  Mysql 体系结构
 *  InnoDB体系结构
 *   *   *   *   *  后台线程
                 *  内存池
                 *  Checkpoint 机制
 *  InnoDB的关键特性
 *   *   *  从insert Buffer到change Buffer
         *  两次写( Double Write)
         *  自适应哈希索引(Adaptive Hash Index)
         *  异步IO(Async IO)
         *  刷新邻接页(Flush Neighbor Page)
 *  这里回答一个面试时被问到的问题：为什么一般情况下要有自增主键？
 *  InnoDB中的索引实现
 *   *   *  InnoDB 支持的索引类型主要有以下几种：
         *  B+树索引（聚集索引和辅助索引）
         *   *   *  聚集索引 (clustered index)
                 *  辅助索引（二级索引） Secondary Index
 *  面试题目解析：以a,b,c创建索引，为啥子以a,c查询时，用不上创建的索引???
 *   *   *   *   *  覆盖索引
         *  哈希索引(是DB自己实现的，人工无法干预。具体略)
         *  全文检索（这玩意儿现在主流应该是ES吧）
         *   *   *  倒排索引，反向索引

# Mysql 体系结构 #

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

1.  Connectors指的是不同语言中与SQL的交互
2.  Management Serveices & Utilities： 系统管理和控制工具
3.  Connection Pool: 连接池。
4.  SQL Interface: SQL接口。接受用户的SQL命令，并且返回用户需要查询的结果。比如select from就是调用SQL Interface。
5.  Parser: 解析器。
6.  Optimizer: 查询优化器。
7.  Cache和Buffer： 查询缓存。
8.  Engine ：存储引擎。

从架构中可以看出，MYSQL的存储引擎是可以自由选择的，可以插件化。

需要特别注意的是：`存储引擎是基于表的，而不是数据库。(搞不懂为啥这样说呐？)`

参考：http://www.jiaochengphp.com/mysql-tutorials-115685.html

大致看完了Mysql的架构体系，我们再来看下，其与文件系统打交道的存储引擎层是如何实现的。以InnoDB为例！

# InnoDB体系结构 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]  
内存池不言而喻，自然是有着维护 所有进程需要访问的多个内部数据结构，缓存磁盘文件等的作用。

后台线程的主要作用就是：`更新缓存。`负责刷新内存池中的数据，以及将已修改的数据文件刷新到磁盘文件。

##### 后台线程 #####

*  Master Thread

主要负责将缓冲池中的数据异步刷新到磁盘，保证数据的一致性，包括脏页的刷新、合并插人缓冲(INSERT BUFFER)、UNDO页的回收等

**这里我有一个问题就是为啥会有脏页呐？**

*  I0 Thread

在InnoDB存储引擎中大量使用了AIO (Async I0)来处理写I0请求，这样可以极大提高数据库的性能。而`IOThread的工作主要是负责这些I0请求的回调(callback)处理.·`

大致有4个IO Thread,分别是write、read、 insert buffer和logI0 thread。

*  Purge Thread

事务被提交后，其所使用的undolog可能不再需要，因此需要`PurgeThread来回收已经使用并分配的undo页。`

*  Page Cleaner Thread

用于将刷新脏页数据。

##### 内存池 #####

*  1.缓冲池

`InnoDB存储引擎是基于磁盘存储的，并将其中的记录按照页的方式进行管理`。因此可将其视为基于磁盘的数据库系统(Disk base Database)。 在数据库系统中，由于CPU速度与磁盘速度之间的鸿沟，基于磁盘的数据库系统通常使用缓冲池技术来提高数据库的整体性能。

这个就如以前写的缓冲一样，不再详述。

对于数据库中页的修改操作，则首先修改在缓冲池中的页，然后再以一一定的频率刷新到磁盘上。这里需要注意的是，页从缓冲池刷新回磁盘的操作并不是在每次页发生更新时触发，而是通过一种称为`Checkpoint 的机制`刷新回磁盘。同样，这也是为了提高数据库的整体性能。

具体缓存的对象有很多,罗列如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]

*  2.LRU List ,Free List和 Flush List

OK，那么`InnoDB是如何管理以上所说到的内存区域的呐？`其实就和OS管理内存(LRU)一样。只不过这里InnoDB做了一些简单的优化。

在InnoDB的存储引擎中，LRU列表中还加人了midpoint 位置.新读取到的页，虽然是最新访问的页，但并不是直接放人到LRU列表的首部，而是`放入到LRU列表的midpoint位置`。这个算法在InnoDB存储引擎下称为`midpoint insertion strateg`y.在默认配置下，该位置在LRU列表长度的5/8处。实现不重要，为什么这样做才是最重要的。

**原因**：若直接将读取到的页放人到LRU的首部，那么某些SQL操作可能会使缓冲池中的页被刷新出，从而影响缓冲池的效率。常见的这类操作为索引或`数据的扫描操作。这类操作需要访问表中的许多页，甚至是全部的页，而这些页通常来说又仅在这次查询操作中需要，并不是活跃的热点数据。如果页被放入LRU列表的首部，那么非常可能将所需要的热点数据页从LRU列表中移除`，而在下一次需要读取该页时，InnoDB 存储引擎需要再次访问磁盘。

其实可以看到，也是根据自身特点才做了这样的东西。如果每次都是访问一个元素的话，这样做我吃屎！！！

free-list：就是DB刚启动时，页面存放的地方。

> 脏页与脏读不同哦！！！终于，我想要了解的脏页来了 。

**脏页：就是 LRU 列表中被修改的页。** 其实就是缓冲与磁盘出现了不一致的情况。

所以 Flush-list 中存在的就是脏页列表。需要注意的是脏页即存在于LRU 又存在于 Flush-list

*  3.重做日志缓冲：顾名思义吧！！！
 *  4.额外的内存池：有些数据结构的内存分配从这里来，而不是缓冲池。

##### Checkpoint 机制 #####

和带有保存点的扁平事务一样。具体怎么将脏页刷新的还是去查看下《Mysql技术内幕》吧。这里就不记录了！！！

依稀记得：超过脏页<70%，就刷新10%之类的。

# InnoDB的关键特性 #

*  插入缓冲(Insert Buffer)
 *  两次写( Double Write)
 *  自适应哈希索引(Adaptive Hash Index)
 *  异步10 (Async IO)
 *  刷新邻接页(Flush Neighbor Page)

### 从insert Buffer到change Buffer ###

Insert Buffer可能会让人认为插人缓冲是缓冲池中的一个组成部分。其实不然，InnoDB 缓冲池中有Insert Buffer信息固然不错，但是`Insert Buffer 和数据页-样，也是物理页的一个组成部分。`

在InnoDB存储引擎中，主键是行唯一的标识符。通常应用程序中行记录的插人顺序是按照主键递增的顺序进行插人的。因此，插人聚集索引( Primary Key) 一般是顺序的，不需要磁盘的随机读取。比如按下列SQL定义表:

CREATE TABLE t (
    
          a INT AUTO INCREMENT,
          b VARCHAR(30),
          PRIMARY KEY (a))

其中a列是自增长的，若对a列插入NULL值，则由于其具有AUTO INCREMENT属性，其值会自动增长。`同时页中的行记录按a的值进行顺序存放。在- -般情况下，不需要随机读取另-个页中的记录`。因此，对于这类情况下的插人操作，速度是非常快的。

但是不可能每张表上只有一个聚集索引，更多情况下，一张表上有多个非聚集的辅助索引( secondary index)。比如，用户需要按照b这个字段进行查找，并且b这个字段不是唯- -的，即表是按如下的SQL语句定义的:

CREATE TABLE t (
    
          a INT AUTO INCREMENT,
          b VARCHAR(30),
          PRIMARY KEY (a),
          key(b)
          ) ;

OK，那么数据的存放还是按主键来的，但是`对于非聚集索引的叶子节点的插入就是离散的。（这也就是说聚集索引的话就始终按照顺序方就得了，但是非聚集索引的话，就可能会发生插入等操作。）`

InnoDB存储引擎开创性地设计了Insert Buffer,`对于非聚集索引的插人或更新操作，不是每一-次直接插入到索引页中，而是先判断插入的非聚集索引页是否在缓冲池中，若在，则直接插人:若不在，则先放人到一个Insert Buffer 对象中，好似欺骗。数据库这个非聚集的索引已经插到叶子节点，而实际并没有，只是存放在另- -个位置。然后再以一定的频率和情况进行Insert Buffer和辅助索引页子节点的merge ( 合并)操作，这时通常能将多个插入合并到一个操作中( 因为在一个索引页中)`，这就大大提高了对于非聚集索引插入的性能。

需要满足的条件是：

*  索引是辅助索引(secondary index)
 *  索引不是唯一(unique) 的。

> 辅助索引不能是唯一-的， 因为在插入缓冲时，数据库并不去查找索引页来判断插人的记录的唯–性。`如果去查找肯定又会有离散读取的情况发生`，从而导致InsertBuffer失去了意义。

change Buffer：是insert Buffer 的升级版，他们之前的实现可查看《技术内幕》

### 两次写( Double Write) ###

当发生数据库宕机时，可能InnoDB存储引擎正在写人某个页到表中，而这个页只写了一部分，比如16KB的页，只写了前4KB,之后就发生了宕机，这种情况被称为部分写失效(partial page write)。

如果发生写失效，可以通过重做日志进行恢复。这是- -个办法。但是`必须清楚地认识到，重做日志中记录的是对页的物理操作，如偏移量800,写'aaa'记录。如果这个**页本身已经发生了损坏，再对其进行重做是没有意义的**。这就是说，在应用(apply) 重做日志前，用户需要-一个页的副本，当写人失效发生时，先通过页的副本来还原该页，再进行重做`，这就是doublewrite。

在\*\*对缓冲池的脏页进行刷新时，并不直接写磁盘，而是会通过memcpy函数将脏页先复制到内存中的doublewrite buffer,之后通过doublewrite buffer再分两次，每次1MB顺序地写人共享表空间的物理磁盘上，然后马上调用fsync 函数，同步磁盘,\*\*避免缓冲写带来的问题。在这个过程中，因为doublewrite页是连续的，因此这个过程是顺序

### 自适应哈希索引(Adaptive Hash Index) ###

内部实现的一种自动根据索引情况建立哈希索引的东西

### 异步IO(Async IO) ###

使用内核级别的AIO。支持多个IO操作合并。具体见：

[只说一件事之 Linux 异步 I/O－AIO][Linux _ I_O_AIO]

### 刷新邻接页(Flush Neighbor Page) ###

当刷新某一个脏页的时候 ，会检查与他相邻的页。

OK，说完了所有涉及到的一些知识点，那我们来看看最新的InnoDB的架构图，相信一定会有不一样的理解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]  
图取自 Mysql 官方文档。版本8.0

# 这里回答一个面试时被问到的问题：为什么一般情况下要有自增主键？ #

其实这个问题 你简单回答也是完全能够应付过去的。但是何乃我这个人就是喜欢研究的更深一点，这也是我们实验室一代一代传承下来的思想。

# InnoDB中的索引实现 #

### InnoDB 支持的索引类型主要有以下几种： ###

*  B+树索引
 *  全文索引
 *  哈希索引

### B+树索引（聚集索引和辅助索引） ###

##### 聚集索引 (clustered index) #####

聚集索引(clustered index)就是按照每张表的主键构造一棵B+树，同时`叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页`。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。 同B+树数据结构- -样，每个数据页都通过一个双向链表来进行链接。

由于`实际的数据页只能按照一棵B+树进行排序，因此每张表只能拥有-一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在B+树索引的叶子节点上直接找到数据,少一次磁盘I/O`。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某- -段范围的数据页需要扫描。

*  优点：
    
     *  1.范围查询(range query),即如果要查找主键某-范围内的数据， 通过叶子节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可
     *  2.对于主键的排序查找和范围查找速度非常快。叶子节点的数据就是用户所要查询的数据。如用户需要查询- -张注册用户的表，查询最后注册的10位用户，由于B+树索引是双向链表的，用户可以快速找到最后一个数据页，并取出10条记录

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 4]  
因为InnoDB的数据文件本身 要按主键聚集，所以**InnoDB要求表必须有主键**（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列 作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

##### 辅助索引（二级索引） Secondary Index #####

其实就是 `叶子节点包含的数据变成了主键的键值`，而不是所有的行记录数据了（`由于InnoDB存储引擎表是索引组织表，因此InnoDB存储引擎的辅助索引的指针指向的就是相应行数据的聚集索引键`）

如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 5]  
因为辅助索引是不影响数据在聚集索引中的组织的，所以他可以存在多个。

了 解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就**很容易明白为什么不建议使用过长的字段作为 主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大**。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为 InnoDB 数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用 自增字段作为主键则是一个很好的选择。

> show index : cardinality接近1就是好的，如果很小，说明索引没有存在的必要了。

# 面试题目解析：以a,b,c创建索引，为啥子以a,c查询时，用不上创建的索引??? #

之前以为很难，其实很简单。见下图就知道了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 6]  
后面的一个值是不排序的哦~~

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

InnoDB存储引擎支持覆盖索引(covering index,或称索引覆盖),即`从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。`使用覆盖索引的-个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

对于InnoDB存储引擎的辅助索引而言，由于其包含了主键信息，因此**其叶子节点存放的数据为(primary key1, primary key2, . key1, key2， .)**

### 哈希索引(是DB自己实现的，人工无法干预。具体略) ###

### 全文检索（这玩意儿现在主流应该是ES吧） ###

##### 倒排索引，反向索引 #####

这里粘一个链接吧！以后希望能遇到这方面的知识点再进行深入学习。

本质上来讲就是（以搜索为例，突然发现我现在对搜索真的很感兴趣啊）：

*  正排-》文档包含哪些单词
 *  倒排-》单词被哪些文档包含

文档->【单词1->单词2->单词3。。。】  
单词->【文档1->文档2->文档3。。。】

https://www.cnblogs.com/zlslch/p/6440114.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]: /images/20211104/5e1236f43a554aa6a28989a204186012.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]: /images/20211104/4a37f761e708474292265201ed8b5a55.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]: /images/20211104/0a6dd30363a441c486b0888d8cad0a86.png
[Linux _ I_O_AIO]: https://blog.csdn.net/liushengxi_root/article/details/89224871
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]: /images/20211104/124821a4e92e4b62aee57ea5028c0a12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 4]: /images/20211104/6a45c70177bd41acb3bb88c4bebe275e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 5]: /images/20211104/10fe4a4793e946dfa5595071535b980d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 6]: /images/20211104/7d6942b55dd54619ad8a6d17b6c7d4e9.png