数据库存储设备文件组织与结构

数据库存储设备文件组织与结构主要内容6.1数据库存储设备

6.2

6.3文件结构

6.4索引技术5/18/202326.1数据库存储设备计算机中有两级存储,分别是主存和辅存根据访问数据的速度、成本和可靠性,存储介质可分成以下六类:5/18/20233

1．高速缓冲存储器（Cache）简称为“高速缓存”，也就是一般说的Cache。Cache访问速度快，但贵，容量小。2.主存储器（MainMemory）

主存储器简称为主存,或内存。主存中的数据在掉电或系统崩溃时,会全部丢失。

5/18/202343.磁盘存储器（Magnetic-DiskStorage）磁盘是目前最常用的外部存储器,由磁性材料制成,数据存储在磁盘表面。磁盘是一种大容量的可直接存取的外部存储设备。在掉电或系统崩溃后,仍能保持数据不丢失。硬磁盘的特性：5/18/20235①硬磁盘的物理特性硬磁盘的总容量为：

盘面数目×每盘面的磁道数×每磁道的盘块数×每盘块的字节数

磁盘是一种直接存储设备，可随机读写任一盘块。盘块地址的形式是：柱面号磁头号盘块号图6.1磁盘块地址形式示意图

5/18/20236②磁盘的性能指标

磁盘的性能用磁盘的容量、存取时间、数据传输速度和可靠性四个参数衡量。③内外存间的数据交换

访问的数据不在主存时,需通过外存加载，所以内外存间要频繁地进行数据交换，每交换一次数据，就称为一次I/O操作。5/18/20237

数据块的长度不一定恰好等于记录的整数倍，通常有两种组块方式：不跨块方式：

一个数据块只包含若干完整记录，不足以容纳一个记录的零头空间放弃不用。跨块方式：

允许一个记录跨在不同数据块。这种组块方式虽然可节省空间，但实现比较困难，用得较少。5/18/20238④廉价磁盘冗余阵列

(RedundantArrayofInexpensive（或Indscendent）Disks，简称RAID)

它是利用一台磁盘阵列控制器来统一管理和控制一组(几台到几十台)磁盘驱动器，组成一个高度可靠的、快速的大容量磁盘系统。

实现途径有两个：

数据重复存储和通过并行提高数据传输速度

RAID按照其基本特性，可分为八级。

5/18/202394磁带磁带是一种顺序存储设备,即磁带只能顺序访问，不能随机访问。主要用于数据备份或数据归档。磁带的可靠性较好，主要有两大用途：

作为磁盘的后援存储器，存储数据库文件的副本

用来存储磁盘上存储不了的大型数据库文件,数据库中不常用的数据库文件或历史数据可以存储在磁带上。

5/18/2023105光存储器

光存储器是多媒体信息的主要存储设备，作为分布式软件的主要存储介质，可存储音频、图像一类的数据。目前流行的光存储器是光盘只读存储器(CD-ROM)。5/18/2023116快擦写存储器（FlashMemory）快擦写存储器又称为“电可擦可编程只读存储器”，快闪存在掉电后仍能保持数据不丢失。快闪存的缺陷是只能支持有限次擦写。而且不能直接重写，必须先擦去整组存储器的内存，然后再写数据进去。

5/18/2023126.2文件组织

外存中，数据库以文件形式组织，而文件又是由记录组成。记录在物理文件中的实现就是本节讨论的内容。文件组织的两种方式：定长格式和变长格式。5/18/2023136.2.1定长记录就是每条记录都是占用一定长度的字节数。记录的排列也就是一张表格每行有相同的长度，以一行为单元进行增加删除等修改操作。Sn1000001甲Sn2000002乙Sn3000003丙Sn4000004丁5/18/202314SnumCnumScoreS003160S001283S005480S004185S006375S003280S002285S004260S003340

图6.2定长记录的文件

5/18/202315图6.3删除记录2，5，7后的文件结构

5/18/202316如上图每条记录包含姓名、学号、班级三条信息。在每条记录中对应的信息占相同的字节数，所以每条记录的长度一定，构成了一个含有四条记录的定长记录的文件。存在的两个问题：删除：删除后是在其位置补充一个记录还是忽略这个位置；长度：若物理上每个块的大小不等于每个记录的长度倍数，则必然在读这样的记录时要访问两个块。

