前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >外部排序的方法

外部排序的方法

作者头像
week
发布2018-08-24 17:05:00
1.1K0
发布2018-08-24 17:05:00
举报
文章被收录于专栏:用户画像

在实际应用中,由于外存设备的不同,通常又可分配磁盘文件排序和磁带文件排序两大类。磁带排序和磁盘排序的基本步骤相类似,主要的不同之处在于初始归并段在外存介质中的分布方式,磁盘是直接存储设备,磁带是顺序存储设备。下面以磁盘为例进行说明。

文件通常是按块存储在磁盘上的,操作系统也是按块对磁盘上的信息进行读写的。因为磁盘读写的机械动作所需时间远远超过内存运算的时间(相比而言,可以忽略不计)。因此,在外部排序过程中的时间代价主要考虑访问磁盘的次数,即I/O次数。

外部排序通常采用归并排序方法。它包括两个相对独立的阶段:首先,根据内存缓冲区的大小,将外存上含n个记录的文件分成若干个长度为h的子文件,依次读入内存并利用有效的内存排序方法对它们进行排序,并将排序后得到的有序子文件重新写回外存,通常称这些有序子文件为归并段或顺串;然后,对这些归并段进行逐趟归并,使归并段(有序的子文件)逐渐由小到大,直至得到整个有序文件为止。

例如,一个含有2000个记录的文件,每个磁盘可容纳250个记录,则该文件包含8个磁盘块。然后对该文件作二路归并排序,每次往内存读入两个磁盘块,排序后再写回磁盘。若把内存工作区等分为3个缓冲区。其中的两个为输入缓冲区。一个为输出缓冲区,在内存中利用简单二路归并merge函数实现二路归并。

首先,从参加归并排序的两个输入归并段R1和R2中分别读入一个块,放入输入缓冲区1和输入缓冲区2中。然后,在内存中进行二路归并,归并出来的对象顺序存放在输出缓冲区中。若输出缓冲区存满,则将其内的对象顺序写到归并段(R1')中,再将该输出缓冲区清空,继续存放归并后的对象。若某一个输入缓冲区的对象取空,则从对应的输入归并段中再读取下一块(这种情况在第一趟归并时不会出现),继续参加归并。如此继续,直到两个输入归并段中对象全部读入内存并都归并完成为止。当R1和R2归并完后,再归并R3和R4、R5和R6、最后归并R7和R8,这算作一趟归并。再把上一趟的结果R1'、R2'、R3'、R4'两两归并,这又是一趟归并。最后把R1''和R2"两两归并,这又是一趟归并。最后把R1"和R2"两两归并段归并,结果得到最终的有序文件,一共进行了3趟归并。

在外部排序中实现两两归并时,不仅要调用merge过程,而且要进行外存的读写;由于不可能将两个有序段及归并结果段同时存放在内存中,需要不停地将数据读出、写入磁盘,这将耗费大量的时间。一般情况下:

Tes=R*Tis+d*Tio+S*(n-1)*Tmg

其中,r是初始归并段个数,Tis是对每一个初始归并段进行内部排序的时间,d是访问外存块的次数,Tio是每一个块的存取时间,S是归并趟数,n是每趟参加二路归并的记录个数,Tmg是每作一次内部归并,取得一个关键字最小记录的时间。显然磁盘存取的时间远远大于内部排序和内部归并的时间,因此要提高外排序的速度,应着力减少d,即I/O次数。

由于外存上信息的读写是以“物理块”为单位的,且每个物理块可容纳250个记录,可知每一趟归并需要进行8次读和8次写,3趟归并加上内部排序时所需进行的读写使得在外排中总共需要进行16*4=64次的读写。故上述二路归并排序的总时间为:

8*Tis+64*Tio+3*2000Tmg

对于上例,若采用思路归并排序只需要2趟归并,外排时总的读写次数便减至2*16+16=48.因此,增大归并路数,可以减少归并趟数,从而减少总的I/O次数。

一般地,对r个初始归并段,作m路平衡归并,归并树可用严格m叉树(即只有度为m与度为0的结点的m叉树)来表示。第一趟可将r个初始并段归并为[r/m]个归并段,以后每一趟归并将L个归并段归并成【L/m】(向下取整)个归并段,直到最后形成一个大的归并段为止。树的高度=【logm r】(向下取整)=归并趟数S.

可见只要增大归并路m,或减少初始归并段个数r,都能减少归并趟数S,以减少读写磁盘次数d,达到提高外部排序速度的目的。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016年09月09日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档