文件组织
Last updated
Last updated
外存中，数据库以文件形式组织，而文件又是由记录组成。
文件组织：记录在物理文件中的实现。
文件组织的两种方式：定长记录和变长记录
就是每条记录都是占用一定长度的字节数。记录的排列也就是一张表格每一行有相同的长度，以一行为单元进行增加删除等修改操作。
优点：起止点容易计算，不需搜索匹配。
存在的两个问题：
删除：删除后是在其位置补充一个记录还是忽略这个位置
长度：若物理上每个块的大小不等于每个记录的长度倍数，则必然在读这样的记录时要访问两个块。
删除方法：
删除记录后，把记录依次上移。缺点是移动次数过多。
把最后的记录补到删除的位置。只需移动一次，但是和方法一一样，都需要移动结点，操作不灵活，出于灵活的考虑必然会想到使用指针，也就是第三种方法。
首先，文件增设“文件首部”，其中有一个指针指向第一个被删除的记录位置，所有被删除记录的位置都用指针链接起来，构成“空闲记录链表”。缺点是这些指针链接的记录被称为“被栓记录”，若被删记录被删掉，则指向记录的指针称为“悬挂指针”，所指空间称为“垃圾”，也就是别人无法使用而又被空闲着。
插入方法：可以根据删除的方法而定，直接插入尾部，或插入到空位置。
实际应用中定长记录格式文件较多，但为了增强文件的灵活性，在数据库系统中，有时需要文件中的记录是变长格式。变长记录的表示有字节串形式和定长形式两种。
尾标志法：把每个记录看成连续的字节串，然后在每个记录的尾部附加“记录尾标志符^”，表明记录结束。
记录长度法：记录的开始加一个记录长度的字段来实现，读取数据时以此作为记录结束与否的标志。
保存不同类型记录于一个文件，每个字段可以变长，允许重复字段。使用文件文件或二进制文件实现，缺点是删除操作和插入操作均很费力。
字节串表示形式缺点：
每条记录长度不一，被删除后的位置难于使用
记录要增长很难
reserved space 预留空间技术
Pointers 指针技术
预留空间技术 Reserved space ——暂时不用的空着
取所有记录中最长的一个记录的长度作为存储空间的记录长度，来存储变长记录。对于预留空间，仍如同定长格式的表格状。
缺点：如果每个记录的差别很大，就会造成大量空间的浪费。
指针技术
解决记录长度差很大的方法，省去过多的空间浪费。每个定长记录后面增加指针指向在上一方法中可以合并为同一记录的其他记录。被指向的整体称为溢出块。
若干个定长记录组成变长记录，每个链表一个记录，如同一章由若干节组成。
