数据是怎么在数据库中存储的(Self Learning Series)

一行数据是怎么存储在不同的数据库系统中的？我们以一个简单的用户表为例：

CREATE TABLE users (
    id INT PRIMARY KEY,
    name VARCHAR(255),
    email VARCHAR(255)
);
 
CREATE INDEX idx_name ON users(name);
 
INSERT INTO users (id, name, email) VALUES (1, 'Alice', '[email protected]');

我们都知道, 数据库想要存储数据在磁盘中, 一定要经过操作系统来进行操作, 也就是说, 一个面向磁盘的数据库系统, 本质就是在管理磁盘上的一堆文件(One or more files)

而数据库系统通常会用自己的格式在这些文件中存储数据, Pg 有自己的格式, MySQL 有自己的格式等等

当然这么多专有格式, 那肯定就有人忍不住想要统一一下了, 例如 Parquet, ORC, Arrow, 不免让人想到一个经典的笑话, 当你面对各种不同的实现和标准, 想要统一的时候, Opus! 现在又多了一种格式了

如果都是使用操作系统给的文件抽象, 那么意味着我们的数据库无法控制底层的文件系统, 如果 Linux 跑在 Ext4, 那 DBMS 就是通过 Ext4 文件系统处理文件

但在上个世纪 80 年代, 也有一些 Crazy 的系统, 选择直接操作 Block Device, 因此建立了自己的一个文件系统, 例如 Oracle ASM, IBM DB2, Sybase / SAP ASE 等, 大多数数据库都是使用操作系统提供的文件系统来存储数据的, 但是不同的数据库系统在存储数据时采用了不同的存储结构和策略, 以优化查询性能和数据管理

我们下面只讨论面向操作系统提供的文件接口的 DBMS

面对这些文件, DBMS 往往又会把文件切成很多固定大小的 Page。这里的 Page 也经常被叫做 Block, 它是 DBMS 读写磁盘和缓存数据的基本单位。

为什么不直接按一行一行读写呢？因为操作系统和磁盘都更擅长处理连续的一块数据。DBMS 也需要把数据放进 Buffer Pool 里缓存, 所以它通常不会说“帮我读第 3 行”, 而是说“帮我读第 42 个 Page”。拿到整个 Page 以后, 再在 Page 内部找到具体的行。

一些商业的 DBMS 可以实现为不同的 Table 设置不同的 Page Size, 而大多数 DBMS 都是 Fixed Size, 如 Pg 采用了 8KB 作为一个 Page 的大小, MySQL InnoDB 默认是 16KB。

这里先统一几个名词:

• Page: DBMS 读写磁盘和 Buffer Pool(内存数据结构) 缓存的基本单位
• PageNo: 一个 Page 在某个 HeapFile 内部的编号
• PageId: 用来定位某个 Page 的完整标识, 从一个 PageId 可以得到物理位置, 对于单文件 DBMS, 可以就是一个数字, 物理位置直接 PageId * PageSize, 对于多文件 DBMS, 可以是 (fileId:PageNo)

如何管理这些 Page 呢, 不同的 DBMS 给出了不同的思路

基于堆文件的存储

基于此的数据库系统: PostgreSQL, SQL Server, Oracle, SQLite

HeapFile: 存放表数据的一组 Page。这里的 Heap 不是数据结构里的堆, 而是说这些记录没有按照某个索引顺序组织, 新行通常会被塞进某个还有空闲空间的 Page

PageHeader

通常每一个 Page 都会包含一些 metadata, 比如

• PgaeSize
• Checksum
• DBMS Version
• Transaction Visibility
• Compression Info
• Schema Info(常见于 Oracle, 目的是为了保障发生事故的时候能恢复, 大多数系统不这么做)
• Data Sumary(比如说最大值/最小值)

Page Layout

如何把一个 Tuple 插入到 Page 中呢

Tuple-oriented Storage

槽页(Slotted Pages) 是最常见的组织方式

当我们要新插入元组的时候, 我们会把它从页末向开头拓展, 而槽数组(Slot Array)是从开头向末尾延伸, Slot Array 每个元素都是一个指针, 指向对应 Tuple 的位置

如果要删除中间的某个元组, 例如这里的 Tuple#3, 有的 DBMS 会考虑压缩它, 把 Tuple#4 移动过去, 但是这会更多的时间, 特别是当后续并发操作持有锁(Latch)的时候, 往往可能会造成更多延迟, 但是好处就是能更好地利用空间, 所以这其实也是一个 trade-off

Log-structred Storage

Index-organized Storage

基于列存储的存储