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

1、2022-3-81数据库系统设计与原理数据库系统设计与原理2022-3-82第第7 7章存储结构和文件结构章存储结构和文件结构主要介绍数据库系统的底层存储。包括存储介质、数据库文件的组织及结构、文件中记录的组织及结构。物理存储介质物理存储介质文件结构文件结构磁盘磁盘文件中记录的组织文件中记录的组织RAIDRAID数据字典的存储数据字典的存储第三级存储第三级存储本章总结本章总结2022-3-83DBMSDBMS总体结构回顾：磁盘存储器总体结构回顾：磁盘存储器应用界面应用界面索引索引统计数据统计数据数据文件数据文件数据字典数据字典应用程序应用程序交互查询交互查询数据库模式数据库模式嵌入式嵌入式DM

2、LDML预编译器预编译器DMLDML编译器编译器DDLDDL解释器解释器查询计算引擎查询计算引擎事务管理器事务管理器缓冲区管理器缓冲区管理器文件管理器文件管理器日志日志2022-3-847.17.1物理存储介质物理存储介质认识存储介质成本与速度随机存取顺序存取联机与脱机存储容量存储易失性高速缓冲存储器主存储器磁盘光盘磁带一级存储一级存储三级存储三级存储二级存储二级存储闪存2022-3-857.27.2磁盘磁盘基本术语转轴磁道扇区柱面盘片旋转读写头磁盘臂磁盘臂装置2022-3-867.27.2磁盘磁盘磁盘的物理特性 磁道： 盘片的表面被逻辑地划分为磁道。 扇区： 磁道又被逻辑地划分为扇区； 扇区

3、是从磁盘读出和写入数据的最小单位，通常大小为512字节。 物理块： 一个盘片的一条磁道内几个连续的扇区构成的序列称为物理块,一般也简称块； 数据在磁盘和主存储器之间以块为单位传输。2022-3-877.27.2磁盘磁盘磁盘的块存取 磁盘的I/O请求指定了要存取的磁盘地址，这个地址是以块号的形式提供的； 数据库的文件管理器将块地址转换成硬件层的柱面号、盘面号和扇区号。数据库缓冲区 数据库的文件管理器只负责将包含用户需要的数据所在的块缓存到主存储器里的数据库缓冲区，或者执行相反的操作； 当新的数据从磁盘到缓存时，根据缓冲区替换策略来安排数据的位置。2022-3-887.27.2磁盘磁盘磁盘质量的度

4、量标准 容量大小 存取时间： 从发出读写请求到数据开始传输之间的时间； 存取时间 = 寻道时间 + 旋转等待时间。 数据传输率： 从磁盘获得数据或者向磁盘存储数据的速率，即I/O吞吐量。 可靠性 性价比2022-3-897.3RAID7.3RAID早期的RAID 经济因素是主要原因，因此： Redundant Arrays of Inexpensive Disks； 中文称为“廉价磁盘冗余阵列”。现在的RAID 价格已经不是主要因素，而磁盘的性能(数据传输率)和可靠性是考虑的主要内容，因此： Redundant Arrays of Independent Disks； 中文称为“独立磁盘冗余阵

5、列”。未来的RAID？真正的百年存储2022-3-8107.3RAID7.3RAID如何提高磁盘的可靠性？ 引入冗余是解决可靠性问题的有效方法： 存储一些通常情况下不需要的额外信息，这些信息可在发生磁盘故障时用于重建丢失的信息。实现冗余的方法 实现冗余最简单、但最昂贵的方法： 复制每一个磁盘，这种技术称为磁盘镜像或磁盘影像； 一个逻辑上的磁盘由两个物理磁盘组成，并且每一个写操作都要在两个磁盘上执行。 实现冗余的第二种方法是存储奇偶校验位。2022-3-8117.3RAID7.3RAID如何提高磁盘的性能 通过在多个磁盘上对数据进行拆分来提高传输率，原因是可以对多个磁盘并行存取。拆分的方法 比特