5/18/2023176.2.1.1删除方法1.删除记录后，把记录依次上移。缺点移动次数过多。2.把最后的记录补到删除的位置。只需移动一次。

以上两个方法都需要移动结点，操作不灵活，处于灵活的考虑必然会想到指针，就是第三种方法。5/18/2023183.把删除的结点用指针链接起来首先，文件增设“文件首部”，其中有一个指针指向第一个被删除的记录位置，所有被删除记录的位置都用指针链接起来，构成“空闲记录链表”。缺点：这些被指针链接的记录被称为“被拴记录”，若被删记录被删掉，则指向记录的指针称为“悬挂指针”，所指空间称为“垃圾”，也就是别人无法使用而又被空闲着。5/18/2023196.2.1.2.插入方法可以根据删除的方法而定，直接插入尾部，或插到空位置。6.2.2变长记录实际应用中定长记录格式文件较多,但为了增强文件的灵活性,在数据库系统中，有时需要文件中的记录是变长格式。变长记录的表示有字节串形式和定长形式两种。

5/18/2023206.2.2.1变长记录的字节串表示形式

①尾标志法

把每个记录看成连续的字节串，然后在每个记录的尾部附加“记录尾标志符”（∧）,表明记录结束。图6.2的定长记录文件可以用图6.4的格式表示。

②记录长度法

记录的开始加一个记录长度的字段来实现，读取数据时以此作为记录结束与否的标志。

5/18/202321SnumCnumScoreCnumScoreCnumScore

S003160280340∧S001283

∧

S005480

∧

S004185260∧

S006375

∧

S002285

∧

图6.4变长记录的字节串表示形式

5/18/202322字节串表示形式缺点：每条记录长度不一，被删除后的位置难于使用。记录要增长很难。“分槽式页结构”：每块的开始设置一个“块首部”，包含以下信息：块中的记录数目，只想块中自由空间尾部的指针，登记每个记录近的开始位置和大小的信息。5/18/202323图6.5分槽式页结构5/18/2023246.2.2.2变长记录的定长表示形式预留空间技术取所有记录中最长的一个记录的长度作为存储空间的记录长度，来存储变长记录。对于预留空间，仍如同定长格式的表格状。缺点：如果每个记录的差别很大，就会造成大量空间的浪费。

5/18/202325例如图6.4的字节串表示形式可以用图6.6的预留空间技术实现。该方法一般在大多数记录的长度接近最大长度时才使用，否则使用时空间浪费很大。SnumCnumScoreCnumScoreCnumScoreS003160280340S001283

∧∧∧S005480

∧∧∧S004185260∧∧S006375

∧∧∧S002285

∧∧∧图6.6变长记录的预留空间表示形式5/18/202326指针技术解决记录长度差很大的方法，省去过多的空间浪费。每个定长记录后面增加指针指向在上一方法中可以合并为同一记录的其他记录。被指向的整体成为溢出块。5/18/202327图6.7变长记录的指针表示方式

5/18/202328图6.8固定块和溢出块结构5/18/2023296.3文件结构

文件中记录的组织方式有无序䖇件、有序文件、聚集文件和HASH文件四种。

6.3.1无序文件无序文件也称为堆文件．无序文件的操作比较简单，但查找效率比较低．无序文件的删除操作比较复杂，常用的方法主要有以下三种：5/18/202330（１）首先找到被删记录所在的磁盘块，然后读到主存缓冲区，在缓冲区中删除记录，最后把缓冲区内容写回到磁盘文件．（２）在每个记录的存储空间增加一个标志位，标识记录删除与否，一般该标志常为空。删除一个记录时，将此记录的标志位置“1”,以后查找记录时跳过有该标志的记录。（３）常用于定长记录文件，删除一个记录时，总是把文件末尾记录移到被删记录位置。

