清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 记录名R 键 1296:姓名:A 性别:男 逻辑地址 出生年月:1971年9月 工资:7元 属性 属性值 图72记录组成例
图7.2 记录组成例
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 图中,1296是名为R的记录在文件中的逻辑地址, 姓名:A”是该记录的键,而“性别’,“出生 年月’,‘工资’等是该记录的属性,紧跟在这 些后面的是属性值。一个记录可以有多个键名,每 个键名可对应于多项属性。再者,根据各系统设计 的要求不一样,记录既可以是定长的,也可以是变 长的。记录的长度可以短到一个字符,也可以长到 一个文件,这要由系统设计人员确定。 常用的记录式结构文件有以下几种: (1)连续结构;(2)多重结构;(3)转置结构;(4)顺 序结构。 下面分别介绍这几种结构
图中，1296是名为R 的记录在文件中的逻辑地址， ‘姓名 : A ’是该记录的键，而 ‘性别’，‘出生 年月’，‘工资’ 等是该记录的属性，紧跟在这 些后面的是属性值。一个记录可以有多个键名，每 个键名可对应于多项属性。再者，根据各系统设计 的要求不一样，记录既可以是定长的，也可以是变 长的。记录的长度可以短到一个字符，也可以长到 一个文件，这要由系统设计人员确定。 常用的记录式结构文件有以下几种: (1) 连续结构； (2) 多重结构； (3) 转置结构； (4) 顺 序结构。 下面分别介绍这几种结构
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS (1)连续结构 连续结构是一种把记录按生成的先后顺序连续排列 的逻辑结构。连续结构的特点是适用性强,可用于 所有文件,且记录的排列顺序与记录的内容无关。 这有利于记录的追加与变更。但是,连续结构文件 的搜索性能较差,例如要找出某个指定键的记录时, 系统必须对文件全体进行搜索。 (2)多重结构 如果把记录按键和记录名排列成行列式结构,则一 个包含n个记录名、m个(mn)个键的文件构成 mn维行列式(如图73)。其中,如果第(1i≤m行 和第j(1≤≤n)列所对应的位置上为1,则表示键Ki 在记录R中;反之,则表示键K不在记录R中。另 外,同一个键也可以同时属于不同记录
(1) 连续结构 连续结构是一种把记录按生成的先后顺序连续排列 的逻辑结构。连续结构的特点是适用性强，可用于 所有文件 ，且记录的排列顺序与记录的内容无关。 这有利于记录的追加与变更。但是，连续结构文件 的搜索性能较差，例如要找出某个指定键的记录时， 系统必须对文件全体进行搜索。 (2) 多重结构 如果把记录按键和记录名排列成行列式结构，则一 个包含n个记录名、m个(m≤n)个键的文件构成一 m*n维行列式(如图7.3)。其中，如果第i(1≤i≤m) 行 和第j(1≤j≤n) 列所对应的位置上为1，则表示键Ki 在记录 R中; 反之,则表示键Ki不在记录 Rj 中。另 外，同一个键也可以同时属于不同记录
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS ri re R2 KK 10 0 图73文件的记录名和键构成的行列式
图7.3 文件的记录名和键构成的行列式
显然,如果只按行列式结构来排列记录,将会浪费 较多的存储空间。从而,我们把行列式中那些为零 的项去掉,并以键Ki为队首,以包含键Ki的记录为 队列元素来构成一个记录队列。对于一个有m个键 的队列来说,这样的队列有m个。这m个队列构成 了该文件的多重结构( multi list。如图74所示。 (3)转置结构 在图74的多重结构中,每个队列中和键直接相连的 只有一个记录。这种结构虽然在探索时要优于连续 结构,但在探索某一特定记录时,必须在找到该记 录所对应的键之后,再在该键所对应的队列中顺序 查找。与此相反,转置结构把含有相同键的记录指 针全部指向该键,也就是说,把所有与同一键对应 的记录的指针连续地置于目录中该键的位置下(图 75)。转置结构最适合于给定键后的记录搜索
显然，如果只按行列式结构来排列记录，将会浪费 较多的存储空间。从而，我们把行列式中那些为零 的项去掉，并以键Ki为队首，以包含键Ki的记录为 队列元素来构成一个记录队列。对于一个有m个键 的队列来说，这样的队列有m个。这m个队列构成 了该文件的多重结构(multi_list)。如图7.4所示。 (3) 转置结构 在图7.4的多重结构中，每个队列中和键直接相连的 只有一个记录。这种结构虽然在探索时要优于连续 结构，但在探索某一特定记录时，必须在找到该记 录所对应的键之后，再在该键所对应的队列中顺序 查找。与此相反，转置结构把含有相同键的记录指 针全部指向该键，也就是说，把所有与同一键对应 的记录的指针连续地置于目录中该键的位置下(图 7.5)。转置结构最适合于给定键后的记录搜索