数据元素的表课件

《数据元素的表课件》由会员分享，可在线阅读，更多相关《数据元素的表课件（106页珍藏版）》请在金锄头文库上搜索。

1、Database System Implementation金培权（金培权（）第第4 4章章 数据元素的表示数据元素的表示2Database System Implementation金培权（）金培权（）主要内容主要内容n数据项的表示（数据项的表示（Data Items）n记录的表示（记录的表示（Records）n记录在块中的组织（记录在块中的组织（Block）n记录的修改记录的修改n块在文件中的组织块在文件中的组织n缓冲区管理缓冲区管理3Database System Implementation金培权（）金培权（）数据元素的表示层次数据元素的表示层次数据项记录块文件属性值的物理组织元组的物

2、理组织记录的物理存放文件由磁盘块构成4Database System Implementation金培权（）金培权（）一、数据项的表示一、数据项的表示n数据项数据项字节序列字节序列表示关系数据库中元组的属性值表示关系数据库中元组的属性值5Database System Implementation金培权（）金培权（）1 1、数据项表示的内容、数据项表示的内容n表示什么？表示什么？姓名姓名年龄年龄出生日期出生日期照片照片n用什么表示？用什么表示？Bytes6Database System Implementation金培权（）金培权（）2 2、数据项表示方法：、数据项表示方法：SQLSQL数据类

3、型数据类型nInteger (short)2 bytes例如，例如，35 表示为表示为nReal，Float4 bytes （32 bits）N bits表示小数，表示小数，M bits表示指数表示指数 7Database System Implementation金培权（）金培权（）2 2、数据项表示方法：、数据项表示方法：SQLSQL数据类型数据类型nChar(n) 或或 Character(n) 定长字符串定长字符串小于小于n时使用特殊填充符时使用特殊填充符例如，若属性类型为例如，若属性类型为Char(5)，则属性值，则属性值cat 表示为表示为 nVarchar(n) 变长字符串变长字

4、符串NULL终止符，例终止符，例 Varchar(5)带长度带长度 定长表示，定长表示，n+1 bytesVarchar(4):cta ctacta3cta 8Database System Implementation金培权（）金培权（）2 2、数据项表示方法：、数据项表示方法：SQLSQL数据类型数据类型nBooleanTRUEFALSEn枚举类型枚举类型RED,GREEN,YELLOW整数表示整数表示RED 1，GREEN 2，YELLOW 3若用两个字若用两个字节的短整型来表示，的短整型来表示，则可以表示可以表示 216 个个不同不同值1111 11110000 00009Databa

5、se System Implementation金培权（）金培权（）2 2、数据项表示方法：、数据项表示方法：SQLSQL数据类型数据类型nDate10字符字符(SQL92)：YYYY-MM-DD字符串表示字符串表示8字符：字符：YYYYMMDD7字符：字符：YYYYDDD, NOT YYMMDD！Integer，自，自1900-01-01以来的天数以来的天数nTime8字符字符(SQL92)：HH:NN:SS 整数秒整数秒Varchar(n)：HH:NN:SS.FF带小数秒带小数秒Integer，自，自00:00:00以来的秒数以来的秒数10Database System Implement

6、ation金培权（）金培权（）2 2、数据项表示方法：、数据项表示方法：SQLSQL数据类型数据类型nBit带长度的二进制位串带长度的二进制位串按字节表示，例如按字节表示，例如 1LengthBits11Database System Implementation金培权（）金培权（）3 3、两种不同的数据项表示、两种不同的数据项表示n定长数据项定长数据项n变长数据项变长数据项带长度带长度 （常用常用!）Null Terminated12Database System Implementation金培权（）金培权（）数据项表示总结数据项表示总结类类 型型 表表 示示 方方 法法整数和实数 字节串

7、字节串定长字符串定长字符串 n字节的数组字节的数组变长字符串变长字符串 VARCHAR(n) 用用n+ 1字节字节 长度加内容空值-终止字符串日期和时间 某种格式的定长字符串 变长值 整数二进制位序列 长度加内容字节表示枚举类型 使用整数编码表示一个枚举类型的值13Database System Implementation金培权（）金培权（）Where are we?Where are we?数据项记录块文件We are here！14Database System Implementation金培权（）金培权（）二、记录的组织二、记录的组织n记录记录数据项数据项 字段，字段，Fields

8、的集合的集合E.g.: Employee record:name field,salary field,date-of-hire field, .15Database System Implementation金培权（）金培权（）1 1、记录的类型、记录的类型n固定格式固定格式 vs. 可变格式可变格式Fixed Format vs. Variable Formatn定长定长 vs. 变长变长Fixed Length vs. Variable Length16Database System Implementation金培权（）金培权（）2 2、固定格式定长记录、固定格式定长记录n所有记录具有

