第6章 数据库存储结构

2019/10/41第六章数据库存储结构2019/10/42主要内容6.1数据库存储设备6.2文件组织6.3文件结构6.4索引技术2019/10/436.1数据库存储设备计算机中有两级存储,分别是主存和辅存根据访问数据的速度、成本和可靠性,存储介质可分成以下六类:2019/10/441．高速缓冲存储器（Cache）简称为“高速缓存”，也就是一般说的Cache。Cache访问速度快，但贵，容量小。2.主存储器（MainMemory）主存储器简称为主存,或内存。主存中的数据在掉电或系统崩溃时,会全部丢失。2019/10/453.磁盘存储器（Magnetic-DiskStorage）磁盘是目前最常用的外部存储器,由磁性材料制成,数据存储在磁盘表面。磁盘是一种大容量的可直接存取的外部存储设备。在掉电或系统崩溃后,仍能保持数据不丢失。硬磁盘的特性：2019/10/46①硬磁盘的物理特性硬磁盘的总容量为：盘面数目×每盘面的磁道数×每磁道的盘块数×每盘块的字节数磁盘是一种直接存储设备，可随机读写任一盘块。盘块地址的形式是：柱面号磁头号盘块号图6.1磁盘块地址形式示意图2019/10/47②磁盘的性能指标磁盘的性能用磁盘的容量、存取时间、数据传输速度和可靠性四个参数衡量。③内外存间的数据交换访问的数据不在主存时,需通过外存加载，所以内外存间要频繁地进行数据交换，每交换一次数据，就称为一次I/O操作。2019/10/48数据块的长度不一定恰好等于记录的整数倍，通常有两种组块方式：不跨块方式：一个数据块只包含若干完整记录，不足以容纳一个记录的零头空间放弃不用。跨块方式：允许一个记录跨在不同数据块。这种组块方式虽然可节省空间，但实现比较困难，用得较少。2019/10/49④廉价磁盘冗余阵列(RedundantArrayofInexpensive（或Indscendent）Disks，简称RAID)它是利用一台磁盘阵列控制器来统一管理和控制一组(几台到几十台)磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。实现途径有两个：数据重复存储和通过并行提高数据传输速度RAID按照其基本特性，可分为八级。2019/10/4104磁带磁带是一种顺序存储设备,即磁带只能顺序访问，不能随机访问。主要用于数据备份或数据归档。磁带的可靠性较好，主要有两大用途：作为磁盘的后援存储器，存储数据库文件的副本用来存储磁盘上存储不了的大型数据库文件,数据库中不常用的数据库文件或历史数据可以存储在磁带上。2019/10/4115光存储器光存储器是多媒体信息的主要存储设备，作为分布式软件的主要存储介质，可存储音频、图像一类的数据。目前流行的光存储器是光盘只读存储器(CD-ROM)。2019/10/4126快擦写存储器（FlashMemory）快擦写存储器又称为“电可擦可编程只读存储器”，快闪存在掉电后仍能保持数据不丢失。快闪存的缺陷是只能支持有限次擦写。而且不能直接重写，必须先擦去整组存储器的内存，然后再写数据进去。2019/10/4136.2文件组织外存中，数据库以文件形式组织，而文件又是由记录组成。记录在物理文件中的实现就是本节讨论的内容。文件组织的两种方式：定长格式和变长格式。2019/10/4146.2.1定长记录就是每条记录都是占用一定长度的字节数。记录的排列也就是一张表格每行有相同的长度，以一行为单元进行增加删除等修改操作。Sn1000001甲Sn2000002乙Sn3000003丙Sn4000004丁2019/10/415SnumCnumScoreS003160S001283S005480S004185S006375S003280S002285S004260S003340图6.2定长记录的文件2019/10/416图6.3删除记录2，5，7后的文件结构2019/10/417如上图每条记录包含姓名、学号、班级三条信息。在每条记录中对应的信息占相同的字节数，所以每条记录的长度一定，构成了一个含有四条记录的定长记录的文件。存在的两个问题：1.删除：删除后是在其位置补充一个记录还是忽略这个位置；2.长度：若物理上每个块的大小不等于每个记录的长度倍数，则必然在读这样的记录时要访问两个块。2019/10/4186.2.1.1删除方法1.删除记录后，把记录依次上移。缺点移动次数过多。2.把最后的记录补到删除的位置。只需移动一次。以上两个方法都需要移动结点，操作不灵活，处于灵活的考虑必然会想到指针，就是第三种方法。2019/10/4193.把删除的结点用指针链接起来首先，文件增设“文件首部”，其中有一个指针指向第一个被删除的记录位置，所有被删除记录的位置都用指针链接起来，构成“空闲记录链表”。缺点：这些被指针链接的记录被称为“被拴记录”，若被删记录被删掉，则指向记录的指针称为“悬挂指针”，所指空间称为“垃圾”，也就是别人无法使用而又被空闲着。2019/10/4206.2.1.2.插入方法可以根据删除的方法而定，直接插入尾部，或插到空位置。6.2.2变长记录实际应用中定长记录格式文件较多,但为了增强文件的灵活性,在数据库系统中，有时需要文件中的记录是变长格式。变长记录的表示有字节串形式和定长形式两种。2019/10/4216.2.2.1变长记录的字节串表示形式①尾标志法把每个记录看成连续的字节串，然后在每个记录的尾部附加“记录尾标志符”（∧）,表明记录结束。图6.2的定长记录文件可以用图6.4的格式表示。②记录长度法记录的开始加一个记录长度的字段来实现，读取数据时以此作为记录结束与否的标志。2019/10/422SnumCnumScoreCnumScoreCnumScoreS003160280340∧S001283∧S005480∧S004185260∧S006375∧S002285∧图6.4变长记录的字节串表示形式2019/10/423字节串表示形式缺点：①每条记录长度不一，被删除后的位置难于使用。②记录要增长很难。“分槽式页结构”：每块的开始设置一个“块首部”，包含以下信息：块中的记录数目，只想块中自由空间尾部的指针，登记每个记录近的开始位置和大小的信息。2019/10/424图6.5分槽式页结构2019/10/4256.2.2.2变长记录的定长表示形式1.预留空间技术取所有记录中最长的一个记录的长度作为存储空间的记录长度，来存储变长记录。对于预留空间，仍如同定长格式的表格状。缺点：如果每个记录的差别很大，就会造成大量空间的浪费。2019/10/426例如图6.4的字节串表示形式可以用图6.6的预留空间技术实现。该方法一般在大多数记录的长度接近最大长度时才使用，否则使用时空间浪费很大。SnumCnumScoreCnumScoreCnumScoreS003160280340S001283∧∧∧S005480∧∧∧S004185260∧∧S006375∧∧∧S002285∧∧∧图6.6变长记录的预留空间表示形式2019/10/4272.指针技术解决记录长度差很大的方法，省去过多的空间浪费。每个定长记录后面增加指针指向在上一方法中可以合并为同一记录的其他记录。被指向的整体成为溢出块。2019/10/428图6.7变长记录的指针表示方式2019/10/429图6.8固定块和溢出块结构2019/10/4306.3文件结构文件中记录的组织方式有无序䖇件、有序文件、聚集文件和HASH文件四种。6.3.1无序文件无序文件也称为堆文件．无序文件的操作比较简单，但查找效率比较低．无序文件的删除操作比较复杂，常用的方法主要有以下三种：2019/10/431（１）首先找到被删记录所在的磁盘块，然后读到主存缓冲区，在缓冲区中删除记录，最后把缓冲区内容写回到磁盘文件．（２）在每个记录的存储空间增加一个标志位，标识记录删除与否，一般该标志常为空。删除一个记录时，将此记录的标志位置“1”,以后查找记录时跳过有该标志的记录。（３）常用于定长记录文件，删除一个记录时，总是把文件末尾记录移到被删记录位置。2019/10/4326.3.2有序文件有序文件是指记录按某个（或某些）域的值的大小顺序组织，一般最为常用的是按关键字的升序或降序排列，即每个记录增加一个指针字段，根据主键的大小用指针把记录链接起来。文件中每个记录增加一个指针字段，根据查找键的大小用指针把记录连接起来。2019/10/433图6.9顺序文件2019/10/434有序文件操作删除：只需修改指针即可。同定长记录的方法三插入：1）定位：找到要插的位置。按查找键的顺序2）插入：在找到记录的块内，如果自由空间有空闲纪录，那么插入；若没有就插入到溢出块中。在初始的时候，可以保持无力顺序和查找键的顺序一致，以提高速度，若多次操作后变化很大，有必要重新组织一次。2019/10/4356.3.3聚集文件文件允许一个文件有多个关系的记录组成，即记录类型文件。例：可以把有关一个人的全部记录信息放在相邻的位置，按人查找信息时就会很方便。2019/10/436图6.10插入一个记录后的顺序文件2019/10/437图6.11聚集文件例子2019/10/4386.3.4HASH文件哈稀(HASH)文件又称为散列文件，是一种支持快速存取的文件存储方法。1．散列的概念：设K是所有查找键值的集合，B是所有桶地址的集合。散列函数h是从K到B的函数，它把每个查找键值映射到地址集合中的地址。其中每个桶的大小一定。查找键集K桶地址集B主文件记录2019/10/439检索：1）检索Ki的记录，首先计算h(Ki)在B集合中2）根据桶地址找到桶3）桶内查找特点：不同的查找键值的记录可能在同一个桶内，找到桶后仍然有进行检测。删除：找到记录直接删除即可。2019/10/4402．散列函数要满足两个条件：1）使地址分布均匀；2）地质分布随机。常用方法：质数除余法。缺点：函数的设计，若设计不好会造成很大的不均匀性，查找时间的浪费。2019/10/4413.散列碰撞问题：由于同所存储的记录数是一定的，再插入操作时很容易发生溢出。原因：一是桶的数目少；二是散列的均匀性不好。解决：1）溢出链法：每个同都作为基本桶存在，若溢出系统提供一处同连接在基本桶后面。2）开放式散列法：只存在基本桶，若溢出就插入其他空闲的桶。有两种选择方式：1。在溢出桶下面的一个空闲桶；2。采用二次散列的方法。2019/10/442图6.12散列结构的溢出链2019/10/443４.散列方法常用的HASH方法有简单HASH方法，动态HASH方法和可扩展的HASH方法．评价：散列方法必须选取恰当的散列函数。2019/10/444图6.13HASH桶目录示例2019/10/4451.简单HASH方法。该方法采用固定个数的HASH桶，即把文件划分为N个HASH桶，每个HASH桶对应一个磁盘块，每个HASH桶有一编号。缺点：⑴只能有效地支持HASH域上具有相等比较的数据操作。⑵由于HASH桶的数量一成不变，当文件记录较少时，影响记录的存取效率。2019/10/4462.动态HASH方法动态HASH方法中，HASH桶与磁盘块一一对应。HASH桶的数量不是固定的，而是随文件记录的变化而增加或减少的。2019/10/447图6.14动态HASH方法结构2019/10/4483.可扩展的HASH方法特点：按照实际需要申请或释放空间。查找：求出h(Ki)前i位值m,沿桶地指表位置m处的指针到达某个同中去找记录。插入：先查找到相应的桶，若有空闲空间直接插入；2019/10/449图6.15可扩展的HASH方法的结构2019/10/450分裂桶：情况一：指向这个桶只有一个指针。增加i的值，桶地址表加倍，每一项之分列成相邻的两项，但是指向同一个桶。新申请的桶，就得到其中第二个指针。情况二：指向这个桶有多个指针。则桶地址表不用扩大只要分裂桶可以了。申请新的桶空间，原来的桶分出后一半指针指向新的桶，从新分配分裂的