6、级拆分： 数据拆分的最简单形式是将每个字节按比特位分开，存储到多个磁盘上。 块级拆分： 在块级拆分中，文件的块被拆分存储到多个磁盘上。如果有n个磁盘，则文件的第i块被存储到第(i mod n) + 1个磁盘上。2022-3-8127.3RAID7.3RAIDRAID级别 镜像+拆分+奇偶校验构成了RAID的不同方案2022-3-8137.3RAID7.3RAID如何正确选择RAID级别 由于RAID2和4被RAID3和5所包容，因此只需要在RAID0、1、3、5和6之间作出选择： RAID0：用于可容忍数据丢失的高性能应用； RAID1：用于存储类似数据库日志的应用，因为它提供了最好的写性能，

7、同时又保证可靠性； RAID3：用于存储大量数据，并提供高的数据传输率； RAID5：用于存储大量数据，且随机读的效率很高。大多数数据库系统都属于这种情况； RAID6：提供比RAID5更高的可靠性，但很多RAID实现并不支持RAID6。2022-3-8147.47.4第三级存储第三级存储传统上，光盘和磁带主要用于备份和归档数据，因此它们一般都是离线(off-line)的存储介质；随着数据的不断膨胀，数据越来越多，我们称之为海量信息；在当前，我们主要用光盘塔或磁带库来存储海量信息，并且使它们变成近线(near-line)或在线(on-line)的存储介质。也就是说，跨过二级存储设备在内存和光盘

8、或磁带之间直接传输数据。2022-3-8157.5DBMS7.5DBMS的文件管理器的文件管理器DBMS的物理存储综述了解数据库的存储结构就必须搞清楚： 数据库的文件组织：一个数据库由几个OS文件构成？ 文件管理器：是DBMS的还是OS自身的？ 数据库文件自身的结构如何？为了能解析每条SQL语句，还必须进一步搞清楚： 文件中记录的存储方式与结构如何？ 文件中记录的组织方式如何？2022-3-8167.5DBMS7.5DBMS的文件管理器的文件管理器数据库与文件管理 在小型关系数据库系统中将各个关系存储在一个个独立的文件中。通常： 文件中的记录都是定长的，文件结构简单； 充分利用了作为OS一部分

9、的文件系统的好处。 大型数据库管理系统在文件管理方面并不直接依赖于操作系统。操作系统只分配给DBMS一个大的操作系统文件，所有关系都存储在这个大文件中。它的好处是： 有利于提高系统的性能； 空间的分配与管理简单、灵活，如簇集文件组织2022-3-817SQL SERVER 2000的数据库文件组织 在MS SQL Server 2000中，一个数据库是由三个操作系统文件构成的，它们分别是： 主数据文件：*.MDF 次数据文件：*.NDF 日志文件：*.LDF这些信息都存放在SYSFILES系统表中SQL SERVER 2000的数据库文件管理 上述数据库文件的管理是由SQL Server自己负

10、责的，而不是依赖于Windows的文件系统。 SQL Server有自己的文件管理器。7.5DBMS7.5DBMS的文件管理器的文件管理器2022-3-818DBMS一般不用OS的文件管理器，而是独立设计其数据库文件的存储结构，有自己的文件管理器。这有以下5个方面的原因：1.更多功能与附加信息：DBMS为了实现其功能，须在文件目录、文件描述块、物理块等部分附加一些信息；传统的文件系统是不提供这些信息的2.批处理与即席访问：传统的文件系统主要面向批处理；而在DBMS中，往往要求即席访问、动态修改：这就要求文件结构能适应数据的动态变化，提供快速访问路径。7.5DBMS7.5DBMS的文件管理器的文

11、件管理器2022-3-819DBMS一般不用OS的文件管理器，而是独立设计其存储结构，有自己的文件管理器。这有以下5个方面的原因：3. 数据共享与并发控制：传统的文件基本上是为某一用户或某类用户服务的，用途比较单一，共享的程度较低；数据库文件是供所有用户共享的，有些用途是不可预知的。这就要求数据库文件的结构能兼顾多方面的要求，提供多种访问路径，并在：并发控制故障恢复数据安全等7.5DBMS7.5DBMS的文件管理器的文件管理器2022-3-820DBMS一般不用OS的文件管理器，而是独立设计其存储结构，有自己的文件管理器。这有以下5个方面的原因：4. 可移植性与实现的可能性：如果采用操作系统的

