外部排序数据结构.ppt
《外部排序数据结构.ppt》由会员分享,可在线阅读,更多相关《外部排序数据结构.ppt(21页珍藏版)》请在优知文库上搜索。
1、外存信息的存取外部排序的方法多路平衡归并p外存储器类型:n1、顺序存取的设备(磁带)、顺序存取的设备(磁带)n2、随机存取的设备(磁盘)、随机存取的设备(磁盘)磁带工作原理:p将磁带盘放在磁带机上,驱动器控制磁带盘转动,带动磁带向前移动,通过读/写头就可以向读出或写入信息。磁带信息存贮p可记下各种文字信息和二进制信息,按字符组存放,而不是按字符存放。读写的启动停止:p磁带不是连续运转的设备,由于读/写需要稳定时进行,因此当启动/停止时,需要一个加速/减速的过程,这个过程磁带不写入任何内容,因而相邻的两个字符组之间要留一个空白,叫做间隙p所需时间由两部分组成:nTi/o = ta+ntwnta为
2、延迟时间,即读写头到传输信息所在的物理块的为延迟时间,即读写头到传输信息所在的物理块的起始位置所需的时间起始位置所需的时间ntw为传输一个一个字符所需的时间为传输一个一个字符所需的时间n特点:特点:p查找速度慢,检索和修改信息不方便,主要用于处理变化小,只进行顺序存取的大量数据p磁盘信息的存取磁盘是一种直接存取的存储设备p磁盘读写块所需的时间组成:nTi/o = tseek + ta + n * twm tseek:读写头定位的时间 ta:等待信息快的初始位置转到读写头下的时间 twm:传输时间外部排序的应用对象保存在外存储器上的信息量很大的数据记录文件。外排序与内排序的差别p内部排序充分利用
3、内存可以随机存取的特点,如n希尔排序中,相隔di的记录关键字可作比较;n堆排序中,完全二叉树中父Ri与子R2i,R2i+1可比n快速排序中,需正向和逆向访问记录序列p外存信息的定位和存取受其物理特性的限制外部排序的实现手段在排序过程中,进行多次内外存之间的数据交换p由两个独立的阶段组成n将外存含n个记录的文件分成若干长度为l的子文件或段,依次读入内存并用内部排序方法排序,将排序后的有序子文件重新写入外存,称为归并段或顺串n对这些归并段进行逐趟归并,(有序子文件)由小变大,直到获得整个有序文件步骤步骤p生成若干初始归并串/顺串(文件预处理)n把含有把含有n个记录的文件,按内存缓冲区大小分成若干长
4、度为个记录的文件,按内存缓冲区大小分成若干长度为L的子文件(段);的子文件(段);n分别调入内存用有效的内排序方法排序后送回外存;分别调入内存用有效的内排序方法排序后送回外存;p 多路合并n对初始归并串逐趟合并,直至最后在外存上得到整个有序文件为止对初始归并串逐趟合并,直至最后在外存上得到整个有序文件为止例例某文件共10000个记录,设每个物理块可以容纳200个记录,内存缓冲区可以容纳5个物理块 1)经过10次内排序后得到10个初始归并段R1R10 2)采用两路归并,需四趟可以得到排好序的文件 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 2000 2000 2000 2000
5、 2000 4000 4000 8000 10000p外存上的信息的读/写以“物理块”为单位,假设每个物理块可容纳200个记录,则每一趟归并所需进行50次“读”和50次“写”,4趟归并并加上内部排序所需进行的读写使得外排序总共需进行500读/写p外部排序所需的总的时间= 内部排序所需的时间(内部排序所需的时间(m*tis) + 外存信息读写的时间(外存信息读写的时间(d*tio) + 内部归并所需的时间(内部归并所需的时间(s*utmg)tis::得到一个厨师归并段进行内部排序所需时间:得到一个厨师归并段进行内部排序所需时间tio:进行一次外存读:进行一次外存读/写所需时间写所需时间utmg:



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 外部 排序 数据结构
