《数据元素的表》ppt课件

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

1、第4章 数据元素的表示,主要内容,数据项的表示（Data Items） 记录的表示（Records） 记录在块中的组织（Block） 记录的修改 块在文件中的组织 缓冲区管理,数据元素的表示层次,数据项,记录,块,文件,属性值的物理组织,元组的物理组织,记录的物理存放,文件由磁盘块构成,一、数据项的表示,数据项 字节序列 表示关系数据库中元组的属性值,1、数据项表示的内容,表示什么？ 姓名 年龄 出生日期 照片 用什么表示？ Bytes,2、数据项表示方法：SQL数据类型,Integer (short) 2 bytes 例如，35 表示为 Real，Float 4 bytes （32 bits

2、） N bits表示小数，M bits表示指数,00000000,00100011,2、数据项表示方法：SQL数据类型,Char(n) 或 Character(n) 定长字符串 小于n时使用特殊填充符 例如，若属性类型为Char(5)，则属性值cat 表示为 Varchar(n) 变长字符串 NULL终止符，例 Varchar(5) 带长度 定长表示，n+1 bytes Varchar(4):,2、数据项表示方法：SQL数据类型,Boolean TRUE FALSE 枚举类型 RED,GREEN,YELLOW 整数表示 RED 1，GREEN 2，YELLOW 3 若用两个字节的短整型来表示，

3、则可以表示 216 个不同值,1111 1111,0000 0000,2、数据项表示方法：SQL数据类型,Date 10字符(SQL92)：YYYY-MM-DD字符串表示 8字符：YYYYMMDD 7字符：YYYYDDD, NOT YYMMDD！ Integer，自1900-01-01以来的天数 Time 8字符(SQL92)：HH:NN:SS 整数秒 Varchar(n)：HH:NN:SS.FF带小数秒 Integer，自00:00:00以来的秒数,2、数据项表示方法：SQL数据类型,Bit 带长度的二进制位串 按字节表示，例如 010111110011,Length,Bits,010111

4、11,00110000,3、两种不同的数据项表示,定长数据项 变长数据项 带长度 （常用!） Null Terminated,数据项表示总结,Where are we?,数据项,记录,块,文件,We are here！,二、记录的组织,记录 数据项 字段，Fields 的集合,E.g.: Employee record: name field, salary field, date-of-hire field, .,1、记录的类型,固定格式 vs. 可变格式 Fixed Format vs. Variable Format 定长 vs. 变长 Fixed Length vs. Variable

5、 Length,2、固定格式定长记录,所有记录具有相同的逻辑结构（模式） 记录的模式（Schema） # fields Name of each field Type of each field Order in record Offset of each field in the record,E.g. 固定格式定长记录,Employee record (1) E#, 2 byte integer (2) Ename, 10 char. Schema (3) Dept, 2 byte code,55,s m i t h,02,83,j o n e s,01,Records,2、固定格式定长记