12、文件管理器作为DBMS的物理层实现的基础，那么DBMS对操作系统的依赖性太大，不利于DBMS的移植；有些操作系统，如Unix，只提供字符流的存取功能，不提供各种文件结构和存取路径，这些只有靠DBMS自身来实现。7.5DBMS7.5DBMS的文件管理器的文件管理器2022-3-821DBMS一般不用OS的文件管理器，而是独立设计其存储结构，有自己的文件管理器。这有以下5个方面的原因：5. 数据的稳定性与动态变化：传统的文件一旦建立以后，数据量是比较稳定的，而且一般只用于只读的应用；数据库文件的数据量变化较大，有些文件在数据模式刚定义时几乎是个空架子，随着应用的开发，数据也不断地增长：数据库文件的

13、结构应能适应这样的变化；数据库中的数据常常要求是可读写的。7.5DBMS7.5DBMS的文件管理器的文件管理器2022-3-822DBMS中文件的管理粒度 DBMS的高层(逻辑层和视图层)把数据看成是“记录”的集合； DBMS的底层(物理层)在处理I/O问题时，把数据看成是“页”的集合： 具体地说，DBMS的文件管理器把数据看成是页的集合，并且提供分配/回收页和读/写页的命令； 通常以磁盘块的大小作为页的大小，以便在一次磁盘I/O中就能够完成一页的读/写。数据库文件的页结构 定长记录方式 变长记录方式7.5DBMS7.5DBMS的文件管理器的文件管理器2022-3-8237.67.6数据库文件

14、的结构数据库文件的结构定长记录方式 记录的移动引起记录RID变化。如果有外部引用指向被移动的记录，如索引，则 2022-3-8247.67.6数据库文件的结构数据库文件的结构变长记录方式 删除 移动 适应性2022-3-825SQL SERVER 2000的页 数据页是表的所有非文本数据和图形数据的存储结构； 数据页的固定大小为8KB，即8192字节，其中8096字节用于存储数据，其余的96字节用于存储页结构信息； 数据页由3个主要的部分组成：它们是7.67.6数据库文件的结构数据库文件的结构记录不能跨页存储，它的最大长度是8060字节！2022-3-826SQL SERVER 2000的文件

15、结构 有一些特殊的元数据页7.67.6数据库文件的结构数据库文件的结构2022-3-827定长记录 首先考虑由有关student记录组成的一个文件。该文件中的记录定义如下： type student = record student_number: char(10); student_name: char(8); department_name: char(22); end 假设每个字符占一个字节，那么一个student记录占40个字节。 7.77.7记录的存储与维护记录的存储与维护2022-3-828定长记录的存储 用文件的头40个字节存储第一个记录，接着的40个字节存储第二个记录，依次类推

16、 这种结构的问题是：删除一条记录时 要么填充被删空间 要么标记被删记录；除非块的大小恰好 是40的倍数，否则 记录会跨块存储。7.77.7记录的存储与维护记录的存储与维护2022-3-829定长记录的维护 方案一： 删除一条记录时，顺序移动其后的所有记录； 插入一条记录则始终在文件的尾部进行。 方案二： 删除一条记录时，移动最后一条记录到此位置； 而插入一条记录则始终在文件的尾部进行。7.77.7记录的存储与维护记录的存储与维护2022-3-830定长记录的维护 方案三： 删除一条记录时，并不着急移动记录，而是将其加入空闲记录列表； 当要插入记录时，使用空闲列表中的记录空间；若没有空闲空间就插

17、入到文件的尾部。7.77.7记录的存储与维护记录的存储与维护额外的结构：文件头指针列2022-3-831变长记录 造成变长记录的原因： 多种记录类型在一个文件中存储； 记录类型允许一个或多个字段是变长的； 记录类型允许可重复的字段。 例如： type course_list = record teacher_name: char(22); course_info: array1. of record course_name: char(30); course_capacity: int; end end 定长部分变长部分7.77.7记录的存储与维护记录的存储与维护2022-3-832变长记录的

18、存储 方法之一：字节流表示法 在每个记录的末尾都附加特殊的记录终止符； 或者是在每个记录的开头存储该记录的长度。问题：磁盘碎片删除一条记录？记录变长了？记录变短了？方案：移动记录的代价7.77.7记录的存储与维护记录的存储与维护2022-3-833变长记录的存储 方法之二：分槽的页结构 用于物理块内部的记录组织； 块头部分：块中记录个数；块中空闲空间的末尾地址；描述块中每个记录的大小和位置的数组； 块尾部分：实际记录从块的尾部开始连续存储； 块中部分：块中空闲空间是连续的。7.77.7记录的存储与维护记录的存储与维护分槽页结构的实例？2022-3-834变长记录的存储方法之二：分槽页结构的维护

