教案数据结构d11

1、第11章 外部排序第 2 页为什么需要文件管理和外排序？文件结构（file structure）对于在外存中存储的数据，其数据结构就称为文件结构数据量太大不可能同时把它们放到内存中需要把全部数据放到磁盘中文件的各种运算外排序是针对磁盘文件所进行的排序操作提高文件存储效率和运算效率11.1 外存信息的存取第 3 页主存储器和外存储器主存储器 ( primary memory 或 main memory，简称内存/主存) 随机访问存储器( RAM )高速缓存( cache )视频存储器( video memory ) 外存储器 ( peripheral storage 或 secondary st

2、orage，简称外存) 硬盘 / 软盘 / 磁带 / U盘11.1 外存信息的存取第 4 页外存的特点优点：永久存储能力、便携性 缺点：访问时间长访问磁盘中的数据比访问内存慢五六个数量级。 因此，在对外存的数据结构及其上的操作时，必须遵循的基本原则是：尽量减少访外次数！ 11.1 外存信息的存取第 5 页磁盘的物理结构11.1 外存信息的存取第 6 页磁盘磁片的组织11.1 外存信息的存取第 7 页磁道的组织（交错法）11.1 外存信息的存取（a）没有扇区交错 （b）以3为交错因子第 8 页磁盘的存取步骤选定某个盘片组选定某个柱面这需要把磁头移动到该柱面 ，这个移动过程称为寻道( seek )

3、 确定磁道 确定所要读写的数据在磁盘上的准确位置这段时间一般称为旋转延迟( rotational delay 或者rotational latency )真正进行读写11.1 外存信息的存取第 9 页磁盘的存取时间11.1 外存信息的存取间时输传磁道寻道时间磁臂等待时间数据信息磁盘旋转方向第 10 页磁盘的存取时间磁盘访问时间主要由寻道时间、旋转延迟时间和数据传输时间组成。 寻道时间（Seek time）tseek：是移动磁盘臂，定位到正确磁道所需的时间。旋转延迟时间tla：是等待被存取的扇区出现在读写头下所需的时间。传输时间twm：是传输一个字符的时间。TI/O=tseek + tla +

4、twm11.1 外存信息的存取第 11 页磁带运行示意11.1 外存信息的存取 磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁带上的信息读入计算机，或把计算机中的信息写在磁带上。第 12 页外存文件的组织 文件是一些记录的集合，每个记录可由一个或多个数据项组成。 数据项也称为字段，或属性。11.1 外存信息的存取职工号姓名性别职务婚姻状况工资156张东男程序员未婚7800860李珍女分析员已婚8900510赵莉女程序员未婚6900950陈萍女程序员未婚6200620周力男分析员已婚10300第 13 页逻辑文件对高级程序语言的编程人员而言，磁盘中可以随机访问的文件被当作一段连续的字节，且可将

5、这些字节结合起来构成记录，这种文件被称为逻辑文件。物理文件实际存储在磁盘中的物理文件通常不是一段连续的字节，而是成块地分布在整个磁盘中。文件管理器是操作系统的一部分，当应用程序请求从逻辑文件中读取数据时，它将这些逻辑位置映射为磁盘中具体的物理位置。11.1 外存信息的存取第 14 页文件的逻辑结构文件是记录的集合。当一个文件的各个记录按照某种次序排列起来时，各记录间就自然地形成了一种线性关系。 因而，文件可看成是一种线性结构。 11.1 外存信息的存取文件的物理结构顺序结构顺序文件 计算寻址结构散列文件 带索引的结构带索引文件 第 15 页文件的物理结构顺序文件：记录按照自然次序依次存储存取第

6、 i 个记录之前，必须存取第 i-1 个记录新记录只能插在文件尾部更新文件中的数据必须将整个文件复制一遍散列文件： 通过散列函数和冲突处理索引文件：带有按关键字数据项进行索引的文件虚拟存储存取方式VSAM：索引顺序文件，用B+树作为动态索引树11.1 外存信息的存取第 16 页文件上的操作检索：在文件中寻找满足一定条件的记录 修改：对记录中某些数据值进行修改。若对关键字进行修改，就相当于删除加插入。插入：向文件中增加一个新记录。 删除：从文件中删去一个记录 。排序 ：对指定好的数据项，按其值的大小把文件中的记录排成序列。常用的是按关键字的排序。 11.1 外存信息的存取第 17 页外排序( e

7、xternal sort )外存设备上（文件）的排序技术由于文件很大，无法把整个文件的所有记录同时调入内存中进行排序，即无法进行内排序 外部排序算法的主要目标：尽量减少读写磁盘的次数 11.2 外部排序的方法第 18 页磁盘排序过程文件分成若干尽可能长的初始顺串；逐步归并归顺串，最后形成一个已排序的文件。顺串 用某种有效的内排序方法对文件的各段进行初始排序，这些经过排序的段通常称为顺串(run) ，它们生成之后立即被写回到外存上。11.2 外部排序的方法第 19 页外排序通常由两个相对独立的阶段组成：文件形成尽可能长的初始顺串逐趟归并顺串，最后形成对整个数据文件的排列文件外排序所需要的时间由三

