先从几个问题开始
MySQL存储结构简介
MySQL InnoDB存储引擎逻辑存储结构
1、表空间(table space)
表空间(Tablespace)是一个逻辑容器,表空间存储的对象是段,在一个表空间中可以有一个或多个段,但是一个段只能属于一个表空间。数据库由一个或多个表空间组成,表空间从管理上可以划分为系统表空间、用户表空间、撤销表空间、临时表空间等。
在 InnoDB 中存在两种表空间的类型:共享表空间和独立表空间。如果是共享表空间就意味着多张表共用一个表空间。如果是独立表空间,就意味着每张表有一个独立的表空间,也就是数据和索引信息都会保存在自己的表空间中。独立的表空间可以在不同的数据库之间进行迁移。
InnoDB把数据保存在表空间内,表空间可以看作是InnoDB存储引擎逻辑结构的最高层。本质上是一个由一个或多个磁盘文件组成的虚拟文件系统。InnoDB用表空间并不只是存储表和索引,还保存了回滚段、双写缓冲区等。
2、段(segment)
范围查询,其实是对 B+ 树叶子节点中的记录进行顺序扫描,而 如果不区分叶子节点和非叶子节点,统统把节点代表的页面放到申请到的区中的话,进行范围扫描的效果就大打折扣了(这里解释一下:因为B+树从上到下查询,如果叶子和非叶子节点混在同一个区中,会让一个区中存储的页目录数据大大减少,造成多个区随机IO发生)。所以对 B+ 树的叶子节点和非叶子节点进行了区别对待,也就是说叶子节点有自己 独有的区 ,非叶子节点也有自己独有的区 。存放叶子节点的区的集合就算是一个段 ( segment ),存放非叶 子节点的区的集合也算是一个段 。也就是说一个索引会生成2个段,一个叶子节点段,一个非叶子节点段。
默认情况下一个使用 InnoDB 存储引擎的表只有一个聚簇索引,一个索引会生成2个段,而段是以区为单位申请存 储空间的,一个区默认占用1M存储空间,所以默认情况下一个只存了几条记录的小表也需要2M的存储空间。
3、区(extent)
在 InnoDB 存储引擎中,一个区会分配 64 个连续的页。因为 InnoDB 中的页大小默认是 16KB,所以一个区的大小是 64*16KB=1MB。在任何情况下每个区大小都为1MB,为了保证页的连续性,InnoDB存储引擎每次从磁盘一次申请4-5个区。默认情况下,InnoDB存储引擎的页大小为16KB,即一个区中有64个连续的页。
为什么要划分多个区呢?
本质上还是为了性能!
如果我们表中数据量很少的话,比如说你的表中只有几十条、几百条数据的话,的确用不到 区 的概念, 因为简单的几个页就能把对应的数据存储起来,但是你架不住表里的记录越来越多呀。
从理论上说,不引入区的概念只使用 页 的概念对存储引擎的运行并没啥影响,但是我 们来考虑一下下边这个场景:
我们每向表中插入一条记录,本质上就是向该表的聚簇索引以及所有二级索引代表的 B+ 树的节点中插入数据。而 B+ 树的每一层中的页都会形成一个双向链表,如果是以 页 为单位来分配存储空间的话,双向链表相 邻的两个页之间的物理位置可能离得非常远。我们介绍 B+ 树索引的适用场景的时候特别提到范围查询只需要定位到最左边的记录和最右边的记录,然后沿着双向链表一直扫描就可以了,而如果链表中相邻的两个页物理位置离得非常远,就是所谓的随机I/O 。再一次强调,磁盘的速度和内存的速度差了好几个数量级, 随机I/O是非常慢的,所以我们应该尽量让链表中相邻的页的物理位置也相邻,这样进行范围查询的时候才可以使用所谓的顺序I/O 。
所以才引入了区 ( extent )的概念,一个区就是在物理位置上连续的64个页。在表中数据量大的时候,为某个索引分配空间的时候就不再按照页为单位分配了,而是按照区为单位分配,甚至在表中的数据十分非常特别多的时候,可以一次性分配多个连续的区。虽然可能造成一点点空间的浪费(数据不足填充满整个区),但是从性能角度看,可以消除很多的随机 I/O ,功大于过嘛!
4、页(Page)
页是InnoDB存储引擎磁盘管理(数据读取)的最小单位,每个页默认16KB;
innoDB存储引擎中,常见的页类型有:
数据页(B-tree Node)
undo页(undo Log Page)
系统页 (System Page)
事物数据页 (Transaction System Page)
插入缓冲位图页(Insert Buffer Bitmap)
插入缓冲空闲列表页(Insert Buffer Free List)
未压缩的二进制大对象页(Uncompressed BLOB Page)
压缩的二进制大对象页 (compressed BLOB Page)
InnoDB页定义
真正处理数据的过程是发生在内存中的,所以需要把磁盘中的数据加载到内存中,如果是处理写入或修改请求的话,还 需要把内存中的内容刷新到磁盘上。而我们知道读写磁盘的速度非常慢,和内存读写差了几个数量级,所以当我们想从表中获取某些记录时, InnoDB 存储引擎需要一条一条的把记录从磁盘上读出来么?不,那样会慢死, InnoDB 采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为 16 KB。也就是在一般情况下,一次最少从磁盘中读取16KB的内容到内存中,一次最少把内存中的16KB内容刷新到磁盘中。
页的结构
从图中可以看出,一个 InnoDB 数据页的存储空间大致被划分成了 7 个部分,有的部分占用的字节数是确定的, 有的部分占用的字节数是不确定的。
各部分的作用:
记录在页中的存储
在页的7个组成部分中,我们自己存储的记录会按照我们指定的行格式存储到 User Records 部分。但是在一开 始生成页的时候,其实并没有 User Records 这个部分,每当我们插入一条记录,都会从 Free Space 部分,也就 是尚未使用的存储空间中申请一个记录大小的空间划分到 User Records 部分,当 Free Space 部分的空间全部被 User Records 部分替代掉之后,也就意味着这个页使用完了,如果还有新的记录插入的话,就需要去申请新的页了,这个过程的图示如下:
行记录格式(Compact类型)
行记录在User_Records中的存在形式
通过next_record属性,可以让页中的多条记录形成一个链表,链表是有序的, 按照主键顺序排序。
行记录的删除
删除第2条记录前后主要发生了这些变化:
第2条记录并没有从存储空间中移除,而是把该条记录的 delete_mask 值设置为 1 。
第2条记录的 next_record 值变为了0,意味着该记录没有下一条记录了。
第1条记录的 next_record 指向了第3条记录。
最大记录 的 n_owned 值从 5 变成了 4。
所以,不论我们怎么对页中的记录做增删改操作,InnoDB始终会维护一条记录的单链表,链表中的各个节点是按照主键值由小到大的顺序连接起来的。
另外,当插入的主键和被删除的主键相同时,删除的行记录存储空间是可以被复用的。
页目录
页目录就是page的目录,就像书的目录,作用是加快查找。
记录在页中按照主键值由小到大顺序串联成一个单链表,那如果我们想根据主键值查找页中的某条记录该咋办呢?比如说这样的查询语句:
SELECT * FROM test WHERE id = 100;
从 Infimum 记录(最小记录)开始,沿着链表一直往后找就可以。
但效率低了些...
更好的办法是:页目录
页目录的生成
它的生成过程是这样的:
将所有正常的记录(包括最大和最小记录,不包括标记为已删除的记录)划分为几个组。
每个组的最后一条记录(也就是组内最大的那条记录)的头信息中的 n_owned 属性表示该记录拥有多少条记录,也就是该组内共有几条记录。
将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近页的尾部的地方,这个地方就是所谓的 Page Directory ,也就是 页目录。页面目录中的这些地址偏移量被称为 槽 (英文名: Slot ),所以这个页面目录就是由 槽组成的。
举例
分组规则:
对于最小记录所在的分组只能有 1 条记录, 最大记录所在的分组拥有的记录条数只能在 18 条之间,剩下的分组中记录的条数范围只能在是 48 条之间。
每个槽中存储的是:当前分组中最大记录的地址偏移量,偏移量从page的0字节开始计算
查找步骤
通过二分法确定该记录所在的槽,并找到该槽中主键值最小的那条记录。
通过记录的 next_record 属性遍历该槽所在的组中的各个记录。
Page Header(页面头部)
专门针对数据页的。
File Header (文件头)
Page Header 是专门针对 数据页 记录的各种状态信息,比方说页里头有多少个记录了呀,有多少个 槽了呀。我们现在描述的 File Header 针对各种类型的页都通用,也就是说不同类型的页都会以 File Header 作 为第一个组成部分,占用固定的 38 个字节
FIL_PAGE_SPACE_OR_CHKSUM
这个代表当前页面的校验和(checksum)。啥是个校验和?就是对于一个很长很长的字节串来说,我们会 通过某种算法来计算一个比较短的值来代表这个很长的字节串,这个比较短的值就称为 校验和 。这样在比 较两个很长的字节串之前先比较这两个长字节串的校验和,如果校验和都不一样两个长字节串肯定是不同 的,所以省去了直接比较两个比较长的字节串的时间损耗。
FIL_PAGE_OFFSET
每一个 页 都有一个单独的页号,就跟你的身份证号码一样, InnoDB 通过页号来可以唯一定位一个 页 。
FIL_PAGE_PREV 和 FIL_PAGE_NEXT
InnoDB 可能不可以一次性为这么多数据分配一个非常大的存 储空间,如果分散到多个不连续的页中存储的话需要把这些页关联起来, FIL_PAGE_PREV 和 FIL_PAGE_NEXT 就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了, 而无需这些页在物理上真正连着。需要注意的是,并不是所有类型的页都有上一个和下一个页的属性,在数据页 (也就是类型为 FIL_PAGE_INDEX 的页)是有这两个属性的,所以所有的数据页其 实是一个双链表(很重要)
InnoDB的索引结构
MySQL中的索引有多种,在InnoDB中,默认情况下所有主键都会自动创建一个B+ 树索引,所以我们仅讨论B+ 树索引。
索引的结构示意图:
对我们的启发