图示 J Input 1 Input 2 output 1 Input B-1 Disk Pass i>o
图示 … … Disk Disk Input 1 Input 2 Input B-1 output 1 Pass i>0 …
计算量分析 ●第一次产生N1=「N/B个runs ●对数据扫描的遍数,变为|ogBN1+ ●最终的O次数为2NogB1N1+1
计算量分析 ⚫第一次产生N1= N/B个runs ⚫对数据扫描的遍数，变为logB-1N1+1 ⚫最终的I/O次数为2N* logB-1N1+1
性能实例 B=3B=5B=9B=17B=129B=257 102 7 2 10 10 10 13 4579 10 17 10 20 10 10 23 12 3456789 10 26 14 455678 2233445 3344 10 30 15 10
性能实例 N B=3 B=5 B=9 B=17 B=129 B=257 102 7 4 3 2 1 1 103 10 5 4 3 2 2 104 13 7 5 4 2 2 105 17 9 6 5 3 3 106 20 10 7 5 3 3 107 23 12 8 6 4 3 108 26 14 9 7 4 4 109 30 15 10 8 5 4
如何减少run的个数 ●在Pass0的过程中,可使用一些技巧,使得最初 的run的长度平均为2B ●基本想法 ○有一个页的输入缓冲区、一个页的输出缓冲区和一个当 前排序缓冲区 ○首先将数据调入当前排序缓冲区(B-2页)进行排序 不断将大于输出缓冲区中数据的最小的记录从当前排序 缓冲区读出送入输出缓冲区,并不断从输入缓冲区中补 充数据 ◎直到当前缓冲区中没有可选的数据为止,则当前run结束
如何减少run的个数 ⚫ 在Pass 0的过程中，可使用一些技巧，使得最初 的run的长度平均为2B ⚫ 基本想法 有一个页的输入缓冲区、一个页的输出缓冲区和一个当 前排序缓冲区 首先将数据调入当前排序缓冲区（B-2页）进行排序 不断将大于输出缓冲区中数据的最小的记录从当前排序 缓冲区读出送入输出缓冲区，并不断从输入缓冲区中补 充数据。 直到当前缓冲区中没有可选的数据为止，则当前run结束
例子 12 2 4 35 10 输入缓冲区当前缓冲区输出缓冲区
例子 12 4 2 8 10 3 5 输入缓冲区 当前缓冲区 输出缓冲区