第8章文件管理和外排序.ppt

《第8章文件管理和外排序.ppt》由会员分享，可在线阅读，更多相关《第8章文件管理和外排序.ppt（95页珍藏版）》请在三一文库上搜索。

1、第8章 文件管理和外排序,任课教员：张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有，转载或翻印必究,北京大学信息学院 Page 2,为什么需要文件管理和外排序？,文件结构( file structure ) 对于在外存中存储的数据，其数据结构就称为文件结构( file structure ) 数据量太大不可能同时把它们放到内存中 需要把全部数据放到磁盘中 文件的各种运算 外排序是针对磁盘文件所进行的排序操作 提高文件存储效率和运算效率,北京大学信息学院 Page 3,本章的安排顺序,8.1 介绍主存和外存的根本差异 8.2 在外存中文件的组织方式 8.3 管

2、理缓冲池的基本方法 8.4 外排序的基本算法,北京大学信息学院 Page 4,主存储器和外存储器,主存储器( primary memory或者main memory ，简称“内存”，或者“主存”) 随机访问存储器( Random Access Memory, 即RAM ) 高速缓存( cache ) 视频存储器( video memory ) 。 外存储器(peripheral storage或者secondary storage，简称“外存”) 硬盘 软盘 磁带,北京大学信息学院 Page 5,主存储器和外存储器 之价格比较,北京大学信息学院 Page 6,外存的优缺点,优点：永久存储能力、

3、便携性 缺点：访问时间长 访问磁盘中的数据比访问内存慢五六个数量级。 所以讨论在外存的数据结构及其上的操作时，必须遵循下面这个重要原则： 尽量减少访外次数！,北京大学信息学院 Page 7,磁盘的物理结构,北京大学信息学院 Page 8,磁盘盘片的组织,北京大学信息学院 Page 9,磁盘存取步骤,选定某个盘片组 选定某个柱面 这需要把磁头移动到该柱面 ，这个移动过程称为寻道( seek ) 确定磁道 确定所要读写的数据在磁盘上的准确位置 这段时间一般称为旋转延迟( rotational delay 或者rotational latency ) 真正进行读写,北京大学信息学院 Page 10,

4、磁盘磁道的组织（交错法）,（a）没有扇区交错；（b）以3为交错因子,北京大学信息学院 Page 11,磁盘访问时间估算,磁盘访问时间主要由寻道时间、旋转延迟时间和数据传输时间组成。 寻道时间（Seek time）：是移动磁盘臂，定位到正确磁道所需的时间。 旋转延迟时间：是等待被存取的扇区出现在读写头下所需的时间。,北京大学信息学院 Page 12,总存取时间(1),（1）数据连续存放，而且给出了平均寻道时间。 总存取时间 = 平均寻道时间 + 第一道读取时间 + (总磁道数1)(第二次寻道时间)+(读取整道的时间) = 平均寻道时间 + (0.5圈延迟+交错因子) 每圈所花时间 + (总磁道数

5、1) 磁道转换时间+(0.5圈延迟+交错因子)每圈所花时间,北京大学信息学院 Page 13,总存取时间(2),（2）数据随机存放 。 总存取时间 = 簇数 平均寻道时间+旋转延迟+读一簇时间 = 簇数 平均寻道时间 + 0.5圈延迟每圈所花时间 + 交错因子（每簇扇区数/每道扇区数）每圈时间,北京大学信息学院 Page 14,例8.1 假定一个磁盘总容为16.8GB，分布在10个盘片上。每个盘片上有13085个磁道，每个磁道中包含256个扇区，每个扇区512个字节，每个簇8个扇区。扇区的交错因子是3。磁盘旋转速率是5400 rpm，磁道转换时间是2.2 ms，随机访问的平均寻道时间是9.5

6、ms。,北京大学信息学院 Page 15,如果读取一个1MB的文件，该文件有2048个记录，每个记录有512字节（1个扇区）。对于以下两种情况，估算进行文件处理的总时间。 （1）假定所有记录在8个连续磁道上； （2）假定文件簇随机地散布在磁盘上。,北京大学信息学院 Page 16,解：我们先总结出一些共有的特性 每个簇为4KB 8个扇区 512 byets 8 4KB 每个磁道有32簇 256个扇区 256 扇区 8（扇区/簇） = 32个簇 每个盘片有1.68GB 16.8GB 10 = 1.68GB 每转一圈的时间为11.1ms (601000)ms/5400圈 = 11.1（ms/圈）=

