文件系统是数据库相当重要的一部分，因此文件系统的设计也是非常关键的一步。
磁盘如此浩大，如何才能找到注定的那个地址呢？下面记录了我对文件系统认知的深入过程。
内存
考虑到内存大小限制，无法一次性将磁盘全部信息载入内存，故内存只保留根节点，需要信息时再根据索引定位寻找
索引主要是B+树。
结构概述
页只需要通过双向链表相关联即可，不要求在物理结构上相连。
每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边的记录生成一个页目录。
通过主键查找某条记录时可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可。
外存
前面了解到SQL语句对 mkDB 文件的影响，在创建数据库的时候程序会相应地创建文件，每一个数据库就是一个文件夹，每一张表就是一个文件。可能有点人会想，为什么要创建这么多文件，能不能全部塞在同一个文件下？先回答是可以的，不管单文件还是多文件其实都不影响，只要能管理好就行，真正的难点是怎么存储文件。
这里我认为多文件方便逻辑梳理，所以我采用的是多文件，也就是一张表一个文件，数据库在运行时，每添加一张表就新建一个“表名.db”的文件用以存储用户数据和“表名.fra”的文件用以存储格式。
页
1个文件就是1张表，1张表至多有255页。数据会被划分至若干个页，页默认大小为 4KB，达到默认大小后就开辟新页，直到页数达到上限255。到达上限后程序拒绝添加数据，因为这程序不挨造。
1页就是4096字节。页下面是行，页管理器会管理每一行的数据。页作为磁盘和内存之间交互的基本单位，不论读一行，还是读多行，都会加载这些行所在的页，否则一次读取（一次 IO 操作）只能处理一行数据，效率非常低。因此，可以认为页（Page）是管理存储空间的基本单位。
内部结构
按类型对页划分，页可以分为：
数据页
索引页
数据页
最大空间限制 4KB 的数据页由七个部分组成：
文件头（File Header）
页头（Page Header）
最大最小记录（Infimum + Supremum）
用户记录（User Records）
空闲空间（Free Space）
页目录（Page Directory）
文件尾（File Tailer）
七 个部分的作用如下：
名称 占用大小 说明
File Header 15 字节 文件头，描述页的信息
Page Header 56 字节 页头，页的状态信息
Infimum + Supremum 13 字节 最大和最小记录，两个虚拟的行记录
User Records 不确定 用户记录，存储的行记录内容
Free Space 不确定 空闲记录，页中还没有被使用的空间
Page Directory 不确定 加快寻找
File Tailer 8 字节 文件尾，校验页是否完整
七个部分又可以分为三类：
第一类：File Header 和 File Tailer
第二类：User Records、Infimum + Supremum 和 Free Space
第三类：Page Directory 和 Page Header
页的主要作用是存储记录，所以 User Records占了页结构的主要空间。
File Header
File Header即文件头部，描述各种页的通用信息（比如页的编号、其上一页、下一页是谁等）。
大小：15 字节。
构成名称 占用空间大小 描述
FIL_PAGE_SPACE_OR_CHKSUM 4 字节 页的校验和（checksum 值）
FIL_PAGE_OFFSET 1 字节 页号
FIL_PAGE_PREV 1 字节 上一个页的页号
FIL_PAGE_NEXT 1 字节 下一个页的页号
FIL_PAGE_LSN 8 字节 页面被最后修改时对应的日志序列位置（Log Sequence Number）
每一个页都有一个单独的页号，就像身份证号码一样，通过页号可以定位到唯一页。
下面介绍构成部分的详细内容：
FIL_PAGE_PREV（4字节）和FIL_PAGE_NEXT（4字节）
mkDB 是以页为单位存放数据的，如果数据分散到多个不连续的页中进行存储，则需要把这些页关联起来，FIL_PAGE_PREV 和 FIL_PAGE_NEXT 分别代表本页的上一个和下一个页的页号。这样可以在内存中建立一个数组把众多页都保存起来，保证这些页之间达到连续。
FIL_PAGE_SPACE_OR_CHKSUM（4字节），又称 校验和（checksum）。
把一个很长的字节串通过算法来得到较短的值来代表字节串，短值就被称为校验和。
当一个页在内存中被修改后，在同步之前会把它的校验和算出来，由于 File Header 在页的开头，所以 File Header 的校验和会先被同步到磁盘。完全写完时，File Trailer 的校验和会被写到页的尾部。如果完全同步成功，则页的首、尾部校验和是一致的；如果首位校验和不一样，说明同步失败，这里的校验方式采用了标准库的 Hash 算法。
FIL_PAGE_OFFSET | FIL_PAGE_PREV | FIL_PAGE_NEXT （各1字节）
表示当前页数，前一页数，后一页数
Page Header
Page Header，即页面头部。
为了得到数据页中记录的状态信息，比如已经存储了多少条记录、第一条记录的地址是什么、页目录中存储了多少个槽等等，特意在页中定义了名为 Page Header 的部分，Page Header 固定占用 56 个字节，专门存储各种状态信息。
名称 大小（单位 字节） 描述
PAGE_N_DIR_DATA 2 当前页拥有的数据个数
PAGE_HEAP_TOP 4 还未使用的空间最小地址，该地址之后就是 Free Space
PAGE_LAST_INSERT 4 最后插入记录的位置
PAGE_N_RECS 4 当前页中记录的数量（不包括最大、最小、被删除的记录）
Infimum + Supremum
Infimum，即最小记录；Supremum，即最大记录。
记录也可以比大小。对于一条完整的记录来说，比较记录的大小就是比较主键的大小。比如插入的 4 条记录的主键值分别是 1、2、3、4，这意味着这 4 条记录是从小到大依次递增。
mkDB 规定的最小记录与最大记录的构造十分简单，都由 4 字节表示的最大主键值和 4 字节大小表示的最大主键值所在行数这两部分组成，总共是(4+4)*2=16字节。
这两条记录由数据库更改，因此它们并不存放在页的 User Records 中，而是单独放在表中。
User Records
User Records，即用户记录。
用户记录中的记录按照 指定的行格式 一条一条地摆放
指定的行格式包含了记录头信息、数据信息。
记录头信息
在记录头信息中，包含了多个属性：
名称 大小（单位 bit） 描述
预留位1 1 不够一个字节，凑数的
预留位2 1 不够一个字节，凑数的
delete_mask 1 标记当前记录是否被删除
min_rec_mask 1 B+Tree 的每层非叶子节点中的最小记录都会添加该标记
n_owned 4 当前记录拥有的记录数
d_owned 8 当前表的成员变量个数
RECORD_LENGTH 16 用户数据的长度
heap_no 32 所在行的行数
next_record 32 下一条记录的偏移量
读入时会一次性全部读入，然后按上述设计去处理，因此，必须熟悉这些属性。下面介绍 记录头信息 中各个属性的作用。
记录头信息：delete_mask
标记当前记录是否被删除，占用 1 个二进制位：
0：记录未被删除
1：记录已被删除
当某条记录被删除后，不会立即从磁盘上移除。如果立即移除，之后的记录需要在磁盘上重新排列，造成性能消耗。所有被删掉的记录会组成一个所谓的垃圾链表，这个链表中的记录占用的空间被称为 可重用空间，当有新记录插入时，可以覆盖这些被删除的记录。
记录头信息：min_rec_mask
B+Tree 的每层 非叶子节点 中的最小记录都会添加该标记，值为1。
前面插入的四条记录的 min_rec_mask 值都是0，意味它们都不是 B+Tree 的非叶子节点中的最小记录（因为它们根本就不是非叶子节点，都是叶子节点）。
记录头信息：record_type
当前记录的类型，共有 4 种类型：
类型值 对应的记录类型
0 普通记录
1 B+Tree 非叶节点记录
2 最小记录
3 最大记录
前面插入的四条记录都是普通记录，因此它们的 record_type 都是 0。
记录头信息：heap_no
当前记录在本页中的位置。
前面插入的四条记录在本页中的位置分别是 2、3、4、5，怎么没有 0 或 1 的记录呢？
mkDB 会自动为每个页添加两条记录，这两条记录称为 伪记录。这两个伪记录一个代表 最小记录，一个代表 最大记录。最小记录和最大记录的 heap_no 值分别是 0 和 1，也就是说它们俩在页中的位置最靠前。
记录头信息：n_owned
页目录中每个组中最后一条记录的头信息中会存储该组一共有多少条记录，存储所用的字段就是 n_owned。
记录头信息：next_record
next_record 在记录头信息中十分重要，它表示从当前记录的真实数据到 下一条 记录的真实数据的 地址偏移量。
比如第一条记录的 next_record 值为 32，意味着从第一条记录的真实数据的地址处向后找 32 个字节就是 下一条 记录的真实数据。
这里的 下一条 记录并不是按照插入顺序插入的下一条记录，而是按照主键值由小到大排列的下一条记录，同时规定 Infimum 记录（即最小记录）的下一条记录是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录是 Supremum 记录（即最大记录）。
记录头信息：delete_mask
如果从表中删除一条记录，被删除记录并没有立即从存储空间中移除，而是把该记录的 delete_mask 值设置为 1；
被删除记录的 next_record 值为 0，表示该记录没有下一条记录；
被删除记录的前一条记录的 next_record 指向了被删除记录的下一条记录；
最大记录的 n_owned 值从 5 变成了 4。
不论怎么对页中的记录做增删改操作，mkDB 始终会维护一条记录的单链表，链表中的各个节点按照主键值由小到大的顺序进行连接。
如果又添加一条 c1 为 2 的记录，则直接复用被删除记录的存储空间。
如果数据页中存在多条被删除掉的记录，这些记录的 next_record 会链接起来，并组成一个垃圾链表，以便后续重用这些存储空间。
数据信息
数据类型 大小 位表示
int 4个字节 00
float 4个字节 01
date 8个字节 10
varchar 至多31个字符 11
表示四种元素需要2bit。
为了实现动态确定用户数据的长度。因为磁盘上的内容对程序而言只是一个字符串，程序需要解析字符串，所以程序必须先确定多少字节表示第一个参数，多少字节表示第二个参数。除此以外，数据信息还需要表示该参数是否为NULL，是否为主键，如果是字符串，还要表示长度，为了降低实现难度，故设一个参数需要一个字节的信息表示，如果是字符串子需要两个字节表示，格式如下
AA B CCCCC
AA表示数据类型，B判断是否主键，CCCCC表示字符串长度，如果不是字符串可忽略。
根据存储方式可得，字符串最长支持2^5-1=31个字符，对于玩具数据库够了。
存储记录会按照指定的行格式存储到 User Records 部分。
但了解一下 innodb 的存储策略不免是个好事。 innodb 先存储几个数字，然后是NULL值列表，再是记录头信息，也就是遇到字符串，从记录头信息里往前推找长度，所以字符串长度在 innodb 里是反过来存储的。比方说有两个字符串，第一个长度15，第二个长度16，那么存储的顺序是 16，15。
Free Space
Free Space，即空闲空间。
在最开始生成页的时候，并没有 User Records。所有空余空间都是 Free Space。每插入一条记录，都会从 Free Space中申请一个记录大小的空间划分到 User Records。当 Free Space 的空间都被 User Records 替代之后，就意味着这个页使用完了，此时再插入新记录，就需要申请新的页。
Page Directory
页目录。
File Tailer
File Trailer，前 4 个字节代表页的校验和，与 File Header 中的校验和相对应。后 4 个字节代表页面被最后修改时对应的日志序列位置（LSN），这部分也是为了校验页的完整性，如果首、尾部的 LSN 值校验失败，说明在同步过程出现了问题。
日志页
日志页单独开辟一个文件，用以保存执行过的指令。保存指令的目的是恢复数据(但我不想再花很长时间写日志恢复)。
实现方式是把输入的指令都保存到日志里。前面介绍过数据页保存有最后一次执行更改时日志所在位置，数据页每次更改都会修改这个值，恢复数据时只需要执行日志从数据页保存的位置那一行开始到最后一行的指令即可。
日志页大小与数据页默认大小相同，均为4Kb。日志页超过4Kb则删除先前的日志。
日志页保存格式如下：
[order] 调用函数+参数+换行， order为序号
举例： [152] Table::create {{"INT","id","KEY"},{"VARCHAR","name"}} 换行
如果说，LSN记录这条日志没有同步，那么在启动数据库的时候会先执行这条日志包含的命令。这样就实现了简单的数据恢复。
从数据页的角度看 B+Tree 的查询
一棵 B+Tree 按照节点类型可以分成两部分：
叶子节点，B+Tree 最底层的节点，节点的高度为 0，存储行记录；
非叶子节点，节点高度大于 0，存储索引键和页面指针，并不存储行记录本身
B+Tree 如何进行记录检索的？
先从 B+Tree 的根开始，逐层检索，直到找到叶子节点，也就是找到对应的数据页为止，然后将数据页加载到内存中，通过链表遍历的方式查找到记录。
普通索引和唯一索引在查询效率上有什么不同？
唯一索引是在普通索引的基础上增加了约束性，即关键字唯一，找到了关键字就会停止检索。
使用普通索引时，用户记录中可能会存在多个关键字相同的情况，根据页结构，在读取一条记录时，不会单独从磁盘中读一条记录出去，而是将这个记录所在的页都加载到内存中进行读取。mkDB 存储引擎的页大小为 4KB，一个页中可能存储着许多记录，因此在使用普通索引进行查找时，也只是在内存中多几次“判断下一条记录”的操作，对 CPU 来说，这些操作消耗的时间是忽略不计的。
所以对一个索引字段进行检索，无论采用普通索引还是唯一索引，在检索效率上几乎没有区别。
