数据元素的表示.ppt

《数据元素的表示.ppt》由会员分享，可在线阅读，更多相关《数据元素的表示.ppt（108页珍藏版）》请在三一办公上搜索。

1、1,第三章 数据元素的表示,2,Previous,磁盘结构对性能的影响DBMS中的数据必须在内存中操作磁盘和主存之间数据传输的单位是块，如果只需要块上的某一项，也需要传输整个块。读/写一个磁盘块称为一次I/O读/写块的时间依数据所在的位置而变化存取时间=寻道时间S旋转延迟R传输时间T,3,数据项的表示（Data Items）记录的表示（Records）记录在块中的组织（Block）记录的修改块在文件中的组织缓冲区管理,主要内容,4,数据元素的表示层次,数据项,记录,块,文件,属性值的物理组织,元组的物理组织,记录的物理存放,文件由磁盘块构成,5,一、数据项的表示,数据项字节序列表示关系数据库中

2、元组的属性值,6,1、数据项表示的内容,表示什么？姓名年龄出生日期照片用什么表示？Bytes,7,2、数据项表示方法：SQL数据类型,Integer(short)2 bytes例如，35 表示为Real，Float4 bytes（32 bits）N bits表示小数，M bits表示指数,00000000,00100011,8,2、数据项表示方法：SQL数据类型,Char(n)或 Character(n)定长字符串小于n时使用特殊填充符例如，若属性类型为Char(5)，则属性值cat 表示为 Varchar(n)变长字符串NULL终止符，例 Varchar(5)长度+内容 定长表示，n+1 b

3、ytesVarchar(4):,9,2、数据项表示方法：SQL数据类型,BooleanTRUEFALSE枚举类型RED,GREEN,YELLOW整数表示RED 1，GREEN 2，YELLOW 3若用两个字节的短整型来表示，则可以表示 216 个不同值,1111 1111,0000 0000,10,2、数据项表示方法：SQL数据类型,Date10字符(SQL92)：YYYY-MM-DD字符串表示8字符：YYYYMMDD7字符：YYYYDDD,NOT YYMMDD！Integer，自1900-01-01以来的天数Time8字符(SQL92)：HH:NN:SS 整数秒Varchar(n)：HH:N

4、N:SS.FF带小数秒Integer，自00:00:00以来的秒数,11,2、数据项表示方法：SQL数据类型,Bit带长度的二进制位串,Length,Bits,01011111,00110000,12,3、两种不同的数据项表示,定长数据项变长数据项带长度（常用!）Null Terminated,13,数据项表示总结,14,Where are we?,数据项,记录,块,文件,We are here！,15,二、记录的组织,记录数据项 字段，Fields 的集合,E.g.:Employee record:name field,salary field,date-of-hire field,.,16

5、,1、记录的类型,固定格式 vs.可变格式Fixed Format vs.Variable Format定长 vs.变长Fixed Length vs.Variable Length,17,2、固定格式定长记录,所有记录具有相同的逻辑结构（模式）记录的模式（Schema）#fieldsName of each fieldType of each fieldOrder in recordOffset of each field in the record,18,E.g.固定格式定长记录,Employee record(1)E#,2 byte integer(2)Ename,10 char.Sch

