数据库基础第四章.ppt

第四章 数据的物理组织 课程目标 了解文件的基本组织方法 了解文件的索引结构 掌握Microsoft SQL Server的数据存储结构 问题的提出 数据库是大量数据的有结构的综合性的集合，如何将这样一个庞大的数据集合以最优的形式组织起来存放在磁盘上是一个非常重要的问题。 所谓优包括两方面：一是存储效率高，节省存储空间；二是存取效率高，速度快，代价小，节省存取时间，这对数据库应用的性能有很大的影响。 物理组织的基本问题 数据库系统是文件系统的发展。数据库实现的基础是操作系统的文件，对数据库的任何操作最终要转化为对文件的操作。 所以在数据库的物理组织中，基本的问题是：如何设计文件组织；如何利用好操作系统提供的基本的文件组织方法。 文件的基本组织方法 讨论的是如何在文件中组织数据库记录。 要求掌握文件的组织方式以及文件中记录的组织形式；理解不同的文件组织的优缺点和维护方法； 文件的基本组织方法 堆文件：没有顺序 顺序文件?? Hash哈希文件 索引文件 索引顺序文件：顺序文件的基础上建索引 索引无序文件：堆文件的基础上建索引 流水文件 流水文件又称堆文件(Pile或Heap)或流年文件(Chronological)，是一种最简单的文件组织方法。 这种文件像一本流水帐，它的组织方法是按照数据到达文件的时间顺序依次连续地存储数据，对数据不分析、不规范，记录的类型既可相同(记录长度一定)，也可不同(记录长度可变) 按先后到达顺序 流水文件 在流水文件中，记录的存放是无序的。在如下情况下，流水文件是一种较好的存储方式： 数据批量加载 表只有几页长，全表扫描的开销也很小 每次访问表时都要检索表中的每条记录 当仅访问表中选定的记录时，流水文件是不合适的 顺序文件 由于流水文件查找很费时，故要求快速响应的任何文件均不宜采用流水文件的组织方法。 主关键字是能够唯一标识记录的某个(些)数据项。不按记录到达的先后次序，而按主关键字值的顺序组织的文件谓之顺序文件 顺序文件 在顺序文件中，记录按地址次序排列，排列顺序为按主关键字值升或降序 顺序文件 如何确定关键字的顺序 顺序文件的存储组织 顺序文件的查找 顺序文件的维护 顺序文件 按码值排序时,其顺序还与存储方式有关。有按二进制数和ASCII码存储两种形式 按二进制数——根据码值数值大小排序 按ASCII码 ——可视为字符串，对二个字符串比较时，从左边第一个字符起进行比较，直到对应字符不相同为止 存储结构 向量结构：按绝对地址顺序连续排练 链结构：用链实现（指针） 块链结构：在一个物理数据块中的记录按地址顺序连续存放，而块与块之间用指针链接以维持逻辑顺序 顺序文件的查找 顺序扫描 分块查找 折半查找 探查 维护 向量结构 链结构 块链结构 思考： 顺序文件的利弊 ？ 顺序文件是在实际应用中用的最多的文件组织形式，原因就是顺序文件结构清晰，容易理解，而且对特定的查询能快速地处理。 当然顺序文件组织也有它的问题，最大的问题就是在向顺序文件插入和删除记录后，首先要保证记录按搜索码顺序重新链接起来，但是要想维护记录的物理顺序则将十分困难。如果靠移动记录的方式来维护记录在物理上的顺序，则维护代价十分昂贵！ Hash文件 Hash方法较普遍地用于造表，特别是编译程序中用它来造符号名表。 Hash的涵义是把东西切碎弄乱，在软件术语中，通常把它翻译成“杂凑”、“混编”、“散列”。实质上是一种符号名变地址的方法，在文件组织中称为关键字变地址—KAT(Key-to-Address Transformation)方法。 这类文件组织利用散列 （Hash）函数Y＝F(X)把码值映射成记录存储地址，直接存取。 其中X为码值，Y为地址。 知道码值立即可算出地址，一般说来查找效率很高。检索时间与数据文件的大小无关。插入、删除和修改记录都较方便。 影响这类存储方法效率的关键在于冲突发生的频率，所谓冲突，是指多个记录计算后取得的存储地址相同，必须采用一定的算法处理其存储位置。 采用这类文件组织需要设计恰当的Hash函数，以求尽可能减少冲突并设计发生冲突时的算法。 为减小冲突，常利用“桶”作为编址的基本单位。把若干存储单元作为一组并以同样的地址加以标识。 文件的索引结构 《新华字典》的索引表是用字母列表或者偏旁部首的分类方式的。 如:安 ?拼音an; 文件的索引结构 词典本身是汉语字典，记录是汉语单词及其解释。若将每页的第一个字与页号列表，那么查字可先查表(称为索引表)，等确定页面号后，再细查该页面。这就是索引文件的基本思想。 由此可见，组织索引表(简称索引)是索引文件的关键。 用户检索要求总是针对某一个属性或某几个属性进行。 例如查找姓名为王平的记录是针对姓名检索；