数据结构课件：第十章 文件、外部排序与外部搜索

《数据结构课件：第十章 文件、外部排序与外部搜索》由会员分享，可在线阅读，更多相关《数据结构课件：第十章 文件、外部排序与外部搜索（232页珍藏版）》请在装配图网上搜索。

1、1 1n主存储器和外存储器主存储器和外存储器 n文件组织文件组织 n外排序外排序 n多级索引结构多级索引结构 n可扩充散列可扩充散列nTrie树树 第十章第十章 文件、外部排序与文件、外部排序与外部搜索外部搜索2 2主存储器与外部存储器主存储器与外部存储器n外存储器与内存储器相比，优点是：外存储器与内存储器相比，优点是：u价格较低价格较低u永久的存储能力永久的存储能力n缺点：缺点：u访问外存储器上的数据比访问内存要慢访问外存储器上的数据比访问内存要慢56个数量级个数量级n要求我们在开发系统时必须考虑如何使外存要求我们在开发系统时必须考虑如何使外存访问次数达到最少。访问次数达到最少。3 3磁带（

2、磁带（tapetape）n磁带是一种顺序存取设备。磁带是一种顺序存取设备。n磁带主要用于备份、存储不经常使用的数据，磁带主要用于备份、存储不经常使用的数据，以及作为将数据从一个系统转移到另一个系统以及作为将数据从一个系统转移到另一个系统的脱机介质。的脱机介质。读出头读出头写入头写入头磁带磁带送带盘送带盘卷带盘卷带盘4 4n磁带卷在一个卷盘上，运行时磁带经过读写磁磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁带上的信息读入计算机，或者把计算头，把磁带上的信息读入计算机，或者把计算机中的信息写到磁带上去。机中的信息写到磁带上去。n数据记录在磁带带面上。在带面上并列存放有数据记录在磁带带面上。在带

3、面上并列存放有 9 个磁道的信息，即个磁道的信息，即每一横排有每一横排有 9 位二进制信位二进制信息息：8 位数据加位数据加 1 位奇偶校验位。位奇偶校验位。n磁带的存储密度用磁带的存储密度用 BPI（Bit Per Inch）为单位，为单位，典型的存储密度有典型的存储密度有 3 种：种：6250BPI（=246排排/mm）、）、1600BPI（=64排排/mm）、）、800BPI（32排排/mm）。正常走带速度为）。正常走带速度为35m/Sec，因设备而异。因设备而异。5 5n数据的传送速度数据的传送速度=存储密度存储密度 走带速度读写走带速度读写时间时间。n在应用中使用文件进行数据处理的基

4、本单位叫在应用中使用文件进行数据处理的基本单位叫做做逻辑记录逻辑记录，简称为记录；在磁带上物理地存，简称为记录；在磁带上物理地存储的记录叫做储的记录叫做物理记录物理记录。n在使用磁带或磁盘存放逻辑记录时，常常把若在使用磁带或磁盘存放逻辑记录时，常常把若干个逻辑记录打包进行存放，把这个过程叫做干个逻辑记录打包进行存放，把这个过程叫做“块化块化”（blocking）。经过块化处理的物理）。经过块化处理的物理记录叫做记录叫做块化记录块化记录。n磁带设备是一种启停设备。磁带每次启停都有磁带设备是一种启停设备。磁带每次启停都有一个加速与减速的过程，在这段时间内走带不一个加速与减速的过程，在这段时间内走带

5、不6 6稳定，只能走空带，这段空带叫做记录间间隙稳定，只能走空带，这段空带叫做记录间间隙IRG（Inter Record Gap）或者块间间隙）或者块间间隙IBG（Inter Block Gap），其长度因设备而异。），其长度因设备而异。磁带速度磁带速度75-200英寸英寸/秒秒传输速度传输速度7000-1250000字字/秒秒1.5-16ms1.5-16ms定速定速加速加速IBG0.30.75英寸英寸减速减速物理记录物理记录启动位置启动位置IBG0.30.75英寸英寸停止位置停止位置传输开始传输开始传输完成传输完成经过时间经过时间7 7n如果每个逻辑记录是如果每个逻辑记录是 80个字符个字符

6、，IRG为为 0.75英英寸寸，则对存储密度为，则对存储密度为 1600BPI 的磁带，一个的磁带，一个逻辑记录仅占逻辑记录仅占 80/1600=1/20英寸英寸。每传输一。每传输一个逻辑记录磁带走过个逻辑记录磁带走过 0.05英寸英寸，接着磁带要走，接着磁带要走过一个过一个IRG占占0.75英寸英寸。结果大部分时间都花。结果大部分时间都花费在走空带上，费在走空带上，存储利用率只有存储利用率只有1/16。n如果将若干逻辑记录存放于一个块，将如果将若干逻辑记录存放于一个块，将IRG变变成成IBG，可以提高存储利用率。例如，将，可以提高存储利用率。例如，将50个个有有80个字符的逻辑记录放在一个块

7、内，此块的个字符的逻辑记录放在一个块内，此块的长度将达到长度将达到50 80/1600=2.5英寸，存储利用率英寸，存储利用率达到达到0.77。因此在磁带上采用。因此在磁带上采用按块读写按块读写。8 8n在磁带设备上读写一块信息所用时间在磁带设备上读写一块信息所用时间tIO=ta+tbn其中，其中，ta 是是延迟时间延迟时间，即读写磁头到达待读写，即读写磁头到达待读写块开始位置所需花费的时间，它与当前读写磁块开始位置所需花费的时间，它与当前读写磁头所在位置有关。头所在位置有关。tb是对一个块进行是对一个块进行读写所用读写所用时间时间，它等于数据传输时间加上，它等于数据传输时间加上IBG时间。时