19、 删除一条记录：它所占用的空间被释放；块中在此之前的记录都要移动；而空闲空间还是集中在块中间。 插入一条记录：在块中空闲空间的尾部给这条记录分配空间。 记录的增长和缩短：该条记录的末尾地址不变；在此记录之前的记录都要移动；块的大小有限制，移动记录的代价并不高。7.77.7记录的存储与维护记录的存储与维护还要修改？2022-3-835变长记录的存储 方法之三：定长表示法 用一个或多个定长记录来表示一个变长记录。 由于所采用的策略不同，定长表示法又分为以下几类： 方法之三(1)-保留空间法 方法之三(2)-指针法 方法之三(3)-锚块-溢出块表示法 定长表示法在实际的DBMS当中很少使用，为什么？

20、但至少可以为我们解决其他问题开拓思路！7.77.7记录的存储与维护记录的存储与维护2022-3-836变长记录的存储 方法之三(1)：保留空间法 假设所有的变长记录都不会超过某个长度，就为每个记录都分配这样长度的空间； 缺陷：假设不合理；浪费大量存储空间7.77.7记录的存储与维护记录的存储与维护2022-3-837变长记录的存储 方法之三(2)：指针法 用一系列通过指针链接起来的定长记录来表示一个变长记录； 优点：与定长记录类似，变长记录是一个链表； 缺点：引入额外结构，浪费存储空间。7.77.7记录的存储与维护记录的存储与维护2022-3-838变长记录的存储 方法之三(3)：锚块-溢出块

21、表示法 指针法的变形；文件使用两种不同的物理块：锚块：包含记录的定长部分和变长部分的第一个分量的块；溢出块：包含记录的变长部分除第一个分量以外的其他分量的块。7.77.7记录的存储与维护记录的存储与维护2022-3-839记录的存储结构 定长记录 记录的字段数是固定的 每个字段都是定长的应存放在数据字典里偏移量7.77.7记录的存储与维护记录的存储与维护2022-3-840记录的存储结构 变长记录 记录的字段数是固定的 某些字段是变长的基地址基地址分槽页分槽页结构的结构的偏移量偏移量1、如何定位某个字段？2、如何处理空值NULL？7.77.7记录的存储与维护记录的存储与维护2022-3-841

22、举例 SQL Server的数据行，即记录的结构 定长记录与变长记录中字段组织方式的结合7.77.7记录的存储与维护记录的存储与维护2022-3-842SQL Server的数据行结构7.77.7记录的存储与维护记录的存储与维护2022-3-843SQL Server的数据行结构 状态位A，即TagA： 位位0 0：版本信息，在SQL Server 2000中该位总是0。 位位1 1到位到位3 3：作为一个3位的值对待0表示该行是一个基本的记录；1表示该行是一个转向记录；2表示该行是一个转向存根；3表示该行是一个索引记录；4表示该行是一块碎片；5表示该行是一个幽灵索引记录；6表示该行是一个幽灵

23、数据记录。7.77.7记录的存储与维护记录的存储与维护2022-3-844SQL Server的数据行结构 状态位A，即TagA： 位位4 4：表示NULL位图的存在性；在SQL Server 2000中，即使任何列都不允许NULL值，NULL位图也总要出现；位4的值总为1；NULL位图能有效地解决空值、空串的问题。 位位5 5：表示行中是否存在变长列。 位位6 6和位和位7 7：在SQL Server 2000中未被使用。7.77.7记录的存储与维护记录的存储与维护2022-3-845SQL Server的数据行结构 列偏移数组： 一个两字节的条目，表示变长列在行中结束的位置。 在行的定长或

