Database Storage

数据库如何表示磁盘文件？

page

MySQL 中的数据文件，是以 page 为单位保存在磁盘当中的。这里的 page 和操作系统的 page 类似，一般磁盘系统和 OS page 都是 4KB，而数据库取决于具体实现，SQLite、ORACLE 实现为 4KB，SQL Serve 实现为 8KB，Mysql 实现为 16KB。

一个 page 可以包含：元数据、索引、日志，或者具体的表数据（元组），但一般来讲，为了方便组织一个 page 中只会包含一个类型的数据。

在一些 DBMS 中，可能还会要求 page 是“self-contained”（自包含）的，即每个页应该包含所有必要的信息，以便在不依赖其他页或外部资源的情况下，能够独立地进行处理和解析。这要求每个 page 都要包含解析表数据的信息，如表头。

文件存储

数据库以 page 为基本单位来组织磁盘文件，不同数据库以不同的数据结构来组织：

Heap File Organization。
Tree File Organization
Sequential / Sorted File Organization
Hashing File Organization

Heap file（堆文件）是一种简单且常见的数据库文件组织方式，用于存储无特定顺序的记录。它是数据库中最基本的数据存储结构之一，通常用于存放表的数据。

Heap file 将文件划分为若干个 page，并用一定的数据结构来存储，如链表、字典。通常字典是更高效的组织方式，DBMS 会维护一个字典页，来记录数据页的存储位置，字典页也会记录一些元数据，如：每页的空闲位置的位图 slots（后面介绍），空闲页的列表。

页布局

每个 page 由两个部分组成，表头和数据：

通常表头会包含：Page Size、Checksum、DBMS Version 等信息，如果要求是 self-contained 的还会由额外的信息。

page 的数据部分有很多组织方法：

面向 tuple

在此方法中，会在 header 中维护一个 slot array，标识元组起始位置的偏移量。MySQL 默认并没有采用此种组织方式。

当我们要定位一个 tuple 时，只要拿到对应的 file_id、page_id 和 slot_offset 就可以很快的定位，他们共同组成一个元组的 ID，SQLite 会为它创建一个隐藏的独立的列，它占据 8Byte 的大小，当然不同数据库实现也不同，PostgreSQL 是 6Byte、SQL Server 是 8Byte。

我们可以通过一些方式来获取到这个 ID，但是我们不应该在应用中使用它，因为这个 ID 标识的是元组的物理位置，DBMS 可能会对 page 进行重排，对应的物理位置也会改变。这个重排的过程可能会发生在一次插入后（SQL Server），或一次垃圾回收后（SQLite vacuum），这取决于数据库的实现。

这样的组织方法有一些缺点：

page 的空间可能不会完全的利用，在插入删除后可能会留下一些内存碎片（所以DBMS 都会在不定时的对 page 进行重拍，但这又会降低效率），在 page header 和 page data 之间可能会存在一些小的内存空间，放不下任何 tuple。
这样还会造成一些无用的磁盘 IO，当我们访问一个元组是，我们就不得不读取一整个 page，page 中其他的元组可能我们并不需要，写的时候也需要将整个 page 写回磁盘，这被称作读写放大。
随机 IO 效率低，如果我们要修改 20 个元组，而这 20 个元组又分布在不同的 20 个 page 中，这会导致大量的磁盘 IO，效率很低。
一些不允许原地更新，只能创建新 page 的场景，该方式就不能胜任了。

日志结构

在日志结构中，我们在 page 中不在记录具体的 tuple，而是维护这些元组的变更日志。

对元组的修改会按照时间顺序一次放入 page 中。每条日志都记录有元组的唯一标识。对于添加和删除，这样的操作很快，只要将日志加到文件末尾即可。每当一个 page 被写满了，就写入磁盘，在该架构中，被写入磁盘的日志都是不可修改的，这意味着我们不能回滚到某个版本后，对该版本进行修改，只能创建一份新的版本。

查询怎么办？遍历记录找到对应元组的最新修改？这样效率太低了。这里的做法是维护每条元组最新修改的索引，索引中记录该修改的位置。