数据库的存储

总所周知, 里CPU越近的存储越小且约昂贵. 而离得越远的设备,空间越大每GB的空间越便宜.

存储设备的分类

易失性存储(Volatile)

意味着当你关闭电源时, 数据将会丢失.
易失性存储提供快速的随机访问, 支持字节级别的定位. 可以通过字节地址的方式进行读取数据.
我们在此称为内存

非易失性存储(No-Volatile)

意味着断电时仍能保持比特位的存储.
它也是块/页寻址的。这意味着，为了读取一个特定偏移量的数值，程序首先必须将4KB的页面加载到内存中，以保存程序要读取的数值。
非易失性存储在传统上更擅长顺序访问（同时读取多个连续的数据块）
我们将把它称为 “磁盘”。我们将不对固态存储（SSD）和旋转式硬盘（HDD）进行（主要）区分。

我们无法直接在磁盘上直接操作数据, 所以DBMS的一项功能就是如何在易失性存储和非易失性存储之间转移数据.

我们将专注于隐藏磁盘的延迟，而不是用寄存器和缓存进行优化，因为从磁盘获取数据的速度非常慢。如果从L1缓存引用中读取数据需要一秒钟，从SSD中读取需要4.4小时，而从HDD中读取需要3.3周。

面向磁盘的数据库管理系统

数据库都在磁盘上，数据库文件中的数据被组织成页，第一页是目录页。为了对数据进行操作，DBMS需要将数据引入内存。它通过拥有一个缓冲池来管理数据在磁盘和内存之间的来回移动。DBMS也有一个执行引擎，将执行查询。执行引擎将要求缓冲池提供一个特定的页面，而缓冲池将负责把该页面带入内存，并给执行引擎一个指向内存中该页面的指针。缓冲池管理器将确保在执行引擎对该部分内存进行操作时，该页就在那里。

数据库和OS

DBMS的一个高级设计目标是支持超过可用内存量的数据库。由于对磁盘的读/写是昂贵的，所以必须仔细管理磁盘的使用。我们不希望从磁盘上获取的东西出现大的停顿，从而拖慢其他一切。我们希望DBMS能够在等待从磁盘获取数据的时候处理其他查询。这个高层次的设计目标就像虚拟内存一样，有一个大的地址空间和一个供操作系统从磁盘上获取页面的地方。实现这种虚拟内存的方法之一是使用mmap来映射进程地址空间中的文件内容，这使得操作系统负责在磁盘和内存之间来回移动页面。不幸的是，这意味着如果mmap遇到页面故障，进程将被阻塞。

如果你需要写东西，你永远不会想在你的DBMS中使用mmap。
DBMS（几乎）总是想自己控制事情，而且可以做得更好，因为它对被访问的数据和被处理的查询了解得更多。
操作系统不是你的朋友。

通过使用操作系统是可以的。

madvise。告诉操作系统你打算什么时候读取某些页面。
mlock。告诉操作系统不要把内存范围交换到磁盘上。
msync: 告诉操作系统将内存范围刷到磁盘上。

出于正确性和性能的考虑，我们不建议在DBMS中使用mmap。尽管系统会有一些看起来像操作系统可以提供的功能，但是让DBMS自己实现这些程序，会给它更好的控制和性能。

文件存储

在其最基本的形式中，DBMS将数据库存储为磁盘上的文件。有些可能使用一个文件层次结构，有些可能使用一个单一的文件（例如SQLite）。
操作系统对这些文件的内容一无所知。只有DBMS知道如何读取解析内容，因为它是以DBMS特有的方式编码的。
DBMS的存储管理器负责管理数据库的文件。它将文件表示为一个页面的集合。它还跟踪哪些数据被读和写到了页面上，以及这些页面上有多少可用空间。

数据页

DBMS将数据库组织在一个或多个文件中的固定大小的数据块，称为页。页中包含不同种类的数据(tuples、索引等)。大多数系统不会在页中混合这些类型。有些系统会要求页是自成一体的，也就是说，阅读每个页所需的所有信息都在页本身。

每个页都有一个唯一的标识符。如果数据库是一个单一的文件，那么页ID可以只是文件的偏移量。大多数DBMS有一个中介层，将页ID映射到文件路径和偏移量。系统的上层会要求提供一个特定的页号。然后，存储管理程序将不得不把这个页号变成一个文件和一个偏移量来寻找这个页。

大多数DBMS使用固定大小的页来避免支持可变大小页所需的工程开销。例如，在可变大小的页中，删除一个页可能会在文件中产生一个洞(碎片空间)，而DBMS不能轻易用新的页面来填补。
在DBMS中，有三个关于页的概念。