7、 11.1（ms/道） 一个磁道是一个整圈，因此，下面计算公式中，所用的单位“圈”等同于“道”,北京大学信息学院 Page 17,数据连续存放，而且给出了平均寻道时间。 总存取时间 = 平均寻道时间 + (0.5圈延迟+交错因子) 每圈所花时间 + (总磁道数1) 磁道转换时间+(0.5圈延迟+交错因子)每圈所花时间 = 9.5ms（平均寻道时间） + (0.5（半圈旋转延迟） + 3（交错因子）)11.1ms/圈 +（8-1）个其他磁道 2.2ms磁道转换时间+(0.5圈延迟+3交错因子)11.1ms/圈 = 9.5ms + 38.9ms + 7 41.1ms = 336.1ms,北京大学信

8、息学院 Page 18,数据随机存放 总簇数：8个磁道 32(簇/磁道) = 256簇 总存取时间 = 簇数 平均寻道时间 + 0.5圈延迟每圈所花时间 + 交错因子（每簇扇区数/每道扇区数）每圈时间 = 256 9.5ms（平均寻道时间） + 0.5（半圈旋转延迟）11.1ms/圈 + 3(交错因子)8(扇区/簇/)256(扇区/道) 11.1ms/圈 256 9.5 + 5.55 + 1.04ms 4119.04ms,北京大学信息学院 Page 19,读一簇的时间 9.5ms(平均寻道时间)+0.5(半圈旋转延迟)11.1ms/圈+1扇区256(扇区/道) 11.1ms/圈 9.5 + 5

9、.55 + 1.04= 16.09ms 定位后，实际读一簇数据的时间 3(交错因子)8(扇区/簇/)256(扇区/道) 11.1ms/圈 1.04ms 读一个字节的时间 9.5ms(平均寻道时间)+0.5(半圈旋转延迟)11.1ms/圈 15.05ms “一次访外”操作 磁盘一次I/O操作访问一个扇区，通常称为访问“一页”（page），或者“一块”(block),北京大学信息学院 Page 20,磁带,主要优点 ：使用方便、价格便宜、容量大、所存储的信息比磁盘和光盘更持久 缺点：速度较慢，只能进行顺序存取,北京大学信息学院 Page 21,磁带运行示意图,磁带卷在一个卷盘上，运行时磁带经过读写

10、磁头，把磁带上的信息读入计算机，或把计算机中的信息写在磁带上。,北京大学信息学院 Page 22,磁带发展史,手工阶段 自动化磁带库系统 虚拟磁带技术,北京大学信息学院 Page 23,外存文件的组织,文件是一些记录的汇集，其中每个记录由一个或多个数据项组成。 数据项有时也称为字段，或者称为属性。例如，一个职工文件里的记录可以包含下列数据项：职工号，姓名，性别，职务，婚姻状况，工资等。,北京大学信息学院 Page 24,文件组织,逻辑文件 对高级程序语言的编程人员而言，存储在磁盘中可以随机访问的文件被当作一段连续的字节，而且可以把这些字节结合起来构成记录，这种文件被称为逻辑文件( logica

11、l file )。 物理文件 实际存储在磁盘中的物理文件( physical file )通常不是一段连续的字节，而是成块地分布在整个磁盘中。 文件管理器 是操作系统的一部分，当应用程序请求从逻辑文件中读解数据时，它把这些逻辑位置映射为磁盘中具体的物理位置。,北京大学信息学院 Page 25,文件的逻辑结构,文件是记录的汇集。 当一个文件的各个记录按照某种次序排列起来时，各纪录间就自然地形成了一种线性关系。 因而，文件可看成是一种线性结构。,北京大学信息学院 Page 26,文件的存储结构,顺序结构顺序文件 计算寻址结构散列文件 带索引的结构带索引文件,北京大学信息学院 Page 27,文件上

12、的操作,检索：在文件中寻找满足一定条件的记录 修改：是指对记录中某些数据值进行修改。若对关键码值进行修改，这相当于删除加插入。 插入：向文件中增加一个新记录。 删除：从文件中删去一个记录 。 排序 ：对指定好的数据项，按其值的大小把文件中的记录排成序列，较常用的是按关键码值的排序。,北京大学信息学院 Page 28,C的流文件,C+程序员对随机访问文件的逻辑视图是一个单一的字节流，即字节数组。 程序员需要管理标志文件当前位置的文件指针。 常见的三个基本文件操作，都是围绕文件指针进行的： 把文件指针设置到指定位置（移动文件指针） 从文件的当前位置读取字节 向文件中的当前位置写入字节,北京大学信息

