数据的表示
1、数据项的表示
2、记录的表示
3、记录在磁盘块中的组织*
4、链表式堆文件和目录式堆文件
数据项的表示
数据项表示关系数据库中元组的属性值，用字节序列来表示
两种不同的数据项表示
- 定长数据项
- 变长数据项
- 带长度 （常用）
- Null Terminated（结束符）
记录的组织
固定格式定长记录
所有记录具有相同的逻辑结构（模式）
考虑如下模式
不考虑寻址特点
依次紧邻存放在磁盘中
考虑寻址特点
假设记录和字段的开始地址必须是4的倍数
记录的首部
- 记录类型（模式信息）
- 记录长度
- 时间戳
- 其它信息
可变格式记录
每个记录的格式不同
带有模式（语义）的方式
- 记录的格式存储在记录中
Key-Value 方式
记录都以“ KEY + VALUE ”方式表示
KEY 与 VALUE 都以字节流（byte string）存储
c
typedef struct {
void *data; //字节流指针
int size; //字节流长度
} DBT;键值对数据库特点
- 数据类型没有限制
- 应用与数据库之间不需转换数据格式
- 不提供KEY和VALUE的内容和结构信息
- 应用必须知道所用的VALUE的含义（由应用来解释语义）
优缺点
- 灵活的记录格式，适合“松散”记录
- 尽管一个记录可能有大量字段，但某个记录通常只有 有限的几个字段
- 例如，病人的检验结果
- 适合处理重复字段
- 适合记录格式演变
- 浪费存储空间
变长记录表示
首部指针法
- 定长字段在前，变长字段在后
- 首部加入两个信息：记录长度，以及所有除第一个之外的变长字段起始处的指针
混合格式
- 保持记录定长，将变长部分【变长字段和重复次数不确定的字段（比如明星影片集）】放在另一个块
- 记录本身存储开始指针 + 长度/结束指针
- 变长字段开始处的指针和该字段的长度
- 指向每一个重复字段开始处的指针和重复次数或者重复结束处
记录在块中的组织（*）
假设和前提
- 块的大小固定
- 记录组织成单个文件
定长记录
一种是块头标识了该块中记录的数量
一种是块头用位图的方式表示空闲槽和已用的槽
变长记录
块头有槽数和槽目录，第几个目录项就对应第几个记录，目录中存有有记录指针和记录长度
图中<i, 3>的寻址有错
记录的分隔
- 定长记录：不需分隔
- 变长记录：使用特殊标记 ，或者通过块内偏移量
跨块和不跨块记录
跨块（spanned）方式下，记录的首部需要存储以下信息
- 一个二进制位表示当前记录是否是一个片段
- 若干二进制位表明是否是记录的第一个片段或最后一个片段
- 指向前一个片段和后一个片段的指针
聚簇
多关系聚簇
经常一起访问的记录存储在同一块或连续块中，提高查询效率
单关系聚簇
另一种聚簇 (对于RDB：单关系上的聚簇) ：将记录按某个字段顺序排列在块中
- 加快按排序字段查询记录时的效率
- 利于归并联接 （will be discussed later）
记录地址
物理地址和逻辑地址
记录的修改
插入
记录无序的情况
- 插入到任意块的空闲空间中
- 或申请一个新块（当所有块都已满时）
- 记录变长时，可使用偏移量表
记录有序的情况
- 找到记录应该放置的块
- 如果有空间，放入并调节记录顺序即可，否则有 两种方法：
- 在“邻近块”中找空间
- 创建溢出块
删除
使用删除标记
- 若使用偏移表，则可以修改偏移表项指针，将其 置空
- 若使用逻辑－物理地址映射表，则可以将物理地 址置空
- 可以在记录首部预留一开始位：0－未删除，1 已删除
看习题理解删除标记
块在文件中的组织
堆文件（Heap File）
- 最基本、最简单的文件结构
- 记录不以任何顺序排序
- 记录可能存放在物理不邻接的块上
- 插入容易，但查找和删除代价高
链表式堆文件组织
维护一个空闲块链表和一个满块链表
目录式堆文件组织
用目录索引指出该文件的数据块在哪（指针）
