文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。
m-路归并排序可用一棵m叉树描述,因为每一次作m路归并都需要m个归并段参加,因为,归并段树是一棵只有度为0和度为m的结点的严格m叉树。
设由置换-选择排序得到9个初始归并段,其长度(记录数)依次为:9,30,12,18,3,17,2,6,24。
现作3-路归并,各叶结点表示参加归并的一个初始归并段,叶结点上的权值表示初始归并过程中的记录数,根结点表示最终生成的归并段,叶结点到根结点的路径长度表示归并过程中的归并趟数,各非叶结点代表归并成的新的归并段,则归并树的带权路径长度WPL即为归并过程中的总记录数,因而在归并过程中,总的I/O次数为2*WPL=484。
归并方案不同,所得归并树亦不同,树的带权路径长度(外存I/O次数亦不同)。为了优化归并树的WPL,可以将Huffman树的思想推广到M叉树的情形。在归并树中,让记录数少的初始归并段最先归并,记录数多的初始归并段最晚归并,就可以建立总的I/O次数达到最少的最佳归并树。对上述9个初始归并段可构造成最佳归并树,按此树进行归并,仅需对外村进行446次读写,这棵树便称为最佳归并树。
Huffman树是一棵严格3叉树。若只有8个初始归并段,设上例中少了一个长度为30的归并段。如果在设计归并方案时,缺额的归并段留着最后,即除了最后一次作2-路归并外,其他各次归并仍都是3-路归并,此归并方案的外存读写次数为386。显然不是最佳方案。
正确的做法是,若初始归并段不足构成一棵严格m叉树时,需添加长度为0的“虚段”,按照Huffman树的原则,权为0的叶子应离根最远。
如何判定添加虚段的数目?
设度为0的结点有N0(=n)个,度为m的结点有Nm个,则对严格m叉树有N0=(m-1)Nm+1,由此可以得出Nm=(N0-1)/(m-1)。
如果(N0-1)%(m-1)=0(%为取余运算),则说明这N0个叶结点(初始归并段)正好可以构造m叉归并树。此时,内结点有Nm个。
如果(N0-1)%(m-1)=u不等于0,则说明对于这N0个叶结点,其中有u个多余,不能包含在m叉归并树中。为构造包含所有N0个初始归并段的m叉归并树,应在原有Nm个内结点的基础上再增加一个内结点。它在归并树中代替了一个叶结点位置,被代替的叶结点家伙是哪个刚才多出的u个叶结点,再加上m-u-1个空归并段,就可以建立归并树。