第十章文件、外部排序与外部搜索学习培训模板课件.ppt

1、第十章第十章 文件、外部排序文件、外部排序与外部搜索与外部搜索主存储器和外存储器主存储器和外存储器 文件组织文件组织 多级索引结构多级索引结构 外排序外排序 1主存储器与外存储器主存储器与外存储器主存储器主存储器又叫又叫内存储器，内存储器，简称为简称为内存；外存内存；外存储器储器简称为简称为外存。外存。外存储器外存储器与与内存储器内存储器相比，优点是：相比，优点是：u价格较低价格较低u永久的存储能力永久的存储能力缺点：缺点：u访问访问外存外存储器上的数据比访问储器上的数据比访问内存内存要慢要慢56个数量级个数量级要求我们在开发系统时必须考虑如何要求我们在开发系统时必须考虑如何使外存使外存访问次

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

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

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

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

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

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

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

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

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

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

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

13、nal delay）时间）时间。5.真正进行读写时间。真正进行读写时间。13在磁盘组上一次读写的时间主要为：在磁盘组上一次读写的时间主要为：tiotseektlatencytrw其中，其中，tseek是是平均寻查时间平均寻查时间，是把磁头定位到，是把磁头定位到要求柱面所需时间，这个时间的长短取决于磁要求柱面所需时间，这个时间的长短取决于磁头移过的柱面数。头移过的柱面数。tlatency是是平均等待时间平均等待时间，是，是将磁头定位到指定块所需时间。将磁头定位到指定块所需时间。trw是传送一个是传送一个扇区数据所需的时间。扇区数据所需的时间。在在MS-DOS系统中，多个扇区集结成组，称为系统中，

14、多个扇区集结成组，称为簇簇。簇是文件分配的最小单位，其大小由操作。簇是文件分配的最小单位，其大小由操作系统决定。在系统决定。在UNIX系统中不使用簇，文件分系统中不使用簇，文件分配的最小单位和读写的最小单位是一个扇区，配的最小单位和读写的最小单位是一个扇区，称为一个称为一个块块（block）。）。14缓冲区（缓冲区（bufferbuffer）磁盘一次读写操作访问一个扇区，称为访问磁盘一次读写操作访问一个扇区，称为访问“一页一页”（page）或）或“一块一块”（block），又），又称为称为“一次访外一次访外”。为了实施磁盘读写操作，在为了实施磁盘读写操作，在内存中内存中需要开辟一需要开辟一些区

15、域，用以存放需要从磁盘读入的信息，或些区域，用以存放需要从磁盘读入的信息，或存放需要写出的信息。这些内存区域称为存放需要写出的信息。这些内存区域称为缓冲缓冲区区。多数操作系统至少设置两个缓冲区，一个多数操作系统至少设置两个缓冲区，一个为为输入缓冲区输入缓冲区，一个为，一个为输出缓冲区输出缓冲区。15例如，在从磁盘向内存读入一个扇区的数据时，例如，在从磁盘向内存读入一个扇区的数据时，数据被存放到输入缓冲区，如果下次需要读入数据被存放到输入缓冲区，如果下次需要读入同一个扇区的数据，就可以直接从缓冲区中读同一个扇区的数据，就可以直接从缓冲区中读取数据，不需要重新读盘。取数据，不需要重新读盘。缓冲区大

16、小应缓冲区大小应与操作系统一次读写的块与操作系统一次读写的块的的大小大小相适应相适应，这样可以通过操作系统一次读写把信，这样可以通过操作系统一次读写把信息全部存入缓冲区中，或把缓冲区中的信息全息全部存入缓冲区中，或把缓冲区中的信息全部写出到磁盘。部写出到磁盘。如果缓冲区大小与磁盘上的块大小不适配，就如果缓冲区大小与磁盘上的块大小不适配，就会造成存储空间的浪费。会造成存储空间的浪费。缓冲区的构造可以看作一个先进先出的缓冲区的构造可以看作一个先进先出的队列队列。16缓冲区的定义及其操作缓冲区的定义及其操作#include#include const int DefaultSize=2048;tem