13、学院 Page 29,C操作二进制文件的常用方式fstream类,fstream类提供函数操作可随机访问的磁盘文件中的信息。 fstream类的主要成员函数包括open，close，read，write，seekg，seekp。,北京大学信息学院 Page 30,fstream类的主要函数成员,#include/fstream=ifstream+ofstream / 打开文件进行处理。 / 模式示例: ios:in | ios:binary void fstream:open(char* name, openmode mode); / 处理结束后关闭文件。 void fstream:close

14、();,北京大学信息学院 Page 31,ftream类的主要函数成员（续1）,/ 从文件当前位置读入一些字节。 / 随着字节的读入，文件当前位置向前移动。 fstream:read(char* ptr, int numbytes); / 向文件当前位置写入一些字节 / (覆盖已经在这些位置的字节)。 / 随着字节的写入，文件当前位置向前移动。 fstream:write(char* ptr, int numbtyes);,北京大学信息学院 Page 32,ftream类的主要函数成员（续2）,/ seekg和seekp：在文件中移动当前位置， / 这样就可以在文件中的任何一个位置 / 读出或

15、写入字节。 / 实际上有两个当前位置， /一个用于读出，另一个用于写入。 / 函数seekg用于改变读出位置， / 函数seekp用于改变写入位置 fstream:seekg(int pos); / 处理输入 fstream:seekg(int pos, ios:curr); fstream:seekp(int pos); / 处理输出 fstream:seekp(int pos, ios:end);,北京大学信息学院 Page 33,缓冲,目的：减少磁盘访问次数的 方法：缓冲( buffering )或缓存( caching ) 在内存中保留尽可能多的块 可以增加待访问的块已经在内存中的机会

16、，因此就不需要访问磁盘,北京大学信息学院 Page 34,缓冲区和缓冲池,存储在一个缓冲区中的信息经常称为一页( page )，往往是一次I/O的量 缓冲区合起来称为缓冲池( buffer pool ),北京大学信息学院 Page 35,替换缓冲区块的策略,“先进先出”(FIFO) “最不频繁使用”(LFU) “最近最少使用”(LRU),北京大学信息学院 Page 36,虚拟存储 ( virtual memory ),虚拟存储使得程序员能够使用比实际内存更大的内存空间。 磁盘中存储虚拟存储器的全部的内容，根据存储器的访问需要把块读入内存缓冲池。,北京大学信息学院 Page 37,虚拟存储,系统

17、运行到某一时刻，虚拟地址空间中有5个页被读入到物理内存中，现在如果需要对地址为24k-28k的页进行访问，就必须替换掉当前物理内存中的一个页框。,北京大学信息学院 Page 38,外排序,外排序( external sort ) 外存设备上(文件)的排序技术 由于文件很大，无法把整个文件的所有记录同时调入内存中进行排序，即无法进行内排序 外部排序算法的主要目标是尽量减少读写磁盘的次数,北京大学信息学院 Page 39,关键码索引排序,索引文件( index file )中 关键码与指针一起存储 指针标识相应记录在原数据文件中的位置 对索引文件进行排序，所需要的I/O操作更少 索引文件比整个数据

18、文件小很多。 在一个索引文件中，只针对关键码排序( key sort )。,北京大学信息学院 Page 40,磁盘排序过程,顺串：用某种有效的内排序方法对文件的各段进行初始排序，这些经过排序的段通常称为顺串( run ) ，它们生成之后立即被写回到外存上。 磁盘排序过程： 文件分成若干尽可能长的初始顺串； 逐步归并顺串归，最后形成一个已排序的文件。,北京大学信息学院 Page 41,置换选择排序,采用置换选择算法，在扫描一遍的前提下，使得所生成的各个顺串有更大的长度。这样减少了初始顺串的个数，有利于在合并时减少对数据的扫描遍数。,北京大学信息学院 Page 42,置换选择算法,假设外排序算法可

19、以使用一个输入缓冲区、一个输出缓冲区、一个能存放M个记录的RAM内存块（可以看成大小为M的连续数组）。排序操作可以利用缓冲区，但只能在RAM中进行。 平均情况下，这种算法可以创建长度为2M个记录的顺串。,北京大学信息学院 Page 43,置换选择方法图示,处理过程为：从输入文件读取记录（一整块磁盘中所有记录），进入输入缓冲区；然后在RAM中放入待排序记录；记录被处理后，写回到输出缓冲区；输出缓冲区写满的时候，把整个缓冲区写回到一个磁盘块。当输入缓冲区为空时，从磁盘输入文件读取下一块记录。,北京大学信息学院 Page 44,置换选择算法,1. 初始化堆： (a) 从磁盘读M个记录放到数组RAM中

