MySQL之InnoDB存储结构总结

数组是最基本的数据结构，很多语言都内置支持数组。数组是使用一块连续的内存空间保存数据，存储一组具有相同类型的数据，保存的数据个数在分配内存的时候就是确定的。

• 访问数组中第n个数据（即根据数据的下标随机访问）的时间复杂度是O(1)；
• 但是要在数组中查找一个指定的数据则是O(N)；

• 最好的情况是在数组的末尾进行操作，时间复杂度是O(1) ；
• 最坏情况是插入或者删除第一个数据，时间复杂度是 O(N) 。在数组的任意位置插入或者删除数据的时候，后面的数据全部需要移动，移动的数据还是和数据个数有关所以总体的时间复杂度仍然是 O(N) 。
• 平均情况时间复杂度也为O(n)。

特点：按照下标（索引）查询速度快、遍历数组方便。

限制：

• 数组大小固定后无法扩容；

• 数组只能存储一种类型的数据；

• 添加删除慢（需要移动其它元素）；

使用场景：频繁查询，对存储空间要求不大、增加删除少的场景。

栈或者称为堆栈，栈是一种特殊的线性表（桶状线性数据结构）。仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作 。

特点：先进后出（FILO）；

限制：只允许操作栈顶，不允许操作栈底；

队列实现了先入先出的语义，队列也可以使用数组和链表来实现。队列也是一种线性表 。不同的是，队列可以在一端添加元素，在另一端取出元素 。

链表是在非连续的内存单元中保存数据，并且通过指针将各个内存单元链接在一起，最右一个节点的指针指向NULL。链表不需要提前分配固定大小存储空间，当需要存储数据的时候分配一块内存并将这块内存插入链表中。

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个节点，一个是存储元素的数据域（内存空间），另一个是指向下一个节点的指针域。根据指针的指向，链表能形成不同的结构。

在链表中查找第n个数据以及查找指定的数据的时间复杂度是O(N)，但是插入和删除数据的时间复杂度是O(1)，因为只需要调整指针就可以：

• 很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
• 添加或删除元素时只需要改变前后两个元素节点的指针域指向地址即可，所以添加删除速度很快。

• 因含有大量的指针域，占用空间较大；
• 查找元素需要遍历链表来查找，非常耗时。

使用场景：数据量较小，需要频繁添加删除操作的场景。

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。针对某个数据的等值查询时间复杂度为O(1)。

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。在图中的数据元素，我们称之为顶点（Vertex），顶点集合有穷非空。在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

因为我们的MySQL没有涉及到图这种数据结构，所以我对图这种数据结构也不是很了解，想要了解的话，请移步：https://www.jianshu.com/p/bce71b2bdbc8。

堆（Heap）是计算机科学中一类特殊的数据结构的统称，堆通常是一个可以被看做一棵完全二叉树的数组对象，根节点可以为大于等于任何子节点（也可以小于等于任意子节点，看具体的排序方法），在存取时没有任何限制，可以随意的访问某一个子节点。最大堆：每个节点的值都大于等于它的孩子节点。最小堆：每个节点的值都小于等于它的孩子节点。

特点：

• 堆中某个节点的值总是不大于或不小于其父节点的值；

• 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

• 每个节点有零个或多个子节点；
• 没有父节点的节点为根节点；
• 每个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树。

• 无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树,也称为自由树；
• 有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
• 二叉树：每个节点最多含有两个子树的树称为二叉树；
• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个节点的二叉树，当且仅当其每一个节点都与深度为K的满二叉树中编号从1至n的节点一一对应时称之为完全二叉树。

其实数据结构是为了方便大家理解数据存储方式的一种逻辑图示的表示方式，真实物理存储就像我们之前学习的MySQL之B+树索引，InnoDB存储引擎的B+树也是一种树形结构，组织的方式是通过目录项，目录项中又包含主键和页号。再来回忆一下这张图。

前段时间我们学习了MySQL之InnoDB记录结构、MySQL之数据页结构、MySQL之B+树索引、MySQL之InnoDB表空间这些知识，从微观角度的一行记录格式一直到宏观的表空间结构都有了较全面的了解，但是里面各种属性、包括属性所占用的字节数等等知识点太多，记不住。其实，工作中我们也很少用到那些个属性，所以，暂时先把那些记不住的属性忘掉，我们把重要的知识点总结整理一下。

InnoDB中有很多不同种类的页（Page），Page的大小为16KB，为了方便管理这些页，InnoDB提出了区（Extent）的概念，连续的64个页就是一个区。每256个区被划分为1个组。

• 1个区 = 64个页 = 1MB

• 1个组 = 256个区 = 256MB

extent 0 ~ extent 255这256个区是第1组，extent 256 ~ extent 511这256个区是第2组，extent 512 ~ extent 767这256个区是第3组，以此类推。

• FSP_HDR类型：用来登记整个表空间的一些整体属性以及本组所有的区（就是extent 0 ~ extent 255第1组这256个区）的属性。整个表空间只有一个FSP_HDR类型的页面。
• IBUF_BITMAP类型：用来存储本组所有区的所有页面关于INSERT BUFFER的信息。
• INODE类型：用来存储许多称为INODE的数据结构。

