本节内容
王道考研/CSKAOYAN.COM
外部排序
王道考研/CSKAOYAN.COM
知识总览
王道考研/CSKAOYAN.COM
外存、内存之间的数据交换
磁盘
内存
磁盘块1
磁盘块2
磁盘块3
磁盘块4
磁盘块5
磁盘块6
磁盘块7
磁盘块8
磁盘块9
磁盘块10
磁盘块11
磁盘块12
磁盘块13
磁盘块14
磁盘块15
….
….
很多很多
1
2
3
8
12
7
操作系统以“块”为单位对磁盘存储空间进⾏管理,如:每块⼤⼩ 1KB
各个磁盘块内存放着各种各样的数据
1
2
3
读磁盘
写磁盘
1KB缓冲区
王道考研/CSKAOYAN.COM
外存、内存之间的数据交换
磁盘
内存
磁盘块1
磁盘块2
磁盘块3
磁盘块4
磁盘块5
磁盘块6
磁盘块7
磁盘块8
磁盘块9
磁盘块10
磁盘块11
磁盘块12
磁盘块13
磁盘块14
磁盘块15
….
….
磁盘的读/写以“块”为单位
数据读⼊内存后才能被修改
修改完了还要写回磁盘
很多很多
磁盘块11
1
2
3
读磁盘
写磁盘
8
12
7
操作系统以“块”为单位对磁盘存储空间进⾏管理,如:每块⼤⼩ 1KB
各个磁盘块内存放着各种各样的数据
1KB缓冲区
1
2
3
王道考研/CSKAOYAN.COM
外存、内存之间的数据交换
磁盘
内存
磁盘块1
磁盘块2
磁盘块3
磁盘块4
磁盘块5
磁盘块6
磁盘块7
磁盘块8
磁盘块9
磁盘块10
磁盘块11
磁盘块12
磁盘块13
磁盘块14
磁盘块15
….
….
磁盘的读/写以“块”为单位
数据读⼊内存后才能被修改
修改完了还要写回磁盘
很多很多
磁盘块11
1
2
3
读磁盘
写磁盘
8
12
7
操作系统以“块”为单位对磁盘存储空间进⾏管理,如:每块⼤⼩ 1KB
各个磁盘块内存放着各种各样的数据
1KB缓冲区
45
23
11
45
23
11
45
23
11
王道考研/CSKAOYAN.COM
外存、内存之间的数据交换
磁盘
内存
磁盘块1
磁盘块2
磁盘块3
磁盘块4
磁盘块5
磁盘块6
磁盘块7
磁盘块8
磁盘块9
磁盘块10
磁盘块11
磁盘块12
磁盘块13
磁盘块14
磁盘块15
….
….
磁盘的读/写以“块”为单位
数据读⼊内存后才能被修改
修改完了还要写回磁盘
很多很多
磁盘块11
1
2
3
读磁盘
写磁盘
8
12
7
操作系统以“块”为单位对磁盘存储空间进⾏管理,如:每块⼤⼩ 1KB
各个磁盘块内存放着各种各样的数据
1KB缓冲区
45
23
11
45
23
11
45
23
11
王道考研/CSKAOYAN.COM
外存、内存之间的数据交换
磁盘
内存
磁盘块1
磁盘块2
磁盘块3
磁盘块4
磁盘块5
磁盘块6
磁盘块7
磁盘块8
磁盘块9
磁盘块10
磁盘块11
磁盘块12
磁盘块13
磁盘块14
磁盘块15
….
….
磁盘的读/写以“块”为单位
数据读⼊内存后才能被修改
修改完了还要写回磁盘
很多很多
磁盘块11
1
2
3
读磁盘
写磁盘
8
12
7
操作系统以“块”为单位对磁盘存储空间进⾏管理,如:每块⼤⼩ 1KB
各个磁盘块内存放着各种各样的数据
1KB缓冲区
45
23
11
45
23
11
45
23
11
王道考研/CSKAOYAN.COM
外部排序原理
磁盘
内存
使⽤“归并排序”的⽅法,最少只需在内存
中分配3块⼤⼩的缓冲区即可对任意⼀个⼤
⽂件进⾏排序
读磁盘
写磁盘
外部排序:数据元素太多,⽆法⼀次全部读⼊内存进⾏排序
45
27
28
1
37
25
42
9
48
36
8
26
14
29
44
18
38
13
19
7
39
41
2
40
15
5
16
30
4
31
11
3
20
12
34
24
43
46
17
32
6
47
22
21
10
33
23
35
输出缓冲区
输⼊缓冲区1
输⼊缓冲区2
王道考研/CSKAOYAN.COM
构造初始“归并段”
磁盘
内存
读磁盘
写磁盘
45
27
28
1
37
25
14
29
44
18
38
13
19
7
39
41
2
40
15
5
16
30
4
31
11
3
20
12
34
24
43
46
17
32
6
47
22
21
10
33
23
35
输⼊缓冲区1
输⼊缓冲区2
42
9
48
36
8
26
“归并排序”要求各个⼦序列有序,每次读⼊
两个块的内容,进⾏内部排序后写回磁盘
输出缓冲区
王道考研/CSKAOYAN.COM
磁盘
内存
读磁盘
写磁盘
45
27
28
1
37
25
14
29
44
18
38
13
19
7
39
41
2
40
15
5
16
30
4
31
11
3
20
12
34
24
43
46
17
32
6
47
22
21
10
33
23
35
输⼊缓冲区1
输⼊缓冲区2
42
9
48
36
8
26
“归并排序”要求各个⼦序列有序,每次读⼊
两个块的内容,进⾏内部排序后写回磁盘
输出缓冲区
构造初始“归并段”