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

第六章数据库存储结构

1/7/20231主要内容6.1数据库存储设备

6.2文件组织

6.3文件结构

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

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

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

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

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

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

1/7/20236②磁盘的性能指标

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

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

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

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

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

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

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

实现途径有两个：

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

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

1/7/202394磁带磁带是是一种种顺序序存储储设备备,即磁磁带只只能顺顺序访访问，，不能能随机机访问问。主要用用于数数据备备份或或数据据归档档。磁带的的可靠靠性较较好，，主要要有两两大用用途：：作为磁磁盘的的后援援存储储器，，存储储数据据库文文件的的副本本用来存存储磁磁盘上上存储储不了了的大大型数数据库库文件件,数数据库库中不不常用用的数数据库库文件件或历历史数数据可可以存存储在在磁带带上。。12/29/2022105光存储器光存储器是是多媒体信信息的主要要存储设备备，作为分分布式软件件的主要存存储介质，，可存储音音频、图像像一类的数数据。目前流行的的光存储器器是光盘只只读存储器器(CD-ROM)。12/29/2022116快擦写写存储器（（FlashMemory）快擦写存储储器又称为为“电可擦擦可编程只只读存储器器”，快闪闪存在掉电电后仍能保保持数据不不丢失。快闪存的缺缺陷是只能能支持有限限次擦写。。而且不能能直接重写写，必须先先擦去整组组存储器的的内存，然然后再写数数据进去。。12/29/2022126.2文件组织织外存中，，数据库库以文件件形式组组织，而而文件又又是由记记录组成成。记录录在物理理文件中中的实现现就是本本节讨论论的内容容。文件组织织的两种种方式：：定长格格式和变变长格式式。12/29/2022136.2.1定定长记录录就是每条条记录都都是占用用一定长长度的字字节数。。记录的的排列也也就是一一张表格格每行有有相同的的长度，，以一行行为单元元进行增增加删除除等修改改操作。。Sn1000001甲Sn2000002乙Sn3000003丙Sn4000004丁12/29/202214SnumCnumScoreS003160S001283S005480S004185S006375S003280S002285S004260S003340图6.2定定长记录的的文件12/29/202215图6.3删除记记录2，5，7后的的文件件结构构12/29/202216如上图图每条条记录录包含含姓名名、学学号、、班级级三条条信息息。在在每条条记录录中对对应的的信息息占相相同的的字节节数，，所以以每条条记录录的长长度一一定，，构成成了一一个含含有四四条记记录的的定长长记录录的文文件。。存在的的两个个问题题：删除：：删除除后是是在其其位置置补充充一个个记录录还是是忽略略这个个位置置；长度：：若物物理上上每个个块的的大小小不等等于每每个记记录的的长度度倍数数，则则必然然在读读这样样的记记录时时要访访问两两个块块。12/29/2022176.2.1.1删除除方方法法1.删删除除记记录录后后，，把把记记录录依依次次上上移移。。缺点点移移动动次次数数过过多多。。2.把把最最后后的的记记录录补补到到删删除除的的位位置置。。只需需移移动动一一次次。。以上上两两个个方方法法都都需需要要移移动动结结点点，，操操作作不不灵灵活活，，处处于于灵灵活活的的考考虑虑必必然然会会想想到到指指针针，，就就是是第第三三种种方方法法。。12/29/2022183.把把删除除的结点点用指针针链接起起来首先，文文件增设设“文件件首部””，其中中有一个个指针指指向第一一个被删删除的记记录位置置，所有有被删除除记录的的位置都都用指针针链接起起来，构构成“空空闲记录录链表””。缺点：这这些被指指针链接接的记录录被称为为“被拴拴记录””，若被被删记录录被删掉掉，则指指向记录录的指针针称为““悬挂指指针”，，所指空空间称为为“垃圾圾”，也也就是别别人无法法使用而而又被空空闲着。。12/29/2022196.2.1.2.插入方方法可以根根据删删除的的方法法而定定，直直接插插入尾尾部，，或插插到空空位置置。6.2.2变长记记录实际应应用中中定长长记录录格式式文件件较多多,但但为了了增强强文件件的灵灵活性性,在在数据据库系系统中中，有有时需需要文文件中中的记记录是是变长长格式式。变长记记录的的表示示有字节串串形式式和定长形形式两种。。12/29/2022206.2.2.1变长记录录的字节节串表示示形式①尾标志法法把每个记记录看成成连续的的字节串串，然后后在每个个记录的的尾部附附加““记录录尾标志志符””（∧∧）,表表明记记录结束束。图6.2的的定长记记录文件件可以用用图6.4的的格式式表示。。②记录长度度法记录的开开始加一一个记录录长度的的字段来来实现，读取数据据时以此此作为记记录结束束与否的的标志。12/29/202221SnumCnumScoreCnumScoreCnumScore