Hardware page（通常为4KB）。
OS page（通常为4KB）。
Database page（512B -16 KB）。
存储设备保证对硬件页的大小进行原子写入。如果硬件页是4KB，而系统试图将4KB写入磁盘，要么所有的4KB都会被写入，要么都不会。这意味着，如果我们的数据库页大于硬件页，DBMS将不得不采取额外的措施来确保数据被安全地写出来，因为当系统崩溃时，程序可以在将数据库页写到磁盘的过程中得到一部分。

数据库堆

有几种方法可以找到DBMS页在磁盘上的位置，而堆文件组织就是其中一种方法。堆文件是一个无序的页集合，其中的 tuples 是以随机顺序存储的。
DBMS可以通过使用页的链表或页目录在磁盘上找到一个给定的页面ID。

链表。头页持有指向空闲页列表和数据页列表的指针。然而，如果DBMS要寻找一个特定的页面，它必须在数据页列表上进行顺序扫描，直到找到它要寻找的页面。
页目录。DBMS维护特殊的页，跟踪数据页的位置以及每页的自由空间量。

从单个文件很容易的定位到 Page 所在的位置.

多文件索引时, 需要定义一个页目录

页布局

每个页都包含一个记录有关页元数据内容的头：
• 页大小
• 校验和
• 数据库管理系统版本
• 交易可见性
• 自包含（有些系统如 Oracle 需要这个）

放置数据的一种简单方法是跟踪 DBMS 在页面中存储了多少 tuple ，然后在每次添加新 tuple 时追加到末尾。但是，当删除 tuple(出现碎片) 或 tuple 具有可变长度属性时(无法确定最后的位置)，就会出现问题。

在页面中布置数据有两种主要方法：(1) slotted-pages 和 (2) log-structured

Slotted Pages：页将插槽映射到偏移量。
• 目前在DBMS 中最常用的方法。
• Header 跟踪使用的槽的数量、最后使用的槽的起始位置的偏移量，以及一个槽数组索引，它跟踪每个 tuple 的开始位置。
• 添加一个 tuple ，槽数组将从头到尾增长， tuple 的数据从尾到头增长。当槽数组的索引和 tuple 数据相遇时，页面被认为已满。

日志结构：后续介绍

记录 ID

DBMS 需要一种方式去跟踪独立的 tuples, 每个 tuples 有唯一的记录ID: 常见的 ID 是 page_id + offset / solt ,也可以对文件位置进行包含

各家大小: postgreSQL: CTID (6-bytes) / SQLite: ROWID (8-bytes) / oracle: ROWID (10-bytes)

tuple 布局

tuple 本质上是一个 字节序列 。DBMS的工作是将这些字节解释为 属性类型 和 值 。

tuple 头。包含关于 tuple 的元数据。

DBMS的并发控制协议的可见性信息（即，关于哪个事务创建/修改该 tuple 的信息）。
NULL值的字节映射。
注意，DBMS不需要在这里存储关于数据库表的元数据。

tuple 数据。属性的实际数据。

属性通常按照你创建表时指定的顺序存储。
大多数DBMS不允许一个 tuple 超过一个页的大小。

唯一标识符

数据库中的每个 tuple 都被分配一个唯一的标识符。
最常见的是：page_id +（offset/slot）。
一个应用程序不能依赖这些ID来表示任何东西。

Denormalized Tuple Data: 如果两个表是相关的，DBMS可以 “预连接 “它们，所以这些表最终会在同一个页上。这使得读取速度加快，因为DBMS只需要加载一个页，而不是两个独立的页。然而，这使得更新更加昂贵，因为DBMS需要为每个 tuple 提供更多的空间。

面向页的架构

插入一个新的 tuple

检查页目录, 寻找一个空闲的页空间.
从磁盘检索该页（如果不在内存中）。
检查插槽阵列，在页中找到适合的空位。

使用记录ID 更新一个存在的值

检查页目录，找到页的位置。
从磁盘检索该页（如果不在内存中）。
使用插槽阵列找到页的偏移量。
覆盖现有数据（如果新数据适合）。

插槽页的问题

碎片化。删除 tuple 会在页面中留下间隙
无用的磁盘I/O。由于非易失性存储的面向块的性质，需要读取整个块来获取一个 tuple
随机的磁盘I/O。磁盘阅读器可能要跳到20个不同的地方来更新20个不同的 tuple，这可能是非常慢的。

日志结构存储

DBMS不存储 tuple ，只存储日志记录

