讲义说明教案讲稿d

1、11.111.1 外存信息的存取外存信息的存取l外部排序：外部排序：指的是大文件的排序，即待指的是大文件的排序，即待排序的记录存储在外部存储器上，在排排序的记录存储在外部存储器上，在排序过程中需要多次进行内、外存间的交序过程中需要多次进行内、外存间的交换。换。l外部排序的机制是由外部排序的机制是由外部存储器存取信外部存储器存取信息息的特点决定。的特点决定。第 2 页第 3 页主存储器和外存储器主存储器和外存储器l主存储器主存储器 ( primary memory 或或 main memory，简称内存简称内存/主存主存) 随机访问存储器随机访问存储器( RAM )高速缓存高速缓存( cache

2、 )。 l外存储器外存储器 ( peripheral storage 或或 secondary storage，简称外存，简称外存) 硬盘硬盘 / 软盘软盘 / 磁带磁带 / U盘盘11.111.1 外存信息的存取外存信息的存取第 4 页l磁盘的物理结构磁盘的物理结构11.111.1 外存信息的存取外存信息的存取11.111.1 外存信息的存取外存信息的存取第 5 页第 6 页l磁盘磁片的组织磁盘磁片的组织11.111.1 外存信息的存取外存信息的存取第 7 页l磁盘的存取步骤磁盘的存取步骤:选定某个盘片组选定某个盘片组选定某个柱面选定某个柱面n这需要把磁头移动到该柱面这需要把磁头移动到该柱面

3、 ，这个移动这个移动过程称为过程称为寻道寻道( seek ) 确定磁道确定磁道 确定所要读写的数据在磁盘上的准确位置确定所要读写的数据在磁盘上的准确位置n这段时间一般称为这段时间一般称为旋转延迟旋转延迟( rotational delay ( rotational delay 或者或者rotational rotational latency )latency )真正进行读写真正进行读写11.111.1 外存信息的存取外存信息的存取第 8 页l磁盘的存取时间磁盘的存取时间11.111.1 外存信息的存取外存信息的存取间间时时输输传传磁道磁道寻道寻道时间时间磁臂磁臂等等待待 时时间间数数据据信信

4、息息磁磁盘盘旋旋转转方方向向第 9 页l扇区的组织（交错法扇区的组织（交错法 interleaving）11.111.1 外存信息的存取外存信息的存取（a a）没有扇区交错）没有扇区交错 （b b）以）以3 3为交错因子为交错因子第 10 页l磁盘的存取时间磁盘的存取时间磁盘访问时间主要由磁盘访问时间主要由寻道时间寻道时间、旋转延迟旋转延迟时间时间和和数据传输时间数据传输时间组成。组成。 寻道时间（寻道时间（Seek time）t tseekseek：是：是移动磁盘移动磁盘臂，定位到正确磁道所需的时间。臂，定位到正确磁道所需的时间。旋转延迟时间旋转延迟时间t tlala：是：是等待被存取的扇区

5、出等待被存取的扇区出现在读写头下所需的时间。现在读写头下所需的时间。传输时间传输时间t twmwm：是：是传输字符的时间。传输字符的时间。T TI/OI/O=t=tseek seek + t+ tlala + t + twmwm11.111.1 外存信息的存取外存信息的存取第 11 页l磁带运行示意磁带运行示意11.111.1 外存信息的存取外存信息的存取 磁带卷在一个卷盘上，运行时磁带经过读磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁带上的信息读入计算机，或把计写磁头，把磁带上的信息读入计算机，或把计算机中的信息写在磁带上算机中的信息写在磁带上。第 12 页l外存的特点外存的特点优点：优

6、点：永久存储能力、便携性永久存储能力、便携性 缺点：访问时间长缺点：访问时间长访问磁盘中的数据比访问内存慢五六个数访问磁盘中的数据比访问内存慢五六个数量级量级。 因此，在对外存的数据结构及其上的操作因此，在对外存的数据结构及其上的操作时，必须遵循的基本原则是：时，必须遵循的基本原则是：尽量减少访外尽量减少访外次数！次数！ 11.111.1 外存信息的存取外存信息的存取第 13 页为什么需要文件管理和外部排序？为什么需要文件管理和外部排序？l文件结构（文件结构（file structure）：）：数据量太大不可能同时都放到内存中，所数据量太大不可能同时都放到内存中，所以需要把全部数据放到外部存储

