第十章外部排序10.1外存信息的特性10.1.1磁带存储器2.分页块存储方法10.1.2磁盘存储器磁盘可分为固定臂盘和活动臂盘两种。固定臂盘的每个盘面的每一磁道上都有独立的磁头，它是固定不动的，专门负责读写某一磁道上的信息。如图：10.2外排序的基本方法10.2.1磁盘排序2.多路归并在非叶结点中，可以只存关键字值及指向相应记录的指针，而不必存放整个记录内容。由于非叶结点总是代表优胜者，所以可以把这种树称为胜方树。盘面上能够存储信息的盘面称为记录面。这样，为了避免对数据进行再分配的扫描，就需要2k台磁带机，现采用非平衡归并，即不同输入带上的顺串个数不同，适当地对顺串进行非均匀分配，就可以用不到2k台磁带机来实现k路归并。最佳归并树如下图所示。如果逐个比较每个顺串的待选记录，从而选出一个关键字值最小的记录，则每选取一个记录需要进行k-1次比较。优点：存储容量大，使用方便，价格便宜。50,90,100,110九道磁带的每一横排中有八个二进制数据位和一个奇偶校验位。外存中把若干个记录（逻辑记录）组合成页块（物理记录）进行存储。假设有n步，我们希望n步之后在T1上正好有一个顺串，而在T2和T3上没有顺串。第一步：把输入文件分段（每段包含600个记录）读入内存并进行内排序，生成初始顺串，然后将这些顺串轮流写到磁带机T1和T2上。磁盘驱动器由主轴和读／写磁头组成，每个盘面都配有一个读／写磁头。已知有31个长度不等的初始归并段，其中8段长度为2，8段长度为3，7段长度为5，5段长度为12，3段长度为20（单位为物理块）。采用多路归并可以减少扫描遍数，如图所示。如果输入文件中的记录按其关键字随机排列，则所生成的初始顺串的平均长度为内存工作区大小的2倍。在k路归并中，为了确定下一个要输出的记录，就需要在k个记录中寻找关键字值最小的那个记录，这要比2路归并复杂些。这种选择树的构造可比作一种淘汰制的体育比赛，其中获胜者便是那个具有较小关键字值的记录。磁带的存取时间主要用在定位上，读／写头与所需信息的距离越远，定位时间就越长。在根结点之上有一个附加的结点，存放全局优胜者。n-501311712345678910111213141516这样，为了避免对数据进行再分配的扫描，就需要2k台磁带机，现采用非平衡归并，即不同输入带上的顺串个数不同，适当地对顺串进行非均匀分配，就可以用不到2k台磁带机来实现k路归并。多路归并方法（1）：胜方树。采用多路归并可以减少扫描遍数，如图所示。如果输入文件中的记录按其关键字随机排列，则所生成的初始顺串的平均长度为内存工作区大小的2倍。n-4053优点：既能进行顺序存取，又能进行直接存取（随即存取），并且存取速度快。一般说来，如果初始顺串有m个，则如图所示那样的归并树就有[log2m]+1层，要对数据进行[log2m]遍扫描。三带2路归并的顺串分布（2）归并：对顺串反复进行归并，直至变成一个顺串。n-73724044败方树：就是在比赛树（选择树）中，每个非叶结点均存放其两个子结点中的败方。外部排序：待排序的记录数n很大，内存容纳不下，必须借用外部存储器才能完成的排序过程。步骤T1T2T3说明在败方树中，当输出全局优胜者记录之后，对树的修改比胜方树容易一些。修改过程如下：将新进入树的叶结点与父结点进行比较，大的存放在父结点，小的与上一级父结点再进行比较，此过程不断进行，直至到根，最后把新的全局优胜者存放到附加的结点。输入文件10，9，20，6，8，12，90，17，14，22，7，24，15，16，11，100，13，18，26，38，30，25，50，28，110，21，40，19，…第四步后－－81归并到T3顺序存取设备（磁带存储器）一个页块（简称块）是磁盘上的一个物理记录，通常可以容纳多个逻辑记录，内存中设置的缓冲区应该与页块的大小相等。第四步：把T1上的顺串1和T3上的顺串3合并，并把结果放到T2上，即为所要求的有序文件。优点：既能进行顺序存取，又能进行直接存取（随即存取），并且存取速度快。第一步：把输入文件分段（每段包含600个记录）读入内存并进行内排序，生成初始顺串，然后将这些顺串轮流写到磁带机T1和T2上。败方树：就是在比赛树（选择树）中，每个非叶结点均存放其两个子结点中的败方。采用多路归并可以减少扫描遍数，如图所示。直接存取设备（磁盘存储器）采用多路归并可以减少扫描遍数，如图所示。如果逐个比较每个顺串的待选记录，从而选出一个关键字值最小的记录，则每选取一个记录需要进行k-1次比较。这样，为了避免对数据进行再分配的扫描，就需要2k台磁带机，现采用非平衡归并，即不同输入带上的顺串个数不同，适当地对顺串进行非均匀分配，就可以用不到