• XDES类型：全称是extent descriptor，用来登记本组256个区的属性。
  
• IBUF_BITMAP类型：同上，不再赘述。

InnoDB存储引擎的表只有一个聚簇索引，一个索引会生成2个段（存放叶子节点的区的集合、存放非叶子节点的区的集合），段是以区为单位申请存储空间的，对于存储记录比较少的表这样的申请方式很浪费。所以，段对于数据量较小的表太浪费存储空间的这种情况，提出了碎片（fragment）区的概念：在一个碎片区中，并不是所有的页都是为了存储同一个段的数据而存在，在碎片区中的页可以用于不同的目的，比如有些页用于段A，有些页用于段B，有些页甚至哪个段都不属于。碎片区直属于表空间，不属于任何一个段。

为某个段分配存储空间的策略：

• 在刚开始向表中插入数据的时候，段是先从某个碎片区以单个页面为单位来分配存储空间。
  

• 当某个段已经占用了32个碎片区页面之后，就会以完整的区为单位来分配存储空间。
  

段是一些零散的页面以及一些完整的区的集合。

表空间的是由若干个区组成，这些区大体上可以分为4种类型：

• 空闲的区（FREE）：现在还没有用到这个区中的任何页面。

• 有剩余空间的碎片区（FREE_FRAG）：碎片区中还有可用的页面。

• 没有剩余空间的碎片区（FULL_FRAG）：碎片区中的所有页面都被使用，没有空闲页面。

• 附属于某个段的区（FSEG）：每一个索引都可以分为叶子节点段和非叶子节点段，除此之外还会定义一些特殊作用的段，在这些段中的数据量很大时将使用区来作为基本的分配单位。

处于FREE、FREE_FRAG以及FULL_FRAG这三种状态的区是独立的，直属于表空间；而处于FSEG状态的区是附属于某个段。

向表中插入数据本质上就是向表中各个索引的叶子节点段、非叶子节点段插入数据，不同的区有不同的状态，看一下向某个段中插入数据的过程：段中数据较少 → 查看表空间中是否有FULL_FRAG的区 → 如有，取一些零散的页把数据插进去。否则，到表空间申请一个状态为FREE的区，状态变为FREE_FRAG，然后从该新申请的区中取一些零散的页把数据插进去 → 之后不同的段使用零散页的时候都会从该区中取，直到该区中没有空闲空间，然后该区的状态就变成了FULL_FRAG。

为区分直属表空间中区的状态，通过XDES Entry结构中List Node的指针将不同状态的区分为3个链表：

• 把状态为FREE的区对应的XDES Entry结构通过List Node来连接成一个链表，这个链表称之为FREE链表；
  
• 把状态为FREE_FRAG的区对应的XDES Entry结构通过List Node来连接成一个链表，这个链表称之为FREE_FRAG链表；
  
• 把状态为FULL_FRAG的区对应的XDES Entry结构通过List Node来连接成一个链表，这个链表我们就称之为FULL_FRAG链表。

除了直属表空间的区外，我们还再考虑一下属于某个段的区状态，InnoDB为每个段中的区对应的XDES Entry结构也建立了3个链表：

• FREE链表：同一个段中，所有页面都是空闲的区对应的XDES Entry结构会被加入到这个链表。注意和直属于表空间的FREE链表区别开了，此处的FREE链表是附属于某个段的。
• NOT_FULL链表：同一个段中，仍有空闲空间的区对应的XDES Entry结构会被加入到这个链表。
• FULL链表：同一个段中，已经没有空闲空间的区对应的XDES Entry结构会被加入到这个链表。

综上所述，1张含有1个聚簇索引、1个二级索引的表，2个索引共4个段，每个段有3个链表，共12个链表，加上直属表空的3个链表，整个独立表空间共需维护15个链表。

记录的额外信息：由变长字段长度列表、NULL值列表、记录头信息组成。

• 变长字段长度列表：在Compact行格式中，所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表，各变长字段数据占用的字节数按照列的顺序逆序存放。

• NULL值列表：Compact行格式把值允许为NULL的列统一管理起来，将每个允许存储NULL的列对应一个二进制位，二进制位按照列的顺序逆序排列。二进制位的值为1时，代表该列的值为NULL，反之亦然。NULL值列表必须用整数个字节的位表示，如果使用的二进制位个数不是整数个字节，则在字节的高位补0。

• 记录头信息：用于描述记录的记录头信息，固定大小5个字节（40二进制位）。record_type：当前记录的类型，一共有4种类型的记录，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录。next_record：从当前记录的真实数据到下一条记录的真实数据的地址偏移量。

记录的真实数据：除了记录的真实数据外，还有固定6字节大小的DB_ROW_ID（行ID）、6字节大小的DB_TRX_ID（事务ID）、7字节大小的DB_ROLL_PTR（回滚指针）。

• 当记录中的数据太多，当前页放不下的时候，会把多余的数据存储到其他页中，这种现象称为行溢出。Compact和Redundant行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分数据，把剩余的数据分散存储在几个其他的页中，然后记录的真实数据处用20个字节存储指向这些页的地址。