8、部分组成：内部排序所需要的时间外存信息读写所需要的时间内部归并所需要的时间 11.2 外部排序的方法第 20 页外排序的时间开销外排序总时间=内部排序产生初始顺段 时间 +外存信息读写时间 +内部归并所需时间 = m*tis + d*tio + s*utmg其中：tis：得到一个初始归并段进行内部排序所需时间m：经过内排序后得到的初始归并段的数量tio：进行一个外存读写的时间d：总的读写次数utmg：对 u 个记录进行内部归并所需时间s：归并的趟数11.2 外部排序的方法第 21 页减少外存信息的读写次数是提高外部排序效率的关键 对同一个文件而言，进行外排序所需读写外存的次数与归并趟数有关系假

9、设有m个初始顺串，每次对k个顺串进行归并，归并趟数为logkm为了减少归并趟数，可以从两个方面着手：减少初始顺串的个数m增加归并的顺串数量k11.2 外部排序的方法第 22 页磁盘排序基本做法的描述假定文件有4500个记录：R1, R2, , R4500。磁盘上 1 块（如 1 个扇区）的尺寸是250个记录，该文件总共需用磁盘的 18 个扇区。内存可供用于排序的空间是 750 个记录大小。排序过程如下： 每次从磁盘读入 3 块（750个记录）到内存，利用内排序算法将它们排好序，然后写回磁盘。这样，磁盘上就得到了6个初始有序段A1、A2、A6。 11.2 外部排序的方法初始有序段A11750有序

10、段A27511500有序段A315012250有序段A422513000有序段A530013750有序段A637514500第 23 页把内存按 250 个记录的长度分成三部分：两部分为输入缓冲区，一部分为输出缓冲区。先对 A1 和 A2 进行归并：先将每段的一块（250个有序记录）读到内存的两个输入缓冲区，用归并排序算法实施排序。边排序，边把结果写到输出缓冲区。输出缓冲区满时，写入磁盘；当一个输入缓冲区的内容归并完腾空时，将该有序段的下一块读入该缓冲区继续归并。这样继续，直到把 A1 和 A2 全归并完毕，磁盘里出现一个含1500个记录的新有序段。11.2 外部排序的方法第 24 页完成一次

11、归并后，对A3和A4、A5和A6实施相同归并。整个文件经一趟归并，在磁盘上得到三个各含1500记录的有序段。11.2 外部排序的方法初始有序段A11750有序段A27511500有序段A315012250有序段A422513000有序段A530013750有序段A6375145003000个记录第2趟归并1500个记录1500个记录1500个记录第1趟归并4500个记录第3趟归并继续进行归并：第 2 趟，第 3 趟。第 25 页分析在一切相同的条件下，如果把例中的 2-路归并改变成 3-路或 6-路（当然，这时所需要的内存缓冲区个数将会变化），那么总的读写磁盘次数就会下降。11.2 外部排序的

12、方法归并路数 总读写磁盘次数 归并趟数 2 132 3 3 108 2 6 72 1第 26 页k-路归并k-路归并时，在 k 个关键字中选最小值。通常可采用直接选择排序方法，对关键字做 k-1次比较。问题：在直接选择排序时许多关键字间进行了不止一次的重复比较，导致时间的浪费。解决办法：若在选择最小者时，将比较结果保留下来，后面需要时加以利用，就可减少比较次数，减少磁盘输入/输出所耗费的时间，从而使排序的速度提高。11.2 外部排序的方法第 27 页选择树选择树是一棵二叉树，该树中的分支结点是该结点两个孩子中的较小者，根结点是这棵树各叶结点中的最小者。11.2 外部排序的方法109206899

13、01769681768 为选择次小者，可把该记录原始位置（叶结点）设成一个大于所有关键字的值“+”。进行输出-调整。最小值+由下往上调整2098k=8时第 28 页选择树为选取下一个最小者，只需对根结点到该叶结点所经路径上的各结点与其左或右兄弟进行比较和适当的调整即可，其他结点保持原样。11.2 外部排序的方法10920+899017892081798+9k=8时输出8，并调整99输出9，并调整+10109输出9，并调整+1710第 29 页胜者树：结点记录胜者信息利用选择树的思想，对有序段进行k-路归并。树的每个叶结点对应一个输入缓冲区，它总是各有序段在归并过程中的当前关键字，分支结点是它的