8、间。n磁带设备只能用于处理变化少，只进行磁带设备只能用于处理变化少，只进行顺序存顺序存取取的大量数据。的大量数据。9 9磁盘（磁盘（discdisc）n磁盘存储器通常称为磁盘存储器通常称为直接存取设备直接存取设备，或，或随机存随机存取设备取设备，它访问外存上文件的任一记录的时间，它访问外存上文件的任一记录的时间几乎相同。几乎相同。n磁盘存储器可以磁盘存储器可以顺序存取顺序存取，也可以，也可以随机存取随机存取。n目前使用较多的是活动臂硬盘组：若干盘片构目前使用较多的是活动臂硬盘组：若干盘片构成磁盘组，它们安装在主轴上，在驱动装置的成磁盘组，它们安装在主轴上，在驱动装置的控制下高速旋转。除了最上面

9、一个盘片和最下控制下高速旋转。除了最上面一个盘片和最下面一个盘片的外侧盘面不用以外，其他每个盘面一个盘片的外侧盘面不用以外，其他每个盘片上下两面都可存放数据。将这些可存放数据片上下两面都可存放数据。将这些可存放数据的盘面称为记录盘面。的盘面称为记录盘面。1010主轴主轴盘片盘片活动臂活动臂（回转臂）（回转臂）读写磁头读写磁头磁道磁道柱面柱面11 11n每个记录盘面上有很多磁道，数据就存放在这每个记录盘面上有很多磁道，数据就存放在这些磁道上。它们在记录盘面上形成一个个同心些磁道上。它们在记录盘面上形成一个个同心圆。圆。n每个记录盘面都有一个读写磁头。所有记录盘每个记录盘面都有一个读写磁头。所有记

10、录盘面的读写磁头都安装在同一个动臂上，随动臂面的读写磁头都安装在同一个动臂上，随动臂向内或向外做径向移动，从一个磁道移到另一向内或向外做径向移动，从一个磁道移到另一个磁道。个磁道。n任一时刻，所有记录盘面的读写磁头停留在各任一时刻，所有记录盘面的读写磁头停留在各个记录盘面的半径相同的磁道上。运行时，由个记录盘面的半径相同的磁道上。运行时，由于盘面做高速旋转，磁头所在的磁道上的数据于盘面做高速旋转，磁头所在的磁道上的数据相继在磁头下，从而可以读写数据相继在磁头下，从而可以读写数据 1212n各个记录盘面上半径相同的磁道合在一起称各个记录盘面上半径相同的磁道合在一起称为为柱面柱面。动臂的移动实际上

11、是将磁头从一个。动臂的移动实际上是将磁头从一个柱面移动到另一个柱面上。柱面移动到另一个柱面上。n一个一个磁道磁道可以划分为若干段，称为可以划分为若干段，称为扇区扇区，一，一个扇区就是一次读写的最小数据量。这样，个扇区就是一次读写的最小数据量。这样，对磁盘存储器来说，从大到小的存储单位是：对磁盘存储器来说，从大到小的存储单位是：盘片组、柱面、磁道和扇区。盘片组、柱面、磁道和扇区。n对磁盘存储器进行一次存取所需时间：对磁盘存储器进行一次存取所需时间：1.当有多个盘片组时，要选定某个盘片组。当有多个盘片组时，要选定某个盘片组。这是由电子线路实现的，速度很快。这是由电子线路实现的，速度很快。13132

12、.选定盘片组后再选定某个柱面，并移动动选定盘片组后再选定某个柱面，并移动动臂把磁头移到此柱面上。这是机械动作，臂把磁头移到此柱面上。这是机械动作，速度较慢。这称为速度较慢。这称为“寻查（寻查（seek）”。3.选定柱面后，要进一步确定磁道，即确定选定柱面后，要进一步确定磁道，即确定由哪个读写磁头读写，由电子线路实现。由哪个读写磁头读写，由电子线路实现。4.确定磁道后，还要确定所要读写数据在确定磁道后，还要确定所要读写数据在磁盘上的位置（如在哪一个扇区）。这实磁盘上的位置（如在哪一个扇区）。这实际上就是在等待要读写的扇区转到读写磁际上就是在等待要读写的扇区转到读写磁头下面。这是机械动作。这段时间

13、一般称头下面。这是机械动作。这段时间一般称为旋转延迟（为旋转延迟（rotational delay）时。）时。5.真正进行读写时间。真正进行读写时间。1414n在磁盘组上一次读写的时间主要为：在磁盘组上一次读写的时间主要为：tiotseektlatencytrwn其中，其中，tseek是是平均寻查时间平均寻查时间，是把磁头定位到，是把磁头定位到要求柱面所需时间，这个时间的长短取决于磁要求柱面所需时间，这个时间的长短取决于磁头移过的柱面数。头移过的柱面数。tlatency是是平均等待时间平均等待时间，是，是将磁头定位到指定块所需时间。将磁头定位到指定块所需时间。trw是传送一个是传送一个扇区数据

14、所需的时间。扇区数据所需的时间。n在在MS-DOS系统中，多个扇区集结成组，称为系统中，多个扇区集结成组，称为簇。簇是文件分配的最小单位，其大小由操作簇。簇是文件分配的最小单位，其大小由操作系统决定。在系统决定。在UNIX系统中不使用簇，文件分系统中不使用簇，文件分配的最小单位和读写的最小单位是一个扇区，配的最小单位和读写的最小单位是一个扇区，1515称为一个块（称为一个块（block）。）。n磁盘一次读写操作访问一个扇区，称为访问磁盘一次读写操作访问一个扇区，称为访问“一页一页”（page）或）或“一块一块”（block），又），又称为称为“一次访外一次访外”。n为了实施磁盘读写操作，在内存

15、中需要开辟一为了实施磁盘读写操作，在内存中需要开辟一些区域，用以存放需要从磁盘读入的信息，或些区域，用以存放需要从磁盘读入的信息，或存放需要写出的信息。这些内存区域称为缓冲存放需要写出的信息。这些内存区域称为缓冲区）。区）。多数操作系统至少设置两个缓冲区，一多数操作系统至少设置两个缓冲区，一个为个为输入缓冲区输入缓冲区；一个为；一个为输出缓冲区输出缓冲区。缓冲区（缓冲区（bufferbuffer）1616n例如在从磁盘向内存读入一个扇区的数据时，例如在从磁盘向内存读入一个扇区的数据时，数据被存放到输入缓冲区，如果下次需要读入数据被存放到输入缓冲区，如果下次需要读入同一个扇区的数据，就可以直接从