7、设备上。以需要把全部数据放到外部存储设备上。对于在外存中存储的数据，其数据结构就对于在外存中存储的数据，其数据结构就称为文件结构。称为文件结构。l对文件的对文件的各种操作各种操作：外部排序是针对外存文件所进行的外部排序是针对外存文件所进行的排序操排序操作，是文件的作，是文件的基础操作基础操作；高效的外部排序；高效的外部排序可以可以提高文件存储效率和其他操作的效率。提高文件存储效率和其他操作的效率。11.111.1 外存信息的存取外存信息的存取第 14 页l文件上的操作文件上的操作l检索检索：在文件中寻找满足一定条件的记录在文件中寻找满足一定条件的记录 l修改修改：对记录中某些数据值进行修改。若

8、对：对记录中某些数据值进行修改。若对关键字进行修改，就相当于删除加插入。关键字进行修改，就相当于删除加插入。l插入插入：向文件中增加一个新记录。向文件中增加一个新记录。 l删除删除：从文件中删去一个记录：从文件中删去一个记录 。l排序排序 ：对指定好的数据项，按其值的大小把对指定好的数据项，按其值的大小把文件中的记录排成序列。常用的是按关键字文件中的记录排成序列。常用的是按关键字的排序。的排序。 11.111.1 外存信息的存取外存信息的存取第 15 页l外存文件的组织外存文件的组织 文件是一些记录的集合，每个记录可由文件是一些记录的集合，每个记录可由一个或多个数据项组成。一个或多个数据项组成

9、。 数据项也称为字段，或属性。数据项也称为字段，或属性。11.111.1 外存信息的存取外存信息的存取职工号职工号姓名姓名性别性别职务职务婚姻状况婚姻状况工资工资156张东张东男男程序员程序员未婚未婚7800860李珍李珍女女分析员分析员已婚已婚8900510赵莉赵莉女女程序员程序员未婚未婚6900950陈萍陈萍女女程序员程序员未婚未婚6200620周力周力男男分析员分析员已婚已婚10300第 16 页l逻辑文件逻辑文件对高级程序语言的编程人员而言，磁盘中可以随机对高级程序语言的编程人员而言，磁盘中可以随机访问的文件访问的文件被当作一段连续的字节被当作一段连续的字节，且可将这些字，且可将这些字

10、节结合起来构成记录，这种文件被称为逻辑文件。节结合起来构成记录，这种文件被称为逻辑文件。l物理文件物理文件实际存储在磁盘中的物理文件通常实际存储在磁盘中的物理文件通常不是一段连续的不是一段连续的字节，而是字节，而是成块地分布成块地分布在整个磁盘中。在整个磁盘中。l文件管理文件管理是操作系统的一部分，当应用程序请求从逻辑文件是操作系统的一部分，当应用程序请求从逻辑文件中读取数据时，它将这些中读取数据时，它将这些逻辑位置映射为磁盘中具逻辑位置映射为磁盘中具体的物理位置体的物理位置。11.111.1 外存信息的存取外存信息的存取第 17 页l文件的逻辑结构文件的逻辑结构文件是记录的集合文件是记录的集

11、合。当一个文件的各个记录按照某种次序排列当一个文件的各个记录按照某种次序排列起来时，各记录间就自然地形成了一种线起来时，各记录间就自然地形成了一种线性关系。性关系。 因而，文件可看成是一种线性结构。因而，文件可看成是一种线性结构。 11.111.1 外存信息的存取外存信息的存取l文件的物理结构文件的物理结构l顺序结构顺序结构顺序文件顺序文件 l计算寻址结构计算寻址结构散列文件散列文件 l带索引的结构带索引的结构带索引文件带索引文件 第 18 页l文件的物理结构文件的物理结构p顺序文件：记录按照自然次序依次存储顺序文件：记录按照自然次序依次存储1.存取第存取第 i 个记录之前，必须存取第个记录之

