2020-11-13

前言

索引是MySQL数据库中很重要的组成部分，也是程序员最关注的部分，索引的目的主要在于提高查询的效率。可以类比于字典中的目录。查找字典中的内容的同时，可以根据目录查找数据的存放位置，从而提取到数据。MySQL 支持多种存储引擎，我们只针对InnoDB下面的B+Tree索引进行学习

 

索引的原理

在生活中随处可见索引的列子，比如上面提到的图书的目录，车次表，原理都是一样的通过不断的缩小查找范围的数据，来获取结果。数据库也是一样的，但是显然要复杂很多，因为我们不仅仅面着着等值查询(=)，还有范围查找(<，>, between and , in )，模糊匹配 (like), 并集的查找（or) 等等。

基于这些问题，数据库改怎么来设计应对这样的问题？基于数据库的实现，我们的数据是保存在磁盘上的，为了提高性能，每次我们又需要把部分数据加载到内存中计算，我们知道访问磁盘的成本大概是访问内存成本的10万倍左右。

磁盘IO跟预读取

这里补充一点计算机的基础知识

• https://blog.****.net/xingjiarong/article/details/46312571硬盘的工作原理

  现代硬盘寻道都是采用CHS(Cylinder Head Sector)的方式，硬盘读取数据时，读写磁头沿径向移动，移到要读取的扇区所在磁道的上方，这段时间称为寻道时间(seek time)。因读写磁头的起始位置与目标位置之间的距离不同，寻道时间也不同。目前硬盘一般为2到30毫秒，平均约为9毫秒。磁头到达指定磁道后，然后通过盘片的旋转，使得要读取的扇区转到读写磁头的下方，这段时间称为旋转延迟时间(rotational latencytime)

• 机械硬盘，每次读取的时候都是依靠机械运动，每次读取时间都分为寻道时间、旋转延迟、传输时间三个部分。寻道时间只的磁头寻找到磁道需要的时间，主流的磁盘大概是在5ms以内；旋转延迟简单理解就是我们经常说的磁盘的转速，eg：7200转，指的是7200/min，等于120/sec ，旋转的延时就是1/120/2(一般都将磁盘旋转周期的一半定义为旋转延迟)约等 4.17ms，传输的时间指将数据从磁盘读取或者写入时间，一般在零点几毫秒，可以忽略。 通过以上理论计算 ，平均访问一次磁盘IO的时间大概是在9ms左右，听起来不错但是针对数据库随随便便上百万，千万级别的的数据，每次IO需要9ms的时间，显然是无法承受的。

• 磁盘的预读:由于磁盘IO是非常昂贵的操作，计算做了一些优化，每次IO的时候，不光是当前磁盘的数据加载内存，而且把相邻的数据也加载到内存缓冲区内。因为计算机认为，当访问一个地址的数据的时候，相邻的数据也很快会被访问。每次IO读取数据的单位称为页（Page）,具体一页数据多少跟操作系统有关系，默认为4Kb，mysql默认为16Kb。这个理论对mysql的索引数据结构非常有帮助。

• SSD的技术发展，取代了传统的机械硬盘，采用了闪存技术，大大提高了磁盘的读写能力。

   

InnoDB 架构

• Master Thread

  • 主要是负责将缓冲池的数据异步刷新到磁盘，保障数据的一致性，包括脏页的刷新，合并插入缓冲（Insert buffer）、回滚页(undo page)的回收等。

• IO Thread

  • InnoDB 存储引擎中大量使用了AIO（Async IO）处理IO的请求，这样可以极大的提高数据库的处理性能。IO Thread(insert buffer thread; log thread ; read thread ; write thread)

• Purge Thread

  • 事务被提交后，使用的undo log 可能不再需要，因此需要 Purge Thread 来回收已经使用并分配的undo 页。

• Page Cleaner Thread

  • 1.2 版本之后引入，将之前版本中的脏页数据刷新操作，用一个单独的线程来操作，目的是为了减轻 Master thread的工作，以及用户查询线程的阻塞。

MySQL数据页结构分析

Page 是InnoDB存储引擎用于管理数据的最小磁盘单位。常见的页类型，有数据页，Undo页，系统页，事务数据页等。我们主要研究一下数据页跟行记录数据结构。

 

1. 从上到下依次为： TableSpace(表空间，ibd文件)、Segment（段，一个索引2个段）、Extent(区,默认1MB，1 extent=64Page)、 Page （页，默认16kb，磁盘管理最小单位）

2. 每个Page占用了16kb，64个连续的Page占用1MB叫做Extent, 多个Extent 组合在一起就是一个表空间，也叫做表文件。

Page跟Row的结构。

Page逻辑结构

几个基本概念

• Page的默认大小是16kb，每个Page用一个32位的数字进行标记，一共有2^32个Page，每个表空间有64T的容量(16*2^32/1024/1024/1024=64TB)

• 每个Page都一个OfferSet,Page0 的offerSet = 0 ,Page1 的offerSet = 16384（16kb），以此类推

• 每个Page有个38字节的字节头，跟8字节的尾，有兴趣的可以研究下

Page的逻辑存储结构图

 

• 如图所示：每个Page 保存着Pre_head和Next_head 的指针信息；Page Head里还保存着Page的类型和Page的序号等信息。

• 页的中间保存着数据记录，其中第一条记录为系统记录，Supermum 保存数据的尾指针信息，Infimum 保存数据的头指针信息。User Record是单链表的形式存储。

• 从上面简单的逻辑存储来看，其实可以发现数据库的存储引擎本质上按照一个文件系统来设计的。

 

MySQL记录存储

• 页头

• 记录页面的控制信息，一共占56字节，包含左右相邻页的指针，以及页面空间的使用情况。

• 虚记录（Infimum+Supremum Records)最小虚记录以及最大虚记录

  两个固定位置存储的记录，本身并不存储数据。

  • 最大虚记录，比页内最大的主键还大

  • 最小虚记录，比页内最小的主键还小

• 记录堆（record heap） 对应 User Record

  • 有效记录 -> 索引正常使用的记录

  • 已删除记录-> 表示索引已经删除的记录，不使用的记录，随着记录的更新和删除越来越频繁，记录堆中的已删除的记录将会越多，出现内存空洞和碎片。这些已删除的记录连接起来，就会形成页面的自由空间链表。

• 未分配空间: 指页面未使用的存储空间，随着页面的不断使用，未分配空间将会越来越小。当新插入一条记录时，首先尝试从自由空间链表，获得合适的存储位置，（空间足够），如果没有满足的，就会在未分配的空间中申请。

• solt 区（目录槽）Page Directory: slot区是一些页面有效记录的指针，每个slot占用两个字节，存储了记录相对页面的首地址的偏移。 记录了页面有序和二分查找的关键。

• 页尾（Page Tailer）: 页面的最后部分，占8个字节，主要存储页面的校验信息。