本讲（第六章）简要说明
授课目的与要求：掌握无序文件，顺序文件，HASH 文件的文件组织方法。授课难点：支持文件空间动态变化的HASH 技术。
作业安排：p.206 1,2,5,9
文件组织和存储结构
为数据库存储模式设计提供多种可供选择的文件组织方法是本讲要解决的问题。按一定的逻辑结构（如顺序、树）组织关联的数据记录（逻辑文件），并用体现逻辑结构的物理存储形式存到物理设备上。目标：根据用户和系统设计要求，组织时空综合性能最佳，易于维护的文件，为数据库提供方便、灵活的文件访问。
Diameter: 1 inch →15 inchesCylinders:100 →2000Surfaces:1 (CDs) →
2 (floppies) →几十
Sector Size:512B →50K Capacity:360 KB (old floppy)
→几百GB
6. 2 文件组织的基本概念
１. 文件的基本组织方法：
２
•
•
•无序文件顺序文件HASH 文件文件的性能度量：文件存储空间利用率操作的时间耗费(典型操作）文件的重新组织（周期和难易）.
３. 逻辑记录与物理记录
物理记录------内外存交换数据的最小单
位，对磁盘而言，控制部件可寻址的最小单位是块（扇段）。一般来说，在同一系统中，块的大小是相同的,512、1024或2048字节等。
逻辑记录：组织用户逻辑文件的基本单
位。
例如：学生基本情况文件中，一个现实学生的学号、姓名、年龄、性别、籍贯等数据组成的一个逻辑记录。
4. 组块方式：
怎样将逻辑记录存放到物理记录（块）中去。
1）定长记录固定组块。
2）变长记录不跨界。
3）变长记录跨界。
4）块列。
Microsoft Office Access将存储在表中的数据划分成大小为2 K的数据页，每个页面包含了一个或多个记录，但记录不能跨越页面。Access采用可变长记录作为标准存储方法，并且可以通过主关键字来对记录进行排序。因为长度可变，所以每个记录都只占据了存储它的实际数据所需的空间。每个页都包含一个头指针，用以创建数据页链表。头指针中包含了两个指针，一个指向它的前驱页面，另一个指向它的后续页面。新的数据将被添加到表的最后一页，这个页面被填满后，则再增加一个页面。Memo和OLE Object字段在页中可以跟记录中的其余
部分分开存储。
6.2 文件的组织方式
无序文件顺序文件散列文件
二、顺序文件
逻辑上按某一关键字（一般为主关键字）顺序排列的文件。
1. 物理结构
1）向量结构，地址连续的空间，地址
顺序实现逻辑顺序。
2）链结构，指针维持逻辑顺序。
3）块链结构，块中地址顺序表示逻辑
顺序，块间指针链接维持逻辑顺序。
顺序文件
2. 查找
1）顺序扫描（向量结构、链结构、块链结构）2）分块查找（向量结构、块链结构）3）折半查找（向量结构）4）探查（向量结构）
HASH文件
2. HASH方法的步骤3. 溢出处理
开寻址列分离溢出区分布溢出区
4. 溢出分析
5. 主要HASH 算法
HASH 文件
6. 支持文件空间动态变化的HASH 技术1）动态HASH 2）可扩展HASH 3）线性HASH
6. 支持文件空间动态变化的HASH 技术
桶号以二进制整数表示，开始时所有记录放在一个桶中。当一个桶溢出时分裂为两个桶：桶号最高位为0的放在一个桶中，桶号最高位为1的放在另一个桶中。当这些桶中又有某个溢出时，该桶又分裂为两个桶按次高位为0的放在一个桶中，次高位为1的放在另一个桶中。
When do we expand file?total # of slots If U > threshold then increase
(and maybe i ) n = U
查询过程：
BEGIN
IF n=0{/*n为溢出计数}THEN m←H j (k)
ELSE
BEGIN
m ←H j (k);
IF m
THEN m ←H j+1(k);END;
搜索值为m 的桶；
END
本讲（第六章）简要说明
授课目的与要求：掌握无序文件，顺序文件，HASH 文件的文件组织方法。授课难点：支持文件空间动态变化的HASH 技术。
作业安排：p.206 1,2,5,9
文件组织和存储结构
为数据库存储模式设计提供多种可供选择的文件组织方法是本讲要解决的问题。按一定的逻辑结构（如顺序、树）组织关联的数据记录（逻辑文件），并用体现逻辑结构的物理存储形式存到物理设备上。目标：根据用户和系统设计要求，组织时空综合性能最佳，易于维护的文件，为数据库提供方便、灵活的文件访问。
Diameter: 1 inch →15 inchesCylinders:100 →2000Surfaces:1 (CDs) →
2 (floppies) →几十
Sector Size:512B →50K Capacity:360 KB (old floppy)
→几百GB
6. 2 文件组织的基本概念
１. 文件的基本组织方法：
２
•
•
•无序文件顺序文件HASH 文件文件的性能度量：文件存储空间利用率操作的时间耗费(典型操作）文件的重新组织（周期和难易）.
３. 逻辑记录与物理记录
物理记录------内外存交换数据的最小单
位，对磁盘而言，控制部件可寻址的最小单位是块（扇段）。一般来说，在同一系统中，块的大小是相同的,512、1024或2048字节等。
逻辑记录：组织用户逻辑文件的基本单
位。
例如：学生基本情况文件中，一个现实学生的学号、姓名、年龄、性别、籍贯等数据组成的一个逻辑记录。
4. 组块方式：
怎样将逻辑记录存放到物理记录（块）中去。
1）定长记录固定组块。
2）变长记录不跨界。
3）变长记录跨界。
4）块列。
Microsoft Office Access将存储在表中的数据划分成大小为2 K的数据页，每个页面包含了一个或多个记录，但记录不能跨越页面。Access采用可变长记录作为标准存储方法，并且可以通过主关键字来对记录进行排序。因为长度可变，所以每个记录都只占据了存储它的实际数据所需的空间。每个页都包含一个头指针，用以创建数据页链表。头指针中包含了两个指针，一个指向它的前驱页面，另一个指向它的后续页面。新的数据将被添加到表的最后一页，这个页面被填满后，则再增加一个页面。Memo和OLE Object字段在页中可以跟记录中的其余
部分分开存储。
6.2 文件的组织方式
无序文件顺序文件散列文件
二、顺序文件
逻辑上按某一关键字（一般为主关键字）顺序排列的文件。
1. 物理结构
1）向量结构，地址连续的空间，地址
顺序实现逻辑顺序。
2）链结构，指针维持逻辑顺序。
3）块链结构，块中地址顺序表示逻辑
顺序，块间指针链接维持逻辑顺序。
顺序文件
2. 查找
1）顺序扫描（向量结构、链结构、块链结构）2）分块查找（向量结构、块链结构）3）折半查找（向量结构）4）探查（向量结构）
HASH文件
2. HASH方法的步骤3. 溢出处理
开寻址列分离溢出区分布溢出区
4. 溢出分析
5. 主要HASH 算法
HASH 文件
6. 支持文件空间动态变化的HASH 技术1）动态HASH 2）可扩展HASH 3）线性HASH
6. 支持文件空间动态变化的HASH 技术
桶号以二进制整数表示，开始时所有记录放在一个桶中。当一个桶溢出时分裂为两个桶：桶号最高位为0的放在一个桶中，桶号最高位为1的放在另一个桶中。当这些桶中又有某个溢出时，该桶又分裂为两个桶按次高位为0的放在一个桶中，次高位为1的放在另一个桶中。
When do we expand file?total # of slots If U > threshold then increase
(and maybe i ) n = U
查询过程：
BEGIN
IF n=0{/*n为溢出计数}THEN m←H j (k)
ELSE
BEGIN
m ←H j (k);
IF m
THEN m ←H j+1(k);END;
搜索值为m 的桶；
END