16、缓冲区中读同一个扇区的数据，就可以直接从缓冲区中读取数据，不需要重新读盘。取数据，不需要重新读盘。n缓冲区大小应与操作系统一次读写的块的大小缓冲区大小应与操作系统一次读写的块的大小相适应，这样可以通过操作系统一次读写把信相适应，这样可以通过操作系统一次读写把信息全部存入缓冲区中，或把缓冲区中的信息全息全部存入缓冲区中，或把缓冲区中的信息全部写出到磁盘。部写出到磁盘。n如果缓冲区大小与磁盘上的块大小不适配，就如果缓冲区大小与磁盘上的块大小不适配，就会造成内存空间的浪费。会造成内存空间的浪费。n缓冲区的构造可以看作一个先进先出的队列。缓冲区的构造可以看作一个先进先出的队列。1717缓冲区的定义及其

17、操作缓冲区的定义及其操作#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!=NULL);buffer()delete data;1818 void OutputInfo(ostream&out,T x);/缓冲区输出 void InputInfo(istream&in,T&x)

18、;/缓冲区输入;template void buffer:OutputInfo(ostream&out,T x)if(current=maxSize)for(int i=0;i maxSize;i+)out datai;current=0;datacurrent=x;current+;1919template void buffer:InputInfo(istream&in,T&x)if(current maxSize)x=datacurrent;current+;else for(int i=0;i datai;current=0;2020文件组织文件组织n什么是文件什么是文件u文件是存储在

19、外存上的数据结构。文件是存储在外存上的数据结构。u文件分操作系统文件和数据库文件文件分操作系统文件和数据库文件 操作系统中的文件是流式文件：是没有操作系统中的文件是流式文件：是没有结构的字符流结构的字符流 数据库文件是具有结构的数据集合数据库文件是具有结构的数据集合u数据结构中讨论的是数据库文件。数据结构中讨论的是数据库文件。n操作系统对文件是按操作系统对文件是按物理记录物理记录读写的，在数据读写的，在数据库中文件按库中文件按页块页块存储和读写。存储和读写。文件的基本概念文件的基本概念2121文件的组成文件的组成n文件文件由由记录记录组成；组成；记录记录由若干由若干数据项数据项组成。组成。n记

20、录是文件存取的基本单位，数据项是文件可记录是文件存取的基本单位，数据项是文件可使用的最小单位。使用的最小单位。n从不同的观点，文件记录分为逻辑记录和物理从不同的观点，文件记录分为逻辑记录和物理记录。前者是面向用户的基本存取单位，后者记录。前者是面向用户的基本存取单位，后者是面向外设的基本存取单位。是面向外设的基本存取单位。n能够唯一标识一个记录的数据项或数据项集称能够唯一标识一个记录的数据项或数据项集称为主关键码项，其值称为主关键码；为主关键码项，其值称为主关键码；n不唯一标识一个记录的数据项或数据项集称为不唯一标识一个记录的数据项或数据项集称为次关键码项，其值称为次关键码。次关键码项，其值称

21、为次关键码。2222n文件结构包括文件的逻辑结构、文件的存储结文件结构包括文件的逻辑结构、文件的存储结构和文件的操作。构和文件的操作。n文件的逻辑结构是线性结构文件的逻辑结构是线性结构，各个记录以线性，各个记录以线性方式排列。方式排列。n文件的存储结构是指文件在外存上的组织方式，文件的存储结构是指文件在外存上的组织方式，它与文件特性有关。它与文件特性有关。u 顺序组织顺序组织u 索引组织索引组织u 直接存取组织（散列组织）直接存取组织（散列组织）n文件的操作是定义在逻辑结构上的，但操作的文件的操作是定义在逻辑结构上的，但操作的具体实现要在存储结构上进行。具体实现要在存储结构上进行。2323n评

22、价一个文件组织的效率评价一个文件组织的效率u执行文件操作所花费的时间执行文件操作所花费的时间u文件组织所需要的空间。文件组织所需要的空间。文件的操作文件的操作检索检索维护维护简单查询简单查询范围查询范围查询函数查询函数查询布尔查询布尔查询插入插入删除删除修改修改重构重构恢复恢复2424顺序文件顺序文件 (Sequential File)(Sequential File)n顺序文件中的记录按它们进入文件的先后顺序顺序文件中的记录按它们进入文件的先后顺序存放，其存放，其逻辑顺序与物理顺序一致逻辑顺序与物理顺序一致。n如果文件的记录按主关键码有序，则称其为如果文件的记录按主关键码有序，则称其为顺顺序

23、有序文件序有序文件，否则称其为，否则称其为顺序无序文件顺序无序文件。n顺序文件通常存放在顺序存取设备（如磁带）顺序文件通常存放在顺序存取设备（如磁带）上或直接存取设备（如磁盘）上。上或直接存取设备（如磁盘）上。n当存放在顺序存取设备上时只能按顺序搜索法当存放在顺序存取设备上时只能按顺序搜索法存取；当存放在直接存取设备上时，可以使用存取；当存放在直接存取设备上时，可以使用顺序搜索法、折半搜索法等存取。顺序搜索法、折半搜索法等存取。2525n顺序文件的存储方式顺序文件的存储方式1.连续文件连续文件：文件的全部记录顺序地存放外：文件的全部记录顺序地存放外存的一个连续的区域中。优点是存取速度存的一个连

24、续的区域中。优点是存取速度快、存储利用率高、处理简单。缺点是区快、存储利用率高、处理简单。缺点是区域大小需事先定义，不能扩充。域大小需事先定义，不能扩充。2.串联文件串联文件：文件记录成块存放于外存中，：文件记录成块存放于外存中，在块中记录顺序连续存放，但块与块之间在块中记录顺序连续存放，但块与块之间可以不连续，通过块链指针顺序链接。优可以不连续，通过块链指针顺序链接。优点是文件可以扩充、存储利用率高。缺点点是文件可以扩充、存储利用率高。缺点是影响了存取是影响了存取和修改的效率。和修改的效率。2626直接存取文件直接存取文件 (Direct Access File)(Direct Access

25、 File)n文件记录的文件记录的逻辑顺序与物理顺序不一定相同逻辑顺序与物理顺序不一定相同。通过记录的关键码可直接确定该记录的地址。通过记录的关键码可直接确定该记录的地址。n利用散列技术组织文件。处理类似散列法，但利用散列技术组织文件。处理类似散列法，但它是存储在外存上的。它是存储在外存上的。n使用散列函数把关键码集合映射到地址集合时，使用散列函数把关键码集合映射到地址集合时，往往会产生地址冲突，处理冲突有两种处理方往往会产生地址冲突，处理冲突有两种处理方式：式：u按桶散列按桶散列u可扩充散列可扩充散列 2727(1)(1)按桶散列按桶散列n文件中的记录成组存放，若干个记录组成一个文件中的记录

26、成组存放，若干个记录组成一个存储单位，称之为存储单位，称之为桶桶。假若一个桶能存放。假若一个桶能存放m个个记录，则记录，则m个互为同义词的记录可以存放在同个互为同义词的记录可以存放在同一地址的桶中。当第一地址的桶中。当第m+1个同义词出现时，才个同义词出现时，才发生发生“溢出溢出”。(a)溢出链溢出链u当发生当发生“溢出溢出”时，将第时，将第m+1个同义词存放个同义词存放到到“溢出桶溢出桶”。并称存放前。并称存放前m个同义词的桶个同义词的桶为为“基桶基桶”。溢出桶和基桶大小相同。当在。溢出桶和基桶大小相同。当在基桶中检索不成功，就循指针到溢出桶中检基桶中检索不成功，就循指针到溢出桶中检索。索。

27、2828n在这种散列文件中删除记录时，因为可能需要在这种散列文件中删除记录时，因为可能需要重新链接，所以只需重新链接，所以只需做一个逻辑删除标记做一个逻辑删除标记即可，即可，待系统做周期性重构时再做物理删除。待系统做周期性重构时再做物理删除。桶大小为3的溢出桶链表示例 070 512 204 246 O1597 177 262 157 116 613 285 635 208 O2923 076 0123456O1O2O3O4O5O6O7015 337 988 O3817 117 390 O4 575 540 435 362 基桶编号基桶编号 基桶区基桶区 溢出桶编号溢出桶编号 溢出桶区溢出桶区

28、2929(b)分布式溢出空间分布式溢出空间u溢出桶按照一定的间溢出桶按照一定的间隔分布在基桶之间。隔分布在基桶之间。如果有一个基桶溢出如果有一个基桶溢出了，系统就将记录存了，系统就将记录存放在下一个溢出桶中。放在下一个溢出桶中。u如果溢出桶自己溢出如果溢出桶自己溢出了，则使用下一个相了，则使用下一个相继的溢出桶，这需要继的溢出桶，这需要第二次溢出处理。第二次溢出处理。01234567891011121314分布式溢出桶分布式溢出桶基桶基桶基桶基桶基桶基桶溢出桶溢出桶溢出桶溢出桶3030n如果系统对基桶按如果系统对基桶按0,1,2,3,4,5,进行编号，进行编号，在按间隔在按间隔 G=5 插入溢

29、出桶后，可按下列公式插入溢出桶后，可按下列公式按字节求出各个桶的实际存储地址：按字节求出各个桶的实际存储地址：n其中，其中，B0是在文件中第是在文件中第0号桶的起始地址，号桶的起始地址，B是每个桶的字节数。在括号中的除数是每个桶的字节数。在括号中的除数5表示每表示每隔隔5个基桶安排一个溢出桶。个基桶安排一个溢出桶。(c)相继相继溢出法溢出法u此方法不设置溢出桶。当记录应存放的桶溢此方法不设置溢出桶。当记录应存放的桶溢出时，溢出记录存放到下一个相继的桶中。出时，溢出记录存放到下一个相继的桶中。.5iiBB0桶桶的的地地址址3131u如果该桶已满，就把它放如果该桶已满，就把它放到再下一个桶中，如此

30、处到再下一个桶中，如此处理，直至把记录存放好。理，直至把记录存放好。u相继溢出法的优点是对溢相继溢出法的优点是对溢出不需要漫长的寻找。紧出不需要漫长的寻找。紧邻的桶通常相距不多于一邻的桶通常相距不多于一次磁盘旋转。但当邻近的次磁盘旋转。但当邻近的多个桶被挤满时，则为了多个桶被挤满时，则为了查找空闲空间就需要检查查找空闲空间就需要检查许多桶。如果桶的容量很许多桶。如果桶的容量很小更是如此。小更是如此。362177597 157 817 575070 246 015 542 389116 204 512 435337 117635 613262 988285 923 076 208相继溢出法相继溢

31、出法 0124356798103232(2)(2)可扩充散列可扩充散列n这是基于数字搜索树的一种散列方法，细节稍这是基于数字搜索树的一种散列方法，细节稍后介绍。后介绍。n散列文件具有随机存放、记录不需进行排序、散列文件具有随机存放、记录不需进行排序、插入删除方便、存取速度快、不需要索引区和插入删除方便、存取速度快、不需要索引区和节省存储空间等优点。节省存储空间等优点。n散列文件不能顺序存取，只能按关键码随机存散列文件不能顺序存取，只能按关键码随机存取。在经过多次插入、删除后，可能出现溢出取。在经过多次插入、删除后，可能出现溢出桶满而基桶内多数记录已被删除的情况。此时桶满而基桶内多数记录已被删除

32、的情况。此时需要重新组织文件。需要重新组织文件。3333索引文件索引文件 (Indexed File)(Indexed File)n索引文件由索引文件由索引表索引表和和主文件主文件组成。组成。n索引表用于指示逻辑记录与物理记录间的对索引表用于指示逻辑记录与物理记录间的对应关系，它是应关系，它是按关键码有序的表按关键码有序的表。u索引顺序文件索引顺序文件：主文件也按关键码有序。：主文件也按关键码有序。此时可对主文件分组，一组记录对应一个此时可对主文件分组，一组记录对应一个索引项。称这种索引表为稀疏索引。索引项。称这种索引表为稀疏索引。u索引非顺序文件索引非顺序文件：主文件中记录未按关键：主文件中

33、记录未按关键码有序。此时，每一个主文件记录必须对码有序。此时，每一个主文件记录必须对应索引项。称这种索引表为稠密索引。应索引项。称这种索引表为稠密索引。3434n静态索引静态索引：采用：采用多级索引结构多级索引结构，每一级索引均每一级索引均为有序表为有序表。优点是结构简单，缺点是修改很不。优点是结构简单，缺点是修改很不方便，每次修改都要重组索引。方便，每次修改都要重组索引。n动态索引动态索引：采用：采用可动态调整的平衡搜索树结构可动态调整的平衡搜索树结构，如二叉搜索树、如二叉搜索树、B_树与树与B+树等树等。优点是插入、。优点是插入、删除和搜索都很方便。删除和搜索都很方便。n在文件中搜索时，访

34、问外存所花费时间比在内在文件中搜索时，访问外存所花费时间比在内存中搜索所需的时间大得多，因此，外存上搜存中搜索所需的时间大得多，因此，外存上搜索一个记录的时间代价主要取决于访问外存的索一个记录的时间代价主要取决于访问外存的次数，即索引树的高度。次数，即索引树的高度。3535 0 1k 2k 3k 4k 5k 6k 7k索引表数据表职工号职工号 姓名姓名 性别性别职务职务婚否婚否 83张珊张珊女女教师教师已婚已婚 08李斯李斯男男教师教师已婚已婚 03王璐王璐男男教务员教务员 已婚已婚 95刘琪刘琪女女实验员实验员 未婚未婚 24岳跋岳跋男男教师教师已婚已婚 47周斌周斌男男教师教师已婚已婚 1

35、7胡江胡江男男实验员实验员 未婚未婚 51林青林青女女教师教师未婚未婚 key addr032k081k176k244k475k517k830953k索引非顺序文件示例索引非顺序文件示例363622 12 13 30 29 3336 42 44 48 39 4060 74 56 79 80 6692 82 88 98 94 子表子表1子表子表2子表子表3子表子表4数据区数据区33488098索引表索引表1234max_ min_ key addr索引顺序文件示例索引顺序文件示例n当记录在外存中有序存放时，可以把所有当记录在外存中有序存放时，可以把所有n个个记录分为记录分为b个子表个子表(块块)

36、存放，一个索引项对应存放，一个索引项对应数据表中一组记录数据表中一组记录(子表子表)。3737n对索引顺序文件进行搜索，一般分为两级对索引顺序文件进行搜索，一般分为两级:u先在索引表先在索引表ID中搜索给定值中搜索给定值K,确定满足确定满足 IDi-1.max_key 1)个个归并段得到归并段得到 l/2 个归并段。总归并趟数等于归个归并段。总归并趟数等于归并树的高度减一：并树的高度减一：log2m。n估计估计 2 路归并排序时间路归并排序时间 tES 的上界为：的上界为：tES=m*tIS+d*tIO+S*n*tmg5656 n对对 4500 个记录排序的例子个记录排序的例子,各种操作的计算

