lecture 3 - 5

总结

Tuple-Oriented Storage: 数据按照行进行存储，适用于事务型应用（OLTP）。适合需要频繁插入、更新和删除操作的应用场景。

Log-Structured Storage: 数据以日志形式顺序写入，适用于写密集型应用。

Index-Organized Storage: 数据与索引一起存储，适合需要频繁查找的应用。

面向元组存储（Tuple-Oriented Storage）

简介:

• 面向元组存储方式将数据按行进行存储，每一行对应数据库表中的一条记录。
• 这种方式也被称为行存储（Row-Oriented Storage）。

特点:

• 数据是逐行存储的，每条记录（元组）存储在一起。
• 适用于需要频繁插入、更新和删除操作的应用场景。
• 适合事务型处理（OLTP：On-line Transaction Processing）。

优点:

• 插入和更新操作相对高效，因为整条记录存储在一起。
• 对于需要访问整行数据的查询非常高效。

缺点:

• 对于只需要部分列的数据分析查询效率较低，因为需要读取整行数据。
• 在列数较多的表中，扫描大量不必要的数据可能导致性能下降。

+----+------------+-------+-------+
| ID | First Name | Age   | Salary|
+----+------------+-------+-------+
|  1 | John       | 30    | 4000  |
|  2 | Jane       | 35    | 5000  |
|  3 | Mike       | 32    | 6000  |
+----+------------+-------+-------+

日志结构存储（Log-Structured Storage）

简介:

• 日志结构存储方式将所有更新操作记录为追加到一个日志文件末尾的序列。
• 这种方式将数据随机写操作转换为顺序写操作，显著提高了磁盘写入效率。

特点:

• 数据和更新操作以日志形式顺序写入。
• 高效处理写操作，适用于写密集型应用。
• 使用垃圾回收机制来清理和整理旧的数据。

优点:

• 顺序写入磁盘提高了写操作的效率。
• 在固态硬盘（SSD）中，顺序写入有助于优化擦除和写入性能。

缺点:

• 需要定期进行垃圾回收以清理旧数据，可能导致额外的系统开销。
• 读取性能可能受到影响，因为数据分布在多个日志文件中。

[Log File]
+----+------------+---+-------+------+-----+
| ID |    Time    |Op | First | Age  | Sal |
+----+------------+---+-------+------+-----+
|  1 | 2023-07-01 | I | John  |  30  | 4000|
|  2 | 2023-07-02 | U | NULL  | NULL | 5000|
|  3 | 2023-07-03 | I | Mike  |  32  | 6000|

索引组织存储（Index-Organized Storage）

简介:

• 索引组织存储方式中，数据按照索引顺序存储在磁盘上，每条记录直接存储在索引位置。
• 这种方式特别适合需要频繁进行查找操作的应用场景。

特点:

• 数据和索引存储在一起，查找时不需要二次定位。
• 高效处理基于索引的查询。
• 索引树通常是B+树或其他平衡树结构。

优点:

• 基于索引的查询速度非常快，因为数据直接存储在索引位置。
• 节省空间，因为不需要单独维护索引和数据。

缺点:

• 更新和插入操作可能变慢，因为需要维护索引结构。
• 不适合频繁变更数据的情境，会导致索引频繁重建。

B+ Tree:
                      Root
                       |
      +----------+-----+-----+----------+
      |    Key1  |    Key2   |    Key3  |
      +----+-----+-----------+-----+----+
           |                      |
      +----+----+            +----+----+
      | Data1   |            |  Data2  |
      +---------+            +---------+

一个非常重要的DBMS的类型是 disk-oriented DBMS，它将数据存储在磁盘上，而不是内存中。主打的是一手non-volatile，即数据不是易失的，每次对数据的改变，都要更新到断电而不失数据的磁盘上。

Volatile Device: CPU registers, CPU cache, DRAM

Non-Volatile SSD, HDD, Network Attached Storage (NAS)

