虚拟存储 虚拟存储 虚拟地址空闻 物理内存地址 虚拟存储( virtual memory 使得程序员能够使用比实际内存 更大的内存空间 ■磁盘中存储虚拟存储器的全部的 内容,根据存储器的访问需要把 块读入内存缓冲池。 85外排序 外排序( external sort) 基本概念 ■外存设备上(文件的排序技术 ①置换选择排序 文件很大 二路外排序 无法把整个文件的所有记录同时 调入内存中进行排序,即无法进 多路归并选择树 行内排序 ■外部排序算法的主要目标是尽量 减少读写磁盘的次数 北大敏息 张幅写 关键码索引排序 磁盘排序过程 ■索引文件( index file)中 关键码与指针一起存储 毆捷行赌排序方暮姦往槊 指针标识相应记录在原数据文件中的位置 对索引文件进行排序,所需要的I/0操作 磁盘排序过程: ■文件分成若干尽可能长的初始顺 索引文件比整个数据文件小很多。 在一个索引文件中,只针对关键码排序 ( key sort)。 逐步归并顺串归,最后形成一个 咔序的文件8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 虚拟存储 „ 虚拟存储( virtual memory ) 使得程序员能够使用比实际内存 更大的内存空间。 „ 磁盘中存储虚拟存储器的全部的 内容，根据存储器的访问需要把 块读入内存缓冲池。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 虚拟存储 „ 系统运行到某一时刻，虚拟地址空间中有5个页被读入到物 理内存中，现在如果需要对地址为24k-28k的页进行访 问，就必须替换掉当前物理内存中的一个页框。 0-4k 4k-8k 8k-12k 12k-16k 16k-20k 0-4k 4k-8k 8k-12k 12k-16k 16k-20k 20k-24k 24k-28k 28k-32k 32k-36k 36k-40k 虚拟地址空间 物理内存地址 1 3 0 4 2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 8.5 外排序 „ 基本概念 „ 置换选择排序 „ 二路外排序 „ 多路归并-----选择树 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 外排序( external sort ) „ 外存设备上(文件)的排序技术 „ 文件很大 „ 无法把整个文件的所有记录同时 调入内存中进行排序，即无法进 行内排序 „ 外部排序算法的主要目标是尽量 减少读写磁盘的次数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 关键码索引排序 „ 索引文件( index file )中 „ 关键码与指针一起存储 „ 指针标识相应记录在原数据文件中的位置 „ 对索引文件进行排序，所需要的I/O操作 更少 „ 索引文件比整个数据文件小很多。 „ 在一个索引文件中，只针对关键码排序 ( key sort )。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 磁盘排序过程 „ 顺串：用内排序方法对文件的各 段进行初始排序，并存放在外存 磁盘排序过程： „ 文件分成若干尽可能长的初始顺 串； „ 逐步归并顺串归，最后形成一个 已排序的文件