直接存取文件(Direct Access File) 又叫散列文件。利用散列技术组织文件。处理 类似散列法，但它是存储在外存上的。 文件记录的逻辑顺序与物理顺序不一定相同。 通过记录的关键码可直接确定该记录的地址。 使用散列函数把关键码集合映射到地址集合时 往往会产生地址冲突，处理冲突有两种处理方 式： ◆按桶散列 ◆可扩充散列 26
直接存取文件 (Direct Access File) • 又叫散列文件。利用散列技术组织文件。处理 类似散列法，但它是存储在外存上的。 • 文件记录的逻辑顺序与物理顺序不一定相同。 通过记录的关键码可直接确定该记录的地址。 • 使用散列函数把关键码集合映射到地址集合时， 往往会产生地址冲突，处理冲突有两种处理方 式： ◆ 按桶散列 ◆ 可扩充散列 26
(1)按桶散列 文件中的记录成组存放，若干个记录组成一个 存储单位，称之为桶。假若一个桶能存放个 记录，则m个互为同义词的记录可以存放在同 一地址的桶中。当第m+1个同义词出现时，才 发生“溢出” (a)溢出链 当发生“溢出”时，将第m+1个同义词存放 到“溢出桶”。并称存放前m个同义词的桶 为“基桶”。氵 溢出桶和基桶大小相同。当在 基桶中检索不成功，就循指针到溢出桶中检 索。 27
(1) 按桶散列 • 文件中的记录成组存放，若干个记录组成一个 存储单位，称之为桶。假若一个桶能存放m个 记录，则m个互为同义词的记录可以存放在同 一地址的桶中。当第m+1个同义词出现时，才 发生“溢出”。 (a) 溢出链 ◆ 当发生“溢出”时，将第m+1个同义词存放 到“溢出桶”。并称存放前m个同义词的桶 为“基桶”。溢出桶和基桶大小相同。当在 基桶中检索不成功，就循指针到溢出桶中检 索。 27
桶大小为3的谥出桶链表示例 基桶编号基桶区 溢出桶编号 溢出桶区 070 015 337 988 512 204 246 817 117 390 597 177 575 540 435 3 262 157 362 4 116 613 5 285 635 208 06 923 076 在这种散列文件中删除记录时，因为可能需要 重新链接，所以只需做一个逻辑删除标记即可 待系统做周期性重构时再做物理删除。 28
桶大小为3的溢出桶链表示例 • 在这种散列文件中删除记录时，因为可能需要 重新链接，所以只需做一个逻辑删除标记即可， 待系统做周期性重构时再做物理删除。 28 070 ∧ 512 204 246 O1 597 177 ∧ 262 157 ∧ 116 613 ∧ 285 635 208 O2 923 076 ∧ 0 1 2 3 4 5 6 O1 O2 O3 O4 O5 O6 O7 015 337 988 O3 817 117 390 O4 575 540 435 ∧ 362 ∧ 基桶编号 基桶区 溢出桶编号 溢出桶区
(b)分布式溢出空间 0 溢出桶按照一定的间 1 2 基桶 隔分布在基桶之间。 3 如果有一个基桶溢出 4 5 溢出桶 了，系统就将记录存 6 放在下一个溢出桶中。 7 基桶 1 如果溢出桶自己溢出 9 了，则使用下一个相 10 11 溢出桶 继的溢出桶，这需要 第二次溢出处理。 1 基桶 分布式溢出桶 29
(b) 分布式溢出空间 ◆ 溢出桶按照一定的间 隔分布在基桶之间。 如果有一个基桶溢出 了，系统就将记录存 放在下一个溢出桶中。 ◆ 如果溢出桶自己溢出 了，则使用下一个相 继的溢出桶，这需要 第二次溢出处理。 29 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 分布式溢出桶 基桶 基桶 基桶 溢出桶 溢出桶
如果系统对基桶按0,1,2,3,4,5，.进行编号 在按间隔G=5插入溢出桶后，可按下列公式 按字节求出各个桶的实际存储地址： 桶的地址=+B-》 其中，B是在文件中第0号桶的起始地址，B是 每个桶的字节数。在括号中的除数5表示每隔5 个基桶安排一个溢出桶。 (心)相继溢出法 ◆此方法不设置溢出桶。当记录应存放的桶溢 出时，溢出记录存放到下一个相继的桶中。 30
• 如果系统对基桶按0, 1, 2, 3, 4, 5, …进行编号， 在按间隔 G = 5 插入溢出桶后，可按下列公式 按字节求出各个桶的实际存储地址： • 其中，B0是在文件中第0号桶的起始地址，B是 每个桶的字节数。在括号中的除数5表示每隔5 个基桶安排一个溢出桶。 (c) 相继溢出法 ◆ 此方法不设置溢出桶。当记录应存放的桶溢 出时，溢出记录存放到下一个相继的桶中。 30 . = + + 5 i B B i 桶的地址 0