S003160280340∧S001283

∧

S005480

∧

S004185260∧

S006375

∧

S002285

∧

图6.4变长长记录的的字节串串表示形形式12/29/202222字节串表示形形式缺点：每条记录长度度不一，被删删除后的位置置难于使用。。记录要增长很很难。“分槽式页结结构”：每块块的开始设置置一个“块首首部”，包含含以下信息：：块中的记录录数目，只想想块中自由空空间尾部的指指针，登记每每个记录近的的开始位置和和大小的信息息。12/29/202223图6.5分槽式页结构构12/29/2022246.2.2.2变变长长记记录录的的定定长长表表示示形形式式预留留空空间间技技术术取所所有有记记录录中中最最长长的的一一个个记记录录的的长长度度作作为为存存储储空空间间的的记记录录长长度度，，来来存存储储变变长长记记录录。。对对于于预预留留空空间间，，仍仍如如同同定定长长格格式式的的表表格格状状。。缺点点：：如如果果每每个个记记录录的的差差别别很很大大，，就就会会造造成成大大量量空空间间的的浪浪费费。。12/29/202225例如图6.4的字字节串表表示形式式可以用用图6.6的的预留留空间技技术实现现。该方方法一般般在大多多数记录录的长度度接近最最大长度度时才使使用，否否则使用用时空间间浪费很很大。SnumCnumScoreCnumScoreCnumScoreS003160280340S001283

∧∧∧S005480

∧∧∧S004185260∧∧S006375

∧∧∧S002285