5/18/2023316.3.2有序文件有序文件是指记录按某个（或某些）域的值的大小顺序组织，一般最为常用的是按关键字的升序或降序排列，即每个记录增加一个指针字段，根据主键的大小用指针把记录链接起来。文件中每个记录增加一个指针字段，根据查找键的大小用指针把记录连接起来。5/18/202332图6.9顺序文件

5/18/202333有序文件操作

删除：只需修改指针即可。同定长记录的方法三

插入：1）定位：找到要插的位置。按查找键的顺序2）插入：在找到记录的块内，如果自由空间有空闲纪录，那么插入；若没有就插入到溢出块中。在初始的时候，可以保持无力顺序和查找键的顺序一致，以提高速度，若多次操作后变化很大，有必要重新组织一次。5/18/2023346.3.3聚集文件文件允许一个文件有多个关系的记录组成，即记录类型文件。例：可以把有关一个人的全部记录信息放在相邻的位置，按人查找信息时就会很方便。5/18/202335图6.10

插入一个记录后的顺序文件

5/18/202336图6.11聚集文件例子5/18/2023376.3.4HASH文件哈稀(HASH)文件又称为散列文件，是一种支持快速存取的文件存储方法。1．散列的概念：设K是所有查找键值的集合，B是所有桶地址的集合。散列函数h是从K到B的函数，它把每个查找键值映射到地址集合中的地址。其中每个桶的大小一定。查找键集K桶地址集B主文件记录5/18/202338检索：1）检索Ki的记录，首先计算h(Ki)在B集合中2）根据桶地址找到桶3）桶内查找

特点：不同的查找键值的记录可能在同一个桶内，找到桶后仍然有进行检测。删除：找到记录直接删除即可。5/18/2023392．散列函数要满足两个条件：1）使地址分布均匀；2）地质分布随机。常用方法：质数除余法。缺点：函数的设计，若设计不好会造成很大的不均匀性，查找时间的浪费。5/18/2023403.散列碰撞

问题：由于同所存储的记录数是一定的，再插入操作时很容易发生溢出。原因：一是桶的数目少；二是散列的均匀性不好。

解决：1）溢出链法：每个同都作为基本桶存在，若溢出系统提供一处同连接在基本桶后面。2）开放式散列法：只存在基本桶，若溢出就插入其他空闲的桶。有两种选择方式：1。在溢出桶下面的一个空闲桶；2。采用二次散列的方法。5/18/202341图6.12

散列结构的溢出链

5/18/202342４.散列方法

常用的HASH方法有简单HASH方法，动态HASH方法和可扩展的HASH方法．评价：散列方法必须选取恰当的散列函数。5/18/202343图6.13HASH桶目录示例

5/18/2023441.简单HASH方法。

该方法采用固定个数的HASH桶，即把文件划分为N个HASH桶，每个HASH桶对应一个磁盘块，每个HASH桶有一编号。缺点：⑴只能有效地支持HASH域上具有相等比较的数据操作。⑵由于HASH桶的数量一成不变，当文件记录较少时，影响记录的存取效率。

5/18/2023452.动态HASH方法

动态HASH方法中，HASH桶与磁盘块一一对应。HASH桶的数量不是固定的，而是随文件记录的变化而增加或减少的。

5/18/202346

图6.14动态HASH方法结构5/18/2023473.可扩展的HASH方法特点：按照实际需要申请或释放空间。查找：求出h(Ki)前i位值m,沿桶地指表位置m处的指针到达某个同中去找记录。插入：先查找到相应的桶，若有空闲空间直接插入；

5/18/202348图6.15可扩展的HASH方法的结构

5/18/202349分裂桶：情况一：指向这个桶只有一个指针。增加i的值，桶地址表加倍，每一项之分列成相邻的两项，但是指向同一个桶。新申请的桶，就得到其中第二个指针。情况二：指向这个桶有多个指针。则桶地址表不用扩大只要分裂桶可以了。申请新的桶空间，原来的桶分出后一半指针指向新的桶，从新分配分裂的桶中的记录。5/18/202350删除：查找到Ki的记录，从桶内删除。删除后如桶为空，桶也删除，还有可能引起桶地址的收缩。显著优点：

►数据量增长后仍然保持由原有的操作和查询性能

►空间开销达到最小5/18/2023516.4索引技术

