数据结构(C语言版)第11章文件与外部排序

格式：ppt
大小：398.00 KB
文档页数：37

下载文档原格式

《数据结构C语言版》----第11章

=
ASL

n
i=1
Pi × C
i
其中，Pi是要查找数据元素出现的概率，Ci是查找相应数据元素的比较次数。定义要查找数据元素的结构体为：
typedef struct { KeyType key; } DataType;
11.2 静态查找表
静态查找表主要有三种结构：
顺序表
有序顺序表
索引顺序表
1.顺序表
下图所示就是一棵二叉排序树
381
12
410
9
40
394
540
35
190
476
760
146
445
600
800
二、二叉排序树的查找算法
int Search(BiTreeNode *root, DataType item) { BiTreeNode *p; if(root != NULL) { p = root; while(p != NULL) { if(p->data.key == item.key) return 1; if(item.key > p->data.key) p = p->rightChild; else p = p->leftChild; } } return 0;
索引表结构图
相关术语
完全索引表:和主表项完全相同，但只包含索引关键字和该数据元素在主表中位置信息的索引表
二级索引表:当主表中的数据元素个数非常庞大时，按照建立索引表的同样方法对索引表再建立的索引表。二级以上的索引结构称作多级索引结构等长索引表:索引表中的每个索引项对应主表中的数据元素个数相等;反之称为不等长索引表。不等长索引表中的索引长度可随着动态插入和动态删除过程改变,因此不仅适用于静态查找问题，而且也适用于动态查找问题。

数据结构-_外部排序

1
5
2
3
5
9
4
5
6
7
5
7
29
9
输5
7
29
9
入 16
12
38
22
缓 49
25
57
47
52
84
66
48
冲
78
91
71
59
区
1234567 5 5 9 5 7 29 9
输5 出缓冲区
注意：挑出冠军需要进行 k-1 次比较，此处需要比较 3 次。 5
EXST
6 物料管理
3、多路平衡归并的实现
Algorithms and DataStructures:EXSORT
区
注意：挑出冠军
输
5
需要进行 k-1 次
出
比较，此处需要
缓
比较 3 次。
冲
区
7
EXST
8 物料管理
3、多路平衡归并的实现
Algorithms and DataStructures:EXSORT
tseck ：找道时间 tla ：等待时间 twm ：传输时间/ 字符，n 字符数。
2
EXST
3 物料管理
2、外部排序的方法
Algorithms and DataStructures:EXSORT
1、步骤： • 生成合并段（run）：读入文件的部分记录到内存－> 在内存中进行内部排序－> 将排好序的这些记录写入外存，形成合并段－> 再读入该文件的下面的记录，往复进行，直至文件中的记录全部形成合并段为止。 7、15、19 8、11、13 16、23、31 5、12

C++语言程序设计第11章

最
升
38888
大
的
初第第第第
始一二三四
状趟趟趟趟
态结结结结
果果果果
12
起泡排序函数模板
例10.3（10-3.h）
13
小结
排序的基本思想；冒泡排序；
14
7
选择排序的基本思想
每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。
初始状态：
[5 4 10 20 12 3]
3 [4 10 20 12 5]
3 4 [10 20 12 5]
3
4
5 [20 12 10]
... ...
第 i 次选择后，将选出的那个记录与第 i 个记录做交换。 8
5 10] 20 12 3 5 10 20] 12 3 5 10 12 20] 3
5 [3] [3
4
5 10 12 20]
6
直接插入排序
在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序法，这里我们只介绍最简单的直接插入排序法。
例10.1 直接插入排序函数模板（10-1.h）
在排序过程中需要完成两种基本操作：比较两个数的大小调整元素在数组中的位置
3
内部排序与外部排序
内部排序：待排序的数据元素存放在计算机内存中进行的排序过程。
外部排序：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。
4
内部排序方法
C++语言程序设计
第十一章群体数据的组织
本章主要内容

文件外部排序与外部搜索

