科大-高级数据库技术05

1、Advanced Database Technologies金培权（金培权（）2Advanced Database Technologies金培权（金培权（）n数据项的表示（数据项的表示（Data Items）n记录的表示（记录的表示（Records）n记录在块中的组织（记录在块中的组织（Block）n记录的修改记录的修改n块在文件中的组织块在文件中的组织n缓冲区管理缓冲区管理3Advanced Database Technologies金培权（金培权（）数据项记录块文件属性值的物理组织元组的物理组织记录的物理存放文件由磁盘块构成4Advanced Database Technologies金

2、培权（金培权（）n数据项数据项字节序列字节序列表示关系数据库中元组的属性值表示关系数据库中元组的属性值5Advanced Database Technologies金培权（金培权（）n表示什么？表示什么？姓名姓名年龄年龄出生日期出生日期照片照片n用什么表示？用什么表示？Bytes6Advanced Database Technologies金培权（金培权（）nInteger (short)2 bytes例如，例如，35 表示为表示为nReal，Float4 bytes （32 bits）N bits表示小数，表示小数，M bits表示指数表示指数 00000000001000117Advanc

3、ed Database Technologies金培权（金培权（）nChar(n) 或或 Character(n) 定长字符串定长字符串小于小于n时使用特殊填充符时使用特殊填充符例如，若属性类型为例如，若属性类型为Char(5)，则属性值，则属性值cat 表示为表示为 nVarchar(n) 变长字符串变长字符串NULL终止符，例终止符，例 Varchar(5)带长度带长度 定长表示，定长表示，n+1 bytesVarchar(4):cta ctacta3cta 8Advanced Database Technologies金培权（金培权（）nBooleanTRUEFALSEn枚举类型枚举类型

4、RED,GREEN,YELLOW整数表示整数表示RED 1，GREEN 2，YELLOW 3若用两个字节的短整型来表示，则可以表示若用两个字节的短整型来表示，则可以表示 216 个个不同值不同值1111 11110000 00009Advanced Database Technologies金培权（金培权（）nDate10字符字符(SQL92)：YYYY-MM-DD字符串表示字符串表示8字符：字符：YYYYMMDD7字符：字符：YYYYDDD, NOT YYMMDD！Integer，自，自1900-01-01以来的天数以来的天数nTime8字符字符(SQL92)：HH:NN:SS 整数秒整数秒

5、Varchar(n)：HH:NN:SS.FF带小数秒带小数秒Integer，自，自00:00:00以来的秒数以来的秒数10Advanced Database Technologies金培权（金培权（）nBit带长度的二进制位串带长度的二进制位串按字节表示，例如按字节表示，例如 010111110011LengthBits010111110011000011Advanced Database Technologies金培权（金培权（）n定长数据项定长数据项n变长数据项变长数据项带长度带长度 （常用常用!）Null Terminated12Advanced Database Technologie

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

7、E.g.: Employee record:name field,salary field,date-of-hire field, .15Advanced Database Technologies金培权（金培权（）n固定格式固定格式 vs. 可变格式可变格式Fixed Format vs. Variable Formatn定长定长 vs. 变长变长Fixed Length vs. Variable Length16Advanced Database Technologies金培权（金培权（）n所有记录具有相同的逻辑结构（模式）所有记录具有相同的逻辑结构（模式）n记录的模式（记录的模式（Sch

8、ema）# fieldsName of each fieldType of each fieldOrder in recordOffset of each field in the record17Advanced Database Technologies金培权（金培权（）Employee record(1) E#, 2 byte integer(2) Ename, 10 char.Schema(3) Dept, 2 byte code55s m i t h0283j o n e s01Records18Advanced Database Technologies金培权（金培权（）n构造构造

9、n不考虑寻址特点不考虑寻址特点19Advanced Database Technologies金培权（金培权（）n考虑寻址特点考虑寻址特点假设记录和字段的开始地址必须是假设记录和字段的开始地址必须是4的倍数的倍数20Advanced Database Technologies金培权（金培权（）n在记录首部（在记录首部（Head）的描述记录的信息）的描述记录的信息记录类型（模式信息）记录类型（模式信息）记录长度记录长度时间戳时间戳其它信息其它信息21Advanced Database Technologies金培权（金培权（）n每个记录的格式不同每个记录的格式不同n记录的格式存储于记录中记录的格