20、。 (b) 设置堆末尾标准LAST M 1。 (c) 建立一个最小值堆。,北京大学信息学院 Page 45,置换选择算法（续）,2. 重复以下步骤，直到堆为空（即LAST 0）： (a) 把具有最小关键码值的记录(根结点)送到输出缓冲区。 (b) 设R是输入缓冲区中的下一条记录。如果R的关键码值大于刚刚输出的关键码值 i. 那么把R放到根结点。 ii. 否则使用数组中LAST位置的记录代替根结点，然后把R放到LAST位置。设置LAST LAST 1。 (c)重新排列堆，筛出根结点。,北京大学信息学院 Page 46,置换选择示例（1）,北京大学信息学院 Page 47,置换选择示例（2）,北京

21、大学信息学院 Page 48,置换选择示例（3）,北京大学信息学院 Page 49,置换选择算法的实现,/置换选择算法 /模板参数Elem代表数组中每一个元素的类型 /A是从外存读入n个元素后所存放的数组，n是数组元素的个数 /in和out分别是输入和输出文件名 template void replacementSelection(Elem * A, int n, const char * in, const char * out),北京大学信息学院 Page 50,置换选择算法的实现（续1）,Elem mval; /存放最小值堆的最小值 Elem r; /存放从输入缓冲区中读入的元素 /输入

22、、输出文件句柄 FILE * inputFile; FILE * outputFile; /输入、输出buffer Buffer input; Buffer output; /初始化输入输出文件 initFiles(inputFile, outputFile, in, out);,北京大学信息学院 Page 51,置换选择算法的实现（续2）,/* 算法主体部分 */ /初始化堆的数据， / 从磁盘文件读入n个数据置入数组A initMinHeapArry(inputFile, n, A); /建立最小值堆 MinHeap H(A, n, n);,北京大学信息学院 Page 52,置换选择算法的

23、实现（续3）,/初始化input buffer，读入一部分数据 initInputBuffer(input, inputFile); for(int last = (n-1); last = 0;) /堆不为空，就做这个循环 mval = H.heapArray0; /堆的最小值 /把mval送到输出缓冲区， /同时处理因缓冲区空或满造成的各种情形 sendToOutputBuffer(input, output, inputFile, outputFile, mval);,北京大学信息学院 Page 53,置换选择算法的实现（续4）,input.read(r); /从输入缓冲区读入一个记录