14、两个孩子结点中键值较小的那个。根结点是树中键最小的。输出根结点后，用该记录所在有序段的下一个关键字填补它的位置，并作适当调整。这样的调整不会涉及到整棵树，而只需考虑从根结点到该位置的路径上的各个结点。11.2 外部排序的方法第 30 页胜者树当前8个待归并有序段的前3个关键字值：10, 15, 19 9, 20, 38 20, 22, 34 6, 15, 258, 17, 50 18, 21, 44 90, 95, 108 24, 32, 6611.2 外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.17

15、50.2144.95108.3266.第 31 页胜者树对 8 个并有序段进行一次归并。先输出根结点上关键字为 6 的记录，它原位于最底层编号为 11 的叶结点处，用15顶替。局部调整 。11.2 外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.1525.1598第 32 页胜者树输出原位于编号为12的记录8，并用它后面值为“17”的关键字进行顶替。做适当调整.11.2 外部排序的方法1092068189024696824681234567891011121314

16、151519.2038.2234.1525.1750.2144.95108.3266.1525.159850.171717938.20101010输出 9，再继续进行调整.第 33 页胜者树：实现胜者树是完全二叉树，算法实现时，采用顺序存储结构保存。非叶结点保存的是“胜者”在树中对应结点的下标（编号）。11.2 外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.9111215111211保存：胜者对应叶结点的编号第 34 页败者树：结点记录败者信息败者树是一棵有 k

17、 个叶结点的二叉树，分支结点存放该结点两个孩子中的较大者（败者），而让较小者（胜者）参加上一层的比较，即胜者“出线”参加下一轮比赛。每个败者都停在自己失败的赛场上。根结点里存放最终的失败者。11.2 外部排序的方法第 35 页败者树：结点记录败者信息根结点里仍存放最终的失败者。11.2 外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.60在根的上面附加一个结点，存放全局的优胜者冠军。第 36 页败者树：结点记录败者信息输出“6”，之后进行调整。11.2 外

18、部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.601525.201598第 37 页败者树：说明 胜者树在人工处理时比较直观，但在程序实现时，特别是在重构比赛树时寻找对手，不如败者树效率高。 由于全胜者（最小元素）所在的从叶到根的内结点中，都记录着被全胜者所击败的对手，所以输出最小元素并由后继者代替之后，重构选择树时，很容易找到要比较的“对手”，所以，实现替代选择合并的算法也就简单了。11.2 外部排序的方法第 38 页败者树：实现是完全二叉树，采用顺序存

19、储。非叶结点保存的是败者在树中对应结点的下标（编号）。11.2 外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.6081013149151211第 39 页算法描述（P298算法11.1）typedef int LoserTreek; /采用顺序存储结构typedef struct KeyType key; ExNode, External k+1 ; / 外结点，存待归并关键字void K_Merge( LoserTree &ls, External &

20、b ) / ls0.k-1：保存非叶结点 / b0bk-1：败者树的 k 个叶结点，k个归并段的当前关键字11.2 外部排序的方法第 40 页算法描述（P298算法11.1）void K_Merge( LoserTree &ls, External &b ) 11.2 外部排序的方法for ( i=0; i= 0 ) if ( bs.key b ls0 .key ) s ls t ; / s：新的胜者的下标 t = t/2; ls 0 = s; / 保存全胜者下标第 42 页算法描述（P299算法11.3）void CreateLoserTree( LoserTree &ls ) / b 0

21、. k-1：为完全二叉树 ls 的叶结点，保存键值 / 沿从叶结点到根的 k 条路径将 ls 调整为败者树11.2 外部排序的方法b k = MINKEY; / 设为最小值for ( i=0; i=0; -i ) Adjust( ls, i ); / 从bk-1 到 b0调整败者第 43 页为一个待排文件创建尽可能大的初始顺串，可以大大减少扫描遍数和外存读写次数。归并顺序的安排也能影响读写次数，把初始顺串长度作为权，其实质就是Huffman树最优化问题。11.2 外部排序的方法第 44 页k路归并是每次将k个顺串合并成一个排好序的顺串。一般情况下，对m个初始顺串进行k路归并时归并趟数为logkm。增加每次归并的顺串数量 k 可减少归并趟数。选择树是完全二叉树，有两种类型：赢者树和败者树。 11.2 外部排序的方法第 45 页多路归并11.2 外部排序的方法三路归并第 46 页问题在合并阶段，如果初始的顺串不等长，应该如何挑选合并对象，减少读块次数，以加快合并速度？实例初始有9个顺串，其长度（块数）依次为：8, 23, 9, 15, 3, 12, 2, 6, 17。采用3路合并。应该如何进行才能使读盘次数最少？11.3 最佳归并树第 47 页实例初始有9个顺串，其长度（块数）依次为：8, 23, 9, 1