17、plate struct buffer T*data;/缓冲区数组 int current,maxSize;/当前指针,缓冲区容量buffer(int sz=DefaultSize):maxSize(sz),current(0)data=new Tsz;assert(data!=NULL);buffer()delete data;17 void OutputInfo(ostream&out,T x);/缓冲区输出 void InputInfo(istream&in,T&x);/缓冲区输入;template void buffer:OutputInfo(ostream&out,T x)if(cu

18、rrent=maxSize)for(int i=0;i maxSize;i+)out datai;current=0;datacurrent=x;current+;18template void buffer:InputInfo(istream&in,T&x)if(current maxSize)x=datacurrent;current+;else for(int i=0;i datai;current=0;19文件组织文件组织什么是文件什么是文件u文件是存储在外存上的数据结构，一般是在逻文件是存储在外存上的数据结构，一般是在逻辑上具有完整意义的一组相关信息项的有序序辑上具有完整意义的一组相

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

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

21、括文件的逻辑结构逻辑结构、文件的、文件的存储结存储结构构和文件的和文件的操作操作。文件的逻辑结构是文件的逻辑结构是线性结构线性结构，各个记录以线性，各个记录以线性方式排列。方式排列。文件的文件的存储结构存储结构是指文件在外存上的组织方式，是指文件在外存上的组织方式，它与文件特性有关。它与文件特性有关。u 顺序组织顺序组织u直接存取组织（散列组织）直接存取组织（散列组织）u索引组织索引组织文件的操作是文件的操作是定义在逻辑结构上定义在逻辑结构上的，但操作的的，但操作的具体实现具体实现要在要在存储结构存储结构上进行。上进行。22评价一个文件组织的效率评价一个文件组织的效率u执行文件操作所花费的时间

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

23、通常存放在顺序存取设备（如磁带）顺序文件通常存放在顺序存取设备（如磁带）上或直接存取设备（如磁盘）上。上或直接存取设备（如磁盘）上。当存放在顺序存取设备上时只能按顺序搜索法当存放在顺序存取设备上时只能按顺序搜索法存取；当存放在直接存取设备上时，可以使用存取；当存放在直接存取设备上时，可以使用顺序搜索法、折半搜索法等存取。顺序搜索法、折半搜索法等存取。24顺序文件的存储方式顺序文件的存储方式1.连续文件连续文件：文件的全部记录顺序地存放于：文件的全部记录顺序地存放于外存的一个连续的区域中。优点是存取速外存的一个连续的区域中。优点是存取速度快、存储利用率高、处理简单。缺点是度快、存储利用率高、处理

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

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

26、一个桶能存放。假若一个桶能存放m个个记录，则记录，则m个互为个互为同义词同义词的记录可以存放在同的记录可以存放在同一地址的桶中。当第一地址的桶中。当第m+1个同义词出现时，才个同义词出现时，才发生发生“溢出溢出”。(a)溢出链溢出链u当发生当发生“溢出溢出”时，将第时，将第m+1个同义词存放个同义词存放到到“溢出桶溢出桶”。并称存放前。并称存放前m个同义词的桶个同义词的桶为为“基桶基桶”。溢出桶和基桶大小相同。当在。溢出桶和基桶大小相同。当在基桶中检索不成功，就循指针到溢出桶中检基桶中检索不成功，就循指针到溢出桶中检索。索。27桶大小为3的溢出桶链表示例 在这种散列文件中删除记录时，因为可能需

27、要在这种散列文件中删除记录时，因为可能需要重新链接，所以只需重新链接，所以只需做一个逻辑删除标记做一个逻辑删除标记即可，即可，待系统做周期性重构时再做物理删除。待系统做周期性重构时再做物理删除。28070 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 基桶编号基桶编号 基桶区基桶区 溢出桶编号溢出桶编号 溢出桶区溢出桶区(b)分布式溢出空间分布式溢出空间u溢出桶按照一定的间溢出桶按照一定的间

28、隔分布在基桶之间。隔分布在基桶之间。如果有一个基桶溢出如果有一个基桶溢出了，系统就将记录存了，系统就将记录存放在下一个溢出桶中。放在下一个溢出桶中。u如果溢出桶自己溢出如果溢出桶自己溢出了，则使用下一个相了，则使用下一个相继的溢出桶，这需要继的溢出桶，这需要第二次溢出处理。第二次溢出处理。2901234567891011121314分布式溢出桶分布式溢出桶基桶基桶基桶基桶基桶基桶溢出桶溢出桶溢出桶溢出桶如果系统对基桶按如果系统对基桶按0,1,2,3,4,5,进行编号，进行编号，在按间隔在按间隔 G=5 插入溢出桶后，可按下列公式插入溢出桶后，可按下列公式按字节求出各个桶的实际存储地址：按字节求

29、出各个桶的实际存储地址：其中，其中，B0是在文件中第是在文件中第0号桶的起始地址，号桶的起始地址，B是每个桶的字节数。在括号中的除数是每个桶的字节数。在括号中的除数5表示每表示每隔隔5个基桶安排一个溢出桶。个基桶安排一个溢出桶。(c)相继相继溢出法溢出法u此方法此方法不设置溢出桶不设置溢出桶。当记录应存放的桶溢。当记录应存放的桶溢出时，溢出记录存放到下一个相继的桶中。出时，溢出记录存放到下一个相继的桶中。30.5iiBB0桶桶的的地地址址u如果该桶已满，就把它放如果该桶已满，就把它放到再下一个桶中，如此处到再下一个桶中，如此处理，直至把记录存放好。理，直至把记录存放好。u相继溢出法的优点是对溢

30、相继溢出法的优点是对溢出不需要漫长的寻找。紧出不需要漫长的寻找。紧邻的桶通常相距不多于一邻的桶通常相距不多于一次磁盘旋转。但当邻近的次磁盘旋转。但当邻近的多个桶被挤满时，则为了多个桶被挤满时，则为了查找空闲空间就需要检查查找空闲空间就需要检查许多桶。如果桶的容量很许多桶。如果桶的容量很小更是如此。小更是如此。31362177597 157 817 575070 246 015 542 389116 204 512 435337 117635 613262 988285 923 076 208相继溢出法相继溢出法 012435679810H(key)=key%11(2)(2)可扩充散列可扩充散列

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

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

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

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

35、k 5k 6k 7k索引表数据表key addr032k081k176k244k475k517k830953k索引非顺序文件示例索引非顺序文件示例索引顺序文件示例索引顺序文件示例当记录在外存中有序存放时，可以把所有当记录在外存中有序存放时，可以把所有n个个记录分为记录分为b个子表个子表(块块)存放，一个索引项对应存放，一个索引项对应数据表中一组记录数据表中一组记录(子表子表)。3722 12 13 30 29 3336 42 44 48 39 4060 74 56 79 80 6692 82 88 98 94 子表子表1子表子表2子表子表3子表子表4数据区数据区33488098索引表索引表12

36、34max_key addr对索引顺序文件进行搜索，一般分为两级对索引顺序文件进行搜索，一般分为两级:u先在索引表先在索引表ID中搜索给定值中搜索给定值K,确定满足确定满足 IDi-1.max_key K IDi.max_key的的 i 值值,即待查记录可能在的子表的序号。即待查记录可能在的子表的序号。u然后再在然后再在第第 i 个子表个子表中按给定值搜索要求的中按给定值搜索要求的记录。记录。索引表是索引表是按按max_key有序有序的的,且长度也不大且长度也不大,可可以折半搜索，也可以顺序搜索。以折半搜索，也可以顺序搜索。各子表内各个记录如果也按关键码有序各子表内各个记录如果也按关键码有序,

37、可以可以采用折半搜索或顺序搜索采用折半搜索或顺序搜索;如果不是按关键码如果不是按关键码有序有序,只能顺序搜索。只能顺序搜索。38索引顺序文件的搜索成功时的平均搜索长度索引顺序文件的搜索成功时的平均搜索长度 ASLIndexSeq=ASLIndex+ASLSubList其中其中,ASLIndex 是在索引表中搜索子表位置的是在索引表中搜索子表位置的平均搜索长度，平均搜索长度，ASLSubList 是在子表内搜索记是在子表内搜索记录位置的搜索成功的平均搜索长度。录位置的搜索成功的平均搜索长度。设把长度为设把长度为n的表分成均等的的表分成均等的b个子表，每个个子表，每个子表子表s个记录，则个记录，则

38、b=n/s。又设表中每个记。又设表中每个记录的搜索概率相等，则每个子表的搜索概率录的搜索概率相等，则每个子表的搜索概率为为1/b，子表内各记录的搜索概率为，子表内各记录的搜索概率为 1/s。若对索引表和子表都用顺序搜索，则索引顺若对索引表和子表都用顺序搜索，则索引顺序搜索的搜索成功时的平均搜索长度为序搜索的搜索成功时的平均搜索长度为 ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+139索引顺序文件的平均搜索长度与表中的记录个索引顺序文件的平均搜索长度与表中的记录个数数n有关，与每个子表中的记录个数有关，与每个子表中的记录个数s有关。在有关。在给定给定n的情况下，的情况

39、下，s 应选择多大？应选择多大？用数学方法可导出用数学方法可导出,当当 s=时时,ASLIndexSeq取取极小值极小值 +1。这个值比顺序搜索强，但比折。这个值比顺序搜索强，但比折半搜索差。但如果子表存放在外存时，还要受半搜索差。但如果子表存放在外存时，还要受到页块大小的制约。到页块大小的制约。若采用折半搜索确定记录所在的子表若采用折半搜索确定记录所在的子表,则搜索则搜索成功时的平均搜索长度为成功时的平均搜索长度为 ASLIndexSeq=ASLIndex+ASLSubList log2(b+1)-1+(s+1)/2 log2(1+n/s)+s/240nn倒排表倒排表 (Inverted I

40、ndex List)(Inverted Index List)对包含有大量数据记录的数据表或文件进行搜对包含有大量数据记录的数据表或文件进行搜索时，最常用的是针对记录的主关键码建立索索时，最常用的是针对记录的主关键码建立索引。主关键码可以唯一地标识该记录。用主关引。主关键码可以唯一地标识该记录。用主关键码建立的索引叫做键码建立的索引叫做主索引主索引。主索引的每个索引项给出记录的关键码和记录主索引的每个索引项给出记录的关键码和记录在表或文件中的存放地址。在表或文件中的存放地址。但在实际应用中有时需要针对但在实际应用中有时需要针对其它属性其它属性进行搜进行搜索。例如，查询如下的职工信息：索。例如，

41、查询如下的职工信息：(1)列出列出所有教师的名单；所有教师的名单；(2)已婚的女性职工有哪些人？已婚的女性职工有哪些人？41 记录关键码 key 记录存放地址 addr这些信息在数据表或文件中都存在，但都不是这些信息在数据表或文件中都存在，但都不是关键码，为回答以上问题，只能到表或文件中关键码，为回答以上问题，只能到表或文件中去顺序搜索，搜索效率极低。去顺序搜索，搜索效率极低。因此，除主关键码外，可以因此，除主关键码外，可以把一些经常搜索的把一些经常搜索的属性设定为属性设定为次关键码次关键码，并，并针对每一个作为次关针对每一个作为次关键码的属性，建立键码的属性，建立次索引次索引。在次索引中，列

42、出该属性的所有取值，并对每在次索引中，列出该属性的所有取值，并对每一个取值建立有序链表，把所有具有相同属性一个取值建立有序链表，把所有具有相同属性值的记录值的记录按存放地址递增的顺序按存放地址递增的顺序或或按主关键码按主关键码递增的顺序递增的顺序链接在一起。链接在一起。4243 0 1k 2k 3k 4k 5k 6k 7k索引表数据表职工号职工号 姓名姓名 性别性别职务职务婚否婚否 83张珊张珊女女教师教师已婚已婚 08李斯李斯男男教师教师已婚已婚 03王璐王璐男男教务员教务员 已婚已婚 95刘琪刘琪女女实验员实验员 未婚未婚 24岳跋岳跋男男教师教师已婚已婚 47周斌周斌男男教师教师已婚已婚

43、 17胡江胡江男男实验员实验员 未婚未婚 51林青林青女女教师教师未婚未婚 key addr032k081k176k244k475k517k830953k索引非顺序文件示例索引非顺序文件示例次索引的索引项由次索引的索引项由次关键码次关键码、链表长度链表长度和和链表链表本身本身等三部分组成。等三部分组成。例如，为了回答上述的查询，我们可以分别建例如，为了回答上述的查询，我们可以分别建立立“性别性别”、“婚否婚否”和和“职务职务”次索引。次索引。44性别次索引次关键码次关键码 男男 女女 计计 数数 5 3 地址指针地址指针指针指针 03 08 17 24 47 51 83 9545婚否次索引次关

44、键码次关键码 已婚已婚 未婚未婚 计计 数数 5 3 地址指针地址指针指针指针 03 08 24 47 83 17 51 95职务次索引次关键码次关键码 教师教师 教务员教务员 实验员实验员 计计 数数 5 1 2 地址指针地址指针指针指针 08 24 47 51 83 03 17 95(1)列出所有教师的名单；列出所有教师的名单；(2)已婚的女性职工有哪些人？已婚的女性职工有哪些人？通过顺序访问通过顺序访问“职务职务”次索引中的次索引中的“教师教师”链，链，可以回答上面的查询可以回答上面的查询(1)。通过对通过对“性别性别”和和“婚否婚否”次索引中的次索引中的“女性女性”链链和和“已婚已婚”

45、链链进行进行求求“交交”运算，就能够找运算，就能够找到所有既是女性又是已婚的职工记录，从而回到所有既是女性又是已婚的职工记录，从而回答上面的查询答上面的查询(2)。倒排表是次索引的一种实现倒排表是次索引的一种实现。在表中所有次关。在表中所有次关键码的链都保存在次索引中，仅通过搜索次索键码的链都保存在次索引中，仅通过搜索次索引就能找到所有具有相同属性值的记录。引就能找到所有具有相同属性值的记录。在次索引中记录在次索引中记录记录存放位置的指针记录存放位置的指针可以可以用主用主关键码表示关键码表示:可通过搜索次索引确定该记录的主可通过搜索次索引确定该记录的主关键码关键码,再通过搜索再通过搜索主索引主

46、索引确定记录的存放地址。确定记录的存放地址。46在倒排表中各个属性链表的长度大小不一在倒排表中各个属性链表的长度大小不一,管管理比较困难。为此引入理比较困难。为此引入单元式倒排表单元式倒排表。在单元式倒排表中在单元式倒排表中,索引项中不存放索引项中不存放记录的存记录的存储地址储地址,而是存放而是存放该记录所在硬件区域（即存该记录所在硬件区域（即存储区域）的标识储区域）的标识。硬件区域可以是磁盘柱面、磁道或一个页块硬件区域可以是磁盘柱面、磁道或一个页块,以以一次一次 I/O 操作能存取的存储空间作为硬件操作能存取的存储空间作为硬件区域区域为最好。为最好。47为使索引空间最小为使索引空间最小,在索

47、引中标识这个硬件区在索引中标识这个硬件区域时可以使用一个能转换成地址的二进制数域时可以使用一个能转换成地址的二进制数,整个次索引形成一个整个次索引形成一个(二进制数的二进制数的)位矩阵位矩阵。例如例如,对于记录学生信息的文件对于记录学生信息的文件,次索引可以是次索引可以是如图（下页）所示的结构。二进位的值为如图（下页）所示的结构。二进位的值为 1 的的硬件区域包含具有该次关键码的记录。硬件区域包含具有该次关键码的记录。4849 硬 件 区 域 1 2 3 4 5 251 252 253 254 次关键码 1 男 1 0 1 1 1 1 0 1 1 (性别)女 1 1 1 1 1 0 1 1 0

48、 次关键码 2 广东 1 0 0 1 0 0 1 0 0 (籍贯)北京 1 1 1 1 1 0 0 1 1 上海 0 0 1 1 1 1 1 0 0 次关键码 3 建筑 1 1 0 0 1 0 1 0 1 (专业)计算机 0 0 1 1 1 0 0 1 1 电机 1 0 1 1 0 1 0 1 0 单元式倒排表结构单元式倒排表结构50n针对一个查询：找出所有针对一个查询：找出所有广东广东籍学籍学建筑建筑的的男男学学生。可以从生。可以从“性别性别”、“籍贯籍贯”、“专业专业”三三个次索引分别抽取属性值为个次索引分别抽取属性值为“男男”、“广东广东”、“建筑建筑”的位向量，按位求交，求得满足查询的

49、位向量，按位求交，求得满足查询要求的记录在哪些硬件区域中，再读入这些硬要求的记录在哪些硬件区域中，再读入这些硬件区域，从中查找所需的数据记录。件区域，从中查找所需的数据记录。n由运算结果可知，在硬件区域由运算结果可知，在硬件区域1，中有所需中有所需的记录。然后将硬件区域的记录。然后将硬件区域1，等读入内存，等读入内存，在其中进行检索，就可取出所需记录。在其中进行检索，就可取出所需记录。1 0 1 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 AND 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0多级索引结构多级索引结构51n当当数据记录数据记录数目特别大，

50、数目特别大，索引表索引表本身也很大，本身也很大，在内存中放不下，需要分批多次读取外存才能在内存中放不下，需要分批多次读取外存才能把索引表搜索一遍。把索引表搜索一遍。n此时此时,可以建立可以建立索引的索引索引的索引(二级索引二级索引)。二级索。二级索引可以常驻内存，二级索引中一个引可以常驻内存，二级索引中一个索引项索引项对应对应一个一个索引块索引块，登记该，登记该索引块的最大关键码及该索引块的最大关键码及该索引块的存储地址。索引块的存储地址。n如果二级索引在内存中也放不下，需要分为许如果二级索引在内存中也放不下，需要分为许多块多次从外存读入。可以建立二级索引多块多次从外存读入。可以建立二级索引的