数据库原理第五章

1、第五章第五章 数据库的存储结构数据库的存储结构 数据库是大量、持久数据的集合，在现阶段数据库是大量、持久数据的集合，在现阶段用内存作为数据库的存储介质是不合适的用内存作为数据库的存储介质是不合适的。n活动头磁盘的存取时间由三部分组成：活动头磁盘的存取时间由三部分组成：寻道寻道时间时间、等待时间以及传输时间。、等待时间以及传输时间。n磁盘上的数据划分为大小相等的物理块。磁磁盘上的数据划分为大小相等的物理块。磁盘与内存间的数据交换以物理块为单位。盘与内存间的数据交换以物理块为单位。n一般，在磁盘和内存之间设立缓冲区以解决一般，在磁盘和内存之间设立缓冲区以解决二者的速度不匹配问题。二者的速度不匹配问

2、题。 由于有多个缓冲块可供申请使用，磁盘的读写由于有多个缓冲块可供申请使用，磁盘的读写操作和读写数据的处理可以重叠进行。操作和读写数据的处理可以重叠进行。读出：读出：i块块缓冲块缓冲块A处理：处理：处理处理A中中i块块i+1块块缓冲块缓冲块B i+2块块缓冲块缓冲块A处理处理B中中i+1块块n记录是目前商用数据库的基本数据单元，有定记录是目前商用数据库的基本数据单元，有定长和变长之分。长和变长之分。n记录的存储结构记录的存储结构LIbbbMINGbbbMALEbb196751218LI?MING?MALE?1967#问题：问题：字段中也需要用到这些分隔符时，如何进行字段中也需要用到这些分隔符时

3、，如何进行表示？表示？02LI04MING04MALE041967问题：计数法对问题：计数法对字段的实际长度字段的实际长度有什么要求？有什么要求？5.2.2 记录在物理块上的分配记录在物理块上的分配设为物理块的有效空间大小，为固定长记设为物理块的有效空间大小，为固定长记录的大小，若录的大小，若，则每个物理块可容纳的记录，则每个物理块可容纳的记录数为：数为：p=B/Rp称为块因子（称为块因子（Blocking Factor）。）。 记录一般不会刚好填满物理块，会留下不用的零头记录一般不会刚好填满物理块，会留下不用的零头空间：空间：BpRR 为了利用这部分空间，可以利用记录的跨块存储组为了利用这部

4、分空间，可以利用记录的跨块存储组织织(spanned organization)。记录记录1记录记录2 2记录记录3 3记录记录4 4记录记录1记录记录2 2记录记录3 3记录记录4 4块块i记录记录4(剩余部剩余部分分)记录记录5 5记录记录6 6记录记录7 7块块i i+1记录记录1记录记录2 2记录记录3 3块块i记录记录3(剩剩余部分余部分)记录记录4 4记录记录5 5块块i i+15.2.3 物理块在磁盘上的分配物理块在磁盘上的分配1 1、连续分配法（、连续分配法（contiguous allocationcontiguous allocation） 将一个文件的块分配在磁盘的连续空

5、间上，将一个文件的块分配在磁盘的连续空间上，块的次序就是其存储的次序，块的次序就是其存储的次序，有利于顺序存取有利于顺序存取多块文件，不利于文件的扩充多块文件，不利于文件的扩充。 每个文件有一个逻辑块号与其物理块地址对每个文件有一个逻辑块号与其物理块地址对照的索引。照的索引。IBM PC/XT0000#原始数据原始数据IBM PC/XT 00001IBM PC/XT 00002压缩数据压缩数据#1#2索引法示例：索引法示例：BeijingNanjingShanghaiCITYCITY表表SHOP#CITY0001Nanjing0002Nanjing0003Nanjing0004Shanghai

6、原始数据原始数据0005ShanghaiSHOP#CITY0001000200030004压缩数据压缩数据0005 不同类型的访问各有其使用的文件结构和不同类型的访问各有其使用的文件结构和存取路径。存取路径。DBMSDBMS通常提供多种文件结构，供数通常提供多种文件结构，供数据库设计者选用。据库设计者选用。1.1.堆文件（堆文件（heap fileheap file）2.2.直接文件（直接文件（direct filedirect file）3.3.索引文件（索引文件（indexed fileindexed file）堆堆文文件件记录记录1 1记录记录6 6记录记录2 2记录记录1 1记录记录2

