最近在学习CMU15-445，学完了Lec3-5感觉受益匪浅，这里就以这三节课的内容为基准大致总结一下关于数据库的相关知识。如果有些说的不清楚或者有问题的部分，恳请大佬指出。
所有内容均来自于CMU15-445（2024fall）的课程，notes，slides，以及个人和AI的对话答疑。
学习过程中会使用AI，但是本文内容基本手打。仅只有一个表格是AI弄的，会以截图的形式发出。其余图片均来自于课程的slides。
首先，关于下图这种计算机存储结构的模型这里就不过多赘述了，我将采用课程的说法，统一把DRAM叫做主存/内存/memory，非易失性存储器统一叫做磁盘/外存。
这三讲聚焦于一个问题：How the DBMS represents the database in files on disk？
即，数据库管理系统如何将数据库表示为磁盘上的文件？
数据必须持久化的存储在磁盘上，但是查询操作需要在内存中进行。
而两者的速度差异决定了整个存储层的设计目标：尽可能减少磁盘I/O次数，尽可能让磁盘I/O是顺序的。
这个矛盾就是这三讲的主线，这三讲的所有知识点，本质上都是在解决这个矛盾。
OS提供了mmap机制来管理磁盘和内存之间的数据，但是mmap会遇到page fault, OS不了解数据内容，访问的方式，无法做出最优的决策。
因此DBMS自己实现了Buffer Pool, 自己决定读写和淘汰页面的时机。
这也就有了这门课程上的一个名句：The operating system is not your friend.
我们的DBMS建立在磁盘之上，其基本架构如下。通过图片很容易得知，lec3-5解决的就是page上的内容。
关于页，课程中区分了三种不同的页的概念：
课程中原句是：A hardware page is the largest block of data that the storage device can guarantee failsafe writes.
可以看出硬件页是可以做到原子性写入的，因此，如果数据库页的大小大于硬件页，写入时需要额外的安全措施保证数据完整性。
有些系统要求页中需要self-contained自己的元数据。例如：Oracle就需要将描述该page中内容的所有元数据，和这些内容数据⼀起保存在该page中，这种情况下，如果你丢失了其他任何page，这并不会影响该page的使用
关于page的存储结构，课程中提到了四种：heap, tree, sequential/sorted, hashing
但是后续课程中只详细讲解了heap的存储结构。
这里的heap，不是数据结构中的堆（二叉堆），而是指无序的空间池，这和 C 语言内存模型（heap memory）中的heap是一个意思。因此，在这里与heap相对的，是有序的排列（例如B+树）
在DBMS眼中，OS 的文件只是一个巨大的、连续的字节数组，也就是说，DBMS是不关心file这个层级的内容。对于DBMS来说，page就是其最小的管理单位，一个file是由很多page组成的。
此外，如图所示，还有一个Page Directory的结构，他的作用是：
本质上是为了加速性能，而不需要挨个找所有的page哪里有空。
图片中的Table X 和 Index Y 是逻辑对象，而 Page Directory 记录的是这些逻辑对象与物理 Page 之间的映射关系。对于查询引擎来说，需要使用Table X，Index Y这样的逻辑对象来代替File0, File1这样的物理层内容，一个Table可以在物理上对应一个或多个文件。
如前文所提的，每个页都一个header，用于记录元数据，包括页的大小，校验和，DBMS版本等内容。
页内的数据组织分为三种不同的存储架构：Tuple-Oriented，Log-Structured，Index-Organized
这种存储方式又叫做Slotted Pages，槽页。具体结构如图，页内有一个槽数组，从页头部向后增长，元组数据则倒过来，从页的尾部向前增长。槽数组记录每个元组的偏移量，当两者相遇时，页满。
这样的存储会带来以下问题：
针对上述槽页的三个问题，我们可以拥有一个完全不同的思路，既然各种对于元组的操作都会打乱原来的布局，或者是增加很多无用的IO，那么我们就不在原来的数据上更新，而是追加修改的日志。
整个结构基于日志结构化文件系统（Log-Structured File Systems, LSFS）和日志结构化合并树（Log-Structured Merge Trees, LSM Tree）
核心操作如下：
大致图示如下：
值得一提的是
当然Log Structured的存储方式也有一些缺点：
这个让我想到了xv6的操作系统文件系统的log结构，两者具有一定的相似之处。
xv6是先写log区，commit之后再apply到原处，最后清理log
Log-Structured的结构是先写MemTable，整理到SSTable之后再进行Compaction，然后清理旧的SSTable
但是从目的来看，xv6的log是为了保证崩溃一致性，而LSM实际是为了写性能优化。
在查阅相关资料之后了解到，由于MemTable是纯内存的，如果崩溃了会丢失，所以在实际的系统中会额外维护一个Write-Ahead Log来保证持久性
前面两种存储模式都有一个特点：表本身是无序的，查找特定元组的时候需要额外的索引。
然而，我们可以把元组本身作为索引数据结构的值来存储。页面布局类似与Slotted Page，但是元组在页内按照key排序。
例如有一张表
CREATE TABLE student (
id INT PRIMARY KEY,
name VARCHAR,
age INT
);
如果按照 id 建B+树，那么传统方式可能是在B+树的index上标注id = 100的时候，指向heap page中tuple所在的位置。查询时先查B+树得到指针，再跳转到heap page读取tuple
但是在索引组织存储中，B+树的叶子节点直接存储tuple本身，查询时直接在B+ 树上读取tuple，不需要二次跳转。
如图所示，B+树节点本质上仍然是一个Page，Page内部采用类似Slotted Page的布局。在一个 page 内部，tuple 通常会按照 key 排序。
这种存储方式是在维护B+树的过程中拥有维护成本。与上面的日志结构存储相比，B+ 树在写入时就付出维护成本；日志结构存储写入时先快写，后面再通过合并付出整理成本。
元组本质上就是一段字节序列。具体来说，元组的头部header包含一些元数据，包括事务可见性信息、NULL值的位图（注意：不存储schema（数据库模式）信息），后面就是元组的数据。
DBMS 希望确保元组是字对齐(word-aligned)的，通常有两种方法：
元组中可以存储五类高级数据类型：
整数 INTEGER / BIGINT / SMALLINT / TINYINT
存储上与C/C++相同
可变精度数字 FLOAT / REAL
存储上与C/C++相同，使用IEEE-754的存储方式。但是其存在一些舍入的误差，因此我们需要更高精度的数据表示
定点精度数字 NUMERIC / DECIMAL
这些是具有任意精度和小数位数的数字数据类型。
会带有额外的元数据，用来告诉系统一些信息，例如：数据的长度，小数点应该在哪里。
当舍入误差不可接受时，会使用这些数据类型。一个实际例子如图
可变长度值 VARCHAR / VARBINARY / TEXT / BLOB
大多数DBMS不允许一个元组超过单个页面的大小。允许超过单页大小的系统，会把数据存储在特殊的溢出页面（overflow page）上，并让元组包含一个指向该页面的引用，溢出页面可以包含指向额外溢出页面的指针，直到所有数据都能被存储下来。
有些系统允许你把这些大值存储在外部文件中，然后让元组包含一个指向该文件的指针。比如说数据库存储的是照片信息，DBMS可以把照片存储在外部文件中，而不是让它们在 DBMS内部占用大量空间。这种做法的一个缺点是：DBMS 无法操作这个文件的内容。因此，这些文件没有持久性保护，也没有事务保护。
存在三种选择：
不采用第三种，浪费空间而且破坏字对齐
为了让 DBMS 能够解释元组中的内容，它会维护一个内部 catalog，用来告诉它关于数据库的元数据，具体来说，元数据包括：
到目前为止我们解决了数据怎么存，但不同工作负载对存储的需求截然不同。一种布局能同时满足所有场景吗？有一说一，我在听lec5前，从来没有想到数据库还能按照列来存储。
按照工作负载来说，我们分为三种不同的工作负载
| 类型 | 特征 | 典型场景 |
|---|---|---|
| OLTP | 短事务，简单查询，以写为主，每次操作少量数据 | 网购平台下单、购物车 |
| OLAP | 长查询，复杂聚合，以读为主，扫描大量数据 | 用户行为分析、推荐系统 |
| HTAP | 二者混合 | 同一实例同时支持交易和分析 |
而对于OLAP这样的情况，如果按照我们传统认知的视角，在访问的时候会访问所有页面，而且存在大量无用的数据访问（如图）为了解决这个问题，column store应运而生。
平时我们认知里的存储模式，以及上文的存储模式，都是行存储，又叫做N-ary Storage Model（NSM）
这样的存储模式就是将一个元组的所有属性连续存储在同一页中，其适合OLTP但是不适合OLAP
而列存储，又叫做Decomposition Storage Model (DSM)，就是倒过来，将同一属性的所有值连续存储在一起。自然而然，这样的存储模式适合OLAP而不适合OLTP
然而这样的存放带来一个问题：我怎么判断这一个的某个数据是哪个tuple的呢？对于固定长度的数据还可以直接计算offset，而对于可变长度的数据呢？有一个反面教材，那就是创造一个数据结构，每一个数据都对应一个序号，如下图。
这种做法完全违背了列存储的初衷，首先每存储一个值，都要造成一定程度的空间浪费额外存储一个 Tuple ID，其次，数据库读取时必须：读取 [ID, value] 对，然后提取出 ID 和 value。那我列存储的空间连续性就被破坏了。
那么对于可变长度的数据，一般采用间接层或者字典编码的方式。
间接层指我们在可变数据的列存储中只存储对应的指针，真正的数据单独存储在一个可变长度的区域 Variable Pool
字典编码适用于有很多重复值的情况，可以直接字典压缩。例如：
字典: ["Andy", "Mr.Pickles", "Bo"]
某一列: [0, 1, 2, 0, 1] ← 固定长度的整数数组
既然存在行存储和列存储，那我们自然可以把这两个结合起来——Partition Attributes Across (PAX)，叫做混合存储。
其存储方式如下：
在文章最开头我提到：
数据必须持久化的存储在磁盘上，但是查询操作需要在内存中进行。而两者的速度差异决定了整个存储层的设计目标：尽可能减少磁盘I/O次数，尽可能让磁盘I/O是顺序的。
而在前文，我们通过使用各种存储手法，尽可能减少了I/O次数。但是我们还有一个方法，可以在单次I/O中获取更多有用的信息——压缩
我们进行数据库压缩具有如下目标：
压缩也存在不同的粒度
在这里我们介绍两种压缩形式
使用通用压缩算法（gzip, LZ4, Snappy, Zstd等），这类压缩存在如下问题：
例如：MySQL InnoDB压缩页到2的幂KB大小存入缓冲池，但每次读/更新都必须先解压。
（该表格为AI生成）
例子：
对于Dictionary Encoding的补充
我们需要解决的问题就是：数据库如何在磁盘文件中表示数据？
紧接着我们按照物理基础 → 文件层 → 页层 → 元组层 → 压缩层的顺序梳理了一遍如何表示数据，如何提高查询/插入的速率
每一层的设计都不是孤立的，而是由上一层所暴露的问题驱动的：物理硬件的速度差距 → 自己管理I/O → 固定大小的页 → 页内如何组织元组 → 工作负载决定行存还是列存 → 列存使得高效压缩成为可能 → 压缩进一步减少I/O
可以看到整个过程就是一条环环相扣的链条，学完这三个lec也是让我受益匪浅啊
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。