∧∧∧图6.6变变长记录录的预留留空间表表示形式式12/29/202226指针技术术解决记录录长度差差很大的的方法，，省去过过多的空空间浪费费。每个定长长记录后后面增加加指针指指向在上上一方法法中可以以合并为为同一记记录的其其他记录录。被指向的的整体成成为溢出出块。12/29/202227图6.7变长记记录的的指针针表示示方式式12/29/202228图6.8固定块块和溢溢出块块结构构12/29/2022296.3文文件结构构文件中记录录的组织方方式有无序䖇件、、有序文件件、聚集文文件和HASH文件四种。。6.3.1无序文件件无序文件也也称为堆文件．无序文件件的操作比比较简单，，但查找效效率比较低低．无序文件的的删除操作作比较复杂杂，常用的的方法主要要有以下三三种：12/29/202230（１）首首先找到到被删记记录所在在的磁盘盘块，然然后读到到主存缓缓冲区，，在缓冲冲区中删删除记录录，最后后把缓冲冲区内容容写回到到磁盘文文件．（２）在在每个记记录的存存储空间间增加一一个标志志位，标标识记录录删除与与否，一一般该标标志常为为空。删删除一个个记录时时，将此此记录的的标志位位置“1”,以以后查查找记录录时跳过过有该标标志的记记录。（３）常常用于定定长记录录文件，，删除一一个记录录时，总总是把文文件末尾尾记录移移到被删删记录位位置。12/29/2022316.3.2有有序文件件有序文件件是指记记录按某某个（或或某些））域的值值的大小小顺序组组织，一一般最为为常用的的是按关关键字的的升序或或降序排排列，即即每个记记录增加加一个指指针字段段，根据据主键的的大小用用指针把把记录链链接起来来。文件中每每个记录录增加一一个指针针字段，，根据查查找键的的大小用用指针把把记录连连接起来来。12/29/202232图6.9顺序文件12/29/202233有序文文件操操作删除：只需需修改改指针针即可可。同同定长长记录录的方方法三三插入：1）定定位：：找到到要插插的位位置。。按查查找键键的顺顺序2）插插入：：在找找到记记录的的块内内，如如果自自由空空间有有空闲闲纪录录，那那么插插入；；若没没有就就插入入到溢溢出块块中。。在初始始的时时候，，可以以保持持无力力顺序序和查查找键键的顺顺序一一致，，以提提高速速度，，若多多次操操作后后变化化很大大，有有必要要重新新组织织一次次。12/29/2022346.3.3聚聚集文文件文件允允许一一个文文件有有多个个关系系的记记录组组成，，即记记录类类型文文件。。例：可可以把把有关关一个个人的的全部部记录录信息息放在在相邻邻的位位置，，按人人查找找信息息时就就会很很方便便。12/29/202235图6.10插入入一一个个记记录录后后的的顺顺序序文文件件12/29/202236图6.11聚集集文文件件例例子子12/29/2022376.3.4HASH文文件哈稀(HASH)文文件又称为散列文件，是一种支持持快速存取的的文件存储方方法。1．散列的概概念：设K是所有查查找键值的集集合，B是所所有桶地址的的集合。散列列函数h是从从K到B的函函数，它把每每个查找键值值映射到地址址集合中的地地址。其中每每个桶的大小小一定。查找键集K桶地址集B主文件记录12/29/202238检索：1）检索Ki的记录录，首先计计算h(Ki)在B集合中2）根据桶桶地址找到到桶3）桶内查查找特点：不同的查找找键值的记记录可能在在同一个桶桶内，找到到桶后仍然然有进行检检测。删除：找到到记录直接接删除即可可。12/29/2022392．散列函函数要满足两个个条件：1）使地址址分布均匀匀；2）地质分分布随机。。常用方法：：质数除余法法。缺点：函数数的设计，，若设计不不好会造成成很大的不不均匀性，，查找时间间的浪费。。12/29/2022403.散散列列碰碰撞撞问题题：由由于于同同所所存存储储的的记记录录数数是是一一定定的的，，再再插插入入操操作作时时很很容容易易发发生生溢溢出出。。原因因：一一是是桶桶的的数数目目少少；；二二是是散散列列的的均均匀匀性性不不好好。。解决决：：1））溢溢出出链链法法：：每每个个同同都都作作为为基基本本桶桶存存在在，，若溢溢出出系系统统提提供供一一处处同同连连接接在在基基本本桶桶后后面面。。2））开开放放式式散散列列法法：：只只存存在在基基本本桶桶，，若若溢溢出出就就插插入入其其他他空空闲闲的的桶桶。。有有两两种种选选择择方方式式：：1。。在在溢溢出出桶桶下下面面的的一一个个空空闲闲桶桶；；2。。采采用用二二次次散散列列的的方方法法。。12/29/202241图6.12散列结构的溢溢出链12/29/202242４.散散列方方法常用的的HASH方方法法有简单HASH方方法，，动态态HASH方方法法和可扩展展的HASH方方法．评价：散列列方法法必须须选取取恰当当的散散列函函数。。12/29/202243图6.13HASH桶桶目录录示例例12/29/2022441.简单单HASH方方法。。该方法采采用固定定个数的的HASH桶桶，即即把文件件划分为为N个个HASH桶桶，每个个HASH桶桶对应一一个磁盘盘块，每每个HASH桶有有一编号号。缺点：⑴只能有有效地支支持HASH域上上具有相相等比较的的数据操操作。⑵由于HASH桶桶的数量量一成不不变，当当文件记录录较少时时，影影响记录录的存取取效率。。12/29/2022452.动动态HASH方方法动态HASH方方法中中，HASH桶桶与与磁盘盘块一一一对对应。。HASH桶桶的的数量量不是是固定定的，，而是是随文文件记记录的的变化化而增增加或或减少少的。。12/29/202246图6.14动态HASH方方法结结构12/29/2022473.可扩展展的HASH方方法特点：：按照实实际需需要申申请或或释放放空间间。查找：：求出h(Ki)前i位值值m,沿桶桶地指指表位位置m处的的指针针到达达某个个同中中去找找记录录。插入入：：先查查找找到到相相应应的的桶桶，，若若有有空空闲闲空空间间直直接接插插入入；；12/29/202248图6.15可可扩扩展展的的HASH方方法法的的结结构构12/29/202249分裂桶：情况一：指向这个桶只只有一个指针针。增加i的的值，桶地址址表加倍，每每一项之分列列成相邻的两两项，但是指指向同一个桶桶。新申请的的桶，就得到到其中第二个个指针。情况二：指向这个桶有有多个指针。。则桶地址表表不用扩大只只要分裂桶可可以了。申请请新的桶空间间，原来的桶桶分出后一半半指针指向新新的桶，从新新分配分裂的的桶中的记录录。12/29/202250删除：查找到Ki的的记录，从桶桶内删除。删删除后如桶为为空，桶也删删除，还有可可能引起桶地地址的收缩。。显著优点：►数据量增长后后仍然保持由由原有的操作作和查询性能能►空间开销达到到最小12/29/2022516.4索索引技技术索引的的组织织方式式主要要有线性索索引和树形索索引两类。。6.4.1线线性索索引线性索索引可可分为为稠密索索引和稀疏索索引两种。。1.稠稠密索索引对主文文件中中每一一个查查找键键值都都建立立一个个索引引记号号优点:查找找、更更新数数据记记录方方便,存存取速速度快快缺点:索引项项多,索索引表表大,空空间代代价大大.12/29/2022522.稀稀疏索索引只对主主文件件中若若干查查找键键值建建立一一个索索引记记号。。在插入入操作作较多多的应应用中中采用用稀疏疏索引引方式式是不不太适适宜的的。12/29/202253K1K2K3…KnA(RK1)A(RK2)A(RK3)…A(RKn)图6.16.索索引结结构12/29/202254图6.17学生关系系索引方方式12/29/2022556.4.2B树1.平衡衡树的概概念m阶平衡衡树或者者为空，，或者满满足下面面条件：：每个节点点之多有有m棵子子树根节点或或为叶结结点，或或至少有有两棵子子树每个非叶叶结点至至少有[m/2]棵子子树根结点到到叶结点点的每一一条路径径都有同同样的长长度，即即叶结点点在同一一层次上上平衡树分分为B+树和B树12/29/202256图6.18多级索引12/29/202257B树在上述定义基基础上同时约约定：除叶结点之外外的所有其它它结点的索引引块最多可存存放m-1个主码码值和m个个地址指针针。其格式为为:叶结点上不包包含数据记录录本身，而是是由记录索引引项组成的记记录索引块，，每个记录索索引项包含含有主码值和和地址指针。。P0K1P1K2P2…Km-1Pm-112/29/202258一般假设，每每一个索引块块能容纳的索索引项数是个个奇数，且m=2d-1≥3;每一个记记录索引块能能容纳的记录录索引项也是是个奇数，且n=2e-1≥3。12/29/202259图6.19多级级索引的B树12/29/2022606.4.3B+树树1．．结结构构每个个结结点点之之多多有有m-1各各查查找找键键Ki，，m个个指指针针Pi;如如上上图图。。P1K1P2................Pn-1Kn-1Pn12/29/202261叶结结点点：：叶结结点点的的指指针针指指向向主主文文件件的的记记录录；；查查找找键键在在[m-1/2]————m-1之之间间；；叶叶结结点点最最后后的的指指针针指指向向下下一一叶叶结结点点。。非叶叶结结点点：：组成成多多级级稀稀疏疏索索引引，，指指针针在在[m/2]————m之之间间，，指指针针Pi指指向向所所有有查查找找键键大大于于等等于于Ki-1,小小于于Ki。。12/29/202262图20B+树树的模型型12/29/202263图6.21图6.19中中的Ｂ树的的Ｂ＋树12/29/202264查询：方法：先找第一个个大于k的的查找键值值，沿其左左面的指针针到达下一一层，以此此查找下去去。特点：查询的层数数相同为树树的高度，，因为都是是在叶结点点链接主文文件。12/29/2022652．修改改操作：：不引起索索引结点点分裂的的插入若以在叶叶结点出出现，直直接插入入记录；；否则，找找到第一一个大于于的查找找键值，，在其前前面插入入，其后后的都向向后移。。12/29/202266不引起索引结结点合并的删删除;查找到主文件件，删除记录录；若主文件中还还有同查找键键的记录不修修改索引；若无，从叶结结点中删除相相应的键值和和指针。引起分裂的插插入;插入叶结点后后，把多出来来的分裂出去去；修改父结结点，插入心心结点中的最最小值，同理理其父结点进进行修改。12/29/202267图6.22在在图6.21中插入入值为41数数据记录后的的Ｂ＋树12/29/202268引起起合合并并的的删删除除在删删除除叶叶结结点点后后，，引引起起结结点点不不符符合合定定义义，，将将被被删删除除，，若若父父结结点点中中有有也也将将删删除除，，导导致致合合并并的的发发生生。。B+树的的性性能能分分析析显著著优优点点：：►搜索索代代价价较较小小；；►解决决了了数数据据记记录录在在插插入入，，删删除除和和未未用用回回收收等等存存储储组组织织问问题题。。12/29/202269图6.23在在图图6.21中中删删除除主主码码值值为为26的的数数据据记记录录后后的的ＢＢ＋＋树树12/29/202270小结结数据据库库是是数数据据的的有有序序集集合合，，需需保保留留在在计计算算机机外外存存介介质质上上反反复复应应用用。。由由于于实实际际应应用用系系统统数数据据规规模模都都很很庞庞大大,加加之之经经常常要要从从数数据据集集合合中中检检索索需需要要的的数数据据，，所所以以数数据据组组织织的的方方式式，，数数据据的的定定位位方方式式，，以以及及数数据据的的维维护护策策略略的的选选取取十十分分重重要要。。12/29/202271在磁盘盘中,数据据库以以文件件形式式组织织。文文件组组织有有两种种方法法：一一种是是把记记录设设计成成定长长格式式,也也就是是每个个文件件只存存储某某一确确定长长度的的记录录；另另一种种是变变长格格式,使之之能存存放不不同长长度的的记录录。实实现变变长记记录的的技术术有多多种,包括括分槽槽式页页结构构、指指针方方法和和保留留空间间等方方法。。12/29/202272小结文件结构有有堆文件、、顺序文件件、散列文文件和聚集集文件等四四种。为了了提高查找找速度,可可以为文件件建立索引引或散列机机制。索引有稠稠密索引引、稀疏疏索引和和多级索索引等形形式。索索引顺序序文件组组织的主主要缺陷陷是随着着文件的的增大,性能会会下降。。为了克克服这个个缺陷,可以使使用B、、B+树树索引。。B+树树索引是是平衡树树,即从从树根到到树叶所所有路径径长度相相等。这这种查找找是简单单有效的的,但插插入和删删除比较较复杂。。B树索索引和B+树索索引类似似。12/29/202273小结B树的主要要优点在在于它去去除了查查找键值值存储中中的冗余余;主要要缺陷在在于整体体的复杂杂性以及及结点大大小给定定时减少少了扇出出。实际际应用中中,人们们总是更更愿意使使用B+树索引引。12/29/202274小结顺序文件件需要一一个索引引结构来来定位数数据。相相比之下下,基于于散列的的文件允允许通过过散列函函数直接接得到记记录所在在的桶地地址。静静态散列列所用的的桶地址址集合是是固定的的,不容容易适应应数据库库数据量量的快速速增长。。可扩充充散列结结构是一一种允许许修改散散列函数数的动态态散列技技术,在在数据库库增加或或缩减时时它可以以通过分分裂或合合并桶来来适应数数据库大大小的变变化。12/29/202275习题1.解释下列术语语:(1)文件件，记录，定定长记录文件件，变长记录录文件，跨块块记录，非跨跨块记录。(2)有有序索引，主主索引，稠密密索引，稀疏疏索引，多级级索引，B树，B+树2.试叙述计计算机系统的的物理存储介介质层次，并并说明每一种种介质的数据据访问速度。。12/29/202276习题3.比较有序文文件和无序序文件的优优缺点，什什么情况下下应该使用用有序文件件，什么情情况下应该该使用无序序文件。4.回答答下列问题题:(1)HASH文文件的桶溢溢出问题是是什么?如何解解决?(2)简单HASH文文件、动态态HASH文件件和可扩展展HASH文件件之间有什什么不同。。12/29/202277习题5.在散列文件件组织中，，是什么原原因引起桶桶溢出的?有什什么办法能能减少桶溢溢出的次数数?6.试举举一个数据据库应用例例子，说明明在表达变变长记录时时，有时指指针形式比比预留空间间方法好。。并作解释释。7.设查找键值值集为{2,3,5,7,11,17,19,23,29,31}。假假设初始时时B+树树为空，，按升序次次序插入键键值。就下下面三种情情况建立三三棵B+树:①4阶阶;②②6阶阶;③③8阶阶。。12/29/2022789、静夜四无无邻，荒居居旧业贫。。。12月-2212月-22Thursday,December29,202210、雨中黄叶叶树，灯下下白头人。。。13:55:0413:55:0413:5512/29/20221:55:04PM11、以我我独沈沈久，，愧君君相见见频。。。12月月-2213:55:0413:55Dec-2229-Dec-2212、故故人人江江海海别别，，几几度度隔隔山山川川。。。。13:55:0413:55:0413:55Thursday,December29,202213、乍见翻疑疑梦，相悲悲各问年。。。12月-2212月-2213:55:0413:55:04December29,202214、他乡生白发发，旧国见青青山。。29十二月月20221:55:04下午13:55:0412月-2215、比不不了得得就不不比，，得不不到的的就不不要。。。。十二月月221:55下下午午12月月-2213:55December29,202216、行动出成成果，工作作出财富。。。2022/12/2913:55:0413:55:0429December202217、做前，，能够环环视四周周；做时时，你只只能或者者最好沿沿着以脚脚为起点点的射线线向前。。。1:55:04下午午1:55下午午13:55:0412月-229、没没有有失失败败，，只只有有暂暂时时停停止止成成功功！！。。12月月-2212月月-22Thursday,December29,202210、很多事事情努力力了未必必有结果果，但是是不努力力却什么么改变也也没有。。。13:55:0413:55:0413:5