6、ema(3)Dept,2 byte code,55,s m i t h,02,83,j o n e s,01,Records,19,2、固定格式定长记录,构造不考虑寻址特点,20,2、固定格式定长记录,考虑寻址特点假设记录和字段的开始地址必须是4的倍数,21,3、记录首部,在记录首部（Head）的描述记录的信息记录类型（模式信息）记录长度时间戳其它信息,22,4、可变格式记录,每个记录的格式不同记录的格式存储于记录中,23,E.g.可变格式变长记录表示,字段数字段E标识码Integer 类型字段 Ename标识码String 类型长度,Employee(E#,Ename),24,4、可变格式记

7、录,好处灵活的记录格式，适合“松散”记录尽管一个记录可能有大量字段，但某个记录通常只有有限的几个字段例如，病人的检验结果适合处理重复字段适合记录格式演变缺点浪费存储空间,25,6、变长记录表示,首部指针法定长字段在前，变长字段在后 name、address变长,26,6、变长记录表示,混合格式：定长记录变长记录,27,Where are we?,数据项,记录,块,文件,We are here！,28,三、记录在块中的组织,假设块的大小固定记录组织成单个文件,Block,A File,A Record,29,三、记录在块中的组织,定长记录的两种块内组织记录地址rid通常使用表示,N,1 0 1

8、0 1 M,槽 1,槽 M,槽 2,M 3 2 1,记录数,槽数,空闲空间,块头,30,三、记录在块中的组织,变长记录在块内的组织,31,三、记录在块中的组织,其他问题记录在块中的分隔(separating records)记录跨块 vs.记录不跨块(spanned vs.unspanned)不同类型的记录聚簇(mixed record types clustering)按序组织(sequencing)记录的分裂(split records)记录地址(record address)记录的修改,32,1、记录在块内的分隔,定长记录：不需分隔使用特殊标记通过块内偏移量,33,2、跨块 vs.不跨块

9、,Unspanned:记录必须在一个块中存储block 1 block 2.Spanned：记录可跨块存储block 1 block 2.,R1,R2,R1,R3,R4,R5,R2,R3(a),R3(b),R6,R5,R4,R7(a),34,2、跨块 vs.不跨块,跨块,Whats the rest?,From where?,35,2、跨块 vs.不可跨块,比较unspanned：实现简单，但空间浪费spanned：有效利用空间，实现更复杂But If record size block size，MUST be spanned,36,3、不同类型的记录聚簇,一个块中存储不同类型的记录（对于R

10、DB：多关系上的聚簇）好处聚簇(clustering)经常一起访问的记录存储在同一块或连续块中,A Dept Record,A Employee Record,A Employee Record,A Block,37,3、不同类型的记录聚簇,学号s1,其他列,学号S1S1s1,其他列,课程号C1C2c3,学号s2,其他列,学号S2S2s2,其他列,课程号C2C5c6,学生表与课程表通过簇键“学号”聚簇,Block,38,3、不同类型的记录聚簇,Q1:select student.s#,ame from student s,sc where s.s#=sc.s#Q2:select*from st

11、udent,如果Q1经常被查询，则聚簇非常有效若Q2经常被查询，则聚簇反而降低了效率,STUDENT(s#,sname,age)SC(s#,cname,score),39,4、在块中按序存储记录,另一种聚簇(对于RDB：单关系上的聚簇)将记录按某个字段顺序排列在块中好处加快按排序字段查询记录时的效率利于归并联接（will be discussed later）,40,4、在块中按序存储记录,按Dept顺序组织的Student记录,无序组织的Student记录,假设一个磁盘块2条定长记录,41,4、在块中按序存储记录,物理连续指针连接,Next(R1),R1,R1,R2,Next(R1),42,

12、5、记录的分裂,适合于变长记录的混合格式表示定长部分存储于某个块中变长部分存储于另一个块中与spanned存储类似,43,6、记录地址,物理地址逻辑地址（间接地址）,44,6、记录地址,记录的纯物理地址主机标识 磁盘或其他设备标识柱面号磁头号（盘面号）块号 块内的偏移量,块地址,45,6、记录地址,记录的纯逻辑地址,物理地址,逻辑地址,映射表,记录地址,纯物理地址,缺点访问代价增加：映射表占存储空间；需要地址转换好处灵活性：删除或移动记录时只要改变映射表项,46,6、记录地址,记录的纯物理地址,记录的纯逻辑地址,tradeoff,47,6、记录地址,借助文件系统的逻辑块地址文件号逻辑块地址块内

13、偏移,文件系统映射,File IDBlock(logical),Block(physical)+offset,记录地址,48,四、记录的修改,插入删除,49,1、插入,记录无序插入到任意块的空闲空间中或申请一个新块（当所有块都已满时）记录变长时，可使用偏移量表,50,1、插入,记录有序找到记录应该放置的块如果有空间，放入并调节记录顺序即可，否则有两种方法：在“邻近块”中找空间 创建溢出块,51,2、删除,立即回收空间例如，加到可用空间列表中删除记录时处理溢出块若删除的记录位于溢出块链上，则删除记录后可对整个链进行重新组织以去除溢出块,52,2、删除,使用删除标记若使用偏移表，则可以修改偏移表项

14、指针，将其置空若使用逻辑物理地址映射表，则可以将物理地址置空可以在记录首部预留一开始位：0未删除，1已删除,1,记录1,0,记录2,53,Where are we?,数据项,记录,块,文件,We are here！,54,五、块在文件中的组织,堆文件（Heap File）最基本、最简单的文件结构记录不以任何顺序排序记录可能存放在物理不邻接的块上插入容易，但查找和删除代价高,55,1、链表式堆文件组织,首块,数据块,数据块,数据块,数据块,数据块,数据块,含空闲空间的块链表,满块链表,56,2、目录式堆文件组织,数据块1,数据块2,数据块N,首块,57,回顾：数据元素的表示层次,数据项,记录,块

15、,文件,属性值的物理组织,元组的物理组织,记录的物理存放,文件由磁盘块构成,58,六、SQL Server的数据存储结构,SQL Server的数据库文件是多个对象的集合，包括多个表、索引等参阅SQL Server联机丛书SQL Server数据库引擎-高级数据库引擎详细信息,59,1、页,在SQL Server中，数据存储的基本单位是页。在 SQL Server 2005 中，页的大小是 8 KB。每页的开头 96 字节，用于存储有关页的系统信息，包括页码、页类型、页的可用空间以及拥有该页的对象的分配单元 ID,96字节,单个数据行最大8060字节,页地址：数据行地址：,60,2、区,区是管

16、理空间的基本单位。一个区是八个物理上连续的页（即 64 KB）。为了使空间分配更有效，SQL Server 2005 对只含少量数据的表不分配完整的区。SQL Server 2005 有两种类型的扩展盘区：统一区：由单个对象所有，区中的所有8页只能由拥有该盘区的对象使用。混合区：最多可由 8 个对象共享。通常从混合区中向新表或新索引分配页。当表或索引增长到 8 页时，就变成统一扩展盘区。,61,2、区,混合区和统一区,62,3、SQL Server文件组织,SQL Server 2005 数据库有三种类型的文件：主要数据文件 主要数据文件是数据库的起点，指向数据库中文件的其它部分。每个数据库都

17、有一个主要数据文件。主要数据文件的推荐文件扩展名是.mdf。次要数据文件 次要数据文件包含除主要数据文件外的所有数据文件。有些数据库可能没有次要数据文件，而有些数据库则有多个次要数据文件。次要数据文件的推荐文件扩展名是.ndf。日志文件 日志文件包含恢复数据库所需的所有日志信息。每个数据库必须至少有一个日志文件，但可以不止一个。日志文件的推荐文件扩展名是.ldf。,63,3、SQL Server文件组织,64,3、SQL Server文件组织,数据文件页数据文件的页按顺序编号，文件首页的页码是 0。每个文件都有一个文件 ID 号。在数据库中唯一标识一页需要同时使用文件 ID 和页码。,65,3

18、、SQL Server文件组织,数据文件的起始结构,66,3、SQL Server文件组织,数据文件的起始结构PFS页：页可用空间(PFS)页记录每页的分配状态，是否已分配单个页以及每页的可用空间量。PFS 对每页都有一个字节，记录该页是否已分配。如果已分配，则记录该页是为空、已满 1%到 50%、已满 51%到 80%、已满 81%到 95%还是已满 96%到 100%。,67,3、SQL Server文件组织,数据文件的起始结构GAM页：全局分配映射表(GAM)页记录已分配的区。每个 GAM 包含 64,000 个区，相当于近 4 GB 的数据。GAM 用一个位来表示所涵盖区间内的每个区的

19、状态。如果位为 1，则区可用；如果位为 0，则区已分配。,68,3、SQL Server文件组织,数据文件的起始结构SGAM 页：共享全局分配映射表(SGAM)页记录当前用作混合区且至少有一个未使用的页的区。每个 SGAM 包含 64,000 个区，相当于近 4 GB 的数据。SGAM 用一个位来表示所涵盖区间内的每个区的状态。如果位为 1，则区正用作混合区且有可用页。如果位为 0，则区未用作混合区，或者虽然用作混合区但其所有页均在使用中。,69,3、SQL Server文件组织,数据文件的起始结构,若要分配统一区，将在 GAM 中搜索是 1 的位，然后将它设成 0。若要查找有可用页的混合区，

20、将在 SGAM 中搜索是 1 的位。若要分配混合区，将在 GAM 中搜索是 1 的位，并将它设置为 0，然后将 SGAM 中相应的位也设置为 1。若要释放扩展盘区，SQL Server 应确保 GAM 位设置为 1 而且 SGAM 位设置为 0。,70,3、SQL Server文件组织,表（Table）的组织,索引分配映射表(IAM)页记录了分配给对象的区。,71,3、SQL Server文件组织,表（Table）的组织IAM 页根据需要分配给每个对象，在文件中的位置也是随机的。系统视图(sys.system_internals_allocation_units)指向对象的第一个 IAM 页。

21、该分配单元的所有 IAM 页都链接到一个链中。,72,3、SQL Server文件组织,表（Table）的组织IAM 页有一个标头，指明 IAM 页所映射的区范围的起始区。IAM 页中还有一个大位图，其中每个位代表一个区。位图中的第一个位代表范围内的第一个区，第二个位代表第二个区，依此类推。如果某个位是 0，它所代表的区将不会分配给拥有该 IAM 页的分配单元。如果这个位是 1，它所代表的区将被分配给拥有该 IAM 页的分配单元。当 需要插入新行而当前页没有可用空间时，SQL Server 使用 IAM 页查找分配给对象的区。对于每个区，SQL Server 搜索 PFS 页以查看是否有一页具

22、有足够的空间容纳这一行。IAM 和 PFS 页通常位于内存中的 SQL Server 缓冲池中,73,七、Oracle的数据存储结构,Oracle数据库空间的分配单位有数据块（Data Block），数据扩展（Extent），和段（Segment）。参阅Oracle Concepts,74,1、块（Block）,数据块（Data Blocks，也称为页）是Oracle存储数据的最小单位。数据库中标准的数据块（data block）容量是由初始化参数 DB_BLOCK_SIZE 指定的，常见大小：2KB、4KB、8KB、16KB。,如块地址，段类型等,数据块的行目录区（row directory

23、）空间被使用后，即使数据行被删除，行目录区空间也不会被回收。,如果数据块属于表或集群的数据段（data segment），或属于索引的索引段（index segment），其可用空间区中还可能会存储事务条目。当数据块中的数据行正在由 INSERT，UPDATE，DELETE，及 SELECT.FOR UPDATE 语句访问，此数据块中就需要保存事务条目。,75,1、扩展区（Extent）,扩展区（extent）是由一组连续的数据块构成的数据库逻辑存储分配单位。当用户创建数据表时，Oracle为此表的数据段（data segment）分配一个包含若干数据块（data block）的初始扩展区（i

24、nitial extent）。,76,1、段（Segment）,段（segment）由一组扩展区（extent）构成。每个段的段头（header block）中包含一个记录此段所有扩展区（extent）的目录。用户使用 CREATE 语句创建表或簇表时，Oracle创建相应的数据段（data segment）。,77,2、表空间（tablespace）,Oracle中的数据逻辑上存储于表空间（tablespace）中，而物理上则存储于属于表空间的数据文件（datafile）中。Oracle数据库中每个表空间都是由一个或多个物理数据文件构成的。一个数据文件只能由一个数据库的一个表空间使用。,78

25、,2、表空间（tablespace）,数据库是由一个或多个被称为表空间（tablespace）的逻辑存储单位构成。表空间内的逻辑存储单位为段（segment），段又可以继续划分为数据扩展（extent）。而数据扩展是由一组连续的数据块（data block）构成。,79,3、表空间管理,数据字典管理（dictionary managed）用两个数据字典来保存表空间的区间使用信息，UET$（已使用的区间）和FET$（空闲空间）。Oracle 8i以前本地管理（locally managed）将存储信息保存在表空间头部的位图。Oracle在为新的数据扩展（extent）寻找可用空间时，首先选择一个

26、属于此表空间的数据文件（datafile），再搜索此数据文件的位图（bitmap）查找连续的数据块（free block）。如果此数据块中没有足够的连续可用空间，Oracle将查询其他数据文件。,80,八、缓冲区管理器,81,八、缓冲区管理器,Buffer PoolFrame（Bucket）Block is maintained.,82,1、frame的参数,DirtyFrame中的块是否已经被修改Pin-countFrame的块的已经被请求并且还未释放的计数，即当前的用户数被钉住的块（Pinned Blocks）不允许写回磁盘,83,2、当请求块时,If requested block is

27、 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 framePin(increment the pin-count of the frame)the block and return its address.,If requests can be predicted(e.g.,sequential scans)b

28、locks can be pre-fetched several blocks at a time!,84,2、当释放块时,Requestor must unpin the frame containing the blockRequestor must indicate whether block has been modified:dirty bit is used for this.,85,3、缓冲区替换策略,Frame is chosen for replacement by a replacement policy:Least-recently-used(LRU),Clock,FIF

29、O,MRU(Most-recently-used)etc.Only frames whose pin-count=0 are candidatesPolicy can have big impact on#of I/Os;depends on the access pattern.,86,3、缓冲区替换策略,LRU(Oracle,Sybase,Informix)当Pin-count为0时，frame放入替换队列选择队列头的frame替换Clock(MS SQL Server)N个frame组成环形，current指针指向当前frame；每个frame有一个referenced位，它在pin-c

30、ount=0时启动；从current开始检查，若pin-count0，current增加1；若referenced已启动，则关闭它并增加current（保证最近的不被替换）；若pin-count=0并且referenced关闭，则替换,87,4、为何不使用OS缓冲区管理？,DBMS经常能预测访问模式(Access Pattern)可以使用更专门的缓冲区替换策略有利于pre-fetch策略的有效使用DBMS需要强制写回磁盘能力（如WAL），OS的缓冲写回一般通过记录写请求来实现（来自不同应用），实际的磁盘修改推迟，因此不能保证写顺序,88,5、错误的记录操作实现例子,例如，插入记录 int in

31、sert_record(DBFILE*,DBRECORD)fopen()fseek()fwrite()没有DBMS自己的缓冲区管理和存储管理直接基于文件系统，使用了FS的缓冲管理不能保证WAL不利于查询优化不适应应用需求,89,6、Block vs.Disk File,Disk File文件存储在磁盘上的物理形式是bits/bytes，block是由OS或DBMS软件对文件所做的抽象，这一抽象是通过控制数据在文件中的起止offset来实现的,Block#1,Block#2,90,6、Buffer vs.Disk File,Bufferset of frames,Fileset of pages

32、,缓冲区管理器,存储管理器,page/block,frame,通常，frame大小page大小,CPU,refers to,91,7、Buffer Size,设计DBMS时应是一个可变的输入参数通常DBMS允许用户自行配置,92,8、Buffer的存储结构,Buffer是一个frame的列表，每个frame用于表示和存放一个磁盘块,#define FRAMESIZE 4096struct bFrame Char field FRAMESIZE;,#define BUFSIZE 1024/frame数目bFrame bufBUFSIZE;/也可以是用户配置的值,Buffer的存储结构定义示例,9

33、3,9、Page/block的一般存储格式,对于定长记录记录地址rid通常使用表示,N,1 0 1 0 1 M,槽 1,槽 M,槽 2,M 3 2 1,记录数,槽数,空闲空间,块头,94,9、Page/block的一般存储格式,Record的存储结构,struct Record int page_id;int slot_num;,95,10、Buffer中的Frame存储结构,Frame,MAX:BUFSIZE*FRAMESIZE,96,10、Buffer中的Frame存储结构,struct Frameint frame_id;int offset;,97,11、Buffer中Frame的查找

34、,读磁盘块时：根据page_id确定在Buffer中是否已经存在frame写磁盘块时：要根据frame_id快速找到文件中对应的page_id,98,11、Buffer中Frame的查找,首先，要维护Buffer中所有frame的维护信息（Buffer Control Blocks），如,struct BCB BCB();int page_id;int frame_id;int count;int time;int dirty;BCB*next;,99,11、Buffer中Frame的查找,建立frame-page之间的索引若用Hash Table，需要建立2个BCB hTableBuffer

35、Size/page 2 frame int hTableBufferSize/frame 2 page,一个简单的Hash Function例子H(k)=(page_id)%(buffersize),100,12、Buffer Manager的基本功能,FixPage(int page_id)将对应page_id的page读入到buffer中。如果buffer已满，则需要选择换出的frame。FixNewPage()在插入数据时申请一个新page并将其放在buffer中。SelectVictim()选择换出的frame_idFindFrame(int page_id)查找给定的page是否已经

36、在某个frame中了SetDirty(int frame_id),101,13、数据库文件的一般组成,数据文件首块在Insert_Record时创建（调用Buffer Manager的FixNewPage），一般块号从0开始系统目录文件首块一般Create_Table时创建（调用Buffer Manager的FixNewPage）,Note：所有数据和元数据操作都唯一通过Buffer Manager来请求page,102,14、文件记录操作与Buffer Manager,文件、记录、索引管理：Insert_Record,Delete_Record,Create_Table,Drop_Table

37、,Create_Index,Buffer Manager：FindFrame,FixPage,FixNewPage,SetDirty,SetVictim,record请求,frame请求,103,15、存储管理器,文件、记录、索引管理：Insert_Record,Delete_Record,Create_Table,Drop_Table,Create_Index,Buffer Manager：FindFrame,FixPage,FixNewPage,SetDirty,SetVictim,record请求,frame请求,page请求,Storage Manager,104,15、存储管理器,p

38、age请求,Storage Manager,Database File,disk file I/O,105,16、存储管理器功能,从磁盘中存取物理数据，为Buffer Manager提供Page抽象OpenFile/CloseFileReadPage/WritePageFileSeekGetNumPagesIncreaseNumPages,106,File、Record&Access Methods,Buffer ManagerFixPage(int page_id)FixNewPage()SelectVictim()Hash(int page_id)SetDirty(int frame_id),Storage ManagerOpenFile(string filename)CloseFile()ReadPage(int page_id)WritePage(int frame_id,bFrame frm)FileSeek(int offset,int pos)IncNumPages()GetNumPages(),Buffer(Main Memory),总体结构图,107,总结,数据项的表示记录的表示记录在块中的组织记录的修改块在文件中的组织缓冲区管理,108,