6、录,构造 不考虑寻址特点,2、固定格式定长记录,考虑寻址特点 假设记录和字段的开始地址必须是4的倍数,3、记录首部,在记录首部（Head）的描述记录的信息 记录类型（模式信息） 记录长度 时间戳 其它信息,4、可变格式记录,每个记录的格式不同 记录的格式存储于记录中,E.g. 可变格式变长记录表示,字段数 字段E标识码 Integer 类型 字段 Ename标识码 String 类型 长度,Employee(E#, Ename),4、可变格式记录,好处 灵活的记录格式，适合“松散”记录 尽管一个记录可能有大量字段，但某个记录通常只有有限的几个字段 例如，病人的检验结果 适合处理重复字段 适合记

7、录格式演变 缺点 浪费存储空间,6、变长记录表示,首部指针法 定长字段在前，变长字段在后 name、address变长,6、变长记录表示,混合格式：定长记录变长记录,Where are we?,数据项,记录,块,文件,We are here！,三、记录在块中的组织,假设 块的大小固定 记录组织成单个文件,Block,A File,A Record,三、记录在块中的组织,定长记录的两种块内组织 记录地址rid通常使用表示,N,1 0 1 0 1 M,槽 1,槽 M,槽 2,M 3 2 1,记录数,槽数,空闲空间,块头,三、记录在块中的组织,变长记录在块内的组织,三、记录在块中的组织,其他问题 记

8、录在块中的分隔 (separating records) 记录跨块 vs.记录不跨块 (spanned vs. unspanned) 不同类型的记录聚簇 (mixed record types clustering) 按序组织 (sequencing) 记录的分裂 (split records) 记录地址 (record address) 记录的修改,1、记录在块内的分隔,定长记录：不需分隔 使用特殊标记 通过块内偏移量,2、跨块 vs. 不跨块,Unspanned: 记录必须在一个块中存储 block 1 block 2 . Spanned：记录可跨块存储 block 1 block 2 .

9、,R1,R2,R1,R3,R4,R5,R2,R3 (a),R3 (b),R6,R5,R4,R7 (a),2、跨块 vs. 不跨块,跨块,Whats the rest?,From where?,2、跨块 vs. 不可跨块,比较 unspanned：实现简单，但空间浪费 spanned：有效利用空间，实现更复杂 But If record size block size，MUST be spanned,3、不同类型的记录聚簇,一个块中存储不同类型的记录 （对于RDB：多关系上的聚簇） 好处聚簇 (clustering) 经常一起访问的记录存储在同一块或连续块中,A Dept Record,A Em

10、ployee Record,A Employee Record,A Block,3、不同类型的记录聚簇,学号 s1,其他列,学号 S1 S1 s1,其他列,课程号 C1 C2 c3,学号 s2,其他列,学号 S2 S2 s2,其他列,课程号 C2 C5 c6,学生表与课程表通过簇键“学号”聚簇,Block,3、不同类型的记录聚簇,Q1: select student.s#,ame from student s,sc where s.s# = sc.s# Q2: select * from student,如果Q1经常被查询，则聚簇非常有效 若Q2经常被查询，则聚簇反而降低了效率,STUDENT

11、(s#,sname,age) SC(s#,cname,score),4、在块中按序存储记录,另一种聚簇 (对于RDB：单关系上的聚簇) 将记录按某个字段顺序排列在块中 好处 加快按排序字段查询记录时的效率 利于归并联接 （will be discussed later）,4、在块中按序存储记录,按Dept顺序组织的Student记录,无序组织的Student记录,假设一个磁盘块2条定长记录,4、在块中按序存储记录,物理连续 指针连接,Next (R1),R1,R1,R2,Next(R1),5、记录的分裂,适合于变长记录的混合格式表示 定长部分存储于某个块中 变长部分存储于另一个块中 与span

12、ned存储类似,6、记录地址,物理地址 逻辑地址（间接地址）,6、记录地址,记录的纯物理地址 主机标识 磁盘或其他设备标识 柱面号 磁头号（盘面号） 块号 块内的偏移量,块地址,6、记录地址,记录的纯逻辑地址,物理地址,逻辑地址,映射表,记录地址,纯物理地址,缺点访问代价增加：映射表占存储空间；需要地址转换 好处灵活性：删除或移动记录时只要改变映射表项,6、记录地址,记录的纯物理地址,记录的纯逻辑地址,tradeoff,6、记录地址,借助文件系统的逻辑块地址 文件号逻辑块地址块内偏移,文件系 统映射,File ID Block(logical),Block(physical) + offset

13、,记录地址,四、记录的修改,插入 删除,1、插入,记录无序 插入到任意块的空闲空间中 或申请一个新块（当所有块都已满时） 记录变长时，可使用偏移量表,1、插入,记录有序 找到记录应该放置的块 如果有空间，放入并调节记录顺序即可，否则有两种方法： 在“邻近块”中找空间 创建溢出块,2、删除,立即回收空间 例如，加到可用空间列表中 删除记录时处理溢出块 若删除的记录位于溢出块链上，则删除记录后可对整个链进行重新组织以去除溢出块,2、删除,使用删除标记 若使用偏移表，则可以修改偏移表项指针，将其置空 若使用逻辑物理地址映射表，则可以将物理地址置空 可以在记录首部预留一开始位：0未删除，1已删除,1,

14、记录1,0,记录2,Where are we?,数据项,记录,块,文件,We are here！,五、块在文件中的组织,堆文件（Heap File） 最基本、最简单的文件结构 记录不以任何顺序排序 记录可能存放在物理不邻接的块上 插入容易，但查找和删除代价高,1、链表式堆文件组织,首块,数据块,数据块,数据块,数据块,数据块,数据块,含空闲空间 的块链表,满块链表,2、目录式堆文件组织,数据块1,数据块2,数据块N,首块,回顾：数据元素的表示层次,数据项,记录,块,文件,属性值的物理组织,元组的物理组织,记录的物理存放,文件由磁盘块构成,六、SQL Server的数据存储结构,SQL Serv

15、er的数据库文件是多个对象的集合，包括多个表、索引等,1、页,在SQL Server中，数据存储的基本单位是页。在 SQL Server 2000 中，页的大小是 8 KB。,96字节,单个数据行 最大8060字节,页地址： 数据行地址：,2、扩展盘区,扩展盘区是一种基本单元，可将其中的空间分配给表和索引。一个扩展盘区是 8 个邻接的页（或 64 KB）。 为了使空间分配更有效，SQL Server 2000 对只含少量数据的表不分配完整的扩展盘区。SQL Server 2000 有两种类型的扩展盘区： 统一扩展盘区：由单个对象所有，扩展盘区中的所有八页只能由拥有该盘区的对象使用。 混合扩展盘区：最多可由 8 个对象共享。 通常从混合扩展盘区中向新表或新索引分配页。当表或索引增长到 8 页时，就变成统一扩展盘区。,2、扩展盘区,混合扩展盘区和统一扩展盘区,3、SQL Server文件组织,SQL Server 2000 数据库有三种类型的文件： 主要数据文件 主要数据文件是数据库的起点，指向数据库中文件的其它部分。每个数据库都有一个主要数据文件。主要数据文件的推荐文件扩展名是 .mdf。 次要数据文件 次要数据文件包含除主要数据文件外的所有数据文件。有些数据库可能没有次要数据文件，而有些数据库则有多个次要数据文件。次要数据文件的推荐文件扩展名是 .ndf。 日志