清华大学数据库access课件 第07章：存储结构和文件结构

数据库系统设计与原理第Ⅱ部分数据存储(第７章－第８章)2/6/20231第7章存储结构和文件结构讲课内容：主要介绍数据库系统的底层存储。包括存储介质、数据库文件的组织及结构、文件中记录的组织及结构。■物理存储介质■文件结构■磁盘■文件中记录的组织■RAID■数据字典的存储■第三级存储■本章总结2/6/20232DBMS总体结构回顾：磁盘存储器用户应用界面索引统计数据数据文件数据字典应用程序交互查询数据库模式应用程序目标码嵌入式DML预编译器DML编译器DDL解释器查询计算引擎事务管理器缓冲区管理器文件管理器查询处理器存储管理器数据库管理系统磁盘存储器权限及完整性管理器日志2/6/20233§7.1物理存储介质认识存储介质成本与速度随机存取顺序存取联机与脱机存储容量存储易失性高速缓冲存储器主存储器磁盘光盘磁带一级存储三级存储二级存储闪存2/6/20234§7.2磁盘基本术语转轴磁道扇区柱面盘片旋转读写头磁盘臂磁盘臂装置2/6/20235§7.2磁盘磁盘的物理特性磁道：盘片的表面被逻辑地划分为磁道。扇区：磁道又被逻辑地划分为扇区；扇区是从磁盘读出和写入数据的最小单位，通常大小为512字节。物理块：一个盘片的一条磁道内几个连续的扇区构成的序列称为物理块,一般也简称块；数据在磁盘和主存储器之间以块为单位传输。2/6/20236§7.2磁盘磁盘的块存取磁盘的I/O请求指定了要存取的磁盘地址，这个地址是以块号的形式提供的；数据库的文件管理器将块地址转换成硬件层的柱面号、盘面号和扇区号。数据库缓冲区数据库的文件管理器只负责将包含用户需要的数据所在的块缓存到主存储器里的数据库缓冲区，或者执行相反的操作；当新的数据从磁盘到缓存时，根据缓冲区替换策略来安排数据的位置。2/6/20237§7.2磁盘磁盘质量的度量标准容量大小存取时间：从发出读写请求到数据开始传输之间的时间；存取时间=寻道时间+旋转等待时间。数据传输率：从磁盘获得数据或者向磁盘存储数据的速率，即I/O吞吐量。可靠性性价比2/6/20238§7.3RAID早期的RAID经济因素是主要原因，因此：RedundantArraysofInexpensiveDisks；中文称为“廉价磁盘冗余阵列”。现在的RAID价格已经不是主要因素，而磁盘的性能(数据传输率)和可靠性是考虑的主要内容，因此：RedundantArraysofIndependentDisks；中文称为“独立磁盘冗余阵列”。未来的RAID？真正的百年存储……2/6/20239§7.3RAID如何提高磁盘的可靠性？引入冗余是解决可靠性问题的有效方法：存储一些通常情况下不需要的额外信息，这些信息可在发生磁盘故障时用于重建丢失的信息。实现冗余的方法实现冗余最简单、但最昂贵的方法：复制每一个磁盘，这种技术称为磁盘镜像或磁盘影像；一个逻辑上的磁盘由两个物理磁盘组成，并且每一个写操作都要在两个磁盘上执行。实现冗余的第二种方法是存储奇偶校验位。2/6/202310§7.3RAID如何提高磁盘的性能通过在多个磁盘上对数据进行拆分来提高传输率，原因是可以对多个磁盘并行存取。拆分的方法比特级拆分：数据拆分的最简单形式是将每个字节按比特位分开，存储到多个磁盘上。块级拆分：在块级拆分中，文件的块被拆分存储到多个磁盘上。如果有n个磁盘，则文件的第i块被存储到第(imodn)+1个磁盘上。2/6/202311§7.3RAIDRAID级别镜像+拆分+奇偶校验构成了RAID的不同方案2/6/202312§7.3RAID如何正确选择RAID级别由于RAID2和4被RAID3和5所包容，因此只需要在RAID0、1、3、5和6之间作出选择：RAID0：用于可容忍数据丢失的高性能应用；RAID1：用于存储类似数据库日志的应用，因为它提供了最好的写性能，同时又保证可靠性；RAID3：用于存储大量数据，并提供高的数据传输率；RAID5：用于存储大量数据，且随机读的效率很高。大多数数据库系统都属于这种情况；RAID6：提供比RAID5更高的可靠性，但很多RAID实现并不支持RAID6。2/6/202313§7.4第三级存储传统上，光盘和磁带主要用于备份和归档数据，因此它们一般都是离线(off-line)的存储介质；随着数据的不断膨胀，数据越来越多，我们称之为海量信息；在当前，我们主要用光盘塔或磁带库来存储海量信息，并且使它们变成近线(near-line)或在线(on-line)的存储介质。也就是说，跨过二级存储设备在内存和光盘或磁带之间直接传输数据。2/6/202314§7.5DBMS的文件管理器DBMS的物理存储综述了解数据库的存储结构就必须搞清楚：数据库的文件组织：一个数据库由几个OS文件构成？文件管理器：是DBMS的还是OS自身的？数据库文件自身的结构如何？为了能解析每条SQL语句，还必须进一步搞清楚：文件中记录的存储方式与结构如何？文件中记录的组织方式如何？2/6/202315§7.5DBMS的文件管理器数据库与文件管理在小型关系数据库系统中将各个关系存储在一个个独立的文件中。通常：文件中的记录都是定长的，文件结构简单；充分利用了作为OS一部分的文件系统的好处。大型数据库管理系统在文件管理方面并不直接依赖于操作系统。操作系统只分配给DBMS一个大的操作系统文件，所有关系都存储在这个大文件中。它的好处是：有利于提高系统的性能；空间的分配与管理简单、灵活，如簇集文件组织2/6/202316SQLSERVER2000的数据库文件组织在MSSQLServer2000中，一个数据库是由三个操作系统文件构成的，它们分别是：主数据文件：*.MDF次数据文件：*.NDF日志文件：*.LDF这些信息都存放在SYSFILES系统表中SQLSERVER2000的数据库文件管理上述数据库文件的管理是由SQLServer自己负责的，而不是依赖于Windows的文件系统。SQLServer有自己的文件管理器。§7.5DBMS的文件管理器2/6/202317DBMS一般不用OS的文件管理器，而是独立设计其数据库文件的存储结构，有自己的文件管理器。这有以下5个方面的原因：更多功能与附加信息：DBMS为了实现其功能，须在文件目录、文件描述块、物理块等部分附加一些信息；传统的文件系统是不提供这些信息的批处理与即席访问：传统的文件系统主要面向批处理；而在DBMS中，往往要求即席访问、动态修改：这就要求文件结构能适应数据的动态变化，提供快速访问路径。§7.5DBMS的文件管理器2/6/202318DBMS一般不用OS的文件管理器，而是独立设计其存储结构，有自己的文件管理器。这有以下5个方面的原因：数据共享与并发控制：传统的文件基本上是为某一用户或某类用户服务的，用途比较单一，共享的程度较低；数据库文件是供所有用户共享的，有些用途是不可预知的。这就要求数据库文件的结构能兼顾多方面的要求，提供多种访问路径，并在：并发控制故障恢复数据安全等§7.5DBMS的文件管理器2/6/202319DBMS一般不用OS的文件管理器，而是独立设计其存储结构，有自己的文件管理器。这有以下5个方面的原因：可移植性与实现的可能性：如果采用操作系统的文件管理器作为DBMS的物理层实现的基础，那么DBMS对操作系统的依赖性太大，不利于DBMS的移植；有些操作系统，如Unix，只提供字符流的存取功能，不提供各种文件结构和存取路径，这些只有靠DBMS自身来实现。§7.5DBMS的文件管理器2/6/202320DBMS一般不用OS的文件管理器，而是独立设计其存储结构，有自己的文件管理器。这有以下5个方面的原因：数据的稳定性与动态变化：传统的文件一旦建立以后，数据量是比较稳定的，而且一般只用于只读的应用；数据库文件的数据量变化较大，有些文件在数据模式刚定义时几乎是个空架子，随着应用的开发，数据也不断地增长：数据库文件的结构应能适应这样的变化；数据库中的数据常常要求是可读写的。§7.5DBMS的文件管理器2/6/202321DBMS中文件的管理粒度DBMS的高层(逻辑层和视图层)把数据看成是“记录”的集合；DBMS的底层(物理层)在处理I/O问题时，把数据看成是“页”的集合：具体地说，DBMS的文件管理器把数据看成是页的集合，并且提供分配/回收页和读/写页的命令；通常以磁盘块的大小作为页的大小，以便在一次磁盘I/O中就能够完成一页的读/写。数据库文件的页结构定长记录方式变长记录方式§7.5DBMS的文件管理器2/6/202322§7.6数据库文件的结构定长记录方式记录的移动引起记录RID变化。如果有外部引用指向被移动的记录，如索引，则……2/6/202323§7.6数据库文件的结构变长记录方式删除移动适应性2/6/202324SQLSERVER2000的页数据页是表的所有非文本数据和图形数据的存储结构；数据页的固定大小为8KB，即8192字节，其中8096字节用于存储数据，其余的96字节用于存储页结构信息；数据页由3个主要的部分组成：它们是……§7.6数据库文件的结构记录不能跨页存储，它的最大长度是8060字节！2/6/202325SQLSERVER2000的文件结构有一些特殊的元数据页§7.6数据库文件的结构2/6/202326定长记录首先考虑由有关student记录组成的一个文件。该文件中的记录定义如下：typestudent=record