37、时各种操作的计算时间如下：间如下：读读18个输入块个输入块,内部排序内部排序6段段,写写18个输出块个输出块6 tIS36 tIO 成对归并初始归并段成对归并初始归并段 R1R6 36 tIO4500 tmg 归并两个具有归并两个具有1500个记录的归并段个记录的归并段R12和和R34 24 tIO3000 tmg 最后将最后将 R1234 和和 R56 归并成一个归并段归并成一个归并段 36 tIO4500 tmgn合计合计 tES6 tIS132 tIO12000 tmg5757 n由于由于 tIO=tseek+tlatency+trw,其中其中,tseek和和tlatency是是机械动作

38、，而机械动作，而trw、tIS、tmg是电子线路的动作是电子线路的动作,所以所以tIO远远大于远远大于tIS和和tmg。想要提高外排序的。想要提高外排序的速度，应着眼于减少速度，应着眼于减少d。n若对相同数目的记录，在同样页块大小的情若对相同数目的记录，在同样页块大小的情况下做况下做 3 路归并或做路归并或做 6 路归并路归并(当然当然,内存缓冲内存缓冲区的数目也要变化区的数目也要变化)，则可做大致比较：，则可做大致比较：2 132 33 108 2 6 72 15858n增大归并路数增大归并路数,可减少归并趟数可减少归并趟数,从而减少总从而减少总读写磁盘次数读写磁盘次数d。n对对 m 个初始

