文件 在现代计算机的应用领域中,数据处理是一个重要方面。 数据处理是对各种类型的大批量的数据进行收集、存 储、排序、检索、计算、修改、输出等分析和加工处 理的过程。例如,用计算机进行企业管理、财务工资 管理、仓库物资管理、情报检索、统计报表等都涉及 到数据存放到外存储器上。有时,为了长期保存原始 数据和加工处理过的数据,也需要将这些数据以文件 的形式存放在外存上。学完本章读者应能掌握文件的 概念、逻辑特性、物理结构和基本操作
文件 在现代计算机的应用领域中，数据处理是一个重要方面。 数据处理是对各种类型的大批量的数据进行收集、存 储、排序、检索、计算、修改、输出等分析和加工处 理的过程。例如，用计算机进行企业管理、财务工资 管理、仓库物资管理、情报检索、统计报表等都涉及 到数据存放到外存储器上。有时，为了长期保存原始 数据和加工处理过的数据，也需要将这些数据以文件 的形式存放在外存上。学完本章读者应能掌握文件的 概念、逻辑特性、物理结构和基本操作
文件的基本概念 与文件有关的基本术语有以下几个: 数据项:数据项是文件中可使用的不可分的最小数据单 位。一个数据项由若干个字符或数字组成,它代表某 事物的一种属性。数据项又称为数据域。例如,个 人书库中的登录号、书号、书名、作者、出版社和价 格等等都是数据项。 记录:记录是由一个或多个数据项根据一定的目的而组 成的数据项集合。例如,由登录号、书号、书名、作 者、出版社和价格等数据项组成的集合是一个职工记 录 文件:文件是大量性质相同的记录组成的集合
文件的基本概念 与文件有关的基本术语有以下几个： 数据项：数据项是文件中可使用的不可分的最小数据单 位。一个数据项由若干个字符或数字组成，它代表某 一事物的一种属性。数据项又称为数据域。例如，个 人书库中的登录号、书号、书名、作者、出版社和价 格等等都是数据项。 记录：记录是由一个或多个数据项根据一定的目的而组 成的数据项集合。例如，由登录号、书号、书名、作 者、出版社和价格等数据项组成的集合是一个职工记 录。 文件：文件是大量性质相同的记录组成的集合
关键字:是能够区别文件中各记录的域。通常,把能唯一标识一个记录的关键字称为主关键字;而那些不能唯 标识一个记录的关键字称为次关键字;由两个以上关键字组成的关键字称为复合关键字 在表10-1所给出的个人书库文件中,各个记录的结构相同,信息长度相同,因而我们将这样的记录称为定长记录 由定长记录组成的文件称为定长记录文件。除了定长记录文件之外,还有不定长记录文件。例如,在学生学 籍管理文件中,不同的年级,或者不同专业的学生,所修的课程数和课程名称都不一样。这样,反映各个学 生的学科成绩的记录长度和结构就不相同,这类记录称为不定长记录。由不定长记录组成的文件叫做不定长 记录文件。 文件的主要操作有以下几种 插入:将一个记录插入某个文件中 删除:从某个文件中删除一个或多个记录 修改:用指定值去修改满足修改条件的某个(或多个)记录中的某个(或多个)数据项的内容 检索:对文件的检索是通过对文件的各种查询来实现的。对表10-1所示的个人书库文件,有以下4种类型的查询: 查询1(Q1):这是简单查询,它规定只查询一个关键字的值。例如查询“书名为数据结构”的书有哪些?又如查 询“书号=1P1787的书是哪一个记录?过些都是简单查询。 查询2(Q2):这是范围性查询,它规定在单个关键字值的某个范围内进行查询。例如查询“价格>2200的书是 哪些记录? 查询3(Q3):这是函数性查询,它要求先规定单个关键字值的某个因数,然后对该函数的值进行查询。例如规定 某个关键字的平均值,可查询“关键字值大于这个平均值”的有哪些记录?对于个人书库文件,可查询“价 格>所有图书的平均价格”是哪些图书? 查询4(Q4):这是布尔查询,即对上述查询Q1Q3用逻辑运算符and(与)、or(或)、mot(非)组合起来进行布 尔查询。例如查询“(书名为数据结构)or(书号=TP1787)”的图书是哪些记录? 在以上的文件操作中,检索是最基本的操作,其它操作都在检索的基础之上进行。 文件的操作又可以分成实时处理和批量处理两种方式。采用实时处理方式时,对任何一类查询或更新,系统应 立即进行响应和处理,一般应在几秒钟之内作出反应。例如,对于一个飞机订票系统,必须在几秒钟之内能 给客户的查询请求输出飞机班次和座位的状况等信息,即应是一个实时检索系统。同理,飞机订票系统应采 用实时更新方式,即当某个航班一个座位被预订出后,应立即更新该航班的座位文件,以免发生差错。采用 批量处理方式,系统不必立即进行响应和处理,因为这时的响应时间不是一个重要因素。例如,对于学生学 籍管理系统来说,可在期末考试全部结束后只进行一次批量处理。 文件的物理结构是指文件在外存上的组织形式。按照文件的检索方式和物理结构,文件分为顺序文件、索引文件 索引顺序文件、直接存取文件、链接文件和多重链表文件、倒排文件。按所存放的外存设备,文件又可以分 为磁带文件和磁盘文件等几类。下面分别加以讨论
关键字：是能够区别文件中各记录的域。通常，把能唯一标识一个记录的关键字称为主关键字；而那些不能唯一 标识一个记录的关键字称为次关键字；由两个以上关键字组成的关键字称为复合关键字。 在表10-1所给出的个人书库文件中，各个记录的结构相同，信息长度相同，因而我们将这样的记录称为定长记录。 由定长记录组成的文件称为定长记录文件。除了定长记录文件之外，还有不定长记录文件。例如，在学生学 籍管理文件中，不同的年级，或者不同专业的学生，所修的课程数和课程名称都不一样。这样，反映各个学 生的学科成绩的记录长度和结构就不相同，这类记录称为不定长记录。由不定长记录组成的文件叫做不定长 记录文件。 文件的主要操作有以下几种： 插入：将一个记录插入某个文件中。 删除：从某个文件中删除一个或多个记录。 修改：用指定值去修改满足修改条件的某个（或多个）记录中的某个（或多个）数据项的内容。 检索：对文件的检索是通过对文件的各种查询来实现的。对表10-1所示的个人书库文件，有以下4种类型的查询： 查询1（Q1）：这是简单查询，它规定只查询一个关键字的值。例如查询“书名为数据结构”的书有哪些？又如查 询“书号=TP1787”的书是哪一个记录？过些都是简单查询。 查询2（Q2）：这是范围性查询，它规定在单个关键字值的某个范围内进行查询。例如查询“价格＞22.00”的书是 哪些记录？ 查询3（Q3）：这是函数性查询，它要求先规定单个关键字值的某个因数，然后对该函数的值进行查询。例如规定 某个关键字的平均值，可查询“关键字值大于这个平均值”的有哪些记录？对于个人书库文件，可查询“价 格＞所有图书的平均价格”是哪些图书？ 查询4（Q4）：这是布尔查询，即对上述查询Q1~Q3用逻辑运算符and（与）、or（或）、not（非）组合起来进行布 尔查询。例如查询“（书名为数据结构）or（书号=TP1787）”的图书是哪些记录？ 在以上的文件操作中，检索是最基本的操作，其它操作都在检索的基础之上进行。 文件的操作又可以分成实时处理和批量处理两种方式。采用实时处理方式时，对任何一类查询或更新，系统应 立即进行响应和处理，一般应在几秒钟之内作出反应。例如，对于一个飞机订票系统，必须在几秒钟之内能 给客户的查询请求输出飞机班次和座位的状况等信息，即应是一个实时检索系统。同理，飞机订票系统应采 用实时更新方式，即当某个航班一个座位被预订出后，应立即更新该航班的座位文件，以免发生差错。采用 批量处理方式，系统不必立即进行响应和处理，因为这时的响应时间不是一个重要因素。例如，对于学生学 籍管理系统来说，可在期末考试全部结束后只进行—次批量处理。 文件的物理结构是指文件在外存上的组织形式。按照文件的检索方式和物理结构，文件分为顺序文件、索引文件、 索引顺序文件、直接存取文件、链接文件和多重链表文件、倒排文件。按所存放的外存设备，文件又可以分 为磁带文件和磁盘文件等几类。下面分别加以讨论
顺序文件 顺序文件是物理结构最简单的文件,也是数据处理历史上最早使用的文件结构。顺序文件的各个记录按输入的先 后次序存放在外存中的连续存储区。为了便于检索和修改文件,文件中的记录通常按关键字的大小次序排列, 成为按关键字排序的顺序文件。表10-1所示的个人书库文件是按关键字登录号排序的文件,它存放到外存的 连续存储区后便得到一个按关键字排序的顺序文件。 顺序文件的基本优点是在连续存取时速度较快。例如,如果文件中的第个记录刚被存取过,而下一个要存取的 记录就是第计1个记录,则此次存取将会很快完成。磁带是比较适用于这种应用的外存设备。存放于磁带上的 文件也只能是顺序文件,这是由磁带的物理特性决定的。存放于磁盘上的文件,既可以是顺序文件,也可以 是索引结构或其它结构类型的文件。 当需要对磁带顺序文件进行检索时,一般是采用顺序扫描的方式来检索满足査询条件的记录。例如,若要检索第i 个记录,则必须先检索前面的计1个记录。为了提高平均检索效率,可采用批量处理技术。如果将对文件的多 个检索请求加以积累和排序,则形成一个称为待办文件(或事务文件)的文件。如果将被查询的文件称为主 文件,则批量检索就是按照待办文件的要求成批地检索主文件。批量检索对于实时应用来说是不适宜的,因 为实时查询要求响应时间快,而在很短的时间间隔内,积累的批处理文件规模太小,不能表现出它的优越性 在磁带顺序文件中插入记录,只能加在文件的末尾,不能插在两个原有记录之间。修改记录,即使在新旧记录 长的情况下,将新记录写在旧记录的位置上,一般不但不可能完全重合,甚至还会破坏邻近记录的信息。因 此,修改一个磁带文件,需要用另一条磁带将原文件复制过来,在复制过程中进行插入、删除、修改记录的 操作。为了提高效率,修改一个顺序文件,也采用成批处理技术。这种批量修改方式很适用于银行帐户结算 管理系统。例如,可把一天的零星支取和存入分别作为记录收集在一起,构成为一个待办文件,在当天下班 时再按照待办文件进行批量修改主文件(头天下班修改过的主文件)的工作,便得到一个新主文件
顺序文件 顺序文件是物理结构最简单的文件，也是数据处理历史上最早使用的文件结构。顺序文件的各个记录按输入的先 后次序存放在外存中的连续存储区。为了便于检索和修改文件，文件中的记录通常按关键字的大小次序排列， 成为按关键字排序的顺序文件。表10-1所示的个人书库文件是按关键字登录号排序的文件，它存放到外存的 连续存储区后便得到一个按关键字排序的顺序文件。 顺序文件的基本优点是在连续存取时速度较快。例如，如果文件中的第i个记录刚被存取过，而下一个要存取的 记录就是第i+1个记录，则此次存取将会很快完成。磁带是比较适用于这种应用的外存设备。存放于磁带上的 文件也只能是顺序文件，这是由磁带的物理特性决定的。存放于磁盘上的文件，既可以是顺序文件，也可以 是索引结构或其它结构类型的文件。 当需要对磁带顺序文件进行检索时，一般是采用顺序扫描的方式来检索满足查询条件的记录。例如，若要检索第i 个记录，则必须先检索前面的i-1个记录。为了提高平均检索效率，可采用批量处理技术。如果将对文件的多 个检索请求加以积累和排序，则形成一个称为待办文件（或事务文件）的文件。如果将被查询的文件称为主 文件，则批量检索就是按照待办文件的要求成批地检索主文件。批量检索对于实时应用来说是不适宜的，因 为实时查询要求响应时间快，而在很短的时间间隔内，积累的批处理文件规模太小，不能表现出它的优越性。 在磁带顺序文件中插入记录，只能加在文件的末尾，不能插在两个原有记录之间。修改记录，即使在新旧记录等 长的情况下，将新记录写在旧记录的位置上，一般不但不可能完全重合，甚至还会破坏邻近记录的信息。因 此，修改一个磁带文件，需要用另一条磁带将原文件复制过来，在复制过程中进行插入、删除、修改记录的 操作。为了提高效率，修改一个顺序文件，也采用成批处理技术。这种批量修改方式很适用于银行帐户结算 管理系统。例如，可把一天的零星支取和存入分别作为记录收集在一起，构成为一个待办文件，在当天下班 时再按照待办文件进行批量修改主文件（头天下班修改过的主文件）的工作，便得到一个新主文件
索引文件 顺序文件的査询速度很慢。采用索引文件可以提高检索效率。实际上,在前面的章节中我们已经运用了索引技术。 索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之,索引指出了记录在存储器中的存储地址 设记录R的关键字为K;,R在外存中的存储地址为A,则(K,A)称为记录R的索引项。索引表(简称索引 是索引项的集合。如果文件中的每个记录都有一个索引项,则这样的索引称为稠密索引。如果多个记录只有 索引项,则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录, 索引文件在外存(磁盘、磁鼓等)中可分为两个存储区:索引区和记录区(数据区)。索引表中的索引项顺序存 放到记录区;记录区按关键字大小次序排列的索引文件称为索引顺序文件。对于索引顺序文件,可以不必使 用稠密索引,只为一个记录块(含多个有序记录)建立一个索引项。记录区不按关键字大小次序排列的索引 文件称为索引非顺序文件,这时应使用稠密索引。图10-2所示的个人书库(价格)索引文件,是一个索引非 顺序文件。 通常,索引项所含的数据信息比记录少得多,因而索引所需的存储空间比文件本身(记录区)所需要的存储空 间少得多。在文件的记录数较少的情况下,可以为每个记录建立一个索引项。文件建立时,开辟一个索引区 般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时,在索引区相应登入一个索引项,即 的缓冲,接关键走行丙部排序。最后将排序好的索分项序写回到磁盘上的素 将索引区中的索引读入内 根据关键字查找索引文件的记录分两步进行。第1步,访问外存的索引区,将索引读入内存缓冲区,使用顺序查 找或折半查找法找出所查记录在外存数据区中的地址,这一过程称为预查找。第2步,如果在预查中已找到了 所查记录的地址,则第2次访问外存,根据已查到的地址,读取所查的记录 删除一个记录时,只需删去相应的索引项,而不必移动数据区中的记录。插入一个新记录时,将记录放到记录 区的末尾,在索引区登记相应的索引项,并对索引区中的索引项重新排序
索引文件 顺序文件的查询速度很慢。采用索引文件可以提高检索效率。实际上，在前面的章节中我们已经运用了索引技术。 索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之，索引指出了记录在存储器中的存储地址。 设记录Ri的关键字为Ki，Ri在外存中的存储地址为Ai，则（Ki，Ai）称为记录Ri的索引项。索引表（简称索引） 是索引项的集合。如果文件中的每个记录都有一个索引项，则这样的索引称为稠密索引。如果多个记录只有 一个索引项，则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录。 索引文件在外存（磁盘、磁鼓等）中可分为两个存储区：索引区和记录区（数据区）。索引表中的索引项顺序存 放在索引区中，但为了便于检索，索引项一般按关键字的大小次序排列。文件中的记录按输入的先后次序存 放到记录区；记录区按关键字大小次序排列的索引文件称为索引顺序文件。对于索引顺序文件，可以不必使 用稠密索引，只为一个记录块（含多个有序记录）建立一个索引项。记录区不按关键字大小次序排列的索引 文件称为索引非顺序文件，这时应使用稠密索引。图10-2所示的个人书库（价格）索引文件，是一个索引非 顺序文件。 通常，索引项所含的数据信息比记录少得多，因而索引所需的存储空间比文件本身（记录区）所需要的存储空 间少得多。在文件的记录数较少的情况下，可以为每个记录建立一个索引项。文件建立时，开辟一个索引区， 一般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时，在索引区相应登入一个索引项，即 把该记录的关键字（主关键字）和记录的存储地址顺序写入索引区。文件建立后，将索引区中的索引读入内 存的缓冲区，按关键字进行内部排序。最后将排序好的索引项顺序写回到磁盘上的索引区。 根据关键字查找索引文件的记录分两步进行。第1步，访问外存的索引区，将索引读入内存缓冲区，使用顺序查 找或折半查找法找出所查记录在外存数据区中的地址，这一过程称为预查找。第2步，如果在预查中已找到了 所查记录的地址，则第2次访问外存，根据已查到的地址，读取所查的记录。 删除一个记录时，只需删去相应的索引项，而不必移动数据区中的记录。插入一个新记录时，将记录放到记录 区的末尾，在索引区登记相应的索引项，并对索引区中的索引项重新排序
索引顺序文件 在实际应用中,索引顺序文件是被经常采用的 种文件结构。它是在顺序文件的基础上,用增 加索引的办法而形成的。文件中的记录按关键 字大小顺序存放在磁盘的连续或相邻的存储区 中。由于记录按关键字排序,因此不必为每 个记录设立一个索引项,而把文件划分为若干 个记录块,只为每块中关键字最大(或最小) 的记录设置一个索引项。这种组织文件的方法 称为索引顺序存取法ISAM( Indexed Sequential Access Method),用这种方法建立起来的索引 文件称为ISAM文件,它是一种专为磁盘存取 设计的文件组织方式
索引顺序文件 在实际应用中，索引顺序文件是被经常采用的一 种文件结构。它是在顺序文件的基础上，用增 加索引的办法而形成的。文件中的记录按关键 字大小顺序存放在磁盘的连续或相邻的存储区 中。由于记录按关键字排序，因此不必为每一 个记录设立一个索引项，而把文件划分为若干 个记录块，只为每块中关键字最大（或最小） 的记录设置一个索引项。这种组织文件的方法 称为索引顺序存取法ISAM（Indexed Sequential Access Method），用这种方法建立起来的索引 文件称为ISAM文件，它是一种专为磁盘存取 设计的文件组织方式
由于磁盘是以盘组、柱面和磁道三级地址存取的设备, 则可对磁盘上的数据文件建立盘组、柱面和磁道三级 索引。文件的记录在同一盘组上存放时,应先集中放 在一个柱面上,然后再顺序存放在相邻的柱面上,对 同一柱面,则应按盘面的次序顺序存放。例如图10-3 为存放在一个磁盘组上的ISAM文件。每个柱面建立 个磁道索引,每个磁道索引项由两部分组成:基本索 引项和溢出索引项,如图10-4所示,每一部分都包括 关键字和指针两项,前者表示该磁道中最大关键字, 后者指示该磁道中第一个记录的位置,柱面索引的每 个索引项也由关键字和指针两部分组成,前者表示 该柱面中最末一个记录的关键字(最大关键字),后 者指示该柱面上的磁道索引位置。柱面索引存放在某 个柱面上,若柱面索引较大,占多个磁道时,则可建 立柱面索引的索引—主索引
由于磁盘是以盘组、柱面和磁道三级地址存取的设备， 则可对磁盘上的数据文件建立盘组、柱面和磁道三级 索引。文件的记录在同一盘组上存放时，应先集中放 在一个柱面上，然后再顺序存放在相邻的柱面上，对 同一柱面，则应按盘面的次序顺序存放。例如图10-3 为存放在一个磁盘组上的ISAM文件。每个柱面建立一 个磁道索引，每个磁道索引项由两部分组成：基本索 引项和溢出索引项，如图10-4所示，每一部分都包括 关键字和指针两项，前者表示该磁道中最大关键字， 后者指示该磁道中第一个记录的位置，柱面索引的每 一个索引项也由关键字和指针两部分组成，前者表示 该柱面中最末一个记录的关键字（最大关键字），后 者指示该柱面上的磁道索引位置。柱面索引存放在某 个柱面上，若柱面索引较大，占多个磁道时，则可建 立柱面索引的索引——主索引
在ISAM文件上检索记录时,先从主索引出发找到相应的柱面索引,再从柱面索引找到记录所在柱 面的磁道索引,最后从磁道索引找到记录所在磁道的第一个记录的位置,由此出发在该磁道 上进行顺序查找直到找到为止;反之,若找遍该磁道而不存在此记录,则表明该文件中无此 记录。 从图10-3中还可以看到,每个柱面上还开辟有一个溢出区;并且,磁道索引项中有溢出索引项 这是为插入记录所设置的。由于ISAM文件中记录是按关键字顺序存放的,则在插入记录时需 移动记录并将同一磁道上最后一个记录移至溢岀区,同时修改磁道索引项。通常溢出区可有 三种设置方法:(1)集中存放 整个文件设一个大的单一的溢出区;(2)分散存放 每个柱面设一个溢出区;(3)集中与分散相结合—溢出时记录先移至每个柱面各自的溢出 区,待满之后再使用公共溢出区。 每个柱面的基本区是顺序存储结构,而溢出区是链表结构。同一磁道溢出的记录由指针相链,该 磁道索引的溢出索引项中的关键字指示该磁道溢出的记录的最大关键字;而指针则指示在溢 出区中的第一个记录。图10-5所示为插入记录和溢出处理的具体例子。 其中(a)为插入前的某一柱面上的状态;(b)为插入R、时,将第二道中关键字大于65的记录顺 次后移,且使R。溢出至溢出区的情况:(c)为插入R。之后的状态,此时2道的基本索引项的 关键字改为80,且溢出索引项的关键字改为90,其指针指向第4道第一个记录即R;(d)是 相继插入R和R3后的状态。在R5插入在第3道的第一个记录的位置而使R14溢出。而由于 80<83<90,则R3被直接插入到溢出区,作为第2道在溢出区的第一个记录,并将它的指针指 向R9的位置,同时修改第2道索引的溢出索引项的指针指向Rs3 ISAM文件中删除记录的操作比插入简单得多,只需找到待删除的记录,在其存储位置上作删除 标记即可,而不需要移动记录或改变指针。则在经过多次的增删后,文件的结构可能变得很 不合理。此时,大量得记录进入溢出区,而基本区中又浪费很多空间。因此,通常需要周期 地整理ISAM文件。把记录读入内存,重新排列,复制成一个新的ISAM文件,填满基本区而 空出溢出区
在ISAM文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱 面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道 上进行顺序查找直到找到为止；反之，若找遍该磁道而不存在此记录，则表明该文件中无此 记录。 从图10-3中还可以看到，每个柱面上还开辟有一个溢出区；并且，磁道索引项中有溢出索引项， 这是为插入记录所设置的。由于ISAM文件中记录是按关键字顺序存放的，则在插入记录时需 移动记录并将同一磁道上最后一个记录移至溢出区，同时修改磁道索引项。通常溢出区可有 三种设置方法：（1）集中存放——整个文件设一个大的单一的溢出区；（2）分散存放—— 每个柱面设一个溢出区；（3）集中与分散相结合——溢出时记录先移至每个柱面各自的溢出 区，待满之后再使用公共溢出区。 每个柱面的基本区是顺序存储结构，而溢出区是链表结构。同一磁道溢出的记录由指针相链，该 磁道索引的溢出索引项中的关键字指示该磁道溢出的记录的最大关键字；而指针则指示在溢 出区中的第一个记录。图10-5所示为插入记录和溢出处理的具体例子。 其中（a）为插入前的某一柱面上的状态；（b）为插入R65时，将第二道中关键字大于65的记录顺 次后移，且使R90溢出至溢出区的情况；（c）为插入R65之后的状态，此时2道的基本索引项的 关键字改为80，且溢出索引项的关键字改为90，其指针指向第4道第一个记录即R90；（d）是 相继插入R95和R83后的状态。在R95插入在第3道的第一个记录的位置而使R145溢出。而由于 80<83<90，则R83被直接插入到溢出区，作为第2道在溢出区的第一个记录，并将它的指针指 向R90的位置，同时修改第2道索引的溢出索引项的指针指向R83。 ISAM文件中删除记录的操作比插入简单得多，只需找到待删除的记录，在其存储位置上作删除 标记即可，而不需要移动记录或改变指针。则在经过多次的增删后，文件的结构可能变得很 不合理。此时，大量得记录进入溢出区，而基本区中又浪费很多空间。因此，通常需要周期 地整理ISAM文件。把记录读入内存，重新排列，复制成一个新的ISAM文件，填满基本区而 空出溢出区
直接存取文件 直接存取文件指的是利用杂凑(Hash)法进行组织的文件。它类似于哈希表, 即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录 散列到存储设备上,故又称散列文件。 与哈希表不同的是,对于文件来说,磁盘上的文件记录通常是成组存放的。 若干个记录组成一个存储单位,在散列文件中这个存储单位叫作桶 个桶能存放的逻辑记录的总数称为桶的容量。假如一个桶能存放m个记 录,即m个同义词的记录可以存放在同一地址的桶中,当第m+1个同义词 出现时则发生“溢出”。处理溢出也可采用哈希表中处理冲突的各种方 法;但对散列文件,主要采用链地址法 当发生“溢出”时,需要将第m+1个同义词存放到另一个桶中,通常称此桶 为“溢出桶”;相对地,称前m个同义词存放的桶为“基桶”。溢出桶 可以有多个,它们和基桶大小相同,相互之间用指针相链接。当在基桶 中没有找到待査记录时,就顺指针所指到溢出桶中进行査找。因此,希 望同一散列地址的溢岀桶和基桶在磁盘上的物理位置不要相距太远,最 好在同一柱面上
直接存取文件 直接存取文件指的是利用杂凑（Hash）法进行组织的文件。它类似于哈希表， 即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录 散列到存储设备上，故又称散列文件。 与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的。 若干个记录组成一个存储单位，在散列文件中这个存储单位叫作桶。一 个桶能存放的逻辑记录的总数称为桶的容量。假如一个桶能存放m个记 录，即m个同义词的记录可以存放在同一地址的桶中，当第m+1个同义词 出现时则发生“溢出”。处理溢出也可采用哈希表中处理冲突的各种方 法；但对散列文件，主要采用链地址法。 当发生“溢出”时，需要将第m+1个同义词存放到另一个桶中，通常称此桶 为“溢出桶”；相对地，称前m个同义词存放的桶为“基桶”。溢出桶 可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶 中没有找到待查记录时，就顺指针所指到溢出桶中进行查找。因此，希 望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最 好在同一柱面上
桶编号 基桶 溢出桶 28N1421 198933 13556 图10.6散列文件示例 例如,某件有18个记录,其关键字分别为28,19,13, 93,89,14,55,69,8,9,16,21,33,81,62,11 34,35。用除留余数法作哈希函数H(key)= key MOD7。 桶的容量m=3,基本桶数=7,由此得到的散列文件如图 10-6所示
例如，某i文件有18个记录，其关键字分别为28，19，13， 93，89，14，55，69，8，9，16，21，33，81，62，11， 34，35。用除留余数法作哈希函数H（key）=key MOD 7。 桶的容量m=3，基本桶数=7，由此得到的散列文件如图 10-6所示。 桶编号 基桶 溢出桶 28 14 21 35 ^ 8 ^ 93 9 16 ^ ^ 81 11 ^ 19 89 33 ^ 13 55 69 62 34 ^ 图 10-6 散列文件示例