将数据库修改（put and delete）记录存储到文件中。每条日志记录包含 tuple 的唯一标识符。
读取一条记录时，DBMS 从最旧的日志扫描到最新的日志, 并对日志进行 “重建” tuple.
写入的速度快，读取的速度可能慢。写入时是连续的，现有的页是不可改变的，这导致了随机磁盘I/O的减少
在 “仅附加” 的存储上工作得很好，因为DBMS不能回溯并更新数据。
为了避免长时间的读取，DBMS 使用索引来定位到日志中的特定位置。它也可以定期地压缩日志。(如果有一个 tuple，然后对其进行了更新，它可以将其压缩到只有插入更新的 tuple 记录）。
数据库可以将日志压缩到按id 排序的表中，因为不再需要临时信息。这些被称为排序字符串表 (SSTables)，它们可以使元组搜索非常快。
压缩的问题在于 DBMS 最终会出现写入放大。（一遍又一遍地重写相同的数据, 因为i日志类型的数据库在压缩的过程中需要一遍又一遍的写入需要保存的数据）

数据存储的形式

tuple 的数据本质上只是字节数组。这取决于 DBMS 如何解释这些字节获得出具体属性的值。数据表示方案是DBMS如何为一个值存储字节。
有五种高级的数据类型可以存储在 tuple 中：整数、可变精度数、定点精度数、可变长度值以及日期和时间。

整形

Most DBMSs store integers using their “native” C/C++ types as specified by the IEEE-754 standard. These values are fixed length.
大多数 DBMS 使用 IEEE-754 标准规定的 “原始” C/C++类型来存储整数。这些值是长度固定的

Examples: INTEGER, BIGINT, SMALLINT, TINYINT.

可变精度数

这些是不精确的、可变精度的数字类型，使用 IEEE-754 标准规定的 “原始” C/C++类型。这些数值也是固定长度的。
对可变精度数字的操作比任意精度数字的计算更快，因为CPU可以直接对它们执行指令。然而，由于有些数字不能精确表示，在进行计算时可能会出现四舍五入的错误。

Examples: FLOAT, REAL.

固定精确数

这些是具有任意精度和比例的数字数据类型。它们通常以精确的、可变长度的二进制表示法（几乎像一个字符串）来存储，并有额外的元数据来告诉系统诸如数据的长度和小数的位置。
这些数据类型在舍入误差不可接受的情况下被使用，但是DBMS为获得这种精度付出了性能上的代价。

Examples: NUMERIC, DECIMAL.

一个库 libfixeypointy
postgre对于 NUMERIC 加法的实现
 mysql 对于加法的实现

变长数据

这些表示任意长度的数据类型。它们通常用 header 的形式进行存储，这个头可以跟踪字符串的长度，以便于跳到下一个值。它还可能包含一个数据的 checksum。
大多数 DBMS 不允许一个 tuple 超过单页的大小。那些允许的系统将数据存储在一个特殊的 “overflow” 页上，并让 tuple 包含对该页的引用。这些溢出页可以包含指向其他溢出页的指针，直到所有的数据都能被存储。

有些系统会让你把这些大的数据存储在一个外部文件中，然后元组将包含一个指向该文件的指针。例如，如果数据库存储的是照片信息，DBMS 可以将照片存储在外部文件中，而不是让它们占用 DBMS 中的大量空间。这样做的一个缺点是，DBMS 不能对这个文件的内容进行操作。因此，没有 “durability” 或事务保护。

Examples: VARCHAR, VARBINARY, TEXT, BLOB.

微软的一篇论文To BLOB or Not To BLOB: Large Object Storage in a Database or a Filesystem?

日期和时间

不同的系统对日期/时间的表示方法不同。通常情况下，它们被表示为自unix纪元以来的一些单位时间（微/毫）秒。

Examples: TIME, DATE, TIMESTAMP.

系统目录

为了使DBMS能够破译 tuple 的内容，它维护了一个内部目录来告诉它关于数据库的 tuple 。元数据将包含关于数据库有哪些表和列的信息，以及它们的类型和值的顺序。
大多数DBMS以它们用于表的格式在自己内部存储目录。他们使用特殊的代码来 “引导 “这些目录表。

5# 存储模式以及压缩

数据库工作模式

OLTP: 联机事务处理过程(Online Transaction Processing)

OLTP的特点是快速、操作耗时短，一次对单个实体进行操作的简单查询，以及重复性的操作。OLTP通常会处理更多的写操作而不是读操作。

一个OLTP的例子是亚马逊的店面。用户可以把东西添加到他们的购物车中，他们可以进行购买，但这些操作只影响他们的账户。

OLAP: 联机分析处理(Online Analytical Processing)

OLAP的特点是执行耗时较长、复杂的查询，读取数据库的大部分内容。在 OLAP 中，数据库系统正在从 OLTP 端收集的现有数据中分析和总结出新数据。

一个OLAP工作负载的例子是亚马逊计算匹兹堡在下雨天购买最多的商品。

HTAP: 混合事务和分析处理(Hybrid Transaction + Analytical Processing)

最近流行的一种新的类型是 HTAP，它就像一个组合，试图在同一个数据库上同时进行OLTP和OLAP。

存储模式

There are different ways to store tuples in pages. We have assumed the n-ary storage model so far.

在页中有不同的方式来存储 tuple 。到目前为止，我们假定采用 n-ary 存储模式。

N-Ary Storage Model (NSM)

在 n-ary 存储模型中，DBMS将单个 tuple 的所有属性连续地存储在一个页中。这种方法非常适合 OLTP ，在此情境下，请求的重心是插入，并且事务倾向于只操作单个实体。只需要一次获取就能够得到一个 tuple 的所有属性。

优势:

插入, 更新, 删除速度快.
适合需要整个 tuple 的查询.

劣势:

不适合扫描表的大部分或者属性的子集

Decomposition Storage Model (DSM)

DBMS在一个数据块中为所有 tuple 的所有属性(列)进行连续存储。因此，它也被称为 “列存储”。这种模式是 OLAP 的理想选择，它有许多只读查询，在表的属性子集上进行大量扫描。

优势:

减少了不必要的 I/O 浪费，因为 DBMS 仅要读取该查询所需的数据
更好的查询处理和数据压缩

劣势:

由于 tuple 分割/缝合，对单个实体的查询、插入、更新和删除的速度很慢。

要在使用列存储时将 tuple 重新组合在一起，有两种常见的方法：最常用的方法是定长偏移。需要知道给定列中的值将与另一列中具有相同偏移量的另一个值匹配，它们将对应于相同的 tuple。因此，列中的每个值的长度都必须相同。

一种不太常见的方法是嵌入 tuple ID。对于列中的每个属性，DBMS 都会存储一个 tuple ID（例如：主键）。此外, 系统还会存储一个映射，告诉它如何跳转到具有该 ID 的每个属性。注意，此方法具有较大的存储开销，因为它需要为每个属性条目存储一个 tuple ID

数据库压缩

压缩在基于磁盘的DBMS中被广泛使用。因为磁盘I/O（几乎）总是主要的瓶颈。因此，这些系统中的压缩可以提高性能，特别是在只读分析工作负载中。如果事先对 tuple 进行了压缩，DBMS可以获取更多有用的 tuple ，代价是压缩和解压的计算开销更大。

内存中的DBMS更加复杂，因为它们不必从磁盘中获取数据来执行一个查询。内存比磁盘快得多，但压缩数据库可以减少DRAM需求和处理。他们必须在速度与压缩率之间取得平衡。压缩数据库可以减少DRAM的需求, 可能会减少查询执行过程中的CPU成本(如果压缩后的数据能在DBMS中直接使用)。

如果数据集是完全随机的比特，那么就没有办法进行压缩。然而，现实世界中的数据集有一些关键属性是可以进行压缩的:

数据集往往有高度倾斜(skewed)的属性值分布（例如，布朗语料库的 Zipfian 分布)。
数据集倾向于在同一元组的属性之间有很高的相关性(correlation)（例如，邮政编码与城市，订单日期与发货日期）。