39、归并段个初始归并段,做做 k 路平衡归并路平衡归并,归并树归并树可用正则可用正则 k 叉树叉树(即只有度为即只有度为 k 与度为与度为0的结的结点的点的 k 叉树叉树)来表示。来表示。n第一趟可将第一趟可将 m 个初始归并段个初始归并段归并为归并为 l=m/k 个归并段个归并段，以后每一趟归并将，以后每一趟归并将 l 个归并段个归并段归并归并成成 l=l/k 个归并段个归并段，直到最后形成一个大，直到最后形成一个大的归并段为止。归并趟数的归并段为止。归并趟数S logkm 树的高树的高度减一度减一。5959k k路平衡归并路平衡归并 (k-way Balanced merging)(k-way

40、 Balanced merging)n做做 k 路平衡归并时路平衡归并时,如果有如果有 m 个初始归并段个初始归并段,则则相应的归并树有相应的归并树有 logkm +1 层层,需要归并需要归并 logkm 趟趟。下图给出对有。下图给出对有 36 个初始归并段的个初始归并段的文件做文件做 6 路平衡归并时的归并树。路平衡归并时的归并树。6060n做内部做内部k路归并时路归并时,在在k个记录中选择最小者，个记录中选择最小者，需要顺序比较需要顺序比较 k-1 次。每趟归并次。每趟归并n个记录需要个记录需要做做(n-1)*(k-1)次比较次比较,S 趟归并总共需要的趟归并总共需要的比较次数为比较次数为