12、前，必须存取第 i-1 个记录个记录2.新记录只能插在文件尾部新记录只能插在文件尾部3.更新文件中的数据必须将整个文件复制一遍更新文件中的数据必须将整个文件复制一遍p散列文件：利用散列文件：利用散列函数和冲突处理散列函数和冲突处理p索引文件：带有按关键字数据项进行索引索引文件：带有按关键字数据项进行索引的文件的文件n虚拟存储存取方式虚拟存储存取方式VSAM：索引顺序文件用：索引顺序文件用B+树作为动态索引树树作为动态索引树11.111.1 外存信息的存取外存信息的存取第 19 页l外部排序外部排序( External Sort )产生的缘由产生的缘由：由于文件很大，无法把整个：由于文件很大，无

13、法把整个文件的所有记录同时调入内存中进行排序，文件的所有记录同时调入内存中进行排序，即即无法进行内部排序无法进行内部排序。对对外存设备上外存设备上（文件（文件）进行）进行的排序技术。的排序技术。 l外部排序算法的主要目标：外部排序算法的主要目标：尽量减少读尽量减少读写磁盘的次数写磁盘的次数 。11.211.2 外部排序的方法外部排序的方法第 20 页l顺串：顺串：用某种有效的用某种有效的内排序方法内排序方法对组成对组成文件的各段文件的各段/ /子文件进行初始排序后重新子文件进行初始排序后重新写回外存的段或子文件被称为写回外存的段或子文件被称为归并段归并段或或顺串顺串(run) (run) 。l

14、外部排序的过程：外部排序的过程：把文件分成若干尽可能长的初始把文件分成若干尽可能长的初始顺串顺串。逐步归并顺串（或归并段），最后形成一逐步归并顺串（或归并段），最后形成一个已排序的文件。个已排序的文件。11.211.2 外部排序的方法外部排序的方法第 21 页l外部排序的时间开销：外部排序的时间开销：总时间总时间 =内部排序产生初始顺段内部排序产生初始顺段 时间时间 +外存信息读写时间外存信息读写时间 +内部归并所需时间内部归并所需时间 = m* *tis + d* *tio + s* *utmg其中：其中：tis：得到一个初始归并段进行内部排序所需时间：得到一个初始归并段进行内部排序所需时间

15、m：经过内排序后得到的初始归并段的数量：经过内排序后得到的初始归并段的数量tio：进行一次外存读写的时间：进行一次外存读写的时间d：总的读：总的读/写次数写次数utmg：对：对 u 个记录进行内部归并所需时间个记录进行内部归并所需时间s：归并的趟数：归并的趟数11.211.2 外部排序的方法外部排序的方法第 22 页p减少外存信息的读写次数减少外存信息的读写次数是提高外部排序效是提高外部排序效率的关键率的关键 ：l对同一个文件而言，进行外排序所需读写外对同一个文件而言，进行外排序所需读写外存的存的次数与归并趟数成正比关系。次数与归并趟数成正比关系。l假设有假设有m个初始顺串，每次对个初始顺串，

16、每次对k个顺串进行归个顺串进行归并，其归并趟数为并，其归并趟数为logkm。p为了减少归并趟数，可以从两个方面着手：为了减少归并趟数，可以从两个方面着手：减少初始顺串的个数减少初始顺串的个数m m增加归并的顺串数量增加归并的顺串数量k k11.211.2 外部排序的方法外部排序的方法第 23 页p外部排序基本做法的描述：外部排序基本做法的描述：假定文件有假定文件有4500个记录：个记录：R1, R2, , R4500。磁。磁盘上盘上 1 块（即块（即1 个扇区）的尺寸是个扇区）的尺寸是250个记录个记录，该文件总共需用磁盘的，该文件总共需用磁盘的 18 个扇区。内存可个扇区。内存可供用于排序的

