数据结构文件及查找PPT学习教案

1、会计学1数据结构文件及查找数据结构文件及查找 数据库文件的每个记录由若干数据项构成。记录是文件存取的基本单位，数据项是文件使用的最小单位。数据项又称关键字项，关键字项的值称为关键字(Key)。能惟一标识一个记录的关键字称为主关键字，而其他的关键字称为次关键字。 文件（File）是性质相同、逻辑上相关的记录的集合。 按文件记录的类型不同可以将文件分为两类：操作系统文件和数据库文件。操作系统文件是一维的字符序列，无结构，无解释。数据库文件是带有结构的记录集合。 第1页/共50页第2页/共50页学号姓名性别年龄200801001张小平立新女20200801003王鹏飞男19

2、200801004王新刚惠女19 下面是一个简单的学生文件，每个学生的情况是一个记录。每个记录由学号、姓名、性别和年龄4个数据项组成。其中“学号”是主关键字，“姓名”、“性别”等是次关键字。第3页/共50页 文件又可分为定长文件和不定长文件。 和其它数据结构一样，文件结构也包括逻辑结构、存储结构以及文件上的各种操作这3个方面。文件的操作是定义在逻辑结构上的，但操作的具体实现要在存储结构上进行 若文件中记录含有的信息长度相同，则称这类记录为定长记录，由这种定长记录组成的文件称为定长文件；若文件中记录含有的信息长度不等，则称为不定长文件。第4页/共50页 文件的逻辑结构是

3、指文件的外部组织形式，是用户对数据的表示和存取方式。 文件中各记录之间存在着逻辑关系，当一个文件的各记录按照某种次序排列起来时，各记录之间自然地形成了一种线性关系。文件中的各个记录最多只有一个前驱记录和一个后继记录，而文件的第一个记录只有后继记录没有前驱记录，文件的最后一个记录只有前驱记录没有后继记录。所以可以把文件看成是线性结构。 第5页/共50页 文件检索就是在文件中查找满足条件的记录，可以按记录的逻辑号查找，也可以按关键字查找。 文件维护主要是指对文件进行记录的插入、删除及修改等更新操作。 文件上的操作主要有两类：检索和维护。第6页/共50页 文件的存储结构是指文件在物理存储介质（磁盘、

4、光盘、U盘）上的组织形式，它决定了文件信息在存储设备上的存储位置。 文件的存取方式与文件的物理结构有关。采用不同的组织形式就得到不同的存储结构。基本的组织有顺序组织、索引组织和Hash组织。 第7页/共50页 顺序文件是指记录按其在文件中的逻辑顺序依次存入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。若顺序文件中的记录按关键字有序，则称此顺序文件为有序顺序文件，否则称为无序顺序文件。第8页/共50页 顺序文件在存储介质中可以有两种不同的实现结构：连续结构和链结构。 连续结构是指逻辑上相邻的记录其存储位置是相邻的，链结构是指物理记录之间的次序由指针链来表示。这两种结构对应

5、的顺序文件分别称为连续顺序文件和链接顺序文件。第9页/共50页 上图为一个具有4个逻辑块的连续结构文件，其逻辑块号0、1、2、3依次存放在物理块15、16、17、18中。 第10页/共50页 排序顺序文件一般顺序文件第11页/共50页连续结构的优点是：(2)顺序访问速度快，对于等长记录的连续文件可以进行顺序存取，也可以进行类似折半查找的随机存取，但是对于不等长记录的连续文件只能进行顺序存取；(3)因为数据集中存放在连续的盘块中，访问时所需的寻道次数和寻道时间少。 (1)结构简单；第12页/共50页连续结构存储的缺点： (1)由于插入和删除记录会引起其它记录的移动，在外存中执行此操作会引起磁头的

6、频繁来回移动，因此连续结构只能在文件的末尾插入记录，删除记录时，只作标记进行逻辑删除，只有用户指定物理删除时才真正删除相应记录，进行记录的移动；第13页/共50页 (2)顺序文件需要连续的盘块存放数据，因此，在插入记录时如果原来分配的盘块已没有空闲空间，而与其邻接的盘块也不空闲时，需要重新在外存中查找新的较大的空闲空间，并将原有数据移动到新空间中，然后才能插入新的数据，因此，连续结构不易动态增长，而且外存容易存在碎片。第14页/共50页 上图为一个4个逻辑块的链结构文件的物理存储。使用链结构时，只要指明该文件的第一个块号就可以按链指针检索整个文件。链结构的另一个特点是文件长度可以动态地增长，只

7、要调整链指针就可插入或删除一个信息块。 链结构文件适用于顺序存取，不便于进行直接存取，存取第i个记录，必须搜索在它之前的i-1个记录。第15页/共50页(1)提高了磁盘空间利用率，解决了磁盘碎片问题；(2)便于文件的插入和删除操作；链结构主要优点是：(3)便于文件的动态增长。 从本质上讲，顺序文件就是线性表，因而对顺序文件的各种操作与线性表类似，但是，外存的访问速度比主存要慢的多，在考虑算法时要立足于尽量减少外存的访问次数，寻道次数和寻道时间。 第16页/共50页稠密索引文件索引对基本文件中的每个记录都保持一个索引项。索引项按记录关键字值大小排序第17页/共50页非稠密索引文件将基本文件分成若

8、干块，每一块内的记录不必排序，但在块与快之间有序，即前一块中的所有记录的关键字都小于后一块中所有记录的关键字。索引表只需对每个块保存一个索引项，分别给出每一块的最大关键字及该块的首地址。这种索引称为非稠密索引非稠密索引分块文件第18页/共50页多级索引文件1.二叉树排序树多级索引2.多分树索引第19页/共50页第20页/共50页第21页/共50页第22页/共50页第23页/共50页第24页/共50页第25页/共50页第26页/共50页第27页/共50页第28页/共50页9.4 B-树与B+树第29页/共50页缩小的查找范围决定。缩小的查找范围决定。第30页/共50页第31页/共50页第32页/共50页第33页/共50页第34页/共50页第35页/共50页 0 1 2 3 4 5 6 7 8 9103050708090第36页/共50页第37页/共50页8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3