41、:S*(n-1)*(k-1)=logkm *(n-1)*(k-1)=log2m *(n-1)*(k-1)/log2k n在初始归并段个数在初始归并段个数 m 与记录个数与记录个数 n 一定时一定时,log2m*(n-1)=const,而而(k-1)/log2k 在在 k 增大时趋于无穷大。因此增大时趋于无穷大。因此,增大归并路数增大归并路数 k,会会使得内部归并的时间增大。使得内部归并的时间增大。6161n使用使用“败者树败者树”从从k个归并段中选最小者个归并段中选最小者,当当k较大时较大时(k 6)，选出排序码最小的记录只需比，选出排序码最小的记录只需比较较 log2k 次。次。S*(n-1

42、)*log2k =logkm *(n-1)*log2k =log2m *(n-1)*log2k /log2k =log2m *(n-1)n排序码比较次数与排序码比较次数与 k 无关无关,总的内部归并时间总的内部归并时间不会随不会随 k 的增大而增大。的增大而增大。n下面讨论利用败者树在下面讨论利用败者树在 k 个输入归并段中选择个输入归并段中选择最小者，实现归并排序的方法。最小者，实现归并排序的方法。6262 n败者树是一棵正则的完全二叉树。其中败者树是一棵正则的完全二叉树。其中 每个叶结点存放各归并段在归并过程中当每个叶结点存放各归并段在归并过程中当前参加比较的记录；前参加比较的记录；每个非

43、叶结点记忆它两个子女结点中记录每个非叶结点记忆它两个子女结点中记录排序码大的结点排序码大的结点(即败者即败者)；n因此，根结点中记忆树中当前记录排序码最小因此，根结点中记忆树中当前记录排序码最小的结点的结点(最小记录最小记录)。n败者树与胜者树的区别在于一个选择了败者败者树与胜者树的区别在于一个选择了败者(排序码大者排序码大者),一个选择了胜者一个选择了胜者(排序码小者排序码小者)。n示例：设有示例：设有 5 个初始归并段个初始归并段,它们中各记录的它们中各记录的排序码分别是：排序码分别是：6363 Run0:17,21,Run1:05,44,Run2:10,12,Run3:29,32,Run

44、4:15,56,冠军冠军(最小记录最小记录),输出段输出段1当前记录当前记录2932 1556 1721 0544 1012 151005172930241k3k4k0k1k2ls1ls0ls2ls4ls3选中选中6464次最小记录次最小记录输出段输出段1 1最小记录，最小记录，段段1 1下一记录参选，下一记录参选，调整败者树调整败者树2932 1556 1721 0544 1012 151044172930142k3k4k0k1k2Run3Run4Run0Run1Run2ls1ls0ls2ls4ls3选中选中6565 n败者树的败者树的高度为高度为 log2k+1，在每次调整，在每次调整,找

45、下找下 一一个具有最小排序码记录时个具有最小排序码记录时,最多做最多做 log2k 次排序次排序码比较。码比较。n在内存中应为每一个归并段分配一个输入缓冲区在内存中应为每一个归并段分配一个输入缓冲区,其大小应能容纳一个页块的记录其大小应能容纳一个页块的记录,编号与归并段编号与归并段号一致。每个输入缓冲区应有一个指针号一致。每个输入缓冲区应有一个指针,指示当指示当前参加归并的记录。前参加归并的记录。n在内存中还应设立一个输出缓冲区在内存中还应设立一个输出缓冲区,其大小相当其大小相当于一个页块大小。它也有一个缓冲区指针于一个页块大小。它也有一个缓冲区指针,指示指示当前可存放结果记录的位置。每当一个

46、记录当前可存放结果记录的位置。每当一个记录 i 被被选出选出,就执行就执行OutputRecord(i)操作操作,将记录存放到将记录存放到输出缓冲区中。输出缓冲区中。6666n在实现利用败者树进行多路平衡归并算法时在实现利用败者树进行多路平衡归并算法时,把把败者树的叶结点和非叶结点分开定义。败者树的叶结点和非叶结点分开定义。n败者树叶结点败者树叶结点key有有k+1个个,key0到到keyk-1存存放各归并段当前参加归并的记录的排序码，放各归并段当前参加归并的记录的排序码，keyk是辅助工作单元是辅助工作单元,在初始建立败者树时使在初始建立败者树时使用用:存放一个最小的在各归并段中不可能出现的

47、存放一个最小的在各归并段中不可能出现的排序码排序码:-MaxNum。n败者树非叶结点败者树非叶结点loser有有k个个,其中其中loser1到到loserk-1存放各次比较的败者的归并段号存放各次比较的败者的归并段号,loser0中是最后胜者所在归并段号。另外还有中是最后胜者所在归并段号。另外还有一个存放各归并段参加归并记录的数组一个存放各归并段参加归并记录的数组rk。6767k k 路平衡归并排序算法路平衡归并排序算法const int MaxValue=;/当作无穷大值使用void kwaymerge(Element*r,int k)int i,q;r=new Elementk;/败者树中

48、的k个记录 int*key=new intk+1;/记录的排序码 int*loser=new intk;/存放败者树 for(i=0;i k;i+)/叶结点的值 InputRecord(ri);keyi=ri.key;for(i=0;i 0;i-)adjust(key,loser,k,i);/从keyk-1到key0调整形成败者树 while(keyloser0!=MaxValue)/选冠军 q=loser0;/取当前最小记录 OutputRecord(rq);/写到输出归并段 InputRecord(rq);/读入下一个记录 keyq=rq.key;adjust(key,loser,k,q)

49、;/从keyq起调整 Output end of run marker;/输出段结束标志 delete r;delete key;delete loser;6969自某叶结点自某叶结点keyqkeyq到败者树根结点到败者树根结点的调整算法的调整算法 void adjust(int key;int loser;int k;int q)/从败者树某叶结点keyq起到根进行比较,将最小/key 记录所在归并段的段号记入loser0。for(int t=(k+q)/2;t 0;t/=2)/t是q的双亲 if(keylosert keyq)/败者记入losert,胜者记入q int temp=q;q=l