persistent memory: 新型技术，速度介于memory和disk之间，可以理解为不易失的内存。

由于我们的DBMS体系结构假设数据库存储在磁盘上，系统无法直接对磁盘上的数据进行操作，因此DBMS的组件负责弄清楚如何在非易失性磁盘和易失性存储器之间移动数据。

DBMS 和 OS

1. OS 一般通过mmap来实现虚拟内存。具体的，当一个进程需要访问一个文件时，OS会使用mmap在进程的地址空间中映射文件的内容，这使得操作系统负责在磁盘和内存之间来回移动页面。不幸的是，这意味着如果mmap遇到页面错误，进程将被阻止。
2. DBMS 也需要处理磁盘和内存之间的交互。DBMS 组件负责将磁盘上的数据加载到内存中，并将内存中的数据写入磁盘。DBMS 还需要处理磁盘和内存之间的同步问题。

但是需要注意的是DBMS一般不用mmap，这种行为被Andy视为弱智，一般采用以下三种方式:

1. madvise：告诉操作系统你计划何时阅读某些页面。
2. mlock：告诉操作系统不要将内存范围交换到磁盘。
3. msync: 告诉操作系统将内存范围刷新到磁盘。

对于进行存储的文件，操作系统对这些文件的内容一无所知。只有DBMS知道如何解密其内容，因为它是以特定于DBMS的方式编码的。

DataBase Pages

类似与虚拟内存里面的页，DBMS也将磁盘上的数据分成固定大小的页。

大多数DBMS使用固定大小 (fixed-size) 的页面来避免支持可变大小页面所需的工程开销。因为，对于可变大小的页面，删除页面可能会在文件中造成漏洞，DBMS无法轻松地用新页面填充这些漏洞

1. Hardware page (usually 4 KB).
2. OS page (4 KB).
3. Database page (1-16 KB).

存储设备保证硬件页面大小的原子写入。如果硬件页面为4 KB，并且系统尝试向磁盘写入4 KB，则会写入全部4 KB，或者不会写入任何4 KB。这意味着，如果我们的数据库页面比硬件页面大，DBMS将不得不采取额外措施来确保数据安全写入，因为当系统崩溃时，程序可以在将数据库页面写入磁盘的过程中进行一半写入。

字节寻址的方式:

1. Linked List: 链表，每个页面都指向下一个页面。
2. Page Directory: 页面目录，包含每个页面的物理地址。类似于索引。

Layout of Pages and Tuple

Page = Page Size + Checksum + DBMS version + Transaction Visibility

Tuple = Tuple Header + Tuple Data + Unique ID

Slotted Pages: 页面(page)将插槽(slot)映射到偏移(offset)

1. 目前DBMS中使用的最常见方法。
2. Header跟踪已使用的槽的数量、最后一个已使用槽的起始位置的偏移量，以及一个槽数组，该数组跟踪每个元组的起始位置。
3. 要添加元组，槽数组将从开始到结束增长，元组的数据将从结束到开始增长。当槽数组和元组数据相遇时，页面被视为已满。

对于课上显示的ctid即page_id, offset，page_id从0开始，而offset从1开始。

我真服了这键盘，z和下键概率失灵，打的我难受死了，直接下单一罐轴

Log-Structured Storage

Slotted-Page Design 肯定是有问题的:

1. Fragmentation: 页面碎片化，因为每次对Tuple进行删除再添加的时候，会导致被更新的东西到最后，比如123三个把2删掉，2留下的空隙就会空着，再插入2就会转而将2插到3的后面。
2. Useless Dist I/O: 因为每次对Tuple进行删除再添加的时候，都需要进行一次磁盘I/O，而这次IO的容量是一整个Page，可能我们需要的只是十分之一的Page，这就浪费了很多的I/O。
3. Random Dist I/O: 因为Tuple分布的分散性，以及读取的最小单位是Page，所以可能读10个各不连续的小Tuple就要读取10个Page。