• 行溢出的临界点：如果一个列中存储的数据小于8099个字节，那么该列就不会成为溢出列，否则该列就需要成为溢出列。不过这个8099个字节的结论只是针对只有一个列的表来说的，如果表中有多个列，那结论就不一致了，所以重点就是：你不用关注这个临界点是什么，只要知道如果我们一条记录的某个列中存储的数据占用的字节数非常多时，该列就可能成为溢出列。

• Dynamic和Compressed行格式类似于COMPACT行格式，在处理行溢出数据时有点儿分歧，它们不会在记录的真实数据处存储字段真实数据的前768个字节，而是把所有的字节都存储到其他页面中，只在记录的真实数据处存储其他页面的地址。

• 在列的值允许为NULL的情况下，gbk字符集下M的最大取值就是32766，utf8字符集下M的最大取值就是21844，这都是在表中只有一个字段的情况下说的，一定要记住一个行中的所有列（不包括隐藏列和记录头信息）占用的字节长度加起来不能超过65535个字节。

• 变长字符集的CHAR(M)类型的列要求至少占用M个字节，而VARCHAR(M)却没有这个要求。比方说对于使用utf8字符集的CHAR(10)的列来说，该列存储的数据字节长度的范围是10～30个字节。即使我们向该列中存储一个空字符串也会占用10个字节，这是怕将来更新该列的值的字节长度大于原有值的字节长度而小于10个字节时，可以在该记录处直接更新，而不是在存储空间中重新分配一个新的记录空间，导致原有的记录空间成为所谓的碎片。

• 聚簇索引（Clustered Index）：

• 二级索引（Secondary Index）：

如果我们想根据c2列的值查找到完整的用户记录的话，仍然需要到聚簇索引中再查一遍，这个过程被称为回表。

• 联合索引（复合索引）：

可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序：1、每条目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序；2、B+树叶子节点处的用户记录由c2、c3和主键c1列组成。联合索引，本质上也是一个二级索引。

• 根页面永不动窝：一个B+树索引的根节点自诞生之日起，便不会再移动。这样只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用到这个索引的时候，都会从那个固定的地方取出根节点的页号，从而来访问这个索引。
• 内节点中目录项记录的唯一性：B+树索引的内节点中目录项记录的内容是索引列 + 页号的搭配，但是对于二级索引来说，会出现重复值的情况。为了让新插入记录能找到自己在那个页里，我们需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的：索引列的值、主键值、页号。也就是我们把主键值也添加到二级索引内节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的。
• 一个页面最少存储2条记录：B+树本质上就是一个大的多层级目录，每经过一个目录时都会过滤掉许多无效的子目录。如果一个大的目录中只存放一个子目录，目录层级非常非常多，而且最后的那个存放真实数据的目录中只能存放一条记录，这样就会造成极大的性能损耗，所以，InnoDB的一个数据页至少可以存放两条记录。

简单总结一下上面的知识点：

• 每个索引都对应一棵B+树，B+树分为好多层，最下边一层是叶子节点，其余的是内节点。所有用户记录都存储在B+树的叶子节点，所有目录项记录都存储在内节点；

• InnoDB存储引擎会自动为主键（如果没有它会自动帮我们添加）建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录；
  

• 我们可以为自己感兴趣的列建立二级索引，二级索引的叶子节点包含的用户记录由索引列 + 主键组成，所以如果想通过二级索引来查找完整的用户记录的话，需要通过回表操作，也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录；
  

• B+树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，而且每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引的话，则页面和记录先按照联合索引前边的列排序，如果该列值相同，再按照联合索引后边的列排序；
  

• 通过索引查找记录是从B+树的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了Page Directory（页目录），所以在这些页面中的查找非常快。

因为B+树的知识点是重中之重，在有了上面数据结构和B+树索引相关的知识的前提下，我们再来进行模拟面试的一问一答，再次加深对B+树索引的理解和理解InnoDB为什么使用B+树来存储索引：

Q-1：MySQL的InnoDB存储索引用的什么数据结构？

A-1：B+树。

Q-2：B+树的查询时间大概多少？

A-2：和树的高度有关，大概是log(n)。

Q-3：Hash表存储索引，查询时间是多少？

A-3：Hash的话，平均时间O(1)。

Q-4：既然Hash比B+树更快，为什么MySQL数据库InnoDB存储引擎使用B+树来存索引呢？

如果在内存中，红黑树比B树效率更高，但是涉及到磁盘操作，B树就更优了。

B+树：B+树是在B树的基础上进行改造，它的数据都在叶子节点，同时叶子节点之间还加了指针形成链表。为什么会这样设计？是因为，MySQL数据库中SELECT数据，不一定只查询1条数据，很多时候会查询多条，如果是多条的话，B树需要做局部的中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子节点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。

A-4：和业务场景有关。如果只查询一个数据，确实是Hash更快，但是数据库中经常会查询多条，这时候由于 B+ 树索引有序，并且又有链表相连，它的查询效率比 Hash 就快很多了。而且数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+ 树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。

end