25
直接存取文件 (Direct Access File)
•
•
•
又叫散列文件。利用散列技术组织文件。处理类似散列法，但它是存储在外存上的。文件记录的逻辑顺序与物理顺序不一定相同。通过记录的关键码可直接确定该记录的地址。使用散列函数把关键码集合映射到地址集合时，往往会产生地址冲突，处理冲突有两种处理方式：按桶散列可扩充散列
7
•
•
•
在磁带设备上读写一块信息所用时间 tIO = ta + tb 其中，ta 是延迟时间，即读写磁头到达待读写块开始位臵所需花费的时间，它与当前读写磁头所在位臵有关。tb是对一个块进行读写所用时间，它等于数据传输时间加上IBG时间。磁带设备只能用于处理变化少，只进行顺序存取的大量数据。
12
2. 选定盘片组后再选定某个柱面，并移动动臂把磁头移到此柱面上。这是机械动作，速度较慢。这称为“寻查（seek）”。 3. 选定柱面后，要进一步确定磁道，即确定由哪个读写磁头读写，由电子线路实现。 4. 确定磁道后，还要确定所要读写数据在磁盘上的位臵（如在哪一个扇区）。这实际上就是在等待要读写的扇区转到读写磁头下面。这是机械动作。这段时间一般称为旋转延迟（rotational delay）时间。 5. 真正进行读写时间。
经过时间物理记录
传输完成
停止位臵
IBG 0.3～0.75英寸
IBG 0.3～0.75英寸
6
•
•
如果每个逻辑记录是 80个字符，IRG为 0.75英寸，则对存储密度为 1600BPI 的磁带，一个逻辑记录仅占 80/1600 = 0.05英寸。每传输一个逻辑记录磁带走过 0.05英寸，接着磁带要走过一个IRG占0.75英寸。结果大部分时间都花费在走空带上，存储利用率只有1/16。如果将若干逻辑记录存放于一个块，将IRG变成IBG，可以提高存储利用率。例如，将50个有80个字符的逻辑记录放在一个块内，此块的长度将达到5080/1600 = 2.5英寸，存储利用率达到0.77。因此在磁带上采用按块读写。

第十一章外部排序

.
2
b1 9 9 18 20 . b2 20
3 4
b4 12 12 37 48 .
10
10 15 16 .
20 22 40 .ຫໍສະໝຸດ §11.4 置换-选择排序
• 问题: 是否可以不用内部排序构造初始归并段? • 例:若初始文件含有24个记录，其的关键字为: 51，49，39，46，38，29，14，61，15，1，48，52， 3，63，27，4，1389，24，46，58，33，76。假设内存工作区可容纳6个记录，则可得如下4个初始归并段： • RUN1：29，38，39，46，49，51 • RUN2：1，14，15，30，48，61 • RUN3：3，4，13，27，52，63 • RUN4：24，33，46，58，76，89
§11.3 多路平衡归并的实现
• 例:
3 1
胜利者
失败者
0
b0 b3 6 6 15 25
.
2
b1 9 9 18 20 . b2 20
4
b4 12 12 37 48 .
10
10 15 16 .
20 22 40 .
§11.3 多路平衡归并的实现
• 例:
1 3 0 1
胜利者
失败者
4 0
b0 b3 15 15 25
15,30,1,48,52,3,63,27,4,… 30,1,48,52,3,63,27,4,…
30,1,48,52,3,63,27,4,… 1,48,52,3,63,27,4,… 48,52,3,63,27,4,… 52,3,63,27,4,…
FO
29,38,39,46,49,51,61
WA
48,1,15,30,52,14 3,63,27,4,…

数据结构-文件与外部排序

2 记录的插入
首先根据待插入记录的关键字查找到相应位置；然后将该磁道中插入位置及以后的记录后移一个位置(若溢出，将该磁道中最后一个记录存入同一柱面的溢出区，并修改磁道索引) ；最后将记录插入到相应位置。
3 记录的删除
只需找到要删除的记录，对其做删除标记，不移动记录。当经过多次插入和删除操作后，基本区有大量被删除的记录，而溢出区也可能有大量记录，则周期性地整理ISAM文件，形成一个新的ISAM文件。
2 文件的有关操作
文件是由大量记录组成的线性表，因此，对文件的操作主要是针对记录的，通常有：记录的检索、插入、删除、修改和排序，其中检索是最基本的操作。
⑴ 检索记录
根据用户的要求从文件中查找相应的记录。 ① 查找下一个记录：找当前记录的下一个逻辑记录； ② 查找第k个记录：给出记录的逻辑序号，根据该序号查找相应的记录； ③ 按关键字查找：给出指定的关键字值，查找关键字值相同或满足条件的记录。对数据库文件，有以下四种按关键字查找的方式：
图11-1 索引结构的基本形式
对于稠密索引，可以根据索引项直接查找到记录的位置。若在索引表中采用顺序查找，查找时间复杂度为 O(n) ；若采用折半查找，查找时间复杂度为O(㏒2n) 。对于稠密索引，索引项数目与数据表中记录数相同，当索引表很大时，检索记录需多次访问外存。对于非稠密索引，查找的基本思想是：首先根据索引找到记录所在块，再将该块读入到内存，然后再在块内顺序查找。平均查找长度由两部分组成：块地址的平均查找长度Lb，块内记录的平均查找长度Lw，即ASLbs=Lb+Lw 若将长度为n的文件分为b块，每块内有s个记录，则 b=n/s 。设每块的查找概率为1/b，块内每个的记录查找概率为1/b，则采用顺序查找方法时有：

c数据结构h11