student_number:char(10);

student_name:char(8);

department_name:char(22);end假设每个字符占一个字节，那么一个student记录占40个字节。§7.7记录的存储与维护2/6/202327定长记录的存储用文件的头40个字节存储第一个记录，接着的40个字节存储第二个记录，依次类推……这种结构的问题是：删除一条记录时要么填充被删空间要么标记被删记录；除非块的大小恰好是40的倍数，否则记录会跨块存储。§7.7记录的存储与维护2/6/202328定长记录的维护方案一：删除一条记录时，顺序移动其后的所有记录；插入一条记录则始终在文件的尾部进行。方案二：删除一条记录时，移动最后一条记录到此位置；而插入一条记录则始终在文件的尾部进行。§7.7记录的存储与维护2/6/202329定长记录的维护方案三：删除一条记录时，并不着急移动记录，而是将其加入空闲记录列表；当要插入记录时，使用空闲列表中的记录空间；若没有空闲空间就插入到文件的尾部。§7.7记录的存储与维护额外的结构：文件头指针列2/6/202330变长记录造成变长记录的原因：多种记录类型在一个文件中存储；记录类型允许一个或多个字段是变长的；记录类型允许可重复的字段。例如：typecourse_list=record

teacher_name:char(22);

course_info:array[1..∞]ofrecordcourse_name:char(30);