17、空间是供用于排序的空间是 750 个记录大小。个记录大小。p排序过程如下：排序过程如下： 每次从磁盘读入每次从磁盘读入 3 块（块（750个记录）到内存，利用内排序算法将它们个记录）到内存，利用内排序算法将它们排好序，然后写回磁盘。这样，磁盘上就得排好序，然后写回磁盘。这样，磁盘上就得到了到了6个初始有序段个初始有序段A1、A2、A6。 11.211.2 外部排序的方法外部排序的方法初始有序段初始有序段A11750有序段有序段A27511500有序段有序段A315012250有序段有序段A422513000有序段有序段A530013750有序段有序段A637514500第 24 页把内存按把内

18、存按 250 个记录的长度分成三部分：个记录的长度分成三部分： 两部分为输入缓冲区，两部分为输入缓冲区， 一部分为输出缓冲区。一部分为输出缓冲区。先对先对 A1 和和 A2 进行归并：进行归并：先将每段的一块（先将每段的一块（250个有序记录）读到内存的两个输入缓冲区个有序记录）读到内存的两个输入缓冲区，用归并排序算法实施排序。边排序，边把结，用归并排序算法实施排序。边排序，边把结果写到输出缓冲区。果写到输出缓冲区。输出缓冲区满时，写入磁盘；当一个输入缓冲输出缓冲区满时，写入磁盘；当一个输入缓冲区的内容归并完腾空时，将该有序段的下一块区的内容归并完腾空时，将该有序段的下一块读入该缓冲区继续归并

19、。读入该缓冲区继续归并。这样继续，直到把这样继续，直到把 A1 和和 A2 全归并完毕，磁全归并完毕，磁盘里出现一个含盘里出现一个含1500个记录的新有序段。个记录的新有序段。11.211.2 外部排序的方法外部排序的方法第 25 页 完成一次归并后，对完成一次归并后，对A3和和A4、A5和和A6实施相实施相同归并。整个文件经一趟归并，在磁盘上得同归并。整个文件经一趟归并，在磁盘上得到三个各含到三个各含1500记录的有序段。记录的有序段。11.211.2 外部排序的方法外部排序的方法初始有序段初始有序段A11750有序段有序段A27511500有序段有序段A315012250有序段有序段A42

20、2513000有序段有序段A530013750有序段有序段A6375145003000个记录个记录第第2趟归并趟归并1500个记录个记录1500个记录个记录1500个记录个记录第第1趟归并趟归并4500个记录个记录第第3趟归并趟归并继续进行归并：继续进行归并：第第 2 趟，第趟，第 3 趟。趟。第 26 页l分析分析在一切相同的条件下，如果把例中的在一切相同的条件下，如果把例中的 2-路归路归并改变成并改变成 3-路或路或 6-路（当然，这时所需要的路（当然，这时所需要的内存缓冲区个数将会变化），那么总的读写磁内存缓冲区个数将会变化），那么总的读写磁盘次数就会下降。盘次数就会下降。11.211

21、.2 外部排序的方法外部排序的方法归并路数归并路数 总读写磁盘次数总读写磁盘次数 归并趟数归并趟数 2 132 3 3 108 2 6 72 1第 27 页lk-路归并路归并k-路归并时，在路归并时，在 k 个关键字中选最小值。通常个关键字中选最小值。通常可采用直接选择排序方法，对关键字做可采用直接选择排序方法，对关键字做 k-1次次比较。比较。问题：问题：在直接选择排序时许多关键字间进行在直接选择排序时许多关键字间进行了不止一次的重复比较，导致时间的浪费。了不止一次的重复比较，导致时间的浪费。解决办法：解决办法：若在选择最小者时，将比较结果若在选择最小者时，将比较结果保留下来，后面需要时加以

