数据储存结构

13.1 Introduction

物理数据库中解决的两个问题：

• 数据组织，即数据的物理存储结构 — Ch13
• 数据访问，例如索引 — Ch14

目标

• 1. 根据DBMS机制，选择合适的数据库物理结构
• 2. 在数据库表上合理设置索引，提高数据查询速度

13.2 File Organization

文件逻辑/物理组织 in Operating System Concepts

• 逻辑结构
• 基于记录的文件
• 基于索引的文件（按内容访问）

物理组织/结构

• contiguous, linked, indexed
• 以block为单位，存储 在secondary storage, i.e. disk, SSD

DB 存储为 DB 文件的集合

• 例如.SQL服务器，主文件，辅文件，日志文件
• 每个文件都是一系列记录
• 每条记录都位于一系列字段中
  一种方法
  记录大小是固定的
  每个文件仅包含一种特定类型的记录
  不同的文件用于不同的关系

每个文件都是记录序列，每个关系表是一组元组，以元组为单位的DB逻辑文件
在以记录为单位的物理文件
元组作为记录存储在数据库中
将元组表示为文件中的记录
固定长度记录
可变长度记录
例如，名称 varchar（20）

Fixed-Length Records 固定长度记录

一个块包含多条记录
存储记录 i 从字节 n （i – 1） 开始，其中 n 是每条记录的大小。
记录访问很简单，但记录可能会跨块
修改： 不允许记录跨越块边界

删除记录 i： 备选方案：
压缩：将记录 i + 1， . . .， n 移动到 i， . . . . ， n – 1
将记录 N 移动到 I
不要移动记录，而是将所有空闲记录链接在空表

Free Lists

将第一条已删除记录的地址存储在文件头中
使用此第一个删除的记录来存储第二个已删除记录的地址，依此类推
将这些存储的地址视为指针，因为它们指向记录的位置。
更节省空间的表示形式
将空间重新用于可用记录的正常属性以存储指针。（使用中的记录中没有存储指针。）

Variable-Length Records 可变长度记录

可变长度记录以多种方式出现
记录类型允许可变长度，例如字符串 （varchar）
一个文件中有多种记录类型，例如多表聚类文件
记录类型允许重复字段，例如多值属性。

如何在块中存储可变长度记录

记录中的属性按顺序存储
首先是固定长度属性，然后是可变长度属性
可变长度属性由固定大小（偏移量、长度）表示，实际数据存储在所有固定长度属性之后
由 null 值位图表示的 Null 值

Variable-Length Records: Slotted Page Structure可变长度记录：开槽页面结构

存储空间分为固定大小的开槽页，4KB或8KB，记录分配给开槽页
记录可以在页面中移动以保持连续
RI 被删除，RI+3、RI+2、RI+1 被移动到删除创建的可用空间
标头中的条目必须更新，例如设置为 -1 指针不应直接指向记录，而应指向标头中记录的条目

13.3 Organization of Records in Files

DB文件可以看作是逻辑级别的一组记录，这些记录在逻辑上组织如下
堆、序列、哈希、聚类
记录的逻辑组织决定了如何访问记录，即访问方法
文件包括多个记录，记录在磁盘上的存放属于文件（记录）结构问题
对于某种结构的文件如何去查找、插入、删除记录，属于文件的存取方法
文件记录的组织结构决定了文件的存取方法

堆 – 放置在任何有空间的地方的记录
没有主键和索引的表中的数据，
例如，学生（ID、姓名、总学分）
序列 – 根据每条记录的搜索键按顺序存储的记录
例如学生（ID、姓名、总学分）， 或学生（ID、姓名、总学分），并附有姓名索引
每个关系的记录可以存储在单独的文件中
多表聚类 – 存储在同一文件中的不同关系的记录
动机：将相关记录存储在同一个块上，以最大程度地减少 I/O，
例如 讲师加入部门，讲师和部门的记录放在一个文件中

Heap File Organization堆文件组织

任何记录都可以放置在文件中有记录空间的任何位置
没有记录的顺序
记录在分配后通常不会移动
关系只有一个文件

以纪录的输入顺序为序，决定了文件中记录顺序
    纪录的存储顺序与记录中的主键无关
e.g. 创建新关系表student (ID, name, total-credits)，    但不在student上定义主键、候选键、各类索引，student被组织为heap file
通过insert，将记录/元组加到堆文件中

自由空间地图
每个区块一个条目。
每个条目都是几位到一个字节，记录空闲块的部分
例如，每个块 3 位 （0-7），值除以 8 表示可用块的分数

二级自由空间地图
例如，每个条目最多存储 4 个第一级自由空间映射条目
定期写入磁盘的可用空间映射，可以对某些条目使用错误（旧）值（将被检测并修复）