11第11章文件与外部排序讲解.ppt

第11章 文件与外部排序 在许多实际应用中，特别是数据处理时，都需要长期存储海量数据，这些数据通常以文件的方式组织并存储在外存。如何有效地管理这些数据，从而给使用者提供方便而高效的使用数据的方法称为文件管理。 在实际存取这些海量数据时，为了方便使用，往往以某种顺序排序后再存储在外存上，这种排序称为外部排序。在排序时由于一次不能将数据文件中的所有数据同时装入内存中进行，因此就必须研究如何对外存上的数据进行排序的技术。 11.1 文件的基本概念 文件存储在外存上，通常是以块(I/O读写的基本单位，称为物理记录)存取。 物理记录和逻辑记录之间的关系是： ① 一个物理记录存放一个逻辑记录； ② 一个物理记录包含多个逻辑记录； ③ 多个物理记录存放一个逻辑记录。 ⑶ 文件(File)：大量性质相同的数据记录的集合。文件的所有记录是按某种排列顺序呈现在用户面前，这种排列顺序可以是按记录的关键字，也可以是按记录进入文件的先后等。则记录之间形成一种线性结构(逻辑上的)，称为文件的逻辑结构；文件在外存上的组织方式称为文件的物理结构。基本的物理结构有：顺序结构，链接结构，索引结构 。 ⑷ 文件的分类 ⑴ 按记录类型，可分为操作系统文件和数据库文件： ① 操作系统文件(流式文件) ： 连续的字符序列(串)的集合； ② 数据库文件： 有特定结构(所有记录的结构都相同)的数据记录的集合。 ⑵ 按记录长度，可分为定长记录文件和不定长记录文件： ① 定长记录文件：文件中每个记录都有固定的数据项组成，每个数据项的长度都是固定的； ② 不定长记录文件：与定长记录文件相反。 ◆ 简单匹配：查找关键字的值与给定的值相等的记录； ◆ 区域匹配：查找关键字的值在某个区域范围内的记录； ◆ 函数匹配：给出关键字的某个函数，查找符合条件的记录； ◆ 组合条件匹配：给出用布尔表达式表示的多个条件组合，查找符合条件的记录。 ⑵ 插入记录 将给定的记录插入到文件的指定位置。插入是首先要确定插入点的位置(检索记录)，然后才能插入。 ⑶ 删除记录 从文件中删除给定的记录。记录的删除有两种情况： ① 在文件中删除第k个记录； ② 在文件中删除符合条件的记录。 ⑷ 修改记录 对符合条件的记录，更改某些属性值。修改时首先要检索到所要修改的记录，然后才能修改。 ⑸ 记录排序 根据指定的关键字，对文件中的记录按关键字值的大小以非递减或非递增的方式重新排列(或存储)。 11.2 文件的组织方式 记录按其在文件中的逻辑顺序依次进入存储介质。在顺序文件中，记录的逻辑顺序和存储顺序是一致的。 ⑴ 根据记录是否按关键字排序：可分为排序顺序文件和一般顺序文件； ⑵ 根据逻辑上相邻的记录的物理位置关系：可分为连续顺序文件和链接顺序文件。 顺序文件类似于线性表的顺序存储结构，比较简单，适合于顺序存取的外存介质，但不适合随机处理。 11.2.2 索引文件 11.2.3 ISAM文件 ◆ 溢出索引项：是为插入记录设置的。关键字域存放该磁道上溢出的记录的最大关键字；指针域存放溢出记录链表的头指针。 在磁道索引的基础上，又为文件所占用的柱面建立一个柱面索引，其结构是： 1 ISAM文件的检索 根据关键字查找时，首先从主索引中查找记录所在的柱面索引块的位置；再从柱面索引块中查找磁道索引块的位置；然后再从磁道索引块中查找出该记录所在的磁道位置；最后从磁道中顺序查找要检索的记录。 2 记录的插入 首先根据待插入记录的关键字查找到相应位置；然后将该磁道中插入位置及以后的记录后移一个位置(若溢出，将该磁道中最后一个记录存入同一柱面的溢出区，并修改磁道索引) ；最后将记录插入到相应位置。 3 记录的删除 只需找到要删除的记录，对其做删除标记，不移动记录。当经过多次插入和删除操作后，基本区有大量被删除的记录，而溢出区也可能有大量记录，则周期性地整理ISAM文件，形成一个新的ISAM文件。 4 ISAM文件的特点 ◆ 优点：节省存储空间，查找速度快； ◆ 缺点：处理删除记录复杂，多次删除后存储空间的利用率和存取效率降低，需定期整理ISAM文件。 11.2.4 VSAM文件 ◆ 若控制区域中没有空白控制空间：则开辟一个新的控制区域，进行控制区间域分裂和相应的顺序集中的结点分裂。也可按B+树的分裂方法进行。 2 记录的删除 先找到要删除的记录，然后将同一控制区间中比删除记录关键字大的所有记录逐个前移，覆盖要删除的记录。当一个控制区间的记录全部删除后，需修改顺序集中相应的索引