外部排序基本上由两个相对独立的结点组成。首先，按可用内存大小，将外存上含有n个记录的文件分成若干
长度为l的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常这些有序子文件称为归并段或顺串(run)；然后对这些归并段进行逐趟归并，使归并段逐渐由小变大，直至得到整个有序文件为止。假设有一个10000个记录的文件，首先通过10次内部排序得到10个初始归并段R1~R10，其中每一段都含1000 个记录。然后对它们作如下的两两归并，直至得到一个有序文件为止。 R1 R2 R1’ R1’’ R1’’’ 有序文件 R3 R2’ R4 R5 R3’ R2’’ R6 R7 R4’ R8 R9 R5’ R3’’ R2’’’ R10
一个10 500*10ms + 4*14ms = 5056 ms。由此可见，要想提高外排的效率关键在于减少外存信息读写的次数d。若对上例采用5－路平衡归并，则可以得到下图，此时只需进行两趟归并，外排时总的读/写次数便减少为2×100 ＋100＝300。 R1 R2 R3 R1’ 有序文件 R4 R5 R6 R7 R8 R2’ R9 R10
数据结构（语言描述语言描述）数据结构（C语言描述）
11.1外部排序外部排序
是对大文件的排序，即待排序的记录存储在外存储器上。
1。外存信息的存取。
磁带：顺序存取，主要用于处理变化少，只进行顺序存取的大量数据。磁盘：随机存取。读取时间包括寻道时间、等待时间和传输时间。
2。外部排序的方法。
由上图可见，由10个初始归并段得到一个有序文件，共进行了四趟归并，该法称为2－路平衡归并。对于外部排序一般情况下所需的总的时间为：内部排序(产生初始归并段）所需时间 m * tis +外存信息读写的时间 d * tio ＋内部归并所需的时间 s * utmg 其中，tis是得到一个初始归并段进行内部排序所需时间的均值；tio是进行依次外存读或写时间的均值；utmg是对u个记录进行内部归并所需的时间；m为经过内部排序之后得到的初始归并段的个数；s为归并的趟数；d为总的读/写次数。于是对上面的10000个记录的所需的总时间为： 10 * tis + 500 * tio + 4 * 10000 tmg 其中tio一般在10ms，而10000tmg的时间为O(10000* log210000)，约为140000 * 100ns = 14ms。10*tis约相当于

严蔚敏《数据结构》(第2版)章节题库-第11章外部排序【圣才出品】

第11章　外部排序一、选择题1．下列排序算法中，其中（）是稳定的。

A．堆排序，起泡排序B．快速排序，堆排序C．直接选择排序，归并排序D．归并排序，起泡排序【答案】D2．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A．快速排序B．堆排序C．归并排序D．直接插入排序【答案】C【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。

不稳定排序有：快速排序、堆排序、shell排序。

时间复杂度平均为O（nlog2n）的有：归并排序、堆排序、shell排序、快速排序。

3．在下面的排序方法中，辅助空间为O（n）的是（）。

A．希尔排序B．堆排序C．选择排序D．归并排序【答案】D4．下列排序算法中，占用辅助空间最多的是（）。

A．归并排序B．快速排序C．希尔排序D．堆排序【解析】归并排序的辅助空间为O（n），快速排序所占用的辅助空间为O（logn），堆排序所占用的辅助空间为O（1）。

5．将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A．N B．2N-1 C．2N D．N-1【答案】A【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。

最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序最好情况下的复杂度为O（n）。

6．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A．插入B．选择C．希尔D．二路归并【答案】A【解析】解此题需要熟知各种排序方法的基本思想。

插入排序的基本思想是：假设待排序的记录存放在数组R[0．．n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0．．i-1]和R[i．．n-1]，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。

将当前无序区的第1个记录R[i]插入到有序区R[0．．i-1]中适当的位置上。

数据结构第十、十一章：排序

14
9.2 交换排序
冒泡排序
排序过程
将第一个记录的关键字与第二个记录的关键字进行比较，将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与为逆序，则交换；第三个记录；依次类推，直至第n-1个记录和第个记录比较个记录和第n个记录比较第三个记录；依次类推，直至第个记录和第为止——第一趟冒泡排序，结果关键字最大的记录被安置在第一趟冒泡排序，为止第一趟冒泡排序最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的个记录进行第二趟冒泡排序，对前个记录进行第二趟冒泡排序记录被安置在第n-1个记录位置记录被安置在第个记录位置重复上述过程，直到“ 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作” 录的操作”为止
按待排序记录所在位置
内部排序：内部排序：待排序记录存放在内存外部排序：外部排序：排序过程中需对外存进行访问的排序
稳定排序和不稳定排序假设Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先假设（，，），且在排序前的序列中领先），且在排序前的序列中于Rj（即i<j）。若在排序后的排序中Ri仍领先于，即那些具（）。若在排序后的排序中仍领先于Rj，）。若在排序后的排序中仍领先于有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之，若Rj领先于，则称所用的则称这种排序方法是稳定的；反之，领先于Ri，领先于方法是不稳定的。方法是不稳定的。按排序依据原则
4
例

外部排序---数据结构

将b[ls[0]]写至输出归并段补充记录(某归并段变空时,补)，调整败者树
算法描述：建立败者树
void CreateLoserTree() { b[k] = MINKEY; for (i = 0; i < k; i++) ls[i] = k; for (i = k - 1; i >= 0; i++) Adjust(i); } void Adjust(int s) { for (t = (s + k) / 2; t > 0; t /= 2) { if (b[s] > b[ls[t]]) s ls[t]; } ls[0] = s; }
外部排序的方法

由两个独立的阶段组成

将外存含n个记录的文件分成若干长度为l的子文件或段，依次读入内存并用内部排序方法排序，将排序后的有序子文件重新写入外存，称为归并段或顺串对这些归并段进行逐趟归并，（有序子文件）由小变大，直到获得整个有序文件

外排序基本方法：归并排序
[步骤] 生成若干初始归并串/顺串(文件预处理) 把含有n个记录的文件，按内存缓冲区大小分成若干长度为L 的子文件（段）；分别调入内存用有效的内排序方法排序后送回外存；多路合并
外排序基本方法：归并排序

外存上的信息的读/写以“物理块”为单位，假设每个物理块可容纳200个记录，则每一趟归并所需进行50次“读”和50次“写”，4趟归并并加上内部排序所需进行的读写使得外排序总共需进行500读/写
外排序基本方法：归并排序

外部排序所需的总的时间= 内部排序所需的时间（m*tis） + 外存信息读写的时间（d*tio） + 内部归并所需的时间（s*utmg） tis:：得到一个厨师归并段进行内部排序所需时间 tio：进行一次外存读/写所需时间 utmg：对u个记录进行内部归并所需的时间 m：经过内部排序后得到初始归并段的个数 s：为归并的趟数 d：为总的读/写次数

数据结构第29讲：第11章外部排序-c

归并段2: {10, 12, ∞}
归并段3: {29, 32, ∞}
归并段4: {15, 56, ∞}
17
05 冠军 (最小记录),
输出段1当前记录
15
选中 10
29
17
29
29 32
归并段3
15
15 56
归并段4
17 21
归并段0
05
05 44
归并段1
10
10 12
归并段2
1.产生“败者树” 2. 输出当前最小； 3. 调整（从叶到根）；
用ls[1, 2, 3, 4, 5]指示内部结点对应的外部结点；
ls0 4 ls1 1
输出： 05，10，12，15， 17，21，29，32， 44，56
0 ls2
2 ls3
ls4 3
b0 b1
b2
b3
b4 56
56
归并段0 归并段1
归并段2
归并段3
归并段4
i 0 1 2 3 4 567 89 ls0 ls1 ls2 ls3 ls4 b0 b1 b2 b3 b4
{ 17，21，05， }
{ 10，12，44 ， }
{ 29，32，56 ， }
29 12 32 29 ─ 32 ─ ─ 32 ───
───
输出文件 FO
MinMax MinMax
05 05 17 05 17 21 05 17 21 44 05 17 21 44 56 05 17 21 44 56
10 10 12 10 12 29 10 12 29 32 10 12 29 32
1. 从比MinMax大的关键字中选择最小的； 2. MinMax越来越大； 3. 当选不出新的MinMax时，当前归并段结束；

数据结构(C语言版)排序

if(r[i].key < r[i-dk].key) {
r[0]=r[i]；
//暂存在r[0]
for(j=i-dk; j>0 &&(r[0].key<r[j].key); j=j-dk) r[j+dk]=r[j]； //关键字较大的记录在子表中后移
r[j+dk]=r[0]； //在本趟结束时将r[i]插入到正确位置
for(k=0；k<t；++k) ShellInsert(L，dlta[k])； //增量为dlta[k]的一趟插入排序
} // ShellSort
希尔排序算法（其中某一趟的排序操作）
void ShellInsert(SqList &L，int dk) {
//对顺序表L进行一趟增量为dk的Shell排序，dk为步长因子 for(i=dk+1；i<=L.length； ++ i) //开始将r[i] 插入有序增量子表
L.r[i]=L.r[i-1]; for(j=i-2; L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j]; // 记录后移 L.r[j+1]=L.r[0]; //插入到正确位置 } }
算法分析
• 设对象个数为n，则执行n-1趟 • 比较次数和移动次数与初始排列有关
•空间复杂度为 o(1) •是一种稳定的排序方法
希尔排序
算法思想的出发点：直接插入排序在基本有序时，效率较高在待排序的记录个数较少时，效率较高
基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

数据结构(第11章)

11.4 置换-选择排序
目标：分析：
如果记录个数为 n ，内存容量为 l 。则初始归并段的个数为： m ＝ n / l
归并趟数 S ＝ logkm
通过减少初始归并段的个数 m 来减少归并趟数的。
问题：
怎样在内存工作区只能容纳 l 记录的情况下，产生记录个数大于 l 的初始归并段？
ls0 2 2 ls1 4 4
输出： 05，10，12
0 ls2
ls4 3 b0 17 b1 44 17 b4 15 44 21 15 56 归并段0 归并段1
归并段4
1 1
ls3 b2 12
b3 29 29 32
归并段3
12
归并段2
i
0 1 2 3 4 5 6 7 8 9 ls0 ls1 ls2 ls3 ls4 b0 b1 b2 b3 b4
56
归并段4

归并段0
44
归并段1

归并段2
i
0 1 2 3 4 5 6 7 8 9 ls0 ls1 ls2 ls3 ls4 b0 b1 b2 b3 b4
用b0 , b1, b2, b3, b4指示参加归并的外部结点；用ls[1, 2, 3, 4, 5]指示内部结点对应的外部结点；
ls0 1 ls1 4
IRG
块3
IRG
记录
成块存放的磁带
IBG（Inter Block Gap）块间间隙
11.1 外存信息的存取
磁盘：是一个扁平的圆盘，盘面上有一些圆圈，称为磁道，信息记录在磁道上。特点：一种直接存取的存储设备。容量大、速度快、存取速度比磁带快。磁盘文件的位置：盘组号、柱面号、磁道号、块（扇区号）找道时间磁盘文件的读写时间：TI/O = tseek +

《数据结构(C版)(第二版)》第11章.

第11章文件
本章学习内容 11.1 文件的基本概念 11.2 顺序文件 11.3 索引文件 11.4 ISAM文件和VSAM文件
11.5 散列文件
11.6 多关键字文件
2018年9月24日
1
11.1 文件的基本概念
文件是由大量性质相同的记录所构成的集合。文件有不同的分类方式：按记录类型分：操作系统文件和数据库文件。按记录是否定长分：定长记录文件和不定长记录文件。按查找关键字多少分：单关键文件和多关键文件。记录有逻辑结构和存储结构之分。记录的逻辑结构，是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。记录的存储结构是指数据在物理存储器中的存储形式，是数据的物理表示和组织。
2018年9月24日
2
文件和数据元素一样，也有逻辑结构和存储结构。文件的逻辑结构可以表现为记录的逻辑结构。文件的存储结构是指文件在物理存储器（磁盘或磁带）中的组织方式。文件可以有各种各样的组织方式，其基本方式有三种：顺序组织、随机组织和链组织。对文件所施加的运算（操作）有两类：查找（检索）和更新（修改）。文件的查找（检索）有三种方式：顺序查找、按记录号直接随机查找、按关键字直接随机查找。
磁道索引 r47 384 3 4150 溢出区
图11-2 ISAM文件结构
2018年9月24日
10
从图11-2可以看到，每个柱面上还开辟有一个溢出区，这是为插入记录所设置的。由于ISAM文件中记录是按关键字顺序存放的，则在插入记录时需移动记录并将同一磁道上最末一个记录移到溢出区，同时修改磁道索引项。通常在文件中可集中设置一个溢出区，或在每个柱面分别设置一个溢出区，或在柱面溢出区满后再使用公共溢出区。引 330
磁道索引 50 164

【数据结构】排序——外部排序

【数据结构】排序——外部排序【数据结构】排序——外部排序外部排序是指⼤⽂件的排序，即排序的记录存储在外存储器上，在排序过程中需进⾏多次的内、外存之间的交换。

外部排序⽅法通常采⽤归并排序有外部排序基本上由两个相对独⽴的阶段组成。

按可⽤内存⼤⼩，将外存上含有n个记录的⽂件分成若⼲长度为l的字⽂件或段。

依次读⼊内存并利⽤有效的内部排序⽅法排序，将排序后得到的有序⼦⽂件（称为归并段或顺串），进⾏逐趟归并，直⾄得到整个有序⽂件为⽌。

在外部排序中实现两两归并，由于不可能将两个有序段及归并结果段同时存放在内存中的缘故，所以不仅要调⽤归并过程，还需要进⾏外存的读_写（对外存上信息的读_写是以“物理块”为单位的）。

耗费时间总时间=内部排序时间(产⽣初始归并段)+外存读写时间+内部归并时间内部排序时间=经过内部排序后得到的初始归并段的个数r * 得到⼀个初始归并段进⾏内部排序多需时间的均值外存读写时间=总的读写次数 * 进⾏⼀次外存读写时间的均值内部归并时间=归并的趟数s * n个记录进⾏内部归并排序的时间优化⽅法增⼤归并路数k减少初始归并段个数r以上两个⽅法都可以减少归并的趟数，进⽽减少读写磁盘的次数，提⾼外部排序速度多路平衡归并与败者树已知增加k可以减少s，从⽽减少总的读写次数。

如果只单纯的增加k⼜会导致内部归并时间增加。

为了使内部归并不受k的增⼤⽽影响，提出了败者树。

败者树的基本思想败者树是树形选择排序的⼀种变型，可视为⼀棵完全⼆叉树。

k个叶⼦节点分别存放k个归并段在归并过程中当前参加⽐较的记录，内部节点⽤来记忆左右⼦树中的“失败者”，⽽让胜者往上继续进⾏⽐较，⼀直到根结点。

若⽐较两个数，⼤的为败者、⼩的为胜利者，则根结点指向的数为最⼩数。

eg、设初始归并段为(10,15,31),(9,20),(6,15,42),(12,37),(84,95),利⽤败者树进⾏m路归并，⼿⼯执⾏选择最⼩的5个关键字的过程。

性能分析k-路归并的败者树的深度为[log2k]+1注意⚠ 在多路平衡归并中采⽤简单⽐较时，k越⼤，关键字的⽐较次数会越⼤。

数据结构11-外部排序

例： 5 - 路平衡归
并的败者树：
[0] 531 [1] 510
[2] 5304
[3] 52
[4] 543
b0 12 b1 1805 b2 30
b3 b4 253 16
12 1805 30 14 12059 38
253 16 17 128598 56
b5
2334
0 3448
28 31
初始归并段
5
8 10 …
磁盘是在一片塑料薄膜上涂有磁性材料用以记录数据的存储介质。它分成多个磁道（柱面），每个磁道又分为多个扇区，多个磁盘组成的磁盘组还涉及到盘片号（磁头号），磁盘绕轴高速旋转，读写头则沿其一条半径作直线运动以寻道。它也不是
连续运转的设备，读写信息只能在旋转稳定时进行，且找到要读写的记录也需要一定的寻道、寻扇区时间，因此，在磁盘上读写信息所需的时间由三部分组成：TI/O = tseek + tla + n tw，其中 tseek 为寻道时间（seek time）， tla 为寻扇区时间（latency time time）， tw 为传输时间（transmission time）。磁盘是一种随机存储设备。
§11.6 最佳归并树
用置换-选择排序得到的初始归并段长度各不相同，那应如何进行 k 路平衡归并呢？这实际上是建立 k 叉霍夫曼树的问题：当初始归并段总数不足（ ( m 1 ) MOD ( k - 1 ) ≠ 0 ）时，需附加 k - ( m - 1 ) MOD ( k - 1 ) -1 个长度为零的虚段，亦即第一次归并时只对 ( m - 1 ) MOD ( k - 1 ) + 1 个初始归并段归并。建立 k 叉霍夫曼树每次仍是选择记录数相对少的初始归并段先进行归并。最佳归并树不适合磁带归并排序。

外部排序---数据结构

外部排序---数据结构外部排序数据结构在计算机科学中，数据的排序是一项非常基础且重要的操作。

当数据量过大，无法一次性全部放入内存进行排序时，就需要用到外部排序这种技术。

想象一下，你有一个巨大的数据集，大到内存根本装不下。

这时候，内部排序算法，比如快速排序、冒泡排序等等，就显得无能为力了。

外部排序就像是一位超级英雄，专门来解决这种内存装不下的大问题。

外部排序的基本思路其实并不复杂，但实现起来却需要一些巧妙的策略。

它通常会将数据分成多个较小的部分，先在内存中对这些小部分进行排序，然后将排序好的小部分逐次合并，最终得到完全有序的数据。

为了更好地理解外部排序，让我们先来看看它的工作流程。

假设我们有一个非常大的文件需要排序，由于内存限制，我们不能一次性把整个文件读入内存。

所以，第一步就是将这个大文件分割成若干个大小适中的子文件，这些子文件能够被轻松地读入内存。

然后，我们在内存中使用一种内部排序算法，比如快速排序，对每个子文件进行单独排序。

接下来就是关键的合并步骤。

我们会从已经排序好的子文件中依次读取数据，然后将它们合并到一个新的文件中。

这个合并的过程就像是把几堆已经排好序的扑克牌重新整理成一整堆有序的扑克牌。

在合并的过程中，我们需要不断地比较来自不同子文件的数据，将较小的数据先放入新文件中。

那么，在这个过程中，有哪些关键的技术和要点呢？首先是数据的分割策略。

我们要确保分割出来的子文件大小合适，既能在内存中高效处理，又不会导致分割次数过多而增加额外的开销。

如果子文件分得太小，那么合并的次数就会增多，效率就会降低；如果分得太大，又无法在内存中进行排序。

其次是内存的使用。

在外部排序中，内存的使用需要非常精细地管理。

我们不仅要为读取和写入数据留出空间，还要为中间的比较和合并操作保留足够的缓冲区。

如果内存使用不当，可能会导致频繁的磁盘读写，大大降低排序的速度。

还有就是合并算法的选择。

常见的合并算法有二路归并和多路归并。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

每个控制区间存放一个或多个逻辑记录，记录是按关键字值顺序存放在控制区间的前端，尾端存放记录的控制信息和控制区间的控制信息，如图11-5所示。
R1 R2 … Rn
未用的 R n的 R1的控制区间的 … 控制信息控制信息自由空间控制信息
图11-5 控制区间的结构
顺序集是由B+树索引结构的叶子结点组成。每个结点存放若干个相邻控制区间的索引项，每个索引项存放一个控制区间中记录的最大关键字值和指向该控制区间的指针。顺序集中的每个结点及与它所对应的全部控制区间组成一个控制区域。顺序集中的结点之间按顺序链接成一个链表，每个结点又在其上层建立索引，并逐层向上按B+树的形式建立多级索引。则顺序集中的每一个结点就是B+树的叶子结点；在顺序集之上的索引部分称为索引集。在VSAM文件上既可以按B+树的方式实现记录的查找，又可以利用顺序集索引实现记录顺序查找。
◆ 若控制区域中没有空白控制空间：则开辟一个新的控制区域，进行控制区间域分裂和相应的顺序集中的结点分裂。也可按B+树的分裂方法进行。
2 记录的删除
先找到要删除的记录，然后将同一控制区间中比删除记录关键字大的所有记录逐个前移，覆盖要删除的记录。当一个控制区间的记录全部删除后，需修改顺序集中相应的索引项。
◆ 简单匹配：查找关键字的值与给定的值相等的记录； ◆ 区域匹配：查找关键字的值在某个区域范围内的记录； ◆ 函数匹配：给出关键字的某个函数，查找符合条件的记录； ◆ 组合条件匹配：给出用布尔表达式表示的多个条件组合，查找符合条件的记录。
⑵ 插入记录
将给定的记录插入到文件的指定位置。插入是首先要确定插入点的位置(检索记录)，然后才能插入。
柱面扇区
…
…
盘面
…
图11-2 一个磁盘组结构形式
பைடு நூலகம்
在每个柱面上，还开辟了一个溢出区，存放从该柱面的磁道上溢出的记录。同一磁道上溢出的记录通常由指针相链接。 ISAM文件为每个磁道建立一个索引项，相同柱面的磁道索引项组成一个索引表，称为磁道索引，由基本索引项和溢出索引项组成，其结构是：
关键字指针关键字指针
11.2.2
索引文件
索引技术是组织大型数据库的一种重要技术，索引是记录和记录存储地址之间的对照表。索引结构(称为索引文件)由索引表和数据表两部分，如图11-1所示。 ◆ 数据表：存储实际的数据记录； ◆ 索引表：存储记录的关键字和记录(存储)地址之间的对照表，每个元素称为一个索引项。如果数据文件中的每一个记录都有一个索引项，这种索引称为稠密索引，否则，称为非稠密索引。对于非稠密索引，通常将文件记录划分为若干块，块内记录可以无序，但块间必须有序。若块内记录是有序的，称为索引顺序文件，否则称为索引非顺序文件。对于索引非顺序文件，只需对每一块建立一个索引项。
关键字指针 263 275 386 593 681 … … 1046 索引表关键字指针 263 386 681 … …
关键字其他域 386 1046 681 263 275 … … 593 数据表
(a) 稠密索引文件
关键字其他域 386 … … 681 263 275 索引表数据表 (b) 非稠密索引文件
图11-1 索引结构的基本形式
对于稠密索引，可以根据索引项直接查找到记录的位置。若在索引表中采用顺序查找，查找时间复杂度为 O(n) ；若采用折半查找，查找时间复杂度为O(㏒2n) 。对于稠密索引，索引项数目与数据表中记录数相同，当索引表很大时，检索记录需多次访问外存。对于非稠密索引，查找的基本思想是：首先根据索引找到记录所在块，再将该块读入到内存，然后再在块内顺序查找。平均查找长度由两部分组成：块地址的平均查找长度Lb，块内记录的平均查找长度Lw，即ASLbs=Lb+Lw 若将长度为n的文件分为b块，每块内有s个记录，则 b=n/s 。设每块的查找概率为1/b，块内每个的记录查找概率为1/b，则采用顺序查找方法时有：
基本索引项
溢出索引项
◆ 基本索引项：关键字域存放该磁道上的最大关键字；指针域存放该磁道的首地址。
◆ 溢出索引项：是为插入记录设置的。关键字域存放该磁道上溢出的记录的最大关键字；指针域存放溢出记录链表的头指针。在磁道索引的基础上，又为文件所占用的柱面建立一个柱面索引，其结构是：
关键字指针
基本区溢出区
… R31 柱面Cn …
┇ ┇
76
┇
3760
348
┇
768
┇
2340
┇
R2340
┇
3760
3760
…
溢出区
R3760
图11-3 ISAM文件结构示意图
1 ISAM文件的检索
根据关键字查找时，首先从主索引中查找记录所在的柱面索引块的位置；再从柱面索引块中查找磁道索引块的位置；然后再从磁道索引块中查找出该记录所在的磁道位置；最后从磁道中顺序查找要检索的记录。
69 124 246
22 38 12 20 24 31 69 38 …… …… 198 246
索引集 246 顺序集
B+ 树
212 228
6 14 8 17 12 20 控制区域
┇ ┇ ┇ 控制区间
……
203 213 233 208 218 238 数据集 212 228 246
图11-4 VSAM文件结构示意图
文件存储在外存上，通常是以块(I/O读写的基本单位，称为物理记录)存取。物理记录和逻辑记录之间的关系是：
① 一个物理记录存放一个逻辑记录；
② 一个物理记录包含多个逻辑记录； ③ 多个物理记录存放一个逻辑记录。 ⑶ 文件(File)：大量性质相同的数据记录的集合。文件的所有记录是按某种排列顺序呈现在用户面前，这种排列顺序可以是按记录的关键字，也可以是按记录进入文件的先后等。则记录之间形成一种线性结构(逻辑上的)，称为文件的逻辑结构；文件在外存上的组织方式称为文件的物理结构。基本的物理结构有：顺序结构，链接结构，索引结构。
4 ISAM文件的特点
◆ 优点：节省存储空间，查找速度快； ◆ 缺点：处理删除记录复杂，多次删除后存储空间的利用率和存取效率降低，需定期整理ISAM文件。
11.2.4 VSAM文件
VSAM(Virtual Storage Access Method，虚拟存取方法)，也是一种索引顺序文件组织方式，利用OS的虚拟存储器功能，采用的是基于B+树的动态索引结构。文件的存取不是以柱面、磁道等物理空间为存取单位，而是以逻辑空间——控制区间(Control Interval)和控制区域(Control Range)为存取单位。一个VSAM文件由索引集、顺序集和数据集组成，如图11-4所示。文件的记录都存放在数据集中，数据集又分成多个控制区间；VSAM进行I/O操作的基本单位是控制区间，由一组连续的存储单元组成，同一文件的控制区间大小相同；
11.2.3 ISAM文件
ISAM(Indexed Sequential Access Method，顺序索引存取方法)，是专为磁盘存取设计的一种文件组织方式，采用静态索引结构，是一种三级索引结构的顺序文件。图11-2是一个磁盘组的结构图。 ISAM文件由基本文磁道件、磁道索引、柱面索引和主索引组成。基本文件按关键字的值顺序存放，首先集中存放在同一柱面上，然后再顺序存放在相邻柱面上；对于同一柱面，则按盘面的次序顺序存放。
11.2 文件的组织方式
文件的组织方式指的是文件的物理结构。
11.2.1 顺序文件
记录按其在文件中的逻辑顺序依次进入存储介质。在顺序文件中，记录的逻辑顺序和存储顺序是一致的。 ⑴ 根据记录是否按关键字排序：可分为排序顺序文件和一般顺序文件； ⑵ 根据逻辑上相邻的记录的物理位置关系：可分为连续顺序文件和链接顺序文件。顺序文件类似于线性表的顺序存储结构，比较简单，适合于顺序存取的外存介质，但不适合随机处理。
2 文件的有关操作
文件是由大量记录组成的线性表，因此，对文件的操作主要是针对记录的，通常有：记录的检索、插入、删除、修改和排序，其中检索是最基本的操作。
⑴ 检索记录
根据用户的要求从文件中查找相应的记录。 ① 查找下一个记录：找当前记录的下一个逻辑记录； ② 查找第k个记录：给出记录的逻辑序号，根据该序号查找相应的记录； ③ 按关键字查找：给出指定的关键字值，查找关键字值相同或满足条件的记录。对数据库文件，有以下四种按关键字查找的方式：
2 记录的插入
首先根据待插入记录的关键字查找到相应位置；然后将该磁道中插入位置及以后的记录后移一个位置(若溢出，将该磁道中最后一个记录存入同一柱面的溢出区，并修改磁道索引) ；最后将记录插入到相应位置。
3 记录的删除
只需找到要删除的记录，对其做删除标记，不移动记录。当经过多次插入和删除操作后，基本区有大量被删除的记录，而溢出区也可能有大量记录，则周期性地整理ISAM文件，形成一个新的ISAM文件。
⑷ 文件的分类
⑴ 按记录类型，可分为操作系统文件和数据库文件： ① 操作系统文件(流式文件) ：连续的字符序列 (串)的集合； ② 数据库文件：有特定结构(所有记录的结构都相同)的数据记录的集合。 ⑵ 按记录长度，可分为定长记录文件和不定长记录文件： ① 定长记录文件：文件中每个记录都有固定的数据项组成，每个数据项的长度都是固定的； ② 不定长记录文件：与定长记录文件相反。
⑶ 删除记录
从文件中删除给定的记录。记录的删除有两种情况： ① 在文件中删除第k个记录； ② 在文件中删除符合条件的记录。
⑷ 修改记录
对符合条件的记录，更改某些属性值。修改时首先要检索到所要修改的记录，然后才能修改。

数据结构(C语言版)第11章文件与外部排序

合集下载