数据库系统存储目标认知
数据库系统通常都是运行在文件系统之上，数据以DB特定的格式存储在文件中以供数据库系统检索、修改，那这些文件通常是如何组织的呢？
数据存储在存储设备上，数据库系统为了能高效管理数据则有两个方向的考虑：
- 数据库应用需求。针对不同的应用场景，可以特定的优化数据库。例如OLAP请求通常检索数据的少数列多数行，因此应该使用使用列式存储；OLTP类请求通常对获取数据tuple的完整或者大多数属性，因此应该采用行式存储。
- 在数据库系统与存储设备之间有着文件系统以及操作系统两层来抽象计算机系统对硬件设备的管理。数据库要达到高效管理数据的目标就要考虑存储设备的读写特性，进而采用不同的数据结构以及复杂的机制（例如缓buffer）来进行数据检索。此处衍生的问题是，优化的数据结构，优化的相应机制，系统的可靠性问题应该分别由数据库系统、文件系统、操作系统承担多少？
两种主要的存储设备访问机制：
- 磁盘：磁盘的数据读写是以block为单位的，且存储架构越下层，其成本越低，访问延迟越高。因此数据库系统如果是基于磁盘，则优化目标应该是尽量减少磁头的转动，也就是尽量保证顺序读写。
- 闪存：典型如SSD。特点是有并行性，随机访问性能比磁盘好，缺点是写的代价高（会有page erase）。
- 内存：不考虑与磁盘比较的绝对性能差异下，内存的特点是随机访问性能更强。因此内存型数据库可以考虑才有特有的优化数据结构。
数据如何存储
如图2，展示了计算机系统中，各层在数据库数据存储功能上的主要职责。
数据库模型中，将数据库分为三个Level：View Level，Logical Level与Physical Level。
- Storage Devices：数据以bit的形式在物理设备上进行存储
- Operating System：提供通用各种物理设备抽象
- File System：负责将存储设备上杂乱的数据存储抽象为一个统一的文件，不负责管理文件中数据。
- Database System：负责将文件中的数据映射为其数据模型，例如关系型数据库中的relation；同时数据库还会根据用户权限、设置等，将所有的数据模型对特定的用户暴露部分数据，亦即View Level。
因此，对于数据库系统，其需要按照特定的格式在文件中存储数据record，进一步设计数据结构检索其中的数据。简单的数据库系统可以直接以文件问单位来进行数据管理，从文件系统中获取到一个文件的内容，并对其进行解析获取数据。然而，如果文件过小，则将创建过多的小文件；如果文件过大，数据库系统将无法控制文件系统对磁盘的访问，导致性能较差。因为数据库的控制粒度是文件，文件内数据访问对其是透明的。
文件通常是以block为单位进行数据存储，因此数据库系统通常以block为单位来进行数据管理。block size的大小根据数据库系统的不同有不同的设置。
基于磁盘的数据库系统设计目标
目标：
- 数据库系统能操作大于内存限制的数据量
- 减少磁盘访问以优化数据库性能
实现目标1有两种途径：
- 直接使用操作系统mmap函数，将磁盘数据直接映射到内存中，由操作系统负责page的置出和置入
- 使用buffer pool，由数据库系统完全控制数据的在内存和磁盘见间的移动
方式1由于由os管理，没有数据库系统的上下文，其可能的频繁page fault置入和置出导致数据库性能degradation.
方式2由数据库系统自己完成page置换，根据上下文及特定算法，可以做到：
- 以正确的顺序flush page
- 大概率的prefetch
- 更优的置换策略
- 线程进程调度
关系型数据库文件格式
数据库系统将文件视为page的集合，根据其自己的策略管理对page的读写，进而优化page的空间利用率和局部性。page是一个固定大小的数据块，数据内容可以是tuple、metadata、索引、日志······每个page根据存储内容不同可以分为不同的page类型，并且大部署数据库系统为每个page跟配了一个唯一的id，并使用某种映射将page id映射到具体的物理存储位置。
一些数据库系统要求page应该是self-contained
文件中page的组织方式：
- heap file organization
- 序列化文件组织
- hash文件组织
heap file organization
在heap file中，page是无序存储的，page中的record也是无序存储的。在heap file组织中，需要一定的metadata来指示哪些page是空闲的，哪些是存储了数据的（类似磁盘管理）。此种metadata实现由两种方案：
-
linked list：文件最开始的header指示了两种类型page list的起始，每个page维护两个双向指针
图3: heap file organization with linked list -
page directory：用一个bitmap来追踪当前文件中的每个page是free/occupied，此方案最大的问题是需要保证内存中该page和磁盘上该page的同步。
图4: heap file organization with page directory
sequential file organization
序列化文件组织并不是以page为单位来进行record的存储，而是直接以record为单位在文件中存储record。序列化文件组织和cluster index比较相关，在此文件组织中，record很具某一个search key的大小顺序在文件中进行存储。record的存储并不是严格的按序存储，而是在每一条record中会有metadata指示其下一顺序数据的位置，如图5所示。
当然，此组织的文件的插入和删除代价较高。因此如图5，如果在插入时，如果一个page中有空闲的空间，直接插入该位置，如果该page没有空间，则将新record插入overflow page中。
page格式
如图6，header通常包含的metadata有：
- page size
- checksum
- DBMS version
- transaction visibility
- compression information
note: Oracle要求page是self-contained
page内存储records有两种类型：
- tuple-oriented
- log structure
tuple-oriented--slotted pages
如图7，在page内使用十一个array保存每条record的位置和size，array从低offset向高offset增加；record存储从过年高offset向低offset增加。
log-structured
在page中存储操作日志，根据日志重新构建数据。此结构的兴起源于当前某些系统是append-only的，适合此种文件格式。
文件内record管理
以关系型数据库为例，关系型数据库中以record为单位进行数据存储。关系型数据库进行record存储管理时通常有两个假设：
- 每条record的大小小于等于block size
- 一条record不会跨block存储
record的格式通常为header(metadata)+data，根据data部分的存储格式不同，可以划分出两种谁方案：
- 定长record
- 变长record
定长record
定长record中每条record的size大小都是固定的，因此可以使用固定的size*num得到一条record在page中的偏移量。删除时可以使用标记删除的方式来标记一条record无效。如图8，通过linked list的方式形成一个free list来管理page中空闲的存储空间。
变长record
变长record中，每条record的长度是不固定的，因此需要解决两个问题：
- 如何准确得分离每一个attribute
- 如何在page中找到一条record（结合slotted page）
问题2上一节已经描述，针对问题1，解决档案如图9所示。在变长record格式中，不区分定长attribute和变长attribute，统统视为变长attribute。在record的header中有定长的信息段存储了每个属性的(offset, length)，通过这个组合就可以找到每个属性的值。
同时，在这里还显示了null map的作用。使用一个bitmap来即可表示出当前tuple中哪些属性是null的。（也是可以用于定长record的格式中的）
注意：在关系代数中，tuple应该是attrubute的无序集合，也就是说属性应该不是排序的，但是在工程实现中，通常存储时是按照create table时指定的先后顺序存储的。
参考：
CMU 15-445/645 03
《Database System Concepts 7th editon》