鉴于此，我们希望数据库压缩方案具有以下目标：

必须产生固定长度的值。除了是独立存储的变长数据。这是因为 DBMS 应该遵循字对齐并能够使用偏移量访问数据。
允许 DBMS 在查询执行期间尽可能长时间地推迟解压缩（延迟实现）.
必须是无损方案，因为谁都不喜欢丢数据。任何类型的有损压缩都必须在应用程序级别执行(数据库不知道哪些数据能够丢失).

Compression Granularity

在向 DBMS 添加压缩之前，我们需要决定要压缩哪种数据。这个决定决定了压缩方案是否可用。有四个级别的压缩粒度：

块级：压缩同一表的元组块。
元组级别：压缩整个元组的内容（仅限NSM）。
属性级别：在一个元组中压缩单个属性值。可以针对同一个元组的多个属性。
列级：压缩为多个元组存储的一个或多个属性的多个值（仅限 DSM）。这允许使用更复杂的压缩方案。

简单的压缩(数据库)

DBMS 使用通用算法（例如 gzip、LZO、LZ4、Snappy、Brotli、Oracle OZIP、Zstd）压缩数据。尽管 DBMS 可以使用多种压缩算法，但工程师通常会选择压缩率较低的算法，以换取更快的压缩/解压缩。

