文件高级程序设计PPT课件

.,1,第九章文件,本章主要内容:1、文件概述2、顺序文件3、索引文件4、ISAM文件5、散列文件本章重点：文件的组织形式与检索方法。本章难点：ISAM文件的组织与检索。,.,2,在现代计算机的应用领域中，数据处理是一个重要方面。数据处理是对各种类型的大批量的数据进行收集、存储、排序、检索、计算、修改、输出等分析和加工处理的过程。例如，用计算机进行企业管理、财务工资管理、仓库物资管理、情报检索、统计报表等都涉及到数据存放到外存储器上。有时，为了长期保存原始数据和加工处理过的数据，也需要将这些数据以文件的形式存放在外存上。学完本章读者应能掌握文件的概念、逻辑特性、物理结构和基本操作。,9.1文件概述,.,3,1、文件概念,1、常用外存：,磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末端记录时）。,.,.,读出头,写入头,原始盘,接收盘,IBG（InterBlockGap）块间间隙,块1,块3,块2,带文件的读写时间：Ti/o=ta+ntwta：延迟时间tw：传输时间/字符n字符数。,.,4,磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。速度快、容量大、直接存取设备。种类：固定头磁盘、活动头磁盘固定头磁盘：每个磁道都有一个磁头（速度快）活动头磁盘：每个盘面共用一个磁头，增加了找道的时间，应用广泛。,柱面：各盘面的直径相同的磁道的总和。,物理位置：盘组号、柱面号、磁道号、块（扇区号）,盘文件的读写时间：Ti/o=tseck+tla+ntwmtseck：找道时间tla：等待时间twm：传输时间/字符，n字符数。,.,5,数据域（数据场）：记录中的每个数据项，称之为域或场（Field）关键字：唯一标识记录的域，称之为关键字。辅助关键字，称之为次关键字。记录（Record）：若干相关的数据项的集合。如果存之于外存，叫做记录。文件：记录的集合。记录的物理结构和逻辑结构：逻辑结构：记录在用户或程序员面前呈现的形式。物理结构：记录在在物理存储器上的存储方式，是数据的物理表示和组织。物理记录和逻辑记录：物理记录：计算机用一条I/O指令进行读写外存的基本单位。通常，对一定的设备和操作系统，大小是固定不变的。逻辑记录：程序员加以定义，用户要求使用的。,2、基本术语：,.,6,记录B,记录C,记录D,记录A,记录A,记录B,记录C,记录D,.,7,检索：顺序存取：存取下一个逻辑记录直接存取：存取第i个逻辑记录按关键字值存取相应的记录：简单询问：查单个记录区域询问：查多个记录函数询问：满足某种条件的记录布尔询问：满足布尔运算组合的询问修改：插入、修改、更新更新方式：实时、批量两种方式,3、检索和修改,.,8,9.2顺序文件,顺序文件是物理结构最简单的文件，也是数据处理历史上最早使用的文件结构。顺序文件的各个记录按输入的先后次序存放在外存中的连续存储区。为了便于检索和修改文件，文件中的记录通常按关键字的大小次序排列，成为按关键字排序的顺序文件。顺序文件的基本优点是在连续存取时速度较快。例如，如果文件中的第i个记录刚被存取过，而下一个要存取的记录就是第i+1个记录，则此次存取将会很快完成。磁带是比较适用于这种应用的外存设备。存放于磁带上的文件也只能是顺序文件，这是由磁带的物理特性决定的。存放于磁盘上的文件，既可以是顺序文件，也可以是索引结构或其它结构类型的文件。,.,9,当需要对磁带顺序文件进行检索时，一般是采用顺序扫描的方式来检索满足查询条件的记录。例如，若要检索第i个记录，则必须先检索前面的i-1个记录。为了提高平均检索效率，可采用批量处理技术。如果将对文件的多个检索请求加以积累和排序，则形成一个称为待办文件（或事务文件）的文件。如果将被查询的文件称为主文件，则批量检索就是按照待办文件的要求成批地检索主文件。批量检索对于实时应用来说是不适宜的，因为实时查询要求响应时间快，而在很短的时间间隔内，积累的批处理文件规模太小，不能表现出它的优越性。,.,10,在磁带顺序文件中插入记录，只能加在文件的末尾，不能插在两个原有记录之间。修改记录，即使在新旧记录等长的情况下，将新记录写在旧记录的位置上，一般不但不可能完全重合，甚至还会破坏邻近记录的信息。因此，修改一个磁带文件，需要用另一条磁带将原文件复制过来，在复制过程中进行插入、删除、修改记录的操作。为了提高效率，修改一个顺序文件，也采用成批处理技术。这种批量修改方式很适用于银行帐户结算管理系统。例如，可把一天的零星支取和存入分别作为记录收集在一起，构成为一个待办文件，在当天下班时再按照待办文件进行批量修改主文件（头天下班修改过的主文件）的工作，便得到一个新主文件。,.,11,9.3索引文件,顺序文件的查询速度很慢。采用索引文件可以提高检索效率。实际上，在前面的章节中我们已经运用了索引技术。索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之，索引指出了记录在存储器中的存储地址。设记录Ri的关键字为Ki，Ri在外存中的存储地址为Ai，则（Ki，Ai）称为记录Ri的索引项。索引表（简称索引）是索引项的集合。,.,12,如果文件中的每个记录都有一个索引项，则这样的索引称为稠密索引。如果多个记录只有一个索引项，则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录。索引文件在外存（磁盘、磁鼓等）中可分为两个存储区：索引区和记录区（数据区）。索引表中的索引项顺序存放在索引区中，但为了便于检索，索引项一般按关键字的大小次序排列。文件中的记录按输入的先后次序存放到记录区；记录区按关键字大小次序排列的索引文件称为索引顺序文件。,.,13,对于索引顺序文件，可以不必使用稠密索引，只为一个记录块（含多个有序记录）建立一个索引项。记录区不按关键字大小次序排列的索引文件称为索引非顺序文件，这时应使用稠密索引。通常，索引项所含的数据信息比记录少得多，因而索引所需的存储空间比文件本身（记录区）所需要的存储空间少得多。在文件的记录数较少的情况下，可以为每个记录建立一个索引项。文件建立时，开辟一个索引区，一般固定在某个磁盘面的一个或多个磁道上。写入一个记录到记录区时，在索引区相应登入一个索引项，即把该记录的关键字（主关键字）和记录的存储地址顺序写入索引区。文件建立后，将索引区中的索引读入内存的缓冲区，按关键字进行内部排序。最后将排序好的索引项顺序写回到磁盘上的索引区。,.,14,根据关键字查找索引文件的记录分两步进行。第1步，访问外存的索引区，将索引读入内存缓冲区，使用顺序查找或折半查找法找出所查记录在外存数据区中的地址，这一过程称为预查找。第2步，如果在预查中已找到了所查记录的地址，则第2次访问外存，根据已查到的地址，读取所查的记录。,.,15,删除一个记录时，只需删去相应的索引项，而不必移动数据区中的记录。插入一个新记录时，将记录放到记录区的末尾，在索引区登记相应的索引项，并对索引区中的索引项重新排序。在实际应用中，索引顺序文件是被经常采用的一种文件结构。它是在顺序文件的基础上，用增加索引的办法而形成的。文件中的记录按关键字大小顺序存放在磁盘的连续或相邻的存储区中。由于记录按关键字排序，因此不必为每一个记录设立一个索引项，而把文件划分为若干个记录块，只为每块中关键字最大（或最小）的记录设置一个索引项。这种组织文件的方法称为索引顺序存取法，用这种方法建立起来的索引文件称为ISAM文件，它是一种专为磁盘存取设计的文件组织方式。,.,16,由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面的次序顺序存放。每个柱面建立一个磁道索引，每个磁道索引项由两部分组成：基本索引项和溢出索引项，每一部分都包括关键字和指针两项，前者表示该磁道中最大关键字，后者指示该磁道中第一个记录的位置，柱面索引的每一个索引项也由关键字和指针两部分组成，前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位置。柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，则可建立柱面索引的索引主索引。,.,17,9.4ISAM文件,1、ISAM（IndexedSequentialAccessMethod索引顺序访问方法）文件文件的组织方式：,磁道索引,R14,R21,R45,R47,R50,R164,磁道索引,R189,R215,R330,磁道索引,R3843,R4150,溢出区,溢出区,溢出区,215,50,3843,164,330,4150,164,330,810,4150,620,1100,4150,柱面C1,柱面C2,柱面Cn,主索引（柱面组索引）,柱面索引,磁道索引,.,18,1、ISAM（IndexedSequentialAccessMethod）文件柱面的安排：,柱面C1,磁道索引,1道,2道至18道存数据,19和20道存溢出记录,关键字指针关键字指针,基本索引项溢出索引项,磁道索引项结构,基本索引项关键字：本道的最大关键字值指针：本道第一个记录的地址溢出索引项关键字：本道的溢出记录的最大关键字值指针：本道的溢出记录的第一个溢出记录的地址,.,19,查找：主索引柱面索引磁道索引磁道的第一个记录,柱面C1,磁道索引,1道,2道3道,19和20道存溢出记录,2、3磁道的磁道索引项,50T21,R60R70R80R85R90,90T31,R14R21R43R47R50,.,20,定义：m阶B+树满足或空，或：A、根结点要么是叶子，要么至少有两个儿子B、除根结点和叶子结点之外，每个结点的儿子个数为:m/2=s2；2.关键字集合分布在整颗树中；3.B-树没有B树平衡的问题；B+树是B-树的变体，也是一种多路搜索树：1.其定义基本与B-树同，除了：2.非叶子结点的子树指针与关键字个数相同；3.非叶子结点子树指针Pi，指向关键字值属于Ki,Ki+1)的子树；4.为所有叶子结点增加一个链指针；5.所有关键字都在叶子结点出现；B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；,.,22,例如：m=3阶B+树。除根结点和叶子结点之外，每个结点的儿子个数至少为m/2=2个；结点的关键字个数至少为1。该B+树的深度为4。叶子结点都在第4层上。,8599,475864,3539,1527,511,39，64，99,11，27,27，99,424547,505558,6164,808185,869499,25,8911,1215,2027,3235,373839,第1层,第2层,第3层(L层),第4层(L1层),.,23,9.5散列文件,散列文件指的是利用杂凑（Hash）法进行组织的文件。它类似于哈希表，即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称散列文件。与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的。若干个记录组成一个存储单位，在散列文件中这个存储单位叫作桶。一个桶能存放的逻辑记录的总数称为桶的容量。假如一个桶能存放m个记录，即m个同义词的记录可以存放在同一地址的桶中，当第m+1个同义词出现时则发生“溢出”。处理溢出也可采用哈希表中处理冲突的各种方法；但对散列文件，主要采用链地址法.,.,24,当发生“溢出”时，需要将第m+1个同义词存放到另一个桶中，通常称此桶为“溢出桶”；相对地，称前m个同义词存放的桶为“基桶”。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶中没有找到待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。,.,25,例如，某i文件有18个记录，其关键字分别为28，19，13，93，89，14，55，69，8，9，16，21，33，81，62，11，34，35。用除留余数法作哈希函数H（key）=keyMOD7。桶的容量m=3，基本桶数=7，由此得到的散列文件如图10-6所示。,.,26,在散列文件中进行查找时，首先根据给定值k求得哈希地址（即基桶号），将基桶的记录读入内存进行顺序查找，若找到关键字等于k的记录，则检索成功；若基桶内没有填满记录或其指针域为空（即无溢出桶）则文件内不含有待查的记录；否则根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。在散列文件中，装填因子=n/bm。其中：n为文件的记录数，b为桶数，m为桶的容量。而存取桶数的期望值=1+/2。在散列文件中删除记录仅需要对被删除记录作一标记即可。,.,27,总之，散列文件的优点是：插入、删除方便，