10、式存储于记录中22Advanced Database Technologies金培权（金培权（）4I524SDROF46 字段数字段数字段字段E标识码标识码Integer 类型类型字段字段 Ename标识码标识码String 类型类型长度长度Employee(E#, Ename)标记字段(Tags)23Advanced Database Technologies金培权（金培权（）n好处好处灵活的记录格式，适合灵活的记录格式，适合“松散松散”记录记录尽管一个记录可能有大量字段，但某个记录通常只尽管一个记录可能有大量字段，但某个记录通常只有有限的几个字段有有限的几个字段例如，病人的检验结果例如，病

11、人的检验结果适合处理重复字段适合处理重复字段适合记录格式演变适合记录格式演变n缺点缺点浪费存储空间浪费存储空间24Advanced Database Technologies金培权（金培权（）n首部指针法首部指针法定长字段在前，变长字段在后定长字段在前，变长字段在后 name、address变长变长25Advanced Database Technologies金培权（金培权（）n混合格式：定长记录变长记录混合格式：定长记录变长记录26Advanced Database Technologies金培权（金培权（）数据项记录块文件We are here！27Advanced Database T

12、echnologies金培权（金培权（）n假设假设块的大小固定块的大小固定记录组织成单个文件记录组织成单个文件assume fixedlength blocksassume a single file (for now)BlockA FileA Record28Advanced Database Technologies金培权（金培权（）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 M 3 2 1 3 2 1记录数槽数空闲空

13、间空闲空间块头块头29Advanced Database Technologies金培权（金培权（）n变长记录在块内的组织变长记录在块内的组织N N242416162020第i块rid=的记录的记录长度24rid=rid=N N 4 3 2 1 4 3 2 1槽数槽数槽目录槽目录空闲空间数据区30Advanced Database Technologies金培权（金培权（）n其他问题其他问题记录在块中的分隔记录在块中的分隔 (separating records)记录跨块记录跨块 vs.记录不跨块记录不跨块 (spanned vs. unspanned)不同类型的记录聚簇不同类型的记录聚簇 (

14、mixed record types clustering)按序组织按序组织 (sequencing)记录的分裂记录的分裂 (split records)记录地址记录地址 (record address)记录的修改记录的修改31Advanced Database Technologies金培权（金培权（）n定长记录：不需分隔定长记录：不需分隔n使用特殊标记使用特殊标记n通过块内偏移量通过块内偏移量32Advanced Database Technologies金培权（金培权（）nUnspanned: 记录必须在一个块中存储记录必须在一个块中存储block 1 block 2 .nSpanned

15、：记录可跨块存储：记录可跨块存储block 1 block 2 .R1R2R1R3R4R5R2R3(a)R3(b)R6R5R4R7(a)33Advanced Database Technologies金培权（金培权（）n跨块跨块Whats the rest?From where?34Advanced Database Technologies金培权（金培权（）n比较比较unspanned：实现简单，但空间浪费：实现简单，但空间浪费spanned：有效利用空间，实现更复杂：有效利用空间，实现更复杂nBut If record size block size，MUST be spanned35Ad

16、vanced Database Technologies金培权（金培权（）n一个块中存储不同类型的记录一个块中存储不同类型的记录（对于（对于RDB：多关系上的聚簇多关系上的聚簇）n好处好处聚簇聚簇 (clustering)经常一起访问的记录存储在同一块或连续块经常一起访问的记录存储在同一块或连续块中中A Dept Record A Employee Record A Employee RecordA Block36Advanced Database Technologies金培权（金培权（）学号学号s1其他列其他列学号学号S1S1s1其他列其他列课程号课程号C1C2c3学号学号s2其他列其他列

17、学号学号S2S2s2其他列其他列课程号课程号C2C5c6学生表与课程学生表与课程表通过簇键表通过簇键“学号学号”聚簇聚簇Block37Advanced Database Technologies金培权（金培权（）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

18、,age) )SC(SC(s#s#, ,cnamecname,score,score) )38Advanced Database Technologies金培权（金培权（）n另一种聚簇另一种聚簇 (对于对于RDB：单关系上的聚簇单关系上的聚簇)将记录按某个字段顺序排列在块中将记录按某个字段顺序排列在块中n好处好处加快按排序字段查询记录时的效率加快按排序字段查询记录时的效率利于归并联接利于归并联接 （will be discussed later）39Advanced Database Technologies金培权（金培权（）化学系化学系化学系化学系化学系化学系化学系化学系物理系物理系物理系物

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

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

21、录的纯逻辑地址物理地址物理地址逻辑地址逻辑地址映射表记录地址纯物理地址缺点访问代价增加：映射表占存储空间；需要地址转换好处灵活性：删除或移动记录时只要改变映射表项45Advanced Database Technologies金培权（金培权（）记录的纯物理地址记录的纯逻辑地址tradeoff46Advanced Database Technologies金培权（金培权（）n借助文件系统的逻辑块地址借助文件系统的逻辑块地址文件号逻辑块地址块内偏移文件号逻辑块地址块内偏移文件系统映射File IDBlock(logical)Block(physical) + offset记录地址47Advance

22、d Database Technologies金培权（金培权（）n插入插入n删除删除48Advanced Database Technologies金培权（金培权（）n记录无序记录无序插入到任意块的空闲空间中插入到任意块的空闲空间中或申请一个新块（当所有块都已满时）或申请一个新块（当所有块都已满时）记录变长时，可使用偏移量表记录变长时，可使用偏移量表49Advanced Database Technologies金培权（金培权（）n记录有序记录有序找到记录应该放置的块找到记录应该放置的块如果有空间，放入并调节记录顺序即可，否如果有空间，放入并调节记录顺序即可，否则有两种方法：则有两种方法：在在

23、“邻近块邻近块”中找空间中找空间 创建溢出块创建溢出块 50Advanced Database Technologies金培权（金培权（）n立即回收空间立即回收空间例如，加到可用空间列表中例如，加到可用空间列表中n删除记录时处理溢出块删除记录时处理溢出块若删除的记录位于溢出块链上，则删除记录若删除的记录位于溢出块链上，则删除记录后可对整个链进行重新组织以去除溢出块后可对整个链进行重新组织以去除溢出块51Advanced Database Technologies金培权（金培权（）n使用删除标记使用删除标记若使用偏移表，则可以修改偏移表项指针，若使用偏移表，则可以修改偏移表项指针，将其置空将其置

24、空若使用逻辑物理地址映射表，则可以将物若使用逻辑物理地址映射表，则可以将物理地址置空理地址置空可以在记录首部预留一开始位：可以在记录首部预留一开始位：0未删除，未删除，1已删除已删除1记录10记录252Advanced Database Technologies金培权（金培权（）数据项记录块文件We are here！53Advanced Database Technologies金培权（金培权（）n堆文件（堆文件（Heap File）最基本、最简单的文件结构最基本、最简单的文件结构记录不以任何顺序排序记录不以任何顺序排序记录可能存放在物理不邻接的块上记录可能存放在物理不邻接的块上n插入容易，

25、但查找和删除代价高插入容易，但查找和删除代价高54Advanced Database Technologies金培权（金培权（）首块数据块数据块数据块数据块数据块数据块含空闲空间的块链表满块链表55Advanced Database Technologies金培权（金培权（）数据块1数据块2数据块N首块56Advanced Database Technologies金培权（金培权（）数据项记录块文件属性值的物理组织元组的物理组织记录的物理存放文件由磁盘块构成57Advanced Database Technologies金培权（金培权（）nSQL Server的数据库文件是多个对象的的数据库文

26、件是多个对象的集合，包括多个表、索引等集合，包括多个表、索引等58Advanced Database Technologies金培权（金培权（）n在在SQL Server中，数据存储的基本单位中，数据存储的基本单位是页。在是页。在 SQL Server 2000 中，页的大中，页的大小是小是 8 KB。9696字节字节单个数据行单个数据行最大最大80608060字节字节页地址：数据行地址：59Advanced Database Technologies金培权（金培权（）n扩展盘区是一种基本单元，可将其中的空间分配扩展盘区是一种基本单元，可将其中的空间分配给表和索引。一个扩展盘区是给表和索引。一

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

28、新表或新索引分配页。当表或索引增长到当表或索引增长到 8 页时，就变成统一扩展盘页时，就变成统一扩展盘区。区。60Advanced Database Technologies金培权（金培权（）n混合扩展盘区和统一扩展盘区混合扩展盘区和统一扩展盘区61Advanced Database Technologies金培权（金培权（）nSQL Server 2000 数据库有三种类型的文件：数据库有三种类型的文件： 主要数据文件主要数据文件 主要数据文件是数据库的起点，指向数据库中文件的其它部主要数据文件是数据库的起点，指向数据库中文件的其它部分。每个数据库都有一个主要数据文件。主要数据文件的推分。每

29、个数据库都有一个主要数据文件。主要数据文件的推荐文件扩展名是荐文件扩展名是 .mdf。次要数据文件次要数据文件 次要数据文件包含除主要数据文件外的所有数据文件。有些次要数据文件包含除主要数据文件外的所有数据文件。有些数据库可能没有次要数据文件，而有些数据库则有多个次要数据库可能没有次要数据文件，而有些数据库则有多个次要数据文件。次要数据文件的推荐文件扩展名是数据文件。次要数据文件的推荐文件扩展名是 .ndf。日志文件日志文件 日志文件包含恢复数据库所需的所有日志信息。每个数据库日志文件包含恢复数据库所需的所有日志信息。每个数据库必须至少有一个日志文件，但可以不止一个。日志文件的推必须至少有一个

30、日志文件，但可以不止一个。日志文件的推荐文件扩展名是荐文件扩展名是 .ldf。62Advanced Database Technologies金培权（金培权（）63Advanced Database Technologies金培权（金培权（）n数据文件的页按顺序编号，文件首页的页数据文件的页按顺序编号，文件首页的页码是码是 0。每个文件都有一个文件。每个文件都有一个文件 ID 号。在号。在数据库中唯一标识一页需要同时使用文件数据库中唯一标识一页需要同时使用文件 ID 和页码。和页码。64Advanced Database Technologies金培权（金培权（）n数据文件的起始结构数据文件的

31、起始结构65Advanced Database Technologies金培权（金培权（）n数据文件的起始结构数据文件的起始结构PFS页：给对象分配了扩展盘区后，页：给对象分配了扩展盘区后，SQL Server 使用使用页可用空间页可用空间 (PFS) 页记录扩展盘页记录扩展盘区的哪些页已分配或可用，以及有多少可用区的哪些页已分配或可用，以及有多少可用的剩余空间。每个的剩余空间。每个 PFS 页包含大约页包含大约 8,000 页页。PFS 对每一页都有一个相应的位图，该位对每一页都有一个相应的位图，该位图记录这一页是空的、图记录这一页是空的、1-50% 已满、已满、51-80% 已满、已满、8

32、1-95% 已满还是已满还是 96-100% 已满。已满。66Advanced Database Technologies金培权（金培权（）n数据文件的起始结构数据文件的起始结构GAM页：页：全局分配映射表全局分配映射表 (GAM) 页记录已分页记录已分配的扩展盘区。每个配的扩展盘区。每个 GAM 包含包含 64,000 个扩个扩展盘区，将近展盘区，将近 4 GB 的数据。的数据。GAM 对所涵盖对所涵盖区间内的每个扩展盘区都有一位。如果这个区间内的每个扩展盘区都有一位。如果这个位是位是 1，则扩展盘区可用；如果这个位是，则扩展盘区可用；如果这个位是 0，则扩展盘区已分配。则扩展盘区已分配。6

33、7Advanced Database Technologies金培权（金培权（）n数据文件的起始结构数据文件的起始结构SGAM 页：页：共享全局分配映射表共享全局分配映射表 (SGAM)页页记录特定的扩展盘区，这些盘区当前用作混记录特定的扩展盘区，这些盘区当前用作混合扩展盘区而且至少有一个未使用的页。合扩展盘区而且至少有一个未使用的页。每每个个 SGAM 包含包含 64,000 个扩展盘区。个扩展盘区。SGAM 对所涵盖区间内的每个扩展盘区都有一位。对所涵盖区间内的每个扩展盘区都有一位。如果这个位是如果这个位是 1，则该扩展盘区就用作混合扩，则该扩展盘区就用作混合扩展盘区且有可用的页；如果这个

34、位是展盘区且有可用的页；如果这个位是 0，则该，则该扩展盘区不用作混合扩展盘区，或者虽然用扩展盘区不用作混合扩展盘区，或者虽然用作混合扩展盘区但其所有页都正在使用中。作混合扩展盘区但其所有页都正在使用中。68Advanced Database Technologies金培权（金培权（）n数据文件的起始结构数据文件的起始结构1.1. 若要分配统一扩展盘区，若要分配统一扩展盘区，SQL Server SQL Server 在在 GAM GAM 中搜索是中搜索是 1 1 的的位，然后将它设成位，然后将它设成 0 0。2.2. 若要查找有可用页的混合扩展盘区，若要查找有可用页的混合扩展盘区，SQL S

35、erver SQL Server 在在 SGAM SGAM 中中搜索是搜索是 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。69Advanced Da

36、tabase Technologies金培权（金培权（）n表（表（Table）的组织）的组织索引分配映射表 (IAM) 页记录了分配给对象的扩展盘区。70Advanced Database Technologies金培权（金培权（）n表（表（Table）的组织）的组织71Advanced Database Technologies金培权（金培权（）n表（表（Table）的组织）的组织数据页没有任何特定的顺序，也不链接在一起。数据页之间唯一的逻辑连接是记录在 IAM 页内的连接。服务器使用 IAM 页查找数据页集合内的页，进行表扫描或串行读。72Advanced Database Technol

37、ogies金培权（金培权（）n表（表（Table）的组织）的组织当当 需要插入新行而当前页没有可用空间时，需要插入新行而当前页没有可用空间时，SQL Server 使用使用 IAM 页查找分配给对象的页查找分配给对象的扩展盘区。对于每个扩展盘区，扩展盘区。对于每个扩展盘区，SQL Server 搜索搜索 PFS 页以查看是否有一页具有足够的空页以查看是否有一页具有足够的空间容纳这一行。间容纳这一行。73Advanced Database Technologies金培权（金培权（）create table student( no char(3), name varchar(15), class

38、varchar(5), address varchar(10), age smallint ) sysindexes表0表示无索引，是堆文件IAM首页74Advanced Database Technologies金培权（金培权（）1B1B2BnB2B 列数列数/8 2B2变长列数变长列数mB状态位A状态位B定长部分长度（不包括列数和NULL位图字节）定长数据列数NULL位图变长列数列偏移数组变长数据75Advanced Database Technologies金培权（金培权（）create table Fixed( col1 int, col2 char(5), col3 char(3),

39、 col4 float ) 不包括列数和NULL位图sysindexesInsert Into Fixed Values(123, ABCD, NULL, 45.6)已分配1个数据页00010000001E文件号：1页号：3076Advanced Database Technologies金培权（金培权（）执行DBCC PAGE(test,1,30,1)，4个字节一组显示100018007b0000004142434420000000cdcccccccccc4640040004定长部分长度24定长字段列数NULL位图00000100Insert Into Fixed Values(123, A

40、BCD, NULL, 45.6)77Advanced Database Technologies金培权（金培权（）78Advanced Database Technologies金培权（金培权（）Buffer PoolFrame（Bucket）Block is maintained.79Advanced Database Technologies金培权（金培权（）nDirtyFrame中的块是否已经被修改中的块是否已经被修改nPin-countFrame的块的已经被请求并且还未释放的计的块的已经被请求并且还未释放的计数，即当前的用户数数，即当前的用户数80Advanced Database T

41、echnologies金培权（金培权（）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 re

42、quests can be predicted (e.g., sequential scans) blocks can be pre-fetched several blocks at a time!81Advanced Database Technologies金培权（金培权（）nRequestor must unpin the frame containing the blocknRequestor must indicate whether block has been modified: dirty bit is used for this.82Advanced Database Te

43、chnologies金培权（金培权（）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.83Advanced Database Technologies金培权（金培

44、权（）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；若；若referenced已启动，则关闭它并增加已启动，则关闭它并增加current（保证最近的

45、不被替换）；若保证最近的不被替换）；若pin-count=0并且并且referenced关闭，则替换关闭，则替换84Advanced Database Technologies金培权（金培权（）nDBMS经常能预测访问模式经常能预测访问模式(Access Pattern)可以使用更专门的缓冲区替换策略可以使用更专门的缓冲区替换策略有利于有利于pre-fetch策略的有效使用策略的有效使用nDBMS需要强制写回磁盘能力（如需要强制写回磁盘能力（如WAL），OS的缓冲写回一般通过记录写请求来的缓冲写回一般通过记录写请求来实现（来自不同应用），实际的磁盘修改实现（来自不同应用），实际的磁盘修改推迟，

46、因此不能保证写顺序推迟，因此不能保证写顺序85Advanced Database Technologies金培权（金培权（）n例如，插入记录例如，插入记录 int insert_record(DBFILE*, DBRECORD)fopen()fseek()fwrite()n没有没有DBMS自己的缓冲区管理和存储管理自己的缓冲区管理和存储管理n直接基于文件系统，使用了直接基于文件系统，使用了FS的缓冲管理的缓冲管理不能保证不能保证WAL不利于查询优化不利于查询优化不适应应用需求不适应应用需求86Advanced Database Technologies金培权（金培权（）nDisk File文件

47、存储在磁盘上的物理形式是文件存储在磁盘上的物理形式是bits/bytes，block是由是由OS或或DBMS软件软件对文件所做的抽象，这一抽象是通过控制对文件所做的抽象，这一抽象是通过控制数据在文件中的起止数据在文件中的起止offset来实现的来实现的0101001001001001011110100111010100101101111Block #1Block #287Advanced Database Technologies金培权（金培权（）Bufferset of framesFileset of pages缓冲区管理器存储管理器page/blockframe通常，frame大小pag

48、e大小CPUrefers to88Advanced Database Technologies金培权（金培权（）n设计设计DBMS时应是一个可变的输入参数时应是一个可变的输入参数n通常通常DBMS允许用户自行配置允许用户自行配置89Advanced Database Technologies金培权（金培权（）90Advanced Database Technologies金培权（金培权（）nBuffer是一个是一个frame的列表，每个的列表，每个frame用用于表示和存放一个磁盘块于表示和存放一个磁盘块#define FRAMESIZE 4096struct bFrame Char fiel

49、d FRAMESIZE ; #define BUFSIZE 1024 / frame数目bFrame bufBUFSIZE; /也可以是用户配置的值Buffer的存储结构定义示例91Advanced Database Technologies金培权（金培权（）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 M 3 2 1 3 2 1记录数槽数空闲空间空闲空间块头块头92Advanced Database Technologies金培权（金培权（）

50、nRecord的存储结构的存储结构struct Record int page_id; int slot_num; 93Advanced Database Technologies金培权（金培权（）FrameMAX:BUFSIZE*FRAMESIZE94Advanced Database Technologies金培权（金培权（）struct Frameint frame_id;int offset; ;95Advanced Database Technologies金培权（金培权（）n读磁盘块时：根据读磁盘块时：根据page_id确定在确定在Buffer中是否已经存在中是否已经存在frame

51、n写磁盘块时：要根据写磁盘块时：要根据frame_id快速找到文快速找到文件中对应的件中对应的page_id96Advanced Database Technologies金培权（金培权（）n首先，要维护首先，要维护Buffer中所有中所有frame的维护的维护信息（信息（Buffer Control Blocks），如），如struct BCB BCB(); int page_id; int frame_id; int count; int time; int dirty; BCB * next; 97Advanced Database Technologies金培权（金培权（）n建立建立frame-page之间的索引之间的索引n若用若用Hash Table，需要建立，需要建立2个个BCB hTableBufferSize /page 2 frame int hTableBufferSize /frame 2 page一个简单的Hash Function例子H(k)=(page_id)%(buffersize)98Advanced Database Technologies金培权（金培权（）nFixPage(int page_id)将对应将对应page_id的的page读入到读入到buffer中。如果中。如果buffer已满，则需要选择换出的已满，则需要选择换