MySQL InnoDB 中有一个使用简单压缩的示例。 DBMS 压缩磁盘页面，将它们填充为2的幂次KB并将它们存储到缓冲池中。但每次 DBMS 尝试读取数据时，都必须对缓冲池中的压缩数据进行解压缩。

由于访问数据需要对压缩数据进行解压，这就限制了压缩方案的范围。如果目标是将整个表压缩成一个巨大的块，那么使用简单的压缩方案是不可能的，因为每次访问都需要压缩/解压缩整个表。因此，对于 MySQL 压缩范围有限, 将表分成更小的块。

另一个问题是这些幼稚的方案也没有考虑数据的高级含义或语义。该算法既不关心数据的结构，也不关心查询计划如何访问数据。因此，这放弃了利用延迟实现的机会，因为 DBMS 无法判断何时可以延迟数据解压缩

5 列压缩

理想情况下, 我们希望能够在不解压数据的情况下, DBMS 能够直接使用压缩后的数据进行执行语句.

列压缩更适合进行这个操作.

Run-Length Encoding (RLE, 游程编码)

RLE 将列中相同值的游程压缩为三元组：
• 属性值
• 列段中的起始位置
• 游程中的元素数量

以下是一个例子, 在此情况下, 执行需要统计各性别人数也很方便

如果没有按照顺序排, 可以预见的是. 所需的空间将比直接存储要大

排序后, 效果明显

DBMS 应该预先对列进行智能排序，以最大化压缩机会。这会聚集相同的属性，从而提高压缩率。

Bit-Packing Encoding

Bit-Packing 是一种数据压缩形式，它减少了一个值序列化后所需的位数。
当属性的值总是小于该值声明的最大值时，将它们存储为较小的数据类型。

一个简单的例子是一个总是介于 0 和 100 之间的整数。通常一个整数将被序列化为 32 位，但知道它的范围是 100，它可以被打包成只有 7 位。
Bit Packing

Mostly Encoding

列中的某个数据类型大于大多数存储值所需的数据类型时，Mostly Encoding 编码很有用. 通过为这种类型的列指定 mostly 编码，您可以将列中的大部分值压缩到较小的标准存储大小, 无法压缩的其余值维护一个查找表来存储它们

Mostly encoding

Bitmap Encoding

DBMS 为 属性的每个唯一值 映射到 单独的比特位，其中向量中的偏移量对应于一个元组。 tuple 中的第 i 个位置对应于表中的第 i 个元组，以指示该值是否存在。 bitmap 通常被分割成块以避免分配大块连续内存。
这种方法仅在值基数较低时才实用，因为位图的大小与属性值的基数成线性关系。如果值的基数很高，则位图会变得比原始数据集大。

Delta Encoding

不是存储精确值，而是记录同一列中 相邻的值 之间的差异。基值可以在线存储或存储在单独的查找表中。我们还可以对存储的增量使用 RLE 以获得更好的压缩率。

Incremental Encoding

这是一种增量编码，其中记录了常见的前缀或后缀及其长度，因此无需重复。这最适合排序的数据。

第三个是与前一个进行比较, 所以相同的前缀是 robb

Dictionary Compression

The most common database compression scheme is dictionary encoding. The DBMS replaces frequent patterns in values with smaller codes. It then stores only these codes and a data structure (i.e., dictionary) that maps these codes to their original value. A dictionary compression scheme needs to support fast encoding/decoding, as well as range queries.

Encoding and Decoding: Finally, the dictionary needs to decide how to encodes (convert uncompressed value into its compressed form)/decodes (convert compressed value back into its original form) data. It is not possible to use hash functions.
The encoded values also need to support sorting in the same order as original values. This ensures that results returned for compressed queries run on compressed data are consistent with uncompressed queries run on original data. This order-preserving property allows operations to be performed directly on the codes.

最常见的数据库压缩方案是字典编码。 DBMS 用较小的代码替换值中的频繁模式。然后它仅存储这些代码和将这些代码映射到其原始值的数据结构（即字典）。字典压缩方案需要支持快速编码/解码，以及范围查询。

编码和解码：最后，字典需要决定如何编码（将未压缩的值转换为压缩形式）/解码（将压缩值转换回其原始形式）数据。不可能使用散列函数。
编码值还需要支持按与原始值相同的顺序排序。这确保了对压缩数据运行的压缩查询返回的结果与对原始数据运行的未压缩查询一致。此保序属性允许直接对代码执行操作。