course_capacity:int;endend

定长部分变长部分§7.7记录的存储与维护2/6/202331变长记录的存储方法之一：字节流表示法在每个记录的末尾都附加特殊的记录终止符⊥；或者是在每个记录的开头存储该记录的长度。问题：磁盘碎片删除一条记录？记录变长了？记录变短了？方案：移动记录的代价§7.7记录的存储与维护2/6/202332变长记录的存储方法之二：分槽的页结构用于物理块内部的记录组织；块头部分：块中记录个数；块中空闲空间的末尾地址；描述块中每个记录的大小和位置的数组；块尾部分：实际记录从块的尾部开始连续存储；块中部分：块中空闲空间是连续的。§7.7记录的存储与维护分槽页结构的实例？2/6/202333变长记录的存储方法之二：分槽页结构的维护删除一条记录：它所占用的空间被释放；块中在此之前的记录都要移动；而空闲空间还是集中在块中间。插入一条记录：在块中空闲空间的尾部给这条记录分配空间。记录的增长和缩短：该条记录的末尾地址不变；在此记录之前的记录都要移动；块的大小有限制，移动记录的代价并不高。§7.7记录的存储与维护还要修改？2/6/202334变长记录的存储方法之三：定长表示法用一个或多个定长记录来表示一个变长记录。由于所采用的策略不同，定长表示法又分为以下几类：方法之三(1)--保留空间法方法之三(2)--指针法方法之三(3)--锚块-溢出块表示法定长表示法在实际的DBMS当中很少使用，为什么？但至少可以为我们解决其他问题开拓思路！§7.7记录的存储与维护2/6/202335变长记录的存储方法之三(1)：保留空间法假设所有的变长记录都不会超过某个长度，就为每个记录都分配这样长度的空间；缺陷：假设不合理；浪费大量存储空间§7.7记录的存储与维护2/6/202336变长记录的存储方法之三(2)：指针法用一系列通过指针链接起来的定长记录来表示一个变长记录；优点：与定长记录类似，变长记录是一个链表；缺点：引入额外结构，浪费存储空间。§7.7记录的存储与维护2/6/202337变长记录的存储方法之三(3)：锚块-溢出块表示法指针法的变形；文件使用两种不同的物理块：锚块：包含记录的定长部分和变长部分的第一个分量的块；溢出块：包含记录的变长部分除第一个分量以外的其他分量的块。§7.7记录的存储与维护2/6/202338记录的存储结构定长记录记录的字段数是固定的每个字段都是定长的应存放在数据字典里偏移量§7.7记录的存储与维护2/6/202339记录的存储结构变长记录记录的字段数是固定的某些字段是变长的基地址分槽页结构的偏移量1、如何定位某个字段？2、如何处理空值NULL？§7.7记录的存储与维护2/6/202340举例SQLServer的数据行，即记录的结构定长记录与变长记录中字段组织方式的结合§7.7记录的存储与维护2/6/202341SQLServer的数据行结构§7.7记录的存储与维护2/6/202342SQLServer的数据行结构状态位A，即TagA：位0：版本信息，在SQLServer2000中该位总是0。位1到位3：作为一个3位的值对待0表示该行是一个基本的记录；1表示该行是一个转向记录；2表示该行是一个转向存根；3表示该行是一个索引记录；4表示该行是一块碎片；5表示该行是一个幽灵索引记录；6表示该行是一个幽灵数据记录。§7.7记录的存储与维护2/6/202343SQLServer的数据行结构状态位A，即TagA：位4：表示NULL位图的存在性；在SQLServer2000中，即使任何列都不允许NULL值，NULL位图也总要出现；位4的值总为1；NULL位图能有效地解决空值、空串的问题。位5：表示行中是否存在变长列。位6和位7：在SQLServer2000中未被使用。§7.7记录的存储与维护2/6/202344SQLServer的数据行结构列偏移数组：一个两字节的条目，表示变长列在行中结束的位置。在行的定长或变长数据块内，SQLServer按照创建表时定义的列顺序来存储数据；这个表的行的定长数据部分包括Col1的数据，后跟Col2和Col4的数据；行的变长数据部分包括Col3的数据，后跟Col5的数据。§7.7记录的存储与维护2/6/202345§7.8文件中记录的组织在文件中组织记录的常用方法堆积的方法排顺的方法哈希的方法簇集的方法层次组织法(B树类文件组织，下章索引介绍)堆文件组织一条记录可以放在文件中的任何地方，只要那个地方有空间存放这条记录；记录是没有顺序的，是堆积起来的。2/6/202346§7.8文件中记录的组织散列文件组织对文件中每个记录的同一属性或属性集需要计算一个散列(Hash)函数；散列函数的结果确定了记录应该存储到文件的哪个物理块中；记录虽然没有顺序，但是有去向的！2/6/202347§7.8文件中记录的组织顺序文件组织根据搜索码值的顺序来逻辑存储记录；搜索码是用于在文件中查找记录的属性或属性集，与码的概念完全不同！为了快速地按搜索码获取记录，通过指针把记录链接起来，每个记录的指针都指向在搜索码顺序上的下一个记录；同时，为了减少顺序文件处理中物理块的访问次数，在物理上也按搜索码值的顺序存储记录，或尽可能地按照搜索码值的顺序来物理存储。2/6/202348§7.8文件中记录的组织顺序文件组织顺序文件组织的好处：结构清晰，容易理解；对特定的查询能快速处理。顺序文件组织的问题：插入和删除记录后，首先要保证记录按搜索码的顺序重新链接起来，但是维护记录的物理顺序则将十分困难；如果靠移动记录的方式来维护记录在物理上的顺序，则代价十分昂贵！2/6/202349§7.8文件中记录的组织顺序文件的维护删除记录：用指针链表来管理删除。插入记录：首先定位要插入的记录按搜索码值排序时它前面那条记录；如果该记录所在的物理块内有空闲空间，就在这个块中插入该记录；否则，将插入到溢出块中；如果溢出块中的记录不多，则这种方式还有效；但记录的搜索码顺序和物理顺序之间的一致性……这时，对记录的顺序处理将明显变得效率低下（随机I/O），需要对文件进行重组：时机和代价。2/6/202350SQLSERVER行偏移数组指出了页中各记录的逻辑顺序；记录的物理顺序与其逻辑顺序不必完全一致！§7.8文件中记录的组织页头：96字节数据行，即记录176行偏移数组095Mianus(96)Downtown(136)Brighton(176)Downtown(216)13621696

