cmu15545-数据存储(Database Storage)

蓝图

数据库自己管理磁盘数据和缓冲区，而不是通过操作系统管理（

Os is not your friend.

）。

数据存储

三层视图

数据库以页（page）为存储数据的基本单位，文件（file）是一系列页的集合，页中存储页数据（data），形成

文件-页-数据

三层架构。

文件有不同的组织形式，页包含页头和页数据，页数据可以采用不同方式组织：元组，日志，索引。

黄色部分为课程会提及的内容。

采用Heapfile进行文件存储时的执行图：

• 页目录：存储管理的页的元信息（空闲页，空页）
• 页头：存储页的元信息（页大小，校验和，数据库版本，事务可见性，压缩元数据）

面向元组的数据存储

• 通过<FileId, PageId, Slot>定位到一个指向tuple的指针（磁盘地址），然后找到tuple。

• slot指针的灵活性：内部元组位置变化时，外部无感知；指针可以指向其他页，可以存储大数据（文件，大文本）；支持变长记录。

• 数据库会为每个元组分配一个数据记录的唯一标识（record identifier），来表示元组的
  
  物理位置
  
  。SQLite和Oracle中为ROWID，Pg中是CTID，<PageId, Slot>。但是他们对于应用程序是无用的。

• Header包含：可见性信息；NULL Bit Map。

• Data包含：行数据。

Tuple只是一个字符串（char[]），本身不存储类型信息，类型信息存在数据库的

System Catalogs

中。（为了保证数据紧凑；非自解释的）

存数据时会遇到的问题：

• 数据对齐：填充，重排序

• 精确值问题：BIGDECIMAL（转为字符串存储）

• 空值：Bit Map；特殊值

• 大值和文件：Overflow Page和External File。

  大值采用溢出页；大文件可以采用溢出页，也可以用外部文件系统存储，然后存储一个指向文件路径的指针，而不是直接存储文件内容（Oracle:BFILE, Microsoft: FILESTREAM）。

日志结构存储

基本概念：

• 利写不利读，非原地更新：只有PUT和DELETE操作，顺序IO。查询时由最新到最老时查询日志。
• 加速查询：索引。

• 加速查询：日志压缩，且压缩时会排序日志。
• 压缩方式：层级压缩，统一压缩

索引组织存储

直接用索引组织数据，数据挂在叶子结点上，Page内部的tuple有序。

SQLite和MySQL默认用这种方式组织数据，Oracle和SQL Server可选。

和基于元组的存储对比：

数据模型

1. N-ary Storage Model (NSM)
2. Decomposition Storage Model (DSM)
3. Hybrid Storage Model (PAX)

NSM

优点：操作一条完整记录时快速。

缺点：操作一批记录的某一个特定列的时候，非顺序读取，会有无效IO，且数据不好做压缩。

DSM

优点：可以取到一批特定列；可以做数据压缩。

缺点：在操作完整记录的时候，需要分解查询，得到结果后还需要再进行合并。

PAX

结合了NSM和DSM，既能一次处理一个完整记录，也能在读取一系列特定的属性时顺序读取并避免过多的无用IO。

数据压缩方式

目标：

1. 压缩结果为定长值（存储定长数据）。

2. 仅在需要时解压缩，否则都采用压缩形式处理数据。

3. 必须是无损的。

常用的压缩方式：字典压缩。

维护字典映射，数据表中存储映射值。结果定长，且可以支持范围查询。

字典映射的实现方式：数组。【哈希表不支持范围查询，B+树内存消耗大】