50、osert;losert=temp;/q与losert交换 loser0=q;7070n每选出一个当前排序码最小的记录每选出一个当前排序码最小的记录,就需要在就需要在将它送入输出缓冲区之后将它送入输出缓冲区之后,从相应归并段的输从相应归并段的输入缓冲区中取出下一个参加归并的记录入缓冲区中取出下一个参加归并的记录,替换替换已经取走的最小记录已经取走的最小记录,再从叶结点到根结点再从叶结点到根结点,沿沿某一特定路径进行调整某一特定路径进行调整,将下一个排序码最小将下一个排序码最小记录的归并段号调整到记录的归并段号调整到loser0中。中。n段结束标志段结束标志MaxNum升入升入loser0,排序

51、完成。排序完成。n归并路数归并路数 k 不是越大越好。归并路数不是越大越好。归并路数 k 增大增大,相应需增加输入缓冲区个数。如果可供使用的相应需增加输入缓冲区个数。如果可供使用的内存空间不变内存空间不变,势必要减少每个输入缓冲区的势必要减少每个输入缓冲区的容量容量,使内外存交换数据的次数增大。使内外存交换数据的次数增大。7171利用败者树进行利用败者树进行 5 路平衡归并的过程路平衡归并的过程(1)初始状态初始状态 (2)加入加入15,调整调整292929151515517171750505055101010-55k3k4k5k0k1k2ls1ls0ls2ls4101010k25050505

52、ls3k11717175k0ls24ls415k4-k5292929k35ls15ls07272(3)加入加入29,调整调整 (4)加入加入10,调整调整2915317171740505055101010-55k3k4k5k0k1k2ls1ls0ls2ls3ls410k22050505ls3k11717174k0ls23ls415k4-k529k35ls15ls0737329153171717405210-15ls1ls0ls2ls3ls410205ls3170ls23ls415-294ls11ls0(5)加入加入05,调整调整 (6)加入加入17,调整调整输出输出057474(7)输出输出0

53、5后调整后调整 (8)输出输出10后调整后调整291531704411042121441703152942输入输入44输出输出12输出输出10输入输入12757529153170442 14k3k4k0k1k2ls1ls0ls2ls3ls4 k2244ls3k1173k0ls24ls456k429k31ls10ls0输入输入输出输出1输入输入(9)输出输出12后调整后调整 (10)输出输出15后调整后调整767629564213442 10k3k4k0k1k2ls1ls0ls2ls3ls4 k2244ls3k1 0k0ls24ls456k429k31ls13ls0输入输入21输出输出29输出输

54、出21输入输入(11)输出输出17后调整后调整 (12)输出输出21后调整后调整 7777(13)输出输出29后调整后调整 (14)输出输出32后调整后调整32564 0442 13k3k4k0k1k2ls1ls0ls2ls3ls4 k2244ls3k1 0k0ls23ls456k4 k34ls11ls0输入输入3输出输出44输出输出32输入输入7878(15)输出输出44后调整后调整 (16)输出输出56后调整后调整 563 0 2 14k3k4k0k1k2ls1ls0ls2ls3ls4 k22 ls3k1 0k0ls23ls4 k4 k31ls14ls0输出输出，结束结束输出输出56输入输

55、入输入输入7979初始归并段的生成初始归并段的生成 (Run Generation)(Run Generation)n为减少读写磁盘次数为减少读写磁盘次数,除增加归并路数除增加归并路数k外外,还还可减少初始归并段个数可减少初始归并段个数m。在总记录数。在总记录数n 一定一定时时,要减少要减少m,必须增大初始归并段长度。必须增大初始归并段长度。n如果规定每个初始归并段等长如果规定每个初始归并段等长,则此长度应根则此长度应根据生成它的内存工作区空间大小而定据生成它的内存工作区空间大小而定,因而因而m的的减少也就受到了限制。减少也就受到了限制。n为了突破这个限制为了突破这个限制,可采用败者树来生成初

56、始可采用败者树来生成初始归并段。在使用同样大内存工作区的情况下归并段。在使用同样大内存工作区的情况下,可以生成平均比原来等长情况下大一倍的初始可以生成平均比原来等长情况下大一倍的初始归并段归并段,从而减少初始归并段个数。从而减少初始归并段个数。8080n设输入文件设输入文件FI中各记录的排序码序列为中各记录的排序码序列为17,21,05,44,10,12,56,32,29。n选择和置换过程的步骤如下：选择和置换过程的步骤如下：从输入文件从输入文件FI中把中把 k 个记录个记录读入内存中读入内存中,并构并构造败者树。造败者树。(内存中存放记录的数组内存中存放记录的数组 r 可容纳可容纳的记录个数

57、为的记录个数为 k)利用败者树在利用败者树在r中选择一个排序码最小的记录中选择一个排序码最小的记录rq,其排序码存入其排序码存入LastKey作为门槛。以后再作为门槛。以后再选出的排序码比它大的记录归入本归并段选出的排序码比它大的记录归入本归并段,比比它小的归入下一归并段。它小的归入下一归并段。将此将此rq记录写到输出文件记录写到输出文件FO中。中。(q是叶结点是叶结点序号序号)8181 若若FI未读完未读完,则从则从FI读入下一个记录读入下一个记录,置换置换rq及败者树中的及败者树中的keyq。调整败者树调整败者树,从所有排序码比从所有排序码比LastKey大的记大的记录中选择一个排序码最小

58、的记录录中选择一个排序码最小的记录rq作为门槛作为门槛,其排序码存入其排序码存入LastKey。重复重复,直到在败者树中选不出排序码比直到在败者树中选不出排序码比LastKey大的记录为止。此时大的记录为止。此时,在输出文件在输出文件FO中得到一个初始归并段中得到一个初始归并段,在它最后加一个归并在它最后加一个归并段结束标志。段结束标志。重复重复,重新开始选择和置换重新开始选择和置换,产生新的初产生新的初始归并段始归并段,直到输入文件直到输入文件FI中所有记录选完为中所有记录选完为止。止。8282输输 入入 文文 件件 FI 内内存存数数组组 r 输输出出文文件件 FO1721 05 44 1

