第十章文件、外部排序与外部搜索.ppt
《第十章文件、外部排序与外部搜索.ppt》由会员分享,可在线阅读,更多相关《第十章文件、外部排序与外部搜索.ppt(135页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第十章 文件、外部排序与外部搜索,主存储器和外存储器 文件组织 多级索引结构 外排序,1,主存储器与外存储器,主存储器又叫内存储器,简称为内存;外存储器简称为外存。外存储器与内存储器相比,优点是:价格较低永久的存储能力缺点:访问外存储器上的数据比访问内存要慢56个数量级要求我们在开发系统时必须考虑如何使外存访问次数达到最少。,2,磁带(tape),磁带是一种顺序存取设备。磁带主要用于备份、存储不经常使用的数据,以及作为将数据从一个系统转移到另一个系统的脱机介质。,3,磁带卷在一个卷盘上,运行时磁带经过读写磁头,把磁带上的信息读入计算机,或者把计算机中的信息写到磁带上去。数据记录在磁带带面上。在
2、带面上并列存放有 9 个磁道的信息,即每一横排有 9 位二进制信息:8 位数据加 1 位奇偶校验位。磁带的存储密度用 BPI(Bit Per Inch)为单位,典型的存储密度有 3 种:6250BPI(=246排/mm)、1600BPI(=64排/mm)、800BPI(32排/mm)。正常走带速度为35m/Sec,因设备而异。,4,数据的传送速度 = 存储密度走带速度。在应用中使用文件进行数据处理的基本单位叫做逻辑记录,简称为记录;在磁带上物理地存储的记录叫做物理记录。在使用磁带或磁盘存放逻辑记录时,常常把若干个逻辑记录打包进行存放,把这个过程叫做“块化”(blocking)。经过块化处理的物
3、理记录叫做块化记录。磁带设备是一种启停设备。磁带每次启停都有一个加速与减速的过程,在这段时间内走带不,5,稳定,只能走空带,这段空带叫做记录间间隙IRG(Inter Record Gap)或者块间间隙IBG(Inter Block Gap),其长度因设备而异。,6,如果每个逻辑记录是 80个字符,IRG为 0.75英寸,则对存储密度为 1600BPI 的磁带,一个逻辑记录仅占 80/1600 = 0.05英寸。每传输一个逻辑记录磁带走过 0.05英寸,接着磁带要走过一个IRG占0.75英寸。结果大部分时间都花费在走空带上,存储利用率只有1/16。如果将若干逻辑记录存放于一个块,将IRG变成IB
4、G,可以提高存储利用率。例如,将50个有80个字符的逻辑记录放在一个块内,此块的长度将达到5080/1600 = 2.5英寸,存储利用率达到0.77。因此在磁带上采用按块读写。,7,在磁带设备上读写一块信息所用时间tIO = ta + tb其中,ta 是延迟时间,即读写磁头到达待读写块开始位置所需花费的时间,它与当前读写磁头所在位置有关。tb是对一个块进行读写所用时间,它等于数据传输时间加上IBG时间。磁带设备只能用于处理变化少,只进行顺序存取的大量数据。,8,磁盘(disc),磁盘存储器通常称为直接存取设备,或随机存取设备,它访问外存上文件的任一记录的时间几乎相同。磁盘存储器可以顺序存取,也
5、可以随机存取。目前使用较多的是活动臂硬盘组:若干盘片构成磁盘组,它们安装在主轴上,在驱动装置的控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外,其他每个盘片上下两面都可存放数据。将这些可存放数据的盘面称为记录盘面。,9,10,每个记录盘面上有很多磁道,数据就存放在这些磁道上。它们在记录盘面上形成一个个同心圆。 每个记录盘面都有一个读写磁头。所有记录盘面的读写磁头都安装在同一个动臂上,随动臂向内或向外做径向移动,从一个磁道移到另一个磁道。任一时刻,所有记录盘面的读写磁头停留在各个记录盘面的半径相同的磁道上。运行时,由于盘面做高速旋转,磁头所在的磁道上的数据相继在磁头下,从而可
6、以读写数据 。,11,各个记录盘面上半径相同的磁道合在一起称为柱面。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。 一个磁道可以划分为若干段,称为扇区,一个扇区就是一次读写的最小数据量。这样,对磁盘存储器来说,从大到小的存储单位是:盘片组、柱面、磁道和扇区。对磁盘存储器进行一次存取所需时间:当有多个盘片组时,要选定某个盘片组。这是由电子线路实现的,速度很快。,12,选定盘片组后再选定某个柱面,并移动动臂把磁头移到此柱面上。这是机械动作,速度较慢。这称为“寻查(seek)”。选定柱面后,要进一步确定磁道,即确定由哪个读写磁头读写,由电子线路实现。确定磁道后,还要确定所要读写数据在磁盘上的
7、位置(如在哪一个扇区)。这实际上就是在等待要读写的扇区转到读写磁头下面。这是机械动作。这段时间一般称为旋转延迟(rotational delay)时间。真正进行读写时间。,13,在磁盘组上一次读写的时间主要为: tiotseektlatencytrw其中,tseek是平均寻查时间,是把磁头定位到要求柱面所需时间,这个时间的长短取决于磁头移过的柱面数。tlatency是平均等待时间,是将磁头定位到指定块所需时间。trw是传送一个扇区数据所需的时间。在MS-DOS系统中,多个扇区集结成组,称为簇。簇是文件分配的最小单位,其大小由操作系统决定。在UNIX系统中不使用簇,文件分配的最小单位和读写的最小
8、单位是一个扇区,称为一个块(block)。,14,缓冲区(buffer),磁盘一次读写操作访问一个扇区,称为访问“一页”(page)或“一块”(block),又称为“一次访外”。为了实施磁盘读写操作,在内存中需要开辟一些区域,用以存放需要从磁盘读入的信息,或存放需要写出的信息。这些内存区域称为缓冲区。多数操作系统至少设置两个缓冲区,一个为输入缓冲区,一个为输出缓冲区。,15,例如,在从磁盘向内存读入一个扇区的数据时,数据被存放到输入缓冲区,如果下次需要读入同一个扇区的数据,就可以直接从缓冲区中读取数据,不需要重新读盘。缓冲区大小应与操作系统一次读写的块的大小相适应,这样可以通过操作系统一次读写
9、把信息全部存入缓冲区中,或把缓冲区中的信息全部写出到磁盘。如果缓冲区大小与磁盘上的块大小不适配,就会造成存储空间的浪费。缓冲区的构造可以看作一个先进先出的队列。,16,缓冲区的定义及其操作,#include #include const int DefaultSize = 2048;template struct buffer T *data;/缓冲区数组 int current, maxSize;/当前指针, 缓冲区容量buffer (int sz = DefaultSize) : maxSize(sz), current(0) data = new Tsz; assert (data !=
10、 NULL); buffer() delete data; ,17,void OutputInfo (ostream,18,template void buffer:InputInfo (istream,19,文件组织,什么是文件文件是存储在外存上的数据结构,一般是在逻辑上具有完整意义的一组相关信息项的有序序列。文件分操作系统文件和数据库文件 操作系统中的文件是流式文件:是没有结构的字符流 数据库文件是具有结构的数据集合数据结构中讨论的是数据库文件。操作系统对文件是按物理记录读写的,在数据库中文件按页块存储和读写。,20,文件的基本概念,文件的组成,文件由记录组成;记录由若干数据项组成。记录是
11、文件存取的基本单位,数据项是文件可使用的最小单位。从不同的观点,文件记录分为逻辑记录和物理记录。前者是面向用户的基本存取单位,后者是面向外设的基本存取单位。能够唯一标识一个记录的数据项或数据项集称为主关键码项,其值称为主关键码;不唯一标识一个记录的数据项或数据项集称为次关键码项,其值称为次关键码。,21,文件结构包括文件的逻辑结构、文件的存储结构和文件的操作。文件的逻辑结构是线性结构,各个记录以线性方式排列。文件的存储结构是指文件在外存上的组织方式,它与文件特性有关。 顺序组织直接存取组织(散列组织)索引组织文件的操作是定义在逻辑结构上的,但操作的具体实现要在存储结构上进行。,22,评价一个文
12、件组织的效率执行文件操作所花费的时间文件组织所需要的空间。,23,文件的操作,检索,维护,简单查询范围查询函数查询布尔查询,插入删除修改重构恢复,顺序文件 (Sequential File ),顺序文件中的记录按它们进入文件的先后顺序存放,其逻辑顺序与物理顺序一致。如果文件的记录按主关键码有序,则称其为顺序有序文件,否则称其为顺序无序文件。顺序文件通常存放在顺序存取设备(如磁带)上或直接存取设备(如磁盘)上。当存放在顺序存取设备上时只能按顺序搜索法存取;当存放在直接存取设备上时,可以使用顺序搜索法、折半搜索法等存取。,24,顺序文件的存储方式连续文件:文件的全部记录顺序地存放于外存的一个连续的
13、区域中。优点是存取速度快、存储利用率高、处理简单。缺点是区域大小需事先定义,不能扩充。串联文件:文件记录成块存放于外存中,在块中记录顺序连续存放,但块与块之间可以不连续,通过块链指针顺序链接。优点是文件可以扩充、存储利用率高。缺点是影响了存取和修改的效率。,25,直接存取文件 (Direct Access File),又叫散列文件。利用散列技术组织文件。处理类似散列法,但它是存储在外存上的。文件记录的逻辑顺序与物理顺序不一定相同。通过记录的关键码可直接确定该记录的地址。使用散列函数把关键码集合映射到地址集合时,往往会产生地址冲突,处理冲突有两种处理方式:按桶散列可扩充散列,26,(1) 按桶散
14、列,文件中的记录成组存放,若干个记录组成一个存储单位,称之为桶。假若一个桶能存放m个记录,则m个互为同义词的记录可以存放在同一地址的桶中。当第m+1个同义词出现时,才发生“溢出”。 (a) 溢出链当发生“溢出”时,将第m+1个同义词存放到“溢出桶”。并称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同。当在基桶中检索不成功,就循指针到溢出桶中检索。,27,桶大小为3的溢出桶链表示例,在这种散列文件中删除记录时,因为可能需要重新链接,所以只需做一个逻辑删除标记即可,待系统做周期性重构时再做物理删除。,28,(b) 分布式溢出空间溢出桶按照一定的间隔分布在基桶之间。如果有一个基桶溢出了,系统就
15、将记录存放在下一个溢出桶中。 如果溢出桶自己溢出了,则使用下一个相继的溢出桶,这需要第二次溢出处理。,29,如果系统对基桶按0, 1, 2, 3, 4, 5, 进行编号,在按间隔 G = 5 插入溢出桶后,可按下列公式按字节求出各个桶的实际存储地址:其中,B0是在文件中第0号桶的起始地址,B是每个桶的字节数。在括号中的除数5表示每隔5个基桶安排一个溢出桶。(c) 相继溢出法此方法不设置溢出桶。当记录应存放的桶溢出时,溢出记录存放到下一个相继的桶中。,30,如果该桶已满,就把它放到再下一个桶中,如此处理,直至把记录存放好。相继溢出法的优点是对溢出不需要漫长的寻找。紧邻的桶通常相距不多于一次磁盘旋
16、转。但当邻近的多个桶被挤满时,则为了查找空闲空间就需要检查许多桶。如果桶的容量很小更是如此。,31,H(key) = key % 11,(2) 可扩充散列,这是基于数字搜索树的一种散列方法,细节参见10.5节。,32,散列文件优缺点,散列文件具有随机存放、记录不需进行排序、插入删除方便、存取速度快、不需要索引区和节省存储空间等优点。散列文件不能顺序存取,只能按关键码随机存取。在经过多次插入、删除后,可能出现溢出桶满而基桶内多数记录已被删除的情况。此时需要重新组织文件。,33,索引文件 (Indexed File),索引文件由索引表和数据表(主文件)组成。索引表用于指示逻辑记录与物理记录间的对应
17、关系,它是按关键码有序的表。索引顺序文件:主文件也按关键码有序。此时可对主文件分组,一组记录对应一个索引项。称这种索引表为稀疏索引。索引非顺序文件:主文件中记录未按关键码有序。此时,每一个主文件记录必须对应一个索引项。称这种索引表为稠密索引。,34,静态索引:采用多级索引结构,每一级索引均为有序表。优点是结构简单,缺点是修改很不方便,每次修改都要重组索引。动态索引:采用可动态调整的平衡搜索树结构,如二叉搜索树、B树与B+树等。优点是插入、删除和搜索都很方便。在文件中搜索时,访问外存所花费时间比在内存中搜索所需的时间大得多,因此,外存上搜索一个记录的时间代价主要取决于访问外存的次数,即索引树的高
18、度。,35,36,0 1k 2k 3k 4k 5k 6k 7k,索引表,数据表,索引非顺序文件示例,索引顺序文件示例,当记录在外存中有序存放时,可以把所有n个记录分为b个子表 (块) 存放,一个索引项对应数据表中一组记录 (子表)。,37,对索引顺序文件进行搜索,一般分为两级:先在索引表ID中搜索给定值K, 确定满足 IDi-1.max_key K IDi.max_key的 i 值, 即待查记录可能在的子表的序号。然后再在第 i 个子表中按给定值搜索要求的记录。索引表是按max_key有序的, 且长度也不大,可以折半搜索,也可以顺序搜索。各子表内各个记录如果也按关键码有序, 可以采用折半搜索或
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 文件 外部 排序 搜索
限制150内