9、相同的逻辑结构（模式）所有记录具有相同的逻辑结构（模式）n记录的模式（记录的模式（Schema）# fieldsName of each fieldType of each fieldOrder in recordOffset of each field in the record17Database System Implementation金培权（）金培权（）E.g. E.g. 固定格式定长记录固定格式定长记录Employee record(1) E#, 2 byte integer(2) Ename, 10 char.Schema(3) Dept, 2 byte code55s m i

10、t h0283j o n e s01Records18Database System Implementation金培权（）金培权（）2 2、固定格式定长记录、固定格式定长记录n构造构造n不考虑寻址特点不考虑寻址特点19Database System Implementation金培权（）金培权（）2 2、固定格式定长记录、固定格式定长记录n考虑寻址特点考虑寻址特点假设记录和字段的开始地址必须是假设记录和字段的开始地址必须是4的倍数的倍数20Database System Implementation金培权（）金培权（）3 3、记录首部、记录首部n在记录首部（在记录首部（Head）的描述记录的

11、信息）的描述记录的信息记录类型（模式信息）记录类型（模式信息）记录长度记录长度时间戳时间戳其它信息其它信息21Database System Implementation金培权（）金培权（）4 4、可变格式记录、可变格式记录n每个记录的格式不同每个记录的格式不同n记录的格式存储于记录中记录的格式存储于记录中22Database System Implementation金培权（）金培权（）E.g. E.g. 可变格式变长记录表示可变格式变长记录表示4I524SDROF46 字段数字段数字段字段E标识码标识码Integer 类型类型字段字段 Ename标识码标识码String 类型类型长度长度E

