文章目录
- 前言
- 堆文件
- 链表实现
- 页目录实现
- 总结
- 系列文章
前言
还记得上次遗留的问题吗？
以什么组织方式将数据保存在磁盘中？
今天我们接着讨论这个问题。
首先想一个问题：有一天，你开着自己心爱的大型SUV去超市购物。在停车场入口看到，剩余车紧缺。你该如何先人一步找到合适的车位？
假如，你是这个超市的老顾客，非常熟悉这里停车场的布局和规则，那么你就更有可能快速找到车位。
停车场的布局和规则，类似于数据库中数据文件的文件组织。
堆文件
堆文件是最常见的数据文件组织形式。
堆文件（Heap File）：
- 数据库最常用的文件组织形式，常用于OLTP型数据库
- 它对页（Page）和记录（Record）没有任何顺序上的要求
- 可以根据需求，将记录插入任何合适的位置
- 页和记录的组织方式，完全由实现者自己定义
堆文件通常有两种实现方式：链表和页目录。
链表实现
在链表实现中：
- 每个数据页（Data Page）包含记录（Record）、指向下一页和上一页的指针
- 有一个头页（Header Page）作为文件的开始，用于将数据页划分为满页和空闲页
在链表实现的堆文件中插入一条记录可以分解为三个动作。
1. 找空位置
- 先找到头页
- 顺着空闲页链表找一个合适的空位
- 如果空闲页链表为空，或者找不到合适的位置，则追加一个空闲页到空闲页链表中
2. 将记录写入空位置
3. 必要时更新链表
- 如果当前空闲页已写满，则将它从空闲页链表移动到满页链表的最前方
- 把它移到满页链表的最前面，是为了提高效率，因为不用遍历整个满页链表
拿停车举例子（如上图右侧所示）。
假设停车场有A、B、C和D四个区域。每当一个区域停满时，管理员会在区域入口放一个禁止入门的路障。这样司机可以快速找到第一个有空位的区域。
你会沿着箭头的方向找到一个适合的空闲车位：
- 因为有路障，你快速驶过A区和B区
- 驶入第一个有空位的区域 - C区
- 发现C区的唯一的空位太小，大型SUV停不进去
- 继续驶入下一个有空位的区域 - D区
- 停入D区最后一个空闲车位
- 此时，管理员会在D区放置路障
页目录实现
在页目录的实现中：
- 每个头页包含一个指向下一个头页的指针，形成页目录
- 每个头页中的记录包含指向数据页的指针和该页的空闲空间信息
- 数据页只存储记录，它们不再需要指向相邻数据页的指针
在页目录实现的堆文件中插入一条记录同样分解为三个动作。
1. 找空位置
- 找到第一个头页，根据头页中记录包含的空闲空间信息，找到一个包含合适空位的数据页
- 如果当前头页找不到，则继续遍历下一个头页
- 如果头页链表为空，或者找不到合适位置，则追加新的头页和数据页
2. 将记录写入空位置
- 顺着头页中记录指向数据页的指针，找到对应的数据页
- 在数据页中找到对应的空位，写入数据
3. 更新状态
- 更新头页中有关数据页空闲空间的信息
接着拿停车举例子（如上图右侧所示）。
假设一个停车场经过了信息化改造，在停车场入口处的显示屏上，显示每个区域的每个车位的状态（是否被占用）和信息（车位尺寸）。
你也会沿着箭头的方向找到一个适合的空闲车位：
- 行驶到显示屏处，找到一个合适的空位，并记录位置（例如D区03车位）
- 直接行使到D区03车位
- 显示屏更新D区03车位状态，变为已被占用
总结
我们先从写的角度进行对比：
| 写入动作 | 链表实现 | 页目录实现 |
|---|---|---|
| 找空位 | 从第一个空闲页开始找 最差情况：追加新的空闲页 平均情况： - 可能访问较多数据页才能找到合适空位 - 例如1号停车场中存在走冤枉路的问题 | 顺着页目录开始找 最差情况：追加新的头页和数据页 平均情况： - 由于空闲信息记录(包含空闲状态和空闲信息)要远小于数据记录 - 因此头页可以包含更多的空闲信息记录 - 也就是说遍历更少的头页就可以找到合适的空位 - 不存在走冤枉路 |
| 写记录 | 因为是直接在数据页中找空位，找到空位后直接写入即可，没有额外成本 | 需要从头页中跳转到数据页中的空位，存在额外成本，但成本较低 |
| 状态更新 | 记录写入空位后，需要更新数据页头部包含空位状态的信息 最坏情况：额外需要修改数据页的指针，从空闲链表移到满页链表 | 更新头页中的状态信息 |
再从删除角度对比：
| 写入动作 | 链表实现 | 页目录实现 |
|---|---|---|
| 找记录 | 遍历数据页（不考虑所以的情况下） | 相同 |
| 删记录 | 在数据页头部中将对应的记录标记为删除，将数据页插入到空闲页链表头部 | 在数据页头部中将对应的记录标记为删除，更新头页中的空闲信息 |
| 辅助成本 | 定期清理空间 | 相同 |
由此可见：
- 页目录的优点是插入记录通常更快。只需读取头页就可以找到空位，需要执行的磁盘I/O更少，因此速度更快
- 页目录适用于频繁地写、更新和删除的场景（数据页中有很多零散的空位）
- 链表实现更简单，适用于写多，但更新和删除较少的场景（此时空闲页链表尽可能短，磁盘I/O次数尽可能少，找空位时间也尽可能短）
系列文章
更多系列文章，请参考：【如此简单！数据库入门系列】之思想地图 – 系列目录
如果喜欢这篇文章，请不要忘记关注、点赞和收藏哦！
您的鼓励将是我创作的最大动力！