3210页号：010槽号在物理上也按搜索码顺序存储记录，或尽可能地按照搜索码顺序物理存储：①不同的页之间：009（A）、010（B-M）、011（N-Z）；②同一页之间；③溢出页：012(A)。在SQLServer中搜索码链表就是行偏移数组2/6/202351§7.8文件中记录的组织行偏移数组可以表示行的逻辑顺序，与行的物理顺序不同；举例：sp_helpstudentselect*fromstudentDBCCTRACEON(3604)GODBCCPAGE(DB_Teaching,1,132,1)GO2/6/202352§7.8文件中记录的组织数据行在页中的真实情况2/6/202353§7.8文件中记录的组织簇集文件组织问题的提出：假设有两个关系course和selecting，对于它们的自然连接运算，用SQL表达如下：selectstudent_number,course_name,course_locationfromcourse,selectingwherecourse.course_name=selecting.course_name2/6/202354§7.8文件中记录的组织簇集文件组织问题的解决：把相关记录放在一个块(或临近块)中存储，一次读块操作就取得所有相关记录；减少了磁盘I/O次数，提高了连接的性能。2/6/202355§7.8文件中记录的组织簇集文件组织簇集的定义：把有关记录按簇集键值集中在一个物理块内或物理上相邻的区域内，以提高某些查询的速度。簇集的缺点：如果改用其他属性或属性集做簇集键，将引起所有记录的移动；如果一个记录的簇集键值修改了，则这个记录也要做相应的移动；如果不是针对簇集设计的查询，而