7、 2记录记录3 3记录记录5 5记录记录6 6记录记录4 4堆堆文文件件记录记录1 1记录记录3 3记录记录5 5记录记录6 6记录记录4 4记录记录7 7记录记录8 8记录记录2 2 假设，要删除右图堆文件中假设，要删除右图堆文件中的第的第2，4，6条数据记录。条数据记录。 直接删除这三条记录的情况直接删除这三条记录的情况如右图所示。如右图所示。 带来什么问题？带来什么问题？作删除作删除标记标记堆堆文文件件记录记录1 1记录记录2 2记录记录3 3记录记录5 5记录记录6 6记录记录4 4记录记录7 7记录记录8 8堆堆文文件件记录记录1 1记录记录3 3记录记录5 5记录记录6 6记录记录

8、4 4记录记录7 7记录记录8 8记录记录2 2堆堆文文件件记录记录1 1记录记录3 3记录记录5 5记录记录7 7记录记录8 8集中删除集中删除记录，并记录，并进行记录进行记录重排重排 解决方法解决方法Student(SNO,SNAME,SEX,BIRTHDATE,DEPT)Student(SNO,SNAME,SEX,BIRTHDATE,DEPT)散列函数散列函数 H(SNO)=Address900412900412李林李林计算机系计算机系 H(900412900412)=addraddr存储空间存储空间900412900412李林李林计算机系计算机系 索引相当于一个映射机构，把关系中相应记

9、录索引相当于一个映射机构，把关系中相应记录的某个（些）属性的键值转换为该记录的存储地的某个（些）属性的键值转换为该记录的存储地址（或地址集）。址（或地址集）。addr1addr2addr3SNOSNOAddressAddress学生表的索引文件学生表的索引文件900412900412addr2900417900417addr1900418900418addr3存储空间存储空间900418900418周力周力计算机系计算机系900412900412李林李林计算机系计算机系900417900417陈燕陈燕计算机系计算机系 针对非散列键和非索引属性的访问，都不能有效发挥直针对非散列键和非索引属性的访

10、问，都不能有效发挥直接文件或索引文件的优势。散列或索引失效时，两者谁的访接文件或索引文件的优势。散列或索引失效时，两者谁的访问代价更大？问代价更大？n非稠密索引与稠密索引非稠密索引与稠密索引1.1.不为每个键值设立索引项的索引不为每个键值设立索引项的索引非稠密索引非稠密索引2.2.可以节省索引的存储空间，代价是文件要按索引可以节省索引的存储空间，代价是文件要按索引键排序键排序3.3.对一个文件，只能为一个索引键（一般为主键）对一个文件，只能为一个索引键（一般为主键）建立非稠密索引建立非稠密索引（为什么？）（为什么？）示例示例查找索引键为查找索引键为211的记录的存储地址的记录的存储地址2117

11、211 稠密索引稠密索引（dense indexdense index） 从数据结构角度看：静态索引是个多分树；动态索从数据结构角度看：静态索引是个多分树；动态索引是一种平衡多分树（即引是一种平衡多分树（即B-B-树），常用树），常用B+树。树。 B+树的限制和规定：树的限制和规定：q 每个节点最多有每个节点最多有2k个键值，个键值，k称为称为B+树的秩树的秩(Order);q 根节点至少有一个键值，其它节点至少有根节点至少有一个键值，其它节点至少有k个键值个键值,节点内，键值有序存放节点内，键值有序存放;q 除叶节点无子女外，其它节点若有除叶节点无子女外，其它节点若有J个键值，则有个键值，则

12、有J+1个子女个子女;q 所有叶节点都处于树的同一层，即树始终保持平衡。所有叶节点都处于树的同一层，即树始终保持平衡。102015 从根向叶搜索，直至相应从根向叶搜索，直至相应叶节点，若该叶节点不满，则叶节点，若该叶节点不满，则将键值插入叶节点中；如叶节将键值插入叶节点中；如叶节点已满（点已满（即已经有即已经有2 2K K个键值个键值），则将此叶节点分裂为二，叶则将此叶节点分裂为二，叶节点分裂后，其双亲节点也必节点分裂后，其双亲节点也必须增加一个键值须增加一个键值，若双亲节点，若双亲节点不满，插入过程结束；否则双不满，插入过程结束；否则双亲节点继续分裂为两个节点，亲节点继续分裂为两个节点，如此