22、利用，就可减少保留下来，后面需要时加以利用，就可减少比较次数，减少磁盘输入比较次数，减少磁盘输入/输出所耗费的时间，输出所耗费的时间，从而使排序的速度提高。从而使排序的速度提高。11.211.2 外部排序的方法外部排序的方法第 28 页l选择树选择树选择树是一棵二叉树，该树中的分支结点是选择树是一棵二叉树，该树中的分支结点是该结点两个孩子中的较小者，根结点是这棵该结点两个孩子中的较小者，根结点是这棵树各叶结点中的最小者。树各叶结点中的最小者。11.211.2 外部排序的方法外部排序的方法10920689901769681768 为选择次小者，可把该记录原始位置（叶结点）设为选择次小者，可把该记

23、录原始位置（叶结点）设成一个大于所有关键字的值成一个大于所有关键字的值“+”。进行。进行输出输出-调整调整。最小值最小值+由下往由下往上调整上调整2098k=8时时第 29 页l选择树选择树为选取下一个最小者，只需对根结点到该叶为选取下一个最小者，只需对根结点到该叶结点所经路径上的各结点与其左或右兄弟进结点所经路径上的各结点与其左或右兄弟进行比较和适当的调整即可，其他结点保持原行比较和适当的调整即可，其他结点保持原样。样。11.211.2 外部排序的方法外部排序的方法10920+899017892081798+9k=8时时输出输出8，并调整，并调整99输出输出9，并调整，并调整+10109输出

24、输出9，并调整，并调整+1710第 30 页l胜者树：结点记录胜者信息胜者树：结点记录胜者信息利用选择树的思想，对有序段进行利用选择树的思想，对有序段进行k-路归并。路归并。树的每个叶结点对应一个树的每个叶结点对应一个输入缓冲区输入缓冲区，它总，它总是各有序段在归并过程中的是各有序段在归并过程中的当前关键字当前关键字，分，分支结点是它的两个孩子结点中支结点是它的两个孩子结点中键值较小键值较小的那的那个。个。根根结点是树中结点是树中键最小键最小的。的。输出根结点后，用该记录所在有序段的下一输出根结点后，用该记录所在有序段的下一个关键字填补它的位置，并作适当调整。这个关键字填补它的位置，并作适当调

25、整。这样的调整不会涉及到整棵树，而只需考虑从样的调整不会涉及到整棵树，而只需考虑从根结点到该位置的路径上的各个结点。根结点到该位置的路径上的各个结点。11.211.2 外部排序的方法外部排序的方法第 31 页l胜者树胜者树当前当前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.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519

26、.2038.2234.1525.1750.2144.95108.3266.第 32 页l胜者树胜者树对对 8 个并有序段进行一次归并。先输出根结个并有序段进行一次归并。先输出根结点上关键字为点上关键字为 6 的记录，它原位于最底层编的记录，它原位于最底层编号为号为 11 的叶结点处，用的叶结点处，用15顶替。局部调整顶替。局部调整 。11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.1525.1598第 33 页l胜者树胜者树输出原位

27、于编号为输出原位于编号为12的记录的记录8，并用它后面值，并用它后面值为为“17”的关键字进行顶替。做适当调整的关键字进行顶替。做适当调整.11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.1525.159850.171717938.20101010输出输出 9，再继续进行调整，再继续进行调整.第 34 页l胜者树胜者树：实现：实现胜者树是胜者树是完全二叉树完全二叉树，算法实现时，采用，算法实现时，采用顺顺序存储结构序存储结构保存。保

28、存。非叶结点非叶结点保存的是保存的是“胜者胜者”在树中对应结点的在树中对应结点的下标下标（编号编号）。）。11.211.2 外部排序的方法外部排序的方法1092068189024696824681234567891011121314151519.2038.2234.1525.1750.2144.95108.3266.9111215111211保存：胜者保存：胜者对应叶结点对应叶结点的编号的编号第 35 页l败者树：结点记录败者信息败者树：结点记录败者信息败者树是一棵有败者树是一棵有 k 个叶结点的二叉树，分支个叶结点的二叉树，分支结点存放该结点两个孩子中的结点存放该结点两个孩子中的较大者较大者

