chapter13_数据库的存储结构_3_文件的存储结构

磁盘空间以块为单位

(1) 文件是相关磁盘块的集合

(2) 文件块在逻辑上连续，在物理存储上可以连续（顺序存储，类似数组），可以不连续（链接存储，类似链表）

按照文件内记录的组织方式，对文件的分类

(1) 无序文件

1° 记录的存储顺序与记录的内容无关，每次都写入到文件的末尾处

2° 插入：直接插入到末尾处

3° 查找：从第一条记录开始扫描

4° 删除：

定长记录：查找要删除的记录，将文件的最后一条记录移动到被删除位置，更新最后一条记录的位置

非定长记录：每个记录内部增加一个是否已经被删除过的标志位，要删除时只将标志位置为1，然后定期清理记录

5° 修改

定长记录：查找位置，直接修改

非定长记录：先删除，再插入

(2) 顺序文件

1° 排序键：用于排序的属性，一般选取经常需要查找的属性作为排序键

2° 查找：

查找排序键：二分查找

查找非排序键：逐个扫描

3° 插入

在块的首部维持一张偏移量表，用于按顺序的保存对应的记录的位置。插入时，记录直接插入到文件末尾，调整偏移量表，使之有序

4° 删除

每个记录内部增加一个是否已经被删除过的标志位，要删除时只将标志位置为1，然后定期清理记录

5° 修改

对非排序键的修改 + 定长记录 --> 查找位置，直接修改

其他情况：先删除，后插入

(3) 散列文件

1° 插入：根据散列键计算散列桶编号，然后插入到该散列桶对应的磁盘块中。如果磁盘块已满，则申请一个新的磁盘块，形成链表

2° 查找：

散列键查找：计算散列桶编号，如果块中有多个记录，则沿着链表顺序查找

非散列键查找：顺序查找

3° 删除：先查找，再直接删除

4° 修改

非散列键：先查找，再修改

散列键：先删除，再插入

存在问题：只适合散列键上的等值比较查找，其他情况和无序文件查找相同

多表聚集文件

(1) 一般情况下，一个关系对应一个实际文件

(2) 多表聚集文件；为了加快查找、连接操作，将所有的关系存储在一个大文件中，由DBMS统一管理

(3) 示例

  不使用聚集

  id   name  sex              id  course  score
  001  张三   男              001   数学    80
  002  李四   男              001   英语    85
                              002   数学    75
                              002   英语    70

  使用聚集
  
  001   张三   男
  001   数学   80
  001   英语   85
  002   李四   男
  002   数学   75
  002   英语   70

假设磁盘块足够大，不使用聚集时至少要2次IO操作；使用聚集时使用1次IO操作

(4) 如果关系中元组很多，聚集文件的优势将更加明显。当一个磁盘块放不下所有元组时，应尽可能放在相邻的磁盘

(5) 聚集文件特别加速了连接操作，但是减慢了单表查询。因此应该添加其他结构，例如用指针将所有单表中的记录连接起来