24、变长数据块内，SQL Server按照创建表时定义的列顺序来存储数据；这个表的行的定长数据部分包括Col1的数据，后跟Col2和Col4的数据；行的变长数据部分包括Col3的数据，后跟Col5的数据。7.77.7记录的存储与维护记录的存储与维护2022-3-8467.87.8文件中记录的组织文件中记录的组织 在文件中组织记录的常用方法 堆积的方法 排顺的方法 哈希的方法 簇集的方法 层次组织法(B树类文件组织，下章索引介绍)堆文件组织 一条记录可以放在文件中的任何地方，只要那个地方有空间存放这条记录； 记录是没有顺序的，是堆积起来的。2022-3-8477.87.8文件中记录的组织文件中记录的

25、组织 散列文件组织 对文件中每个记录的同一属性或属性集需要计算一个散列(Hash)函数； 散列函数的结果确定了记录应该存储到文件的哪个物理块中； 记录虽然没有顺序，但是有去向的！2022-3-8487.87.8文件中记录的组织文件中记录的组织 顺序文件组织 根据搜索码值的顺序来逻辑存储记录； 搜索码是用于在文件中查找记录的属性或属性集，与码的概念完全不同！ 为了快速地按搜索码获取记录，通过指针把记录链接起来，每个记录的指针都指向在搜索码顺序上的下一个记录； 同时，为了减少顺序文件处理中物理块的访问次数，在物理上也按搜索码值的顺序存储记录，或尽可能地按照搜索码值的顺序来物理存储。2022-3-8

26、497.87.8文件中记录的组织文件中记录的组织 顺序文件组织 顺序文件组织的好处： 结构清晰，容易理解； 对特定的查询能快速处理。 顺序文件组织的问题： 插入和删除记录后，首先要保证记录按搜索码的顺序重新链接起来，但是维护记录的物理顺序则将十分困难； 如果靠移动记录的方式来维护记录在物理上的顺序，则代价十分昂贵！2022-3-8507.87.8文件中记录的组织文件中记录的组织 顺序文件的维护 删除记录： 用指针链表来管理删除。 插入记录： 首先定位要插入的记录按搜索码值排序时它前面那条记录； 如果该记录所在的物理块内有空闲空间，就在这个块中插入该记录；否则，将插入到溢出块中；如果溢出块中的记

27、录不多，则这种方式还有效；但记录的搜索码顺序和物理顺序之间的一致性这时，对记录的顺序处理将明显变得效率低下（随机I/O），需要对文件进行重组：时机和代价。2022-3-851SQL SERVER 行 偏 移 数组 指 出 了页 中 各 记录 的 逻 辑顺序； 记 录 的 物理 顺 序 与其 逻 辑 顺序 不 必 完全一致！7.87.8文件中记录的组织文件中记录的组织 页头：96字节数据行，即记录176行偏移数组095Mianus (96)Downtown(136)Brighton(176)Downtown(216)13621696 3 2 1 0页号：010槽号在物理上也按搜索码顺序存储记录，

28、或尽可能地按照搜索码顺序物理存储：不同的页之间：009（A）、010（B-M）、011（N-Z）；同一页之间；溢出页：012(A)。在SQL Server中搜索码链表就是行偏移数组2022-3-8527.87.8文件中记录的组织文件中记录的组织行偏移数组可以表示行的逻辑顺序，与行的物理顺序不同；举例：sp_help studentselect * from studentDBCC TRACEON(3604) GO DBCC PAGE(DB_Teaching,1,132,1) GO2022-3-8537.87.8文件中记录的组织文件中记录的组织数据行在页中的真实情况2022-3-8547.87.

29、8文件中记录的组织文件中记录的组织 簇集文件组织 问题的提出： 假设有两个关系course和selecting，对于它们的自然连接运算，用SQL表达如下：select student_number, course_name, course_location from course, selecting where course.course_name = selecting.course_name2022-3-8557.87.8文件中记录的组织文件中记录的组织 簇集文件组织 问题的解决： 把相关记录放在一个块(或临近块)中存储，一次读块操作就取得所有相关记录； 减少了磁盘I/O次数，提高了连接的性能。 2022-3-8567.87.8文件中记录的组织文件中记录的组织 簇集文件组织 簇集的定义： 把有关记录按簇集键值集中在一个物理块内或物理上相邻的区域内，以提高某些查询的速度。 簇集的缺点： 如果改用其他属性或属性集做簇集键，将引起所有记录的移动； 如果一个记录的簇集键值修改了，则这个记录也要做相应的移动； 如果不是针对簇集