索引的组织方式主要有线性索引和树形索引两类。6.4.1线性索引线性索引可分为稠密索引和稀疏索引两种。1.稠密索引对主文件中每一个查找键值都建立一个索引记号优点:查找、更新数据记录方便,存取速度快缺点:索引项多,索引表大,空间代价大.

5/18/2023522.稀疏索引只对主文件中若干查找键值建立一个索引记号。在插入操作较多的应用中采用稀疏索引方式是不太适宜的。

5/18/202353K1K2K3…KnA(RK1)A(RK2)A(RK3)…A(RKn)图6.16.索引结构

5/18/202354图6.17学生关系索引方式

5/18/2023556.4.2B树1.平衡树的概念

m阶平衡树或者为空，或者满足下面条件：每个节点之多有m棵子树根节点或为叶结点，或至少有两棵子树每个非叶结点至少有[m/2]棵子树根结点到叶结点的每一条路径都有同样的长度，即叶结点在同一层次上平衡树分为B+树和B树

5/18/202356图6.18多级索引

5/18/202357B树在上述定义基础上同时约定：除叶结点之外的所有其它结点的索引块最多可存放m-1个主码值和m个地址指针。其格式为:

叶结点上不包含数据记录本身，而是由记录索引项组成的记录索引块，每个记录索引项包含有主码值和地址指针。

P0K1P1K2P2…Km-1Pm-15/18/202358一般假设，每一个索引块能容纳的索引项数是个奇数，且m=2d-1≥3;每一个记录索引块能容纳的记录索引项也是个奇数，且n=2e-1≥3。

5/18/202359图6.19多级索引的B树5/18/2023606.4.3B+树1．结构每个结点之多有m-1各查找键Ki，m个指针Pi;如上图。P1K1P2................Pn-1Kn-1Pn5/18/202361叶结点：叶结点的指针指向主文件的记录；查找键在[m-1/2]——m-1之间；叶结点最后的指针指向下一叶结点。非叶结点：组成多级稀疏索引，指针在[m/2]——m之间，指针Pi指向所有查找键大于等于Ki-1,小于Ki。5/18/202362图20B+树的模型

5/18/202363

图6.21图6.19中的Ｂ树的Ｂ＋树5/18/202364查询：

方法：先找第一个大于k的查找键值，沿其左面的指针到达下一层，以此查找下去。

特点：查询的层数相同为树的高度，因为都是在叶结点链接主文件。5/18/2023652．修改操作：不引起索引结点分裂的插入若以在叶结点出现，直接插入记录；否则，找到第一个大于的查找键值，在其前面插入，其后的都向后移。5/18/202366不引起索引结点合并的删除;查找到主文件，删除记录；若主文件中还有同查找键的记录不修改索引；若无，从叶结点中删除相应的键值和指针。引起分裂的插入;插入叶结点后，把多出来的分裂出去；修改父结点，插入心结点中的最小值，同理其父结点进行修改。

5/18/202367图6.22在图6.21中插入值为41数据记录后的Ｂ＋树

5/18/202368引起合并的删除在删除叶结点后，引起结点不符合定义，将被删除，若父结点中有也将删除，导致合并的发生。B+树的性能分析显著优点：►搜索代价较小；

►解决了数据记录在插入，删除和未用回收等存储组织问题。5/18/202369图6.23在图6.21中删除主码值为26的数据记录后的Ｂ＋树5/18/202370小结

数据库是数据的有序集合，需保留在计算机外存介质上反复应用。由于实际应用系统数据规模都很庞大,加之经常要从数据集合中检索需要的数据，所以数据组织的方式，数据的定位方式，以及数据的维护策略的选取十分重要。5/18/202371在磁盘中,数据库以文件形式组织。文件组织有两种方法：一种是把记录设计成定长格式,也就是每个文件只存储某一确定长度的记录；另一种是变长格式,使之能存放不同长度的记录。实现变长记录的技术有多种,包括分槽式页结构、指针方法和保留空间等方法。5/18/202372小结

文件结构有堆文件、顺序文件、散列文件和聚集文件等四种。为了提高查找速度,可以为文件建立索引或