12、mployee(E#, Ename)标记字段(Tags)23Database System Implementation金培权（）金培权（）4 4、可变格式记录、可变格式记录n好处好处灵活的记录格式，适合灵活的记录格式，适合“松散松散”记录记录尽管一个记录可能有大量字段，但某个记录通常只尽管一个记录可能有大量字段，但某个记录通常只有有限的几个字段有有限的几个字段例如，病人的检验结果例如，病人的检验结果适合处理重复字段适合处理重复字段适合记录格式演变适合记录格式演变n缺点缺点浪费存储空间浪费存储空间24Database System Implementation金培权（）金培权（）6 6、变长记

13、录表示、变长记录表示n首部指针法首部指针法定长字段在前，变长字段在后定长字段在前，变长字段在后 name、address变长变长25Database System Implementation金培权（）金培权（）6 6、变长记录表示、变长记录表示n混合格式：定长记录变长记录混合格式：定长记录变长记录26Database System Implementation金培权（）金培权（）Where are we?Where are we?数据项记录块文件We are here！27Database System Implementation金培权（）金培权（）三、记录在块中的组织三、记录在块中的组织

14、n假设假设块的大小固定块的大小固定记录组织成单个文件记录组织成单个文件assume fixedlength blocksassume a single file (for now)BlockA FileA Record28Database System Implementation金培权（）金培权（）三、记录在块中的组织三、记录在块中的组织n定长记录的两种块内组织定长记录的两种块内组织记录地址记录地址rid通常使用通常使用表示表示槽槽 1 1槽槽 N N槽槽 2 2N N1 0 1 0 1 M1 0 1 0 1 M槽槽 1 1槽槽 M M槽槽 2 2M 3 2 1M 3 2 1记录数槽数空闲空

15、间空闲空间块头块头29Database System Implementation金培权（）金培权（）三、记录在块中的组织三、记录在块中的组织n变长记录在块内的组织变长记录在块内的组织N N242416162020第i块rid=的记录的记录长度24rid=rid=N 4 3 2 1N 4 3 2 1槽数槽数槽目录槽目录空闲空间数据区30Database System Implementation金培权（）金培权（）三、记录在块中的组织三、记录在块中的组织n其他问题其他问题记录在块中的分隔记录在块中的分隔 (separating records)记录跨块记录跨块 vs.记录不跨块记录不跨块 (s

16、panned vs. unspanned)不同类型的记录聚簇不同类型的记录聚簇 (mixed record types clustering)按序组织按序组织 (sequencing)记录的分裂记录的分裂 (split records)记录地址记录地址 (record address)记录的修改记录的修改31Database System Implementation金培权（）金培权（）1 1、记录在块内的分隔、记录在块内的分隔n定长记录：不需分隔定长记录：不需分隔n使用特殊标记使用特殊标记n通过块内偏移量通过块内偏移量32Database System Implementation金培权（）

17、金培权（）2 2、跨块、跨块 vs. vs. 不跨块不跨块nUnspanned: 记录必须在一个块中存储记录必须在一个块中存储block 1 block 2 .nSpanned：记录可跨块存储：记录可跨块存储block 1 block 2 .R1R2R1R3R4R5R2R3(a)R3(b)R6R5R4R7(a)33Database System Implementation金培权（）金培权（）2 2、跨块、跨块 vs. vs. 不跨块不跨块n跨块跨块Whats the rest?From where?34Database System Implementation金培权（）金培权（）2 2、跨

18、块、跨块 vs. vs. 不可跨块不可跨块n比较比较unspanned：实现简单，但空间浪费：实现简单，但空间浪费spanned：有效利用空间，实现更复杂：有效利用空间，实现更复杂nBut If record size block size，MUST be spanned35Database System Implementation金培权（）金培权（）3 3、不同类型的记录聚簇、不同类型的记录聚簇n一个块中存储不同类型的记录一个块中存储不同类型的记录（对于（对于RDB：多关系上的聚簇多关系上的聚簇）n好处好处聚簇聚簇 (clustering)经常一起访问的记录存储在同一块或连续块中经常一起访

19、问的记录存储在同一块或连续块中A Dept Record A Employee Record A Employee RecordA Block36Database System Implementation金培权（）金培权（）3 3、不同类型的记录聚簇、不同类型的记录聚簇学号学号s1其他列其他列学号学号S1S1s1其他列其他列课程号课程号C1C2c3学号学号s2其他列其他列学号学号S2S2s2其他列其他列课程号课程号C2C5c6学生表与课程学生表与课程表通过簇键表通过簇键“学号学号”聚簇聚簇Block37Database System Implementation金培权（）金培权（）3 3、不

20、同类型的记录聚簇、不同类型的记录聚簇Q1: select student.s#,ame from student s,sc where s.s# = sc.s# Q2: select * from studentn如果如果Q1经常被查询，则聚簇非常有效经常被查询，则聚簇非常有效n若若Q2经常被查询，则聚簇反而降低了效率经常被查询，则聚簇反而降低了效率STUDENT(STUDENT(s#s#,sname,age),sname,age)SC(SC(s#s#, ,cnamecname,score),score)38Database System Implementation金培权（）金培权（）4 4

21、、在块中按序存储记录、在块中按序存储记录n另一种聚簇另一种聚簇 (对于对于RDB：单关系上的聚簇单关系上的聚簇)将记录按某个字段顺序排列在块中将记录按某个字段顺序排列在块中n好处好处加快按排序字段查询记录时的效率加快按排序字段查询记录时的效率利于归并联接利于归并联接 （will be discussed later）39Database System Implementation金培权（）金培权（）4 4、在块中按序存储记录、在块中按序存储记录化学系化学系化学系化学系化学系化学系化学系化学系物理系物理系物理系物理系物理系物理系中文系中文系化学系化学系物理系物理系物理系物理系化学系化学系中文系中

22、文系化学系化学系物理系物理系化学系化学系按按Dept顺序组织的顺序组织的Student记录记录无序组织的无序组织的Student记录记录假设一个磁盘块假设一个磁盘块2条定长记录条定长记录40Database System Implementation金培权（）金培权（）4 4、在块中按序存储记录、在块中按序存储记录n物理连续物理连续n指针连接指针连接Next (R1)R1R1R2Next(R1)41Database System Implementation金培权（）金培权（）5 5、记录的分裂、记录的分裂n适合于变长记录的混合格式表示适合于变长记录的混合格式表示定长部分存储于某个块中定长部分

23、存储于某个块中变长部分存储于另一个块中变长部分存储于另一个块中与与spanned存储类似存储类似42Database System Implementation金培权（）金培权（）6 6、记录地址、记录地址n物理地址物理地址n逻辑地址（间接地址）逻辑地址（间接地址）43Database System Implementation金培权（）金培权（）6 6、记录地址、记录地址n记录的纯物理地址记录的纯物理地址主机标识主机标识 磁盘或其他设备标识磁盘或其他设备标识柱面号柱面号磁头号（盘面号）磁头号（盘面号） 块号块号 块内的偏移量块内的偏移量块地址44Database System Impleme

24、ntation金培权（）金培权（）6 6、记录地址、记录地址n记录的纯逻辑地址记录的纯逻辑地址物理地址物理地址逻辑地址逻辑地址映射表记录地址纯物理地址缺点访问代价增加：映射表占存储空间；需要地址转换好处灵活性：删除或移动记录时只要改变映射表项45Database System Implementation金培权（）金培权（）6 6、记录地址、记录地址记录的纯物理地址记录的纯逻辑地址tradeoff46Database System Implementation金培权（）金培权（）6 6、记录地址、记录地址n借助文件系统的逻辑块地址借助文件系统的逻辑块地址文件号逻辑块地址块内偏移文件号逻辑块地址

25、块内偏移文件系统映射Block(logical)Block(physical) + offset记录地址47Database System Implementation金培权（）金培权（）四、记录的修改四、记录的修改n插入插入n删除删除48Database System Implementation金培权（）金培权（）1 1、插入、插入n记录无序记录无序插入到任意块的空闲空间中插入到任意块的空闲空间中或申请一个新块（当所有块都已满时）或申请一个新块（当所有块都已满时）记录变长时，可使用偏移量表记录变长时，可使用偏移量表49Database System Implementation金培权（）金

26、培权（）1 1、插入、插入n记录有序记录有序找到记录应该放置的块找到记录应该放置的块如果有空间，放入并调节记录顺序即可，否则如果有空间，放入并调节记录顺序即可，否则有两种方法：有两种方法：在在“邻近块邻近块”中找空间中找空间 创建溢出块创建溢出块 50Database System Implementation金培权（）金培权（）2 2、删除、删除n立即回收空间立即回收空间例如，加到可用空间列表中例如，加到可用空间列表中n删除记录时处理溢出块删除记录时处理溢出块若删除的记录位于溢出块链上，则删除记录后若删除的记录位于溢出块链上，则删除记录后可对整个链进行重新组织以去除溢出块可对整个链进行重新组

27、织以去除溢出块51Database System Implementation金培权（）金培权（）2 2、删除、删除n使用删除标记使用删除标记若使用偏移表，则可以修改偏移表项指针，将若使用偏移表，则可以修改偏移表项指针，将其置空其置空若使用逻辑物理地址映射表，则可以将物理若使用逻辑物理地址映射表，则可以将物理地址置空地址置空可以在记录首部预留一开始位：可以在记录首部预留一开始位：0未删除，未删除，1已删除已删除1记录10记录252Database System Implementation金培权（）金培权（）Where are we?Where are we?数据项记录块文件We are he

28、re！53Database System Implementation金培权（）金培权（）五、块在文件中的组织五、块在文件中的组织n堆文件（堆文件（Heap File）最基本、最简单的文件结构最基本、最简单的文件结构记录不以任何顺序排序记录不以任何顺序排序记录可能存放在物理不邻接的块上记录可能存放在物理不邻接的块上n插入容易，但查找和删除代价高插入容易，但查找和删除代价高54Database System Implementation金培权（）金培权（）1 1、链表式堆文件组织、链表式堆文件组织首块数据块数据块数据块数据块数据块数据块含空闲空间的块链表满块链表55Database System

29、 Implementation金培权（）金培权（）2 2、目录式堆文件组织、目录式堆文件组织数据块1数据块2数据块N首块56Database System Implementation金培权（）金培权（）回顾：数据元素的表示层次回顾：数据元素的表示层次数据项记录块文件属性值的物理组织元组的物理组织记录的物理存放文件由磁盘块构成57Database System Implementation金培权（）金培权（）六、六、SQL ServerSQL Server的数据存储结构的数据存储结构nSQL Server的数据库文件是多个对象的集的数据库文件是多个对象的集合，包括多个表、索引等合，包括多个表、

30、索引等58Database System Implementation金培权（）金培权（）1 1、页、页n在在SQL Server中，数据存储的基本单位是中，数据存储的基本单位是页。在页。在 SQL Server 2000 中，页的大小中，页的大小是是 8 KB。9696字节字节单个数据行单个数据行最大最大80608060字节字节页地址：数据行地址：59Database System Implementation金培权（）金培权（）2 2、扩展盘区、扩展盘区n扩展盘区是一种基本单元，可将其中的空间分配扩展盘区是一种基本单元，可将其中的空间分配给表和索引。一个扩展盘区是给表和索引。一个扩展盘区是

31、 8 个邻接的页（或个邻接的页（或 64 KB）。）。n为了使空间分配更有效，为了使空间分配更有效，SQL Server 2000 对对只含少量数据的表不分配完整的扩展盘区。只含少量数据的表不分配完整的扩展盘区。SQL Server 2000 有两种类型的扩展盘区：有两种类型的扩展盘区： 统一扩展盘区：由单个对象所有，扩展盘区中的所有统一扩展盘区：由单个对象所有，扩展盘区中的所有八页只能由拥有该盘区的对象使用。八页只能由拥有该盘区的对象使用。混合扩展盘区：最多可由混合扩展盘区：最多可由 8 个对象共享。个对象共享。 n通常从混合扩展盘区中向新表或新索引分配页。通常从混合扩展盘区中向新表或新索引

32、分配页。当表或索引增长到当表或索引增长到 8 页时，就变成统一扩展盘区。页时，就变成统一扩展盘区。60Database System Implementation金培权（）金培权（）2 2、扩展盘区、扩展盘区n混合扩展盘区和统一扩展盘区混合扩展盘区和统一扩展盘区61Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织nSQL Server 2000 数据库有三种类型的文件：数据库有三种类型的文件： 主要数据文件主要数据文件 主要数据文件是数据库的起点，指向数据库中文件的其它部主要数据文件是数据库的起点，

33、指向数据库中文件的其它部分。每个数据库都有一个主要数据文件。主要数据文件的推分。每个数据库都有一个主要数据文件。主要数据文件的推荐文件扩展名是荐文件扩展名是 .mdf。次要数据文件次要数据文件 次要数据文件包含除主要数据文件外的所有数据文件。有些次要数据文件包含除主要数据文件外的所有数据文件。有些数据库可能没有次要数据文件，而有些数据库则有多个次要数据库可能没有次要数据文件，而有些数据库则有多个次要数据文件。次要数据文件的推荐文件扩展名是数据文件。次要数据文件的推荐文件扩展名是 .ndf。日志文件日志文件 日志文件包含恢复数据库所需的所有日志信息。每个数据库日志文件包含恢复数据库所需的所有日志

34、信息。每个数据库必须至少有一个日志文件，但可以不止一个。日志文件的推必须至少有一个日志文件，但可以不止一个。日志文件的推荐文件扩展名是荐文件扩展名是 .ldf。62Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织63Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n数据文件的页按顺序编号，文件首页的页数据文件的页按顺序编号，文件首页的页码是码是 0。每个文件都有一个文件。每个文件都有一个文件 ID 号。在

35、号。在数据库中唯一标识一页需要同时使用文件数据库中唯一标识一页需要同时使用文件 ID 和页码。和页码。64Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n数据文件的起始结构数据文件的起始结构65Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n数据文件的起始结构数据文件的起始结构PFS页：给对象分配了扩展盘区后，页：给对象分配了扩展盘区后，SQL Server 使用使用页可用空间页可用空间 (PFS)

36、页记录扩展盘页记录扩展盘区的哪些页已分配或可用，以及有多少可用的区的哪些页已分配或可用，以及有多少可用的剩余空间。每个剩余空间。每个 PFS 页包含大约页包含大约 8,000 页。页。PFS 对每一页都有一个相应的位图，该位图对每一页都有一个相应的位图，该位图记录这一页是空的、记录这一页是空的、1-50% 已满、已满、51-80% 已已满、满、81-95% 已满还是已满还是 96-100% 已满。已满。66Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n数据文件的起始结构数据文件的起始结构GAM页

37、：页：全局分配映射表全局分配映射表 (GAM) 页记录已分页记录已分配的扩展盘区。每个配的扩展盘区。每个 GAM 包含包含 64,000 个扩个扩展盘区，将近展盘区，将近 4 GB 的数据。的数据。GAM 对所涵盖对所涵盖区间内的每个扩展盘区都有一位。如果这个位区间内的每个扩展盘区都有一位。如果这个位是是 1，则扩展盘区可用；如果这个位是，则扩展盘区可用；如果这个位是 0，则，则扩展盘区已分配。扩展盘区已分配。67Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n数据文件的起始结构数据文件的起始结构

38、SGAM 页：页：共享全局分配映射表共享全局分配映射表 (SGAM)页页记录特定的扩展盘区，这些盘区当前用作混合记录特定的扩展盘区，这些盘区当前用作混合扩展盘区而且至少有一个未使用的页。扩展盘区而且至少有一个未使用的页。每个每个 SGAM 包含包含 64,000 个扩展盘区。个扩展盘区。SGAM 对对所涵盖区间内的每个扩展盘区都有一位。如果所涵盖区间内的每个扩展盘区都有一位。如果这个位是这个位是 1，则该扩展盘区就用作混合扩展盘，则该扩展盘区就用作混合扩展盘区且有可用的页；如果这个位是区且有可用的页；如果这个位是 0，则该扩展，则该扩展盘区不用作混合扩展盘区，或者虽然用作混合盘区不用作混合扩展

39、盘区，或者虽然用作混合扩展盘区但其所有页都正在使用中。扩展盘区但其所有页都正在使用中。68Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n数据文件的起始结构数据文件的起始结构1.1.若要分配统一扩展盘区，若要分配统一扩展盘区，SQL Server SQL Server 在在 GAM GAM 中搜索是中搜索是 1 1 的的位，然后将它设成位，然后将它设成 0 0。2.2.若要查找有可用页的混合扩展盘区，若要查找有可用页的混合扩展盘区，SQL Server SQL Server 在在 SGAM SGA

40、M 中中搜索是搜索是 1 1 的位。的位。3.3.若要分配混合扩展盘区，若要分配混合扩展盘区，SQL Server SQL Server 在在 GAM GAM 中搜索是中搜索是 1 1 的的位，并将它设置为位，并将它设置为 0 0，然后将，然后将 SGAM SGAM 中相应的位也设置为中相应的位也设置为 1 1。4.4.若要释放扩展盘区，若要释放扩展盘区，SQL Server SQL Server 应确保应确保 GAM GAM 位设置为位设置为 1 1 而而且且 SGAM SGAM 位设置为位设置为 0 0。69Database System Implementation金培权（）金培权（）3

41、 3、SQL ServerSQL Server文件组织文件组织n表（表（Table）的组织）的组织索引分配映射表 (IAM) 页记录了分配给对象的扩展盘区。70Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n表（表（Table）的组织）的组织71Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n表（表（Table）的组织）的组织数据页没有任何特定的顺序，也不链接在一起。数据页之间唯一的逻辑连接是记录在

42、IAM 页内的连接。服务器使用 IAM 页查找数据页集合内的页，进行表扫描或串行读。72Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织n表（表（Table）的组织）的组织当当 需要插入新行而当前页没有可用空间时，需要插入新行而当前页没有可用空间时，SQL Server 使用使用 IAM 页查找分配给对象的页查找分配给对象的扩展盘区。对于每个扩展盘区，扩展盘区。对于每个扩展盘区，SQL Server 搜索搜索 PFS 页以查看是否有一页具有足够的空页以查看是否有一页具有足够的空间容纳这一行。间容纳这

43、一行。73Database System Implementation金培权（）金培权（）3 3、SQL ServerSQL Server文件组织文件组织create table student( no char(3), name varchar(15), class varchar(5), address varchar(10), age smallint ) sysindexes表0表示无索引，是堆文件IAM首页74Database System Implementation金培权（）金培权（）4 4、SQL ServerSQL Server记录结构记录结构1B1B2BnB2B 列数列数/

44、8 2B2变长列数变长列数mB状态位A状态位B定长部分长度（不包括列数和NULL位图字节）定长数据列数NULL位图变长列数列偏移数组变长数据75Database System Implementation金培权（）金培权（）4 4、SQL ServerSQL Server记录结构记录结构create table Fixed( col1 int, col2 char(5), col3 char(3), col4 float ) 不包括列数和NULL位图sysindexesInsert Into Fixed Values(123, ABCD, NULL, 45.6)已分配1个数据页E文件号：1页号

45、：3076Database System Implementation金培权（）金培权（）4 4、SQL ServerSQL Server记录结构记录结构执行DBCC PAGE(test,1,30,1)，4个字节一组显示100018007b0000004142434420000000cdcccccccccc4640040004定长部分长度24定长字段列数NULL位图Insert Into Fixed Values(123, ABCD, NULL, 45.6)77Database System Implementation金培权（）金培权（）七、缓冲区管理器七、缓冲区管理器78Database

46、System Implementation金培权（）金培权（）七、缓冲区管理器七、缓冲区管理器Buffer PoolFrame（Bucket）Block is maintained.79Database System Implementation金培权（）金培权（）1 1、frameframe的参数的参数nDirtyFrame中的块是否已经被修改中的块是否已经被修改nPin-countFrame的块的已经被请求并且还未释放的计数的块的已经被请求并且还未释放的计数，即当前的用户数，即当前的用户数80Database System Implementation金培权（）金培权（）2 2、当请求块时

47、、当请求块时nIf requested block is not in pool:Choose a frame for replacementIf frame is dirty (some blocks are modified and havent been written to disk), write it to diskRead requested block into chosen framenPin (increment the pin-count of the frame) the block and return its address. If requests can be

48、predicted (e.g., sequential scans) blocks can be pre-fetched several blocks at a time!81Database System Implementation金培权（）金培权（）2 2、当释放块时、当释放块时nRequestor must unpin the frame containing the blocknRequestor must indicate whether block has been modified: dirty bit is used for this.82Database System Im

49、plementation金培权（）金培权（）3 3、缓冲区替换策略、缓冲区替换策略nFrame is chosen for replacement by a replacement policy:Least-recently-used (LRU), Clock, FIFO, MRU (Most-recently-used) etc.nOnly frames whose pin-count=0 are candidatesnPolicy can have big impact on # of I/Os; depends on the access pattern.83Database Syste

50、m Implementation金培权（）金培权（）3 3、缓冲区替换策略、缓冲区替换策略nLRU (Oracle, Sybase, Informix)当当Pin-count为为0时，时，frame放入替换队列放入替换队列选择队列头的选择队列头的frame替换替换nClock (MS SQL Server)N个个frame组成环形，组成环形，current指针指向当前指针指向当前frame；每个每个frame有一个有一个referenced位，它在位，它在pin-count=0时启动；时启动；从从current开始检查，若开始检查，若pin-count0，current增加增加1；若；若ref

51、erenced已启动，则关闭它并增加已启动，则关闭它并增加current（保证最近的不被替换）；若（保证最近的不被替换）；若pin-count=0并且并且referenced关闭，则替换关闭，则替换84Database System Implementation金培权（）金培权（）4 4、为何不使用、为何不使用OSOS缓冲区管理？缓冲区管理？nDBMS经常能预测访问模式经常能预测访问模式(Access Pattern)可以使用更专门的缓冲区替换策略可以使用更专门的缓冲区替换策略有利于有利于pre-fetch策略的有效使用策略的有效使用nDBMS需要强制写回磁盘能力（如需要强制写回磁盘能力（如W

52、AL），），OS的缓冲写回一般通过记录写请求来实现的缓冲写回一般通过记录写请求来实现（来自不同应用），实际的磁盘修改推迟，（来自不同应用），实际的磁盘修改推迟，因此不能保证写顺序因此不能保证写顺序85Database System Implementation金培权（）金培权（）5 5、错误的记录操作实现例子、错误的记录操作实现例子n例如，插入记录例如，插入记录 int insert_record(DBFILE*, DBRECORD)fopen()fseek()fwrite()n没有没有DBMS自己的缓冲区管理和存储管理自己的缓冲区管理和存储管理n直接基于文件系统，使用了直接基于文件系统，使用

53、了FS的缓冲管理的缓冲管理不能保证不能保证WAL不利于查询优化不利于查询优化不适应应用需求不适应应用需求86Database System Implementation金培权（）金培权（）6 6、Block vs. Disk FileBlock vs. Disk FilenDisk File文件存储在磁盘上的物理形式是文件存储在磁盘上的物理形式是bits/bytes，block是由是由OS或或DBMS软件软件对文件所做的抽象，这一抽象是通过控制对文件所做的抽象，这一抽象是通过控制数据在文件中的起止数据在文件中的起止offset来实现的来实现的1101101111Block #1Block #2

54、87Database System Implementation金培权（）金培权（）6 6、Buffer vs. Disk FileBuffer vs. Disk FileBufferset of framesFileset of pages缓冲区管理器存储管理器page/blockframe通常，frame大小page大小CPUrefers to88Database System Implementation金培权（）金培权（）7 7、Buffer SizeBuffer Sizen设计设计DBMS时应是一个可变的输入参数时应是一个可变的输入参数n通常通常DBMS允许用户自行配置允许用户自行配

55、置89Database System Implementation金培权（）金培权（）7 7、Buffer SizeBuffer Size配置配置配置配置实例实例实例实例90Database System Implementation金培权（）金培权（）8 8、BufferBuffer的存储结构的存储结构nBuffer是一个是一个frame的列表，每个的列表，每个frame用用于表示和存放一个磁盘块于表示和存放一个磁盘块#define FRAMESIZE 4096struct bFrame Char field FRAMESIZE ; #define BUFSIZE 1024 / frame数

56、目bFrame bufBUFSIZE; /也可以是用户配置的值Buffer的存储结构定义示例91Database System Implementation金培权（）金培权（）9 9、Page/blockPage/block的一般存储格式的一般存储格式n对于定长记录对于定长记录记录地址记录地址rid通常使用通常使用表示表示槽槽 1 1槽槽 N N槽槽 2 2N N1 0 1 0 1 M1 0 1 0 1 M槽槽 1 1槽槽 M M槽槽 2 2M 3 2 1M 3 2 1记录数槽数空闲空间空闲空间块头块头92Database System Implementation金培权（）金培权（）9 9、

57、Page/blockPage/block的一般存储格式的一般存储格式nRecord的存储结构的存储结构struct Record int page_id; int slot_num; 93Database System Implementation金培权（）金培权（）1010、BufferBuffer中的中的FrameFrame存储结构存储结构FrameMAX:BUFSIZE*FRAMESIZE94Database System Implementation金培权（）金培权（）1010、BufferBuffer中的中的FrameFrame存储结构存储结构struct Frame int fra

58、me_id;int offset; ;95Database System Implementation金培权（）金培权（）1111、BufferBuffer中中FrameFrame的查找的查找n读磁盘块时：根据读磁盘块时：根据page_id确定在确定在Buffer中是否已经存在中是否已经存在framen写磁盘块时：要根据写磁盘块时：要根据frame_id快速找到文快速找到文件中对应的件中对应的page_id96Database System Implementation金培权（）金培权（）1111、BufferBuffer中中FrameFrame的查找的查找n首先，要维护首先，要维护Buffe

59、r中所有中所有frame的维护的维护信息（信息（Buffer Control Blocks），如），如struct BCB BCB(); int page_id; int frame_id; int count; int time; int dirty; BCB * next; 97Database System Implementation金培权（）金培权（）1111、BufferBuffer中中FrameFrame的查找的查找n建立建立frame-page之间的索引之间的索引n若用若用Hash Table，需要建立，需要建立2个个BCB hTableBufferSize /page 2 f

60、rame int hTableBufferSize /frame 2 page一个简单的Hash Function例子H(k)=(page_id)%(buffersize)98Database System Implementation金培权（）金培权（）1212、Buffer ManagerBuffer Manager的基本功能的基本功能nFixPage(int page_id)将对应将对应page_id的的page读入到读入到buffer中。如果中。如果buffer已满，则需要选择换出的已满，则需要选择换出的frame。nFixNewPage()在插入数据时申请一个新在插入数据时申请一个新

61、page并将其放在并将其放在buffer中。中。nSelectVictim()选择换出的选择换出的frame_idnFindFrame(int page_id)查找给定的查找给定的page是否已经在某个是否已经在某个frame中了中了nSetDirty(int frame_id)99Database System Implementation金培权（）金培权（）1313、数据库文件的一般组成、数据库文件的一般组成n数据文件数据文件首块在首块在Insert_Record时创建（调用时创建（调用Buffer Manager的的FixNewPage），一般块号从），一般块号从0开开始始n系统目录文件

62、系统目录文件首块一般首块一般Create_Table时创建（调用时创建（调用Buffer Manager的的FixNewPage）Note：所有数据和元数据操作都唯一通过Buffer Manager来请求page100Database System Implementation金培权（）金培权（）1414、文件记录操作与、文件记录操作与Buffer ManagerBuffer Manager文件、记录、索引管理：Insert_Record,Delete_Record,Create_Table,Drop_Table,Create_Index,Buffer Manager：FindFrame,Fi

63、xPage,FixNewPage,SetDirty,SetVictim,record请求frame请求101Database System Implementation金培权（）金培权（）1515、存储管理器、存储管理器文件、记录、索引管理：Insert_Record,Delete_Record,Create_Table,Drop_Table,Create_Index,Buffer Manager：FindFrame,FixPage,FixNewPage,SetDirty,SetVictim,record请求frame请求page请求Storage Manager102Database Sys

64、tem Implementation金培权（）金培权（）1515、存储管理器、存储管理器page请求Storage ManagerDatabase Filedisk 103Database System Implementation金培权（）金培权（）1616、存储管理器功能、存储管理器功能n从磁盘中存取物理数据，为从磁盘中存取物理数据，为Buffer Manager提供提供Page抽象抽象OpenReadPage/WritePageGetNumPagesIncreaseNumPages104Database System Implementation金培权（）金培权（）File、Record

65、 & Access MethodsBuffer ManagerFixPage(int page_id)FixNewPage()SelectVictim()Hash(int page_id)SetDirty(int frame_id)Storage ManagerOpen )CloseFile()ReadPage(int page_id)WritePage(int frame_id, bFrame frm) FileSeek(int offset, int pos) IncNumPages()GetNumPages()Buffer (Main Memory)总体结构图105Database System Implementation金培权（）金培权（）总结总结n数据项的表示数据项的表示n记录的表示记录的表示n记录在块中的组织记录在块中的组织n记录的修改记录的修改n块在文件中的组织块在文件中的组织n缓冲区管理缓冲区管理106Database System Implementation金培权（）金培权（）考虑考虑n如何衡量数据组织方法的好坏？如何衡量数据组织方法的好坏？性能性能 (performance)灵活性灵活性 (flexibility)复杂程度复杂程度 (complexity)空间利用率空间利用率 (space utilization)