29、（败败者者），而让较小者（胜者）参加上一层的比），而让较小者（胜者）参加上一层的比较，即胜者较，即胜者“出线出线”参加下一轮比赛。每个参加下一轮比赛。每个败者都停在自己失败的赛场上。败者都停在自己失败的赛场上。根根结点里存放结点里存放最终的失败者最终的失败者。11.211.2 外部排序的方法外部排序的方法第 36 页l败者树：结点记录败者信息败者树：结点记录败者信息根结点里仍存放最终的失败者。根结点里仍存放最终的失败者。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525

30、.1750.2144.95108.3266.60在根的上面附加一个结点，存放全局的优胜在根的上面附加一个结点，存放全局的优胜者者冠军。冠军。第 37 页l败者树：结点记录败者信息败者树：结点记录败者信息输出输出“6”，之后进行调整。，之后进行调整。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.601525.201598第 38 页l败者树败者树：说明：说明 胜者树在人工处理时比较胜者树在人工处理时比较直观直观，但在程序实，

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

32、叉树完全二叉树，采用，采用顺序存储顺序存储。非叶结点非叶结点保保存的是败者在树中对应结点的存的是败者在树中对应结点的下标下标（编号编号）。）。11.211.2 外部排序的方法外部排序的方法81020189092412345678910111213141510920681890241519.2038.2234.1525.1750.2144.95108.3266.6081013149151211第 40 页l算法描述（算法描述（P298算法算法11.1）typedef int LoserTreek; /采用顺序存储结构采用顺序存储结构typedef struct KeyType key; ExNo

33、de, External k+1 ; / 外结点，存待归并关键字外结点，存待归并关键字void K_Merge( LoserTree &ls, External &b ) / ls0.k-1：保存非叶结点：保存非叶结点 / b0bk-1：败者树的：败者树的 k 个叶结点，个叶结点，k个归并段的个归并段的当前关键字当前关键字11.211.2 外部排序的方法外部排序的方法第 41 页l算法描述（算法描述（P298算法算法11.1）void K_Merge( LoserTree &ls, External &b ) 11.211.2 外部排序的方法外部排序的方法for

34、 ( i=0; i= 0 ) if ( bs.key b ls0 .key ) s ls t ; / s：新的胜者的下标：新的胜者的下标 t = t/2; ls 0 = s; / 保存全胜者下标保存全胜者下标第 43 页l算法描述（算法描述（P299算法算法11.3）void CreateLoserTree( LoserTree &ls ) / b 0 . k-1：为完全二叉树：为完全二叉树 ls 的叶结点，保存键值的叶结点，保存键值 / 沿从叶结点到根的沿从叶结点到根的 k 条路径将条路径将 ls 调整为败者树调整为败者树11.211.2 外部排序的方法外部排序的方法b k = MI

35、NKEY; / 设为最小值设为最小值for ( i=0; i=0; -i ) Adjust( ls, i ); / 从从bk-1 到到 b0调整败者调整败者第 44 页lk路归并是每次将路归并是每次将k个顺串合并成一个排好序个顺串合并成一个排好序的顺串。一般情况下，对的顺串。一般情况下，对m个初始顺串进行个初始顺串进行k路归并时归并趟数为路归并时归并趟数为logkm。增加每次归并的。增加每次归并的顺串数量顺串数量 k 可减少归并趟数。可减少归并趟数。l选择树是完全二叉树，有两种类型：赢者树选择树是完全二叉树，有两种类型：赢者树和败者树。和败者树。 11.211.2 外部排序的方法外部排序的方法第 45 页l多路归并多路归并11.211.2 外部排序的方法外部排序的方法三路归并三路归并第 46 页l问题问题在合并阶段，如果初始的顺串不等长，应该在合并阶段，如果初始的顺串不等长，应该如何挑选合并对象，减少读块次数，以加快如何挑选合并对象，减少读块次数，以加快合并速度？合并速度？l实例实例初始有初始有9个顺串，其长度（块数）依次为：个顺串，其长度（块数）依次为：8, 23, 9, 15, 3, 12, 2, 6, 17。采用。采用3路合并。应该路合并。应该如何进行才能使读盘次数最少？如何进行才能使读盘次数最少？11.2