59、0 12 56 32 2944 10 12 56 32 29 17 21 0510 12 56 32 29 17 21 44 0512 56 32 29 10 21 44 05 1756 32 29 10 12 44 05 17 2132 29 10 12 56 05 17 21 4429 10 12 32 05 17 21 44 5629 10 12 32 05 17 21 44 56 29 10 12 32 29 12 32 10 29 32 10 12 32 10 12 29 10 12 29 32 10 12 29 32 8383n若按在若按在k路平衡归并排序中所讲的，每个初始路平衡归

60、并排序中所讲的，每个初始归并段的长度与内存工作区的长度一致归并段的长度与内存工作区的长度一致,则上则上述述9个记录可分成个记录可分成3个初始归并段：个初始归并段：Run0 05,17,21 Run1 10,12,44 Run2 29,32,56 n但采用上述选择与置换的方法但采用上述选择与置换的方法,可生成可生成2个长度个长度不等的初始归并段不等的初始归并段:Run0 05,17,21,44,56 Run1 10,12,29,32 8484 n在利用败者树生成在利用败者树生成不等长初始归并段不等长初始归并段的算法和的算法和调整败者树并选出最小记录的算法中，用两个调整败者树并选出最小记录的算法中

61、，用两个条件来决定谁为败者，谁为胜者。条件来决定谁为败者，谁为胜者。u首先比较两个记录所在归并段的段号首先比较两个记录所在归并段的段号,段号段号小者为胜者，段号大者为败者小者为胜者，段号大者为败者；u在归并段的段号相同时在归并段的段号相同时,排序码小者为胜者，排序码小者为胜者，排序码大者为败者排序码大者为败者。n比较后把败者记录在记录数组比较后把败者记录在记录数组r中的序号记入它中的序号记入它的双亲结点中的双亲结点中,把胜者记录在记录数组把胜者记录在记录数组r中的序中的序号记入工作单元号记入工作单元 s 中中,向更上一层进行比较向更上一层进行比较,最最后的胜者记入后的胜者记入 loser0中。

62、中。8585 17,21,05,44,10,12,56,32,29(1)初始化初始化 (2)输入输入17,调整调整17000000000ls1ls0ls2k2k0k100021ls0ls1k0ls2171k200k100排序码排序码段号段号8686 17,21,05,44,10,12,56,32,29(3)输入输入21,调整调整 (4)输入输入05,建败者树建败者树2121111710020ls1ls0ls2k2k0k1051210ls0ls1k0ls2171211k105选选058787 17,21,05,44,10,12,56,32,29(5)lastKey=05,置换置换 (6)last

63、Key=17,置换置换 k0,选择选择17 k2,段号加段号加1,选择选择2144211117144102ls1ls0ls2k2k0k1441021ls0ls1k0ls2102k2211k110选选21选选178888 17,21,05,44,10,12,56,32,29(7)lastKey=21,置换置换 (8)lastKey=44,置换置换k1,段号加段号加1,选择选择44 k0,选择选择5612122110244120ls1ls0ls2k2k0k1561210ls0ls1k0ls2102k2122k156选选56选选448989(9)lastKey=56,置换置换 (10)输出段结束标志

64、输出段结束标志,k0,段号加段号加1,本段结束本段结束 选择选择1032122110232202ls1ls0ls2k2k0k1322012ls0ls1k0ls2102k2122k1选选109090 17,21,05,44,10,12,56,32,29(11)lastKey=10,置换置换 (12)lastKey=12,k1 置置 k2,选择选择12 虚段虚段,选择选择2929122229232201ls1ls0ls2k2k0k1322012ls0ls1k0ls2292k2123k1选选29选选12虚段虚段9191 17,21,05,44,10,12,56,32,29(13)lastKey=29

65、,k2 置置 (14)lastKey=32,k0 置置 虚段虚段,选择选择32 虚段虚段,本段结束本段结束123229332210ls1ls0ls2k2k0k1323021ls0ls1k0ls2293k2123k1选选32虚段虚段虚段虚段虚段虚段虚段虚段虚段虚段9292(15)输出段结束标志输出段结束标志,结束结束123229332301ls1ls0ls2k2k0k1段号段号超出超出9393并行操作的缓冲区处理并行操作的缓冲区处理n如果采用如果采用 k 路归并路归并对对 k 个归并段个归并段进行归并，至进行归并，至少需要少需要 k 个输入缓冲区个输入缓冲区和和 1 个输出缓冲区个输出缓冲区。每

66、。每个缓冲区存放一个页块的信息。个缓冲区存放一个页块的信息。n但要同时进行输入、内部归并、输出操作，这但要同时进行输入、内部归并、输出操作，这些缓冲区就不够了。例如，些缓冲区就不够了。例如，u在输出缓冲区满需要向磁盘写出时，就必须在输出缓冲区满需要向磁盘写出时，就必须中断内部归并的执行。中断内部归并的执行。u在某一输入缓冲区空，需要从磁盘上再输入在某一输入缓冲区空，需要从磁盘上再输入一个新的页块的记录时，也不得不中断内部一个新的页块的记录时，也不得不中断内部归并。归并。9494n由于由于内外存信息传输时间内外存信息传输时间与与CPU运行时间运行时间相比相比要长得多，使得内部归并经常处于等待状态。要长得多，使得内部归并经常处于等待状态。n为了改变这种状态，希望使输入、内部归并、为了改变这种状态，希望使输入、内部归并、输出并行进行。对于输出并行进行。对于 k 路归并，必须设置路归并，必须设置 2k 个个输入缓冲区和输入缓冲区和 2 个输出缓冲区。个输出缓冲区。n示例：给每一个归并段固定分配示例：给每一个归并段固定分配 2 个输入缓冲个输入缓冲区，做区，做 2 路归并。假设存在路归并。假设存