数据结构导论“文件”.ppt

第7章 文 件 7.1 基本概念7.1.1 文件结构 7.1.2 外存储器件简介 7.2? 顺序文件 7.3? 索引文件 7.4 ?ISAM文件 7.5 VSAM文件 7.6 散列文件 7.7 多关键字文件 7.7.1 多重表文件 7.7.2 倒排文件 * 以上各章的讨论都是针对存放在内存中的数据的。但是，如果数据的“规模“很大（包含的数据元素很多）、或者需要长期保存，则必须存放在外部储器中。通常将存放在外存中的数据称为文件。由于外存设备与内存储器的物理特性不同，前面介绍的各种数据组织方法和操作方法不能简单地照搬过来，需要根据文件的特点专门加以考虑。 ●文件是由特性相同的记录所构成的集合，其中每个记录由若干个数据项构成，这就是文件的逻辑结构。记录是文件的基本存取单位。 住址 年龄 性别 姓名 职工号 … … … … … 寿春路40号 24 男 胡卫东 0006 中山路18号 27 女 张 红 0005 红星路100号 25 男 李 明 0002 长江路41号 30 男 王 平 0001 图7-1 文件示例 文件由若干条记录组成。单位有多少人，文件就有多少条记录。每个职工的信息集中在一条记录中。职工号为主关键字，姓名等项为次关键字。 从用户的观点看，记录应是存取操作的基本单位。但从外存储设备的观点看，应按其他标准确定基本存取单位。为了区分这两种标准。通常将按用户观点的基本存取单（即记录）称为逻辑记录，将按外存设备观点的基本存取单位称为物理记录。 文件的基本运算有两种：检索和修改。 其中文件的检索又有三种方式：　（１）顺序存取：依次存取一个逻辑记录。　（２）直接存取：存取第i个逻辑记录。　（３）按关键字存取：存取键值等于给定值的记录。　 文件的修改包括插入一个记录、删除一个记录和更新一个记录三种运算。 下面分别举例说明这三种运算（略）。 文件在存储介质（如磁盘和磁带）上的实际组织方式称为文件的存储结构或物理结构，常见的有四种：顺序组织、索引组织、散列组织、和链组织。为了讨论文件的组织方式，先简单介绍磁带存储器和磁盘存储器的有关知识。 磁带存储器把信息存储在磁带上，磁带机可以控制磁带前进，后退，磁带机上读写磁头可以读写磁带上的信息。磁带的运行情况类似以录音机上录音带的运行。 磁盘存储器是目前使用得最广泛的外存设备。微机上使用上的磁盘分为两种：硬盘和软盘。磁盘有点像唱片，但是磁盘的磁道不是螺旋线，而是同心圆。若干个盘片可以通过一个主轴串在一起，构成一个盘组。各个盘面半径相同的磁盘在一起称作一个柱面。盘组有多少个盘面，则说每个柱面有多少个磁道。一个磁道可分为若干段，每段是一个物理记录。一个盘组上从大到小的存储单位为：柱面、磁道、物理记录。 主机对外存储器的数据不能直接地进行存取。要读外存上的数据，首先要通道把数据读到内存缓冲区，然后从外存区读取数据。写数据时，将数据送到缓冲区，再通过通道将缓冲区内容写到外存储器。一次从内存读数据或往外存写数据的过程称作一次访外。一次访外可传送若干个字节，访外时间包括定位和传送时间。节省存取时间的一个有效办法是，使每次访外，在内存和外内之间传送一批较大的数据，从而减少访外次数。 分页块的存储方法是一种有利于减少访问外存次数又便于管理方法，一个块页是磁带或磁盘上的一个物理记录，它包括多个逻辑记录，内存中设置的缓冲区应该和页块的大小相等。每次访外，是把一个页块读入一个缓冲区或者把一个缓冲区写到一个页块。 若一次访外所传送的页块上有多少在近期进行处理的逻辑记录，则分页块的存储方式可以使访问次数大大减少。 我们可以用访外次数作为衡量检索效率的一个重要参数。检索一次，访外次数越少，效率越高，相反，则效率就越低。另一个衡量检索效率的参数是磁头定位，检索某一记录，磁头定位时间越少，效率越高，否则，效率就越低。 文件在外存储器上组织结构主要有三种：顺序文件、散列文件、索引文件。这三种组织方式分别适于不同的外存储器，它们的检索效率是不同的，下面分别讨论这几种文件在外存储上是如何组织的，有关的运算是如何实现的。 顺序文件是文件的一种常见组织形式，在顺序文件中，所有逻辑记录在存储介质中的实际顺序与它们进入存储器的顺序一致。　顺序文件适宜于顺序存取和成批处理，顺序文件特别适用于磁带存储器，也适用于磁盘存储器。 ●顺序文件的检索操作方法如下： (１) 顺序文件的顺序存取：从文件的第一个记录开始一个一个依次读入各个记录进行处理和使用。顺序文件对这种存取方法效率很高，因为省去很多磁头定位时间。 (２) 顺序文件的随机存取：对顺序文件的这种检索方式，由于没有建立逻辑记录和物理记录之间的直接对应关系每次检索都要从文件的第一记录开始