https://15445.courses.cs.cmu.edu/fall2018/slides/03-storage1.pdf
本章重点介绍“面向磁盘”的DBMS体系结构，该体系结构假定数据库的主存储位置位于磁盘上。
在storarge层次结构的顶部，最接近CPU的设备，是最快的存储，但它也是最小和最昂贵的。离CPU越远，存储设备的容量越大，也越来越慢。这些设备每GB也更便宜。
内存是易失装置：
•易失性意味着如果从机器上拉电源，则数据会丢失。
•易失性存储支持快速随机访问，具有字节可寻址位置。
•出于我们的目的，我们将始终将此存储类称为“内存”。
非易失性设备：
•非易失性意味着不需要为存储设备提供连续电源，以便设备保留其存储的位。
•传统上，非易失性存储在顺序访问（同时读取多个数据块）和块可寻址方面更好。
•我们将在整个课程中将其称为“磁盘”。我们不会对固态存储（SSD）或旋转硬盘（HDD）进行区分。
还有一类新的存储设备即将推出，称为非易失性存储器。这些设备的设计是两全其美的：几乎与DRAM一样快但具有磁盘的持久性。但本章不会涉及。
为什么不用os
DBMS的高级设计目标是支持超出可用内存量的数据库。
由于读/写磁盘很昂贵，因此必须谨慎管理。
我们可以使用mmap映射进程地址空间中文件的内容，但如果mmap遇到页面错误，这将阻止进程，如果进程锁定了其他元组就麻烦了。
•如果需要编写，您永远不想在DBMS中使用mmap
•DBMS（几乎）总是希望自己控制事物
•DBMS（几乎）总是希望自己控制事物，并且可以做得更好。操作系统不是您的朋友。
→按正确的顺序将脏页刷新到磁盘。
→专业预取。（prefetching)
→缓冲区更换政策。(自定义更加合适的缓冲区替换策略）
→线程/进程调度。
dbms 如何把文件组织成一个可用的数据库
存储管理器负责维护数据库的文件。
它将文件组织为页面集合。
→跟踪读取/写入页面的数据。
→跟踪可用空间。
那么一个页面是什么呢？
页面是固定大小的数据块。
→它可以包含元组，元数据，索引，日志记录......
→大多数系统不混合页面类型。
→某些系统需要页面自包含。
每个页面都有一个唯一的标识符。
→DBMS使用间接层将页面ID映射到物理存储位置。
页面大小
一个heap file 是一组页面的表示。有2种方式来表示一个heap file
分别是链表法，和字典法。
链表法
链表法里会有一个header，存储2个链表头，一个是使用的page 块的链表头，另一个是空闲的page块的链表头。
字典法
DBMS维护特殊页面，用于跟踪数据库文件中数据页面的位置。
该目录还记录每页的空闲插槽数。
DBMS必须确保目录页面与数据页面同步。
页结构
每个页面都包含一个header，用于记录有关页面内容的元数据：
在页面中布置数据有两种方法：（1）元组导向（2）日志导向。
Slotted Pages：页面将插槽映射到偏移。
•当今DBMS中最常用的方法。
•header跟踪已使用的插槽和上次使用的插槽的起始位置的偏移量。
Log-Structured：DBMS不存储元组，而是存储日志记录。
•将记录存储到文件中，了解数据库的修改方式（插入，更新，删除）。
•要读取记录，DBMS会向后扫描日志文件并“重新创建”元组。
•快速写入，可能导致读取速度慢。
为了解决读取慢的问题
- 构建索引以允许它跳转到日志中的位置。
- 定期压缩日志。
下面是使用日志导向的数据库
2种日志压缩方式
元组本质上是一个字节序列。 DBMS的工作是将这些字节解释为属性类型和值。
元组标题：包含有关元组的元数据。
- 并发控制的可见性信息。
- NULL值的位图。
- 请注意，我们不需要在此处存储有关数据库架构的元数据。
元组数据：属性的实际数据。
•属性通常按创建表时指定的顺序存储。
•大多数DBMS不允许元组超过页面大小。
总结
数据库按页面组织。
跟踪页面有不同方式。
存储页面有不同方式。
存储元组有不同方法。
第二部分
https://15445.courses.cs.cmu.edu/fall2018/slides/04-storage2.pdf
一次数据库的交互流程
数据表示
这决定了DBMS如何在内存中存储值的实际位。
所有整数都存储在IEEE-754标准规定的“本机”C / C ++中。
Variable Precision Numbers
•不精确的可变精度数值类型，它使用IEEE-754标准指定的“本机”C / C ++类型。
•比任意精度数字更快，因为CPU可以直接对它们执行指令。
•示例：FLOAT，REAL
Fixed Point Precision Numbers
•具有任意精度和比例的数字数据类型。 通常存储在精确的可变长度二进制文件中
具有附加元数据的表示。
•当舍入错误不可接受时使用。
•示例：NUMERIC，DECIMAL
超大值
一般我们不会允许一个tuple的值超过一个页的大小。但是万一数据库帧的需要存一个很大的值该怎么办呢？
如果是varchar 类型，他会用一个指针指到一个overflow page上
如果是blob类型，会引用外部文件。
但是DBMS无法操纵外部文件的内容。
→没有耐久性保护。
→没有交易保护。
OLTP VS OLAP
OLTP：在线事务处理
•短暂的事务
•占用资源少
•重复性操作
•通常是人们首先构建的应用程序类型
OLAP：在线分析处理
•长时间运行的查询
•复杂的连接
•探索性查询
行存储 vs 列存储
N-Ary存储模型（NSM）
DBMS连续存储单个元组的所有属性。也被称为“行存储”。这个
对于OLTP工作负载而言，此方法非常理想，因为事务往往只运行单个实体并插入繁重的工作负载。
好处：
•快速插入，更新和删除。
•适用于需要整个元组的查询。
缺点：
•不适合扫描表格的大部分和/或属性的子集。这是因为它通过获取处理查询不需要的数据来污染缓冲池。
组织NSM数据库有两种不同的方法：
•堆有组织表：元组存储在称为堆的块中，堆不一定定义订单。
•索引组织表：元组存储在主键索引本身中，但与聚簇索引不同。
分解存储模型（DSM）
DBMS在一个数据块中连续存储所有元组的单个属性。也称为“列存储”。此模型非常适用于OLAP工作负载，其中只读查询对表的属性子集执行大型扫描。
好处：
•减少查询执行期间浪费的工作量，因为DBMS仅读取该查询所需的数据。
•启用更好的压缩，因为同一属性的所有值都连续存储在单个列中。
缺点：
•由于元组拆分/拼接，点查询，插入，更新和删除的速度很慢
那在列存储中，我们如何来恢复出一行呢？
