开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第五课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/15861
第五课（三）
内容介绍
一、Data Guides
二、Existence of Multiple DataGuides
三、Annotations
四、Strong Data Guides
五、Mapping Long Records to Pages
六、Allocation and Free-Space Management
七、文件组织
八、文件中的记录组织
七、文件组织
文件组织是数据库保存为若干文件的集合。其中文件是记录的序列，记录是字段的序列。记录方法有定长记录、变长记录、指针法。
1.定长记录
简单方法：
（1）记录 i 从字节 n * ( i - 1 ) 开始存储,其中 n 是记录大小。
（2）记录存取简单，但记录可能跨块。唯一的变化是不允许记录跨越块边界。
删除记录 i 可选则的方法:
（1）将记录 i+1 ,...， n 前移成 i ...， n-1 。
（2）将记录 n 前移成 i 。
（3）不移动记录，而是将所有自由记录链成一条自由链表。
2.自由链表
自由链表是指在文件头中存储第一条被删记录的地址，然后在第一条被删记录中，存储第二条被删记录的地址，等等。这些存储的地址可视为指针，因为它们“指向”记录的位置。它是更有效利用空间的表示法，可以重新利用自由记录的正常字段空间来存储指针（使用中的记录则不存储指针）。
3.变长记录
数据库系统中在多种情况下需要变长记录。一个文件中需要存储多种记录类型，允许一个或多个变长字段的记录类型，允许重复字段的记录类型，以上几种情况都需要用到变长记录。
它的方法有预留空间法、字节串表示法、指针法、 Slotted Page 结构.
（1）预留空间法
它是利用具有已知最大长度的定长记录，较小记录中的未用空间用 null 或 end - of - record 符号填充。
（2）字节串表示法
它在每条记录末尾附加控制字符 end - of - record ( L )，缺点是难以删除或增长。
（3）指针法
变长记录可用若干通过指针念在一起的定长记录表示，即使是最大记录，长度未知时也可以使用。缺点是除了链中首记录，其他所有记录中都可能有空间浪费。解决方法是文件中采用两种块，锚块和溢出块，锚块包含链中的首记录，溢出块包含链中其他记录。
解决方法是文件中采用两种块，锚块和溢出块，锚块包含链中的首记录，溢出块包含链中其他记录。
（4） Slotted Page 结构
Slotted page 页头包含记录登记项数目、块中自由空间末端、每条记录的位置和大小。记录可以在页内移动以便保持记录间的连续存储，但页头中的登记项必须更新。指针不能直接指向记录，而是指向该记录在页头中的登记项。
八、文件中的记录组织
文件中的记录组织有堆、顺序、散列、聚簇、动机。堆，记录可至于文件中的任何有空间的地方。顺序，记录按顺序存储，基于每条记录在搜索键上的值。散列，对记录的某些属性 k 计算散列函数 h（ k ） ，计算结果决定该记录应该置于文件的哪个块中。每一个关系的记录可存储在单独的文件中，但在聚簇文件组织下，多个关系的记录可存储于同一文件中。动机，相关联的记录存储在同一块中可减少磁盘 I/O 。
1.顺序文件组织
它适用于需要顺序处理整个文件的应用，文件中的记录按搜索键排序。
删除时可利用指针链。插入时需要确定带插入记录的位置。若有自由空间，则在该处插入，若无自由空间，则插入到溢出块，两种情况都有，则需要更新指针链。需要不时重组文件，以恢复物理存储的顺序。
2.聚簇文件组织
简单的文件结构将每个关系存储在一个单独的文件中，利用聚簇文件组织可以将多个关系存储在一个文件中。
有利于涉及 depositor 和 customer 的查询，以及涉及单个客户和他的账户的查询，对只涉及 customer 的查询不好(可用指针链，见上图)，容易导致变长记录。