13、继续直到插入过程中止。如此继续直到插入过程中止。插入算法：插入算法：(K=1): 10，15，20，25，30，35，40，50101510, 15202520,25301015203025201015,253015253510203040,50 先从根节点出发，找到先从根节点出发，找到待删除键值所在叶节点；若待删除键值所在叶节点；若删除该键值后，叶节点中键删除该键值后，叶节点中键值数减为值数减为K-1K-1个，则个，则向其左向其左右兄弟叶节点借一个键值，右兄弟叶节点借一个键值，以保持每个叶节点存放键值以保持每个叶节点存放键值不少于不少于K K个个；若其左右叶节；若其左右叶节点都只有点都只有K

14、 K个键值，则可个键值，则可将将该叶节点与其左（或右）叶该叶节点与其左（或右）叶节点合并成包含节点合并成包含2 2K-1K-1个键值个键值的叶节点，合并后，其双亲的叶节点，合并后，其双亲节点要减少一个键值节点要减少一个键值，有可，有可能导致双亲节点的合并。能导致双亲节点的合并。删除算法：删除算法：15253510203040,501010,153525,3510,153040,50 SHST索引集索引集顺序集顺序集节点类型节点类型块中索引键数块中索引键数0P0K1P1K1nKnP索引集节索引集节点点0K0tid1K1tidnKntid顺序集节顺序集节点点注：注：1.1.节点一般是一个物理块。节

15、点一般是一个物理块。2.2.元组标识符元组标识符tidtid，实际上是记录的地址，由块号和实际上是记录的地址，由块号和记录在块中记录在块中的指针号的指针号组成（使用组成（使用记录在块中的指针号记录在块中的指针号表示记录在块中的位置，表示记录在块中的位置，好于直接用记录在块中的地址，方便记录在块内移动）。好于直接用记录在块中的地址，方便记录在块内移动）。 P0K0Ki-1PiKiKn-1PnKxKxKx注意：注意：索引集节点中的键值索引集节点中的键值不一定不一定是文件中是文件中当前存在的键值（仅起当前存在的键值（仅起“导航路标导航路标”的作的作用）。在搜索过程中，即使发现索引集节点用）。在搜索过

16、程中，即使发现索引集节点中的键值等于要找的键值，查找仍要按上述中的键值等于要找的键值，查找仍要按上述规则进行下去。规则进行下去。问题：若在某个索引集结点中找到了待查找问题：若在某个索引集结点中找到了待查找记录相应的索引键值，是否还要继续遍历记录相应的索引键值，是否还要继续遍历B+B+树，为什么？树，为什么？0P0KiP1iKiKnP1nK0sK0tidsjKjtid)1( nsK1ntid顺序集节点中的键值要满足如下关系：顺序集节点中的键值要满足如下关系：如果如果Pi=P0，则则Ks0Ks1Ks1Ks0Kn-1; ;否则：否则：Ki-1Ks0Ks1Ks(n-1)Ki .nB B+ +树实现的主

17、索引稍加修改后也可用于次索引树实现的主索引稍加修改后也可用于次索引（把顺（把顺序集结点的序集结点的tidtid换成指针，因为一个键值可能对应多个换成指针，因为一个键值可能对应多个tidtid）。nB B+ +树实现的各种索引都是稠密索引（非稠密索引的概树实现的各种索引都是稠密索引（非稠密索引的概念源于静态索引），提供了顺序搜索的功能，这是它念源于静态索引），提供了顺序搜索的功能，这是它的优点。的优点。 设索引属性不同键值的数目为设索引属性不同键值的数目为N，若索引键不若索引键不是候选键，则记录数通常大于是候选键，则记录数通常大于N。 B+树的级数决定于树的级数决定于N，而不是记录数！而不是记录数！ 假设假设B+树索引部分共有树索引部分共有L级，其秩为级，其秩为k，则各级则各级的最小结点数依次为：的最小结点