24、if(!less(r, mval) /若r的关键码值大于等于刚才输出缓冲区记录的关键码值，/把r放到根结点 H.heapArray0 = r; else /否则用last位置的记录代替根结点，把r放到last位置 H.heapArray0 = H.heapArraylast; H.heapArraylast = r; H.setSize(last); last-; ,北京大学信息学院 Page 54,置换选择算法的实现（续5）,H.SiftDown(0); /把根结点记录下降到合适的位置 /for /算法结束工作： /处理输出缓冲区，输入/输出文件 endUp(output, inputFil

25、e, outputFile); ,北京大学信息学院 Page 55,置换选择算法的效果,如果堆的大小是M 一个顺串的最小长度就是M个记录 至少原来在堆中的那些记录将成为顺串的一部分 最好的情况下，例如输入已经被排序，有可能一次就把整个文件生成为一个顺串。,北京大学信息学院 Page 56,扫雪机模型,扫雪机模型显示扫雪机在环绕一圈过程中的行为。根据“扫雪机”模型的分析，可以预计平均情况下顺串总长度是数组长度的两倍。,北京大学信息学院 Page 57,二路外排序,归并原理：把第一阶段所生成的顺串加以合并(例如通过若干次二路合并)，直至变为一个顺串为止，即形成一个已排序的文件。,北京大学信息学院

26、Page 58,二路归并外排序,北京大学信息学院 Page 59,多路归并,三路归并,北京大学信息学院 Page 60,选择树,在K路归并中，最直接的方法就是作K-1次比较来找出所要的记录，但这样做花的代价较大，我们采用选择树的方法来实现K路归并。 选择树是完全二叉树，有两种类型：赢者树和败方树。,北京大学信息学院 Page 61,赢者树,叶子节点用数组L表示 代表各顺串在合并过程中的当前记录（图中标出了它们各自的关键码值）； 分支节点用数组B表示 每个分支节点代表其两个儿子结点中的赢者(关键码值较小的)所对应数组L的索引。 因此，根结点是树中的最终赢者的索引，即为下一个要输出的记录结点。,北

27、京大学信息学院 Page 62,赢者树示例（1）,根结点所指向的L4记录具有最小的关键码值6，它所指的记录是顺串4的当前记录，该记录即为下一个要输出的记录。,北京大学信息学院 Page 63,赢者树示例（2）,重构后的赢者树，改动的节点用较粗的框显示出来。为了重构这颗树，只须沿着从结点L4到根结点的路径重新进行比赛。,北京大学信息学院 Page 64,赢者树ADT,template class WinerTree public: Create(); /创建一个空的赢者树 Iitialize(T a, int n); /返回比赛的赢者 Replay(i); /选手i变化时，重建赢者树 ;,北京大

28、学信息学院 Page 65,赢者树与数组的对应关系,外部节点的数目为n，LowExt代表最底层的外部节点数目 ；offset代表最底层外部节点之上的所有节点数目 。每一个外部节点Li所对应的内部节点Bp，i和p之间存在如下的关系： p =,北京大学信息学院 Page 66,赢者树的类定义,template class WinnerTree private: int MaxSize; /允许的最大选手数 int n; /当前大小 int LowExt; /最低层的外部节点数 int offset; /2s+11 int * B; /内部节点数组 T * L; /外部节点数组 void Play(

29、int p, int lc, int rc, int(* winner)(T A, int b, int c);,北京大学信息学院 Page 67,赢者树的类定义（续）,public: WinnerTree(int Treesize = MAX); WinnerTree()delete B; void Initialize(T A, int size,int (*winner)(T A, int b, int c); /初始化赢者树 int Winner();/返回最终胜者的索引 void RePlay(int i, int(*winner)(T A, int b, int c); /位置i的

30、外部选手改变后重构赢者树 ;,北京大学信息学院 Page 68,败方树,所谓败方树就是在选择 (比赛)树中，每个非叶结点均存放其两个子结点中的败方所对应叶子节点的索引值。 此外，还另加进一个结点，即结点B0，以代表比赛的全局获胜者的索引值。,北京大学信息学院 Page 69,败方树比赛过程,将新进入树的结点与其父结点进行比赛 把败者存放在父结点中 而把胜者再与上一级的父结点进行比赛 这样的比赛不断进行，直到结点B1处比完 把败者的索引放在结点B1 把胜者的索引放到结点B0,北京大学信息学院 Page 70,败方树示例（1）,北京大学信息学院 Page 71,败方树示例（2）： L4节点15进入

31、 后做重构,北京大学信息学院 Page 72,败方树 ADT,template class LoserTree private: int MaxSize; /最大选手数 int n; /当前选手数 int LowExt; /最底层外部节点数 int offset; /最底层外部节点之上的节点总数 int * B; /赢者树数组，实际存放的是下标 T * L; /元素数组 void Play(int p, int lc, int rc, int(* winner)(T A, int b, int c);,北京大学信息学院 Page 73,败方树ADT（续）,public: LoserTree(i

32、nt Treesize = MAX); LoserTree()delete B; void Initialize(T A, int size,int (*winner)(T A, int b, int c), int(*loser)(T A, int b, int c); /初始化败方树 int Winner(); /返回最终胜者索引 /位置i的选手改变后重构败方树 void RePlay(int i, int(*winner)(T A, int b, int c), int (*loser)(T A, int b, int c);,北京大学信息学院 Page 74,败方树的实现,/构造函数

33、template LoserTree:LoserTree(int TreeSize) MaxSize = TreeSize; B = new intMaxSize; n = 0; /析构函数 template LoserTree:LoserTree() delete B; ,北京大学信息学院 Page 75,败方树的实现（续1）,/成员函数Winner，返回最终胜者的索引 /在败方树中这个索引存放在B0中 template int LoserTree:Winner() return (n)?B0:0; ,北京大学信息学院 Page 76,败方树的实现（续2）,/成员函数Initilalize负

34、责初始化败方树 template void LoserTree:Initialize(T A, int size, int(*winner)(T A, int b, int c), int(*loser)(T A, int b, int c) /能否处理size个选手的数组a if(size MaxSize | size 2) cout“Bad Input!“endlendl; return; ,北京大学信息学院 Page 77,败方树的实现（续3）,/初始化成员变量 n = size; L = A; /计算s=2log(n-1) int i,s; for(s = 1; 2*s = n-1; s+=s); LowExt = 2*(n-s); offset = 2*s-1;,北京大学信息学院 Page 78,败方树的实现（续4）,/最底层外部结点的比赛 for(i = 2; i = LowExt; i+=2) Play(offset+i)/