日志结构存储将数据以事务的形式写入磁盘，并将日志写入磁盘以确保数据完整性。它储存的内容不是Tuple而是日志。

它记录了包含元组的唯一标识符、操作类型（PUT/DELETE），对于PUT，还包含元组的内容。

但是Slotted-Page Design和Log-Structured Storage都会基于index来组织，他们都是Index-Organized Storage。

Data Representation

如何在磁盘上存储数据，以及如何在内存中表示数据。

首先DBMS需要保证Tuple数据的字对齐(word-aligned)。主要有两种方式:

1. padding: 填充字节，在短Tuple的后面添加字节
2. reordering: 重排序

数据类型:

1. Integers: INTEGER, BIGINT, SMALLINT, TINYINT
2. Variable Precision Numbers: FLOAT, REAL
3. Fixed-Point Precision Numbers: DECIMAL, Numeric
4. Variable Length Data: VARCHAR, VARBINARY, TEXT, BLOB
5. Dates and Times: TIME, DATE, TIMESTAMP
6. Null Data Type

DataBase Workloads

OLTP: Online Transaction Processing

• 事务处理，主要负责处理大量的短事务。
• 快速、短时间运行的操作、重复操作和一次在单个实体上操作的简单查询。OLTP工作负载通常处理的写操作多于读取操作，并且每次只读取/更新少量数据

OLAP: Online Analytical Processing

• 分析处理，主要负责处理大量的长事务。
• 长期运行，复杂的查询并在数据库的大部分地区进行读取。在OLAP工作负载中，数据库系统通常是从OLTP侧收集的现有数据分析和得出新数据。

HTAP: Hybrid Transactional + Analytical Processing

• 结合了OLTP和OLAP的工作负载。
• 比较主流流行的新数据库工作负载

Storage Models

1. NSM (N-Ary Storage Model): 多值存储模型，每个元组可以有多个值。简单来说就是适用于对于单行的处理，以行为单位进行处理。比如每个用户只需要读取自己的信息就可以了，而不需要知道其他人的，所以是OLTP的。
   1. PROs: 适用于对单个元组进行快速查询的场景。单行快速插入、更新、删除。
   2. CONs: 对于以列为单位的不符合，因为列每行只需要一个attribute，造成资源的浪费
2. DSM (Decomposition Storage Model): 分解存储模型，以列为单位，每个tuple存的不同于NSM那样是一个用户的信息，而是所有用户的某个信息(比如姓名)放在同一个tuple。将元组分解为多个字段，每个字段可以有自己的类型。适用于OLAP。
   1. PROs: 适用于需要对元组进行复杂查询的场景。列存储，适合分析和只读查询，容易压缩。
   2. CONs: 对于单个元组的复杂查询不适用，更新效率低。
3. PAX (Partition Attribute Across): 行被水平地划分为多组行。在每个行组中，属性被垂直划分为列。每个行组的行子集类似于列存储。

DataBase Compression

压缩是数据库存储的一种重要方式，可以减少磁盘空间的使用，提高查询效率。压缩可以减少磁盘I/O，提高查询速度。因为在Slotted-Page Design中，每次删除都会导致页面碎片化，所以压缩可以减少碎片化。减少硬件资源的损耗。

但是压缩也不是压的越小越好，而是需要在速度和压缩率之间做权衡。

其中有四种压缩粒度(Compression Granularity):

1. Block level: 压缩同一个table当中的Tuples
2. Tuple level: 压缩整个Tuple的内容(NSM Only)
3. Attribute level: 压缩Tuple的某个属性，在一个Tuple中压缩单个属性值。可以针对同一Tuple的多个属性
4. Columnar level: 压缩整个列的内容，压缩整个列的多个值。(DSM Only)
   • RLE(Run Length Encoding)将单列中相同值的运行（连续实例）压缩为三元组(value, start_position, length)