开发者学堂课程【从0到1数据库内核实战教程：MiniOB 存储实现原理】学习笔记，与课程紧密连接，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1083/detail/16099
MiniOB 存储实现原理
首先回顾一下 MiniOB 的框架：
首先看到右边的 sower 一些基础组件的组成，Parser（解析器） 、Resolver 、优化器以及执行器，本节课重点内容为执行器访问的存储引擎，存储引擎控制整个数据、记录在磁盘文件存储的方式以及与数控模块进行交互的方法。存储引擎里面有三个比较关键的模块，分别为Buffer Pool 、B+-Tree 、Record Manager，其中Buffer Pool 是文件与内存交互的关键组件，Record Manager 组织记录数据在文件里的存放方式，B+-Tree 是有关索引的内容。
首先学习 MiniOB 里面文件存放的方式，PPT 内容比较简单反映出MiniOB 的内容也是比较简单的。文件管理一些基础对象，基础对象里面含有数据结构、表、索引。观察右图，数据库在此处为一个文件夹，是一个目录，在MiniOB 创建时会默认创建一个dbsys 的目录，所有的操作都默认在此处进行执行。一个数据库里面会有多张表，此示例有三张表，分析以下三张表的内容：第一个为源数据text 1 .table ，源数据表明数据类型、数据索引、字段类别及类型以及每个类型的长度等。接下来为数据文件，是执行记录存放的文件。然后为索引文件，索引实际上有许多个，此示例只显示一个，索引文件为表明+索引名称（创建索引时所取名称，不一定为i_开头）+后缀名，从后缀名中可以看出文件类型。实际上每张表都有多个索引，此示例比较简单只显示一个索引，此为一个示意图。
接下来是 MiniOB 十分重要的组件Buffer Pool ，Buffer Pool 是在传统数据库里面十分基础的组件，观察此示意图：
右边为一个磁盘，左边为一个内存，数据库数据存放在磁盘里面，为一个磁盘数据库，不能直接从磁盘读取数据，从磁盘中加载数据读取到内存，在CPU 中执行运算，再展示给前端用户。写入也是一致的，首先先写入内存，然后写入磁盘，此做法为一种十分常见的缓存机制。然后讲解Buffer Pool 在MiniOB 的组织方式：
观察示意图可知，左边为内存，内存是比较少的，内存里面分成四个Frame ，分别对应右边的多个文件，每个文件按照页进行划分，每个页的大小都是固定的，例如4K，8K或者16K，每个页读取时都是以页为单位与每个Frame 相对应。Buffer Pool 在MiniOB 的组织是Buffer Pool 的一个对象对应一个物理文件，然后所有的Buffer Pool 使用的内存管理组件Free Manager 是公共的。在内存读取文件时时与内存的交互方式，例如根据以上示意图的状态，Frame1 关联了一个磁盘文件的页面，Frame2 关联了另一个页面，Frame3 相当于一个空闲页面，没有关联任何磁盘文件，Frame4 也关联了一个页面。若此时需要读取Page 3 页面，首先需要从内存里面找一个空闲的Frame，即为Frame3，然后把Frame3 与之进行关联，再将Frame3 的数据读取到Frame里面，所有内存的Frame都已经读取页面。若此时再读取一个页面Page 5，此时已经找不到内存，有两种方式，若内存里面还有空闲，则可以再申请一个Frame，与之关联起来。第二种情况为再次对Page4进行读取，内存已经满了，此时需要从已有的Frame 里面进行淘汰，例如此示例将Frame1淘汰，然后Frame1与Page4关联起来，此时Page4里面的内存读取至Frame1。淘汰是需要淘汰条件与算法的，此知识点先做简单了解，细节先不做深入讨论。
一个物理文件里面都是有组织结构的，组织结构也是比较简单的，接下来对此进行讲解：
文件第一页称为页头或者文件头，文件头是一个特殊的页面，页面上会有一个页号0，还有一个Page Header为当前的文件的页面总数。接下来对页面进行分配，当前状态下分配了13个页面，Buffer way 表示当前对应页面的分配状态，1代表已经分配，0代表空闲页面。可以看出当前的组织结构是存在缺陷的，整个页头的大小是受页面大小限制的，即能够申请的页面格数是受页面大小控制的。同学们若有兴趣可以扩展实现一个无限大或者可以实现更大页面的一个算法。然后介绍普通页面，普通页面除了页头，对Buffer Pool 来说，第一个字段是使用四字节的Pool 进行表示的，即为Page number ，页头也为一个Page number 。接下来为数据，使用Buffer Pool 一些模块进行控制，例如Record Manager与B+-Tree 会自主定义结构，但第一个字段都为Page number ，业务使用模块都是Page data 作为组织。
接下来学习MiniOB 的记录管理，记录可以为一行数据，记录管理模块主要负责记录磁盘存放的方式和格式以及对数据进行增删改查的方法。MiniOB 的Record Manager有一定的前提为记录通常是比较短的，加上一个页面头之后并不会超过一个页面的大小；另一个前提为记录都是固定长度的，此简化可以让学习MiniOB 显得更加简单一些。例如要实现一个变长的Record ，需要把整个设计推翻，然后实现变长。Record Manager 的实现方式，即Record Manager 在文件中进行组织，Record Manager 是在Buffer Pool 的基础上实现的，Page 0是在Buffer Pool 里面使用的源数据，而Record Manager 是利用一些其他的页面，每一个页面有一个头信息，然后为bite map ，表示最近的记录是否为有效数据，若为1则代表数据有效。
接下来学习代码的内容：
Free Manager 为管理内存，MiniOB 里面只有一个Free Manager 对象，是一个封装的对象，可以简单的认为是一个链表，里面存放了一系列的内存页帧，页帧可以对应文件以及页号，即某一个页帧对应一个文件。以上为Buffer Pool ，Buffer Pool 里面都有对应特定文件。若要获取一个页面，已有页面直接找出即可，若没有页面则需要申请一个页面与之进行关联，以此进行页面的读取。若需要分配一个新的页面，例如Frame3 上面已经有六个页面，此时文件增多，故需要再申请一个新的页面，则需要用到以下函数：
若删除的文件较多，page 3已经被清空，有效数据就可以直接删除，对此函数进行操作，例如需要淘汰一个页帧或者页面（此时没有内存），需要在淘汰之前将写入的数据调至磁盘中，则需要使用以下函数：
在读取Page 4的内容时，已经关联了Frame 1，记录下来之后增加一个引用技术，一个页面可以有多个地方进行调用读取的，都是关联的内存页帧1，则内存就会增加两次至三次。若是在其他地方引用之后再读取页面，不能对此进行释放，否则会导致其他数据丢失。若要淘汰页面，则需要其他页面的引用技术为零时才能被淘汰。同时会进行记录引用技术对应的文件即页数，修改或者淘汰数据时需要将数据写入磁盘中。以上内容为Buffer Pool 的代码介绍。接下来介绍Record Manager 的代码：
页头的每一页都有当前页面记录的个数及行数、能容纳的最大行数、每条记录的实际大小、每条记录占用的实际空间大小，值得注意的是，一条记录数据大概是27个字节，但是存放时可能需要执行八字节对齐，此处为字节对齐后的大小，最后为第一条记录的偏移量。
首先浏览一下关键数据结构：
观察上图可知，Record File Handler 为管理整个文件的记录，即为一个表格。每个文件都是分页的，每一页及文件的存放方式、增删改查，还有一些辅助的类，例如扫描整个文件记录的类、扫描某个页的类等。
