数据库的存储结构ppt课件

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 i记录记录4(剩余部剩余部分分)记录记录5 5记录记录6 6记录记录7 7块块i+1i+1记录记录1记录记录2 2记录记录3 3块块i i记录记录3(剩剩余部分余部分)记录记录4 4记录记录5 5块块i+1i+15.2.3 物理块在磁盘上的分配物理块在磁盘上的分配1 1、延续分配法、延续分配法contiguous allocationcontiguous allocation 将一个文件的块分配在磁盘的延续空间上，将一个文件的

5、块分配在磁盘的延续空间上，块的次序就是其存储的次序，有利于顺序存取块的次序就是其存储的次序，有利于顺序存取多块文件，不利于文件的扩展。多块文件，不利于文件的扩展。IBM PC/XT0000#原始数据原始数据IBM PC/XT 00001IBM PC/XT 00002紧缩数据紧缩数据#1#2索引法例如：索引法例如：BeijingNanjingShanghaiCITYCITY表表SHOP#CITY0001Nanjing0002Nanjing0003Nanjing0004Shanghai原始数据原始数据0005ShanghaiSHOP#CITY0001000200030004紧缩数据紧缩数据0005

6、 不同类型的访问各有其运用的文件构造和不同类型的访问各有其运用的文件构造和存取途径。存取途径。DBMSDBMS通常提供多种文件构造，供数通常提供多种文件构造，供数据库设计者选用。据库设计者选用。1.1.堆文件堆文件heap fileheap file2.2.直接文件直接文件direct filedirect file3.3.索引文件索引文件indexed fileindexed file堆堆文文件件记录记录1 1记录记录6 6记录记录2 2记录记录1 1记录记录2 2记录记录3 3记录记录5 5记录记录6 6记录记录4 4堆堆文文件件记录记录1 1记录记录3 3记录记录5 5记录记录6 6记录

7、记录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记录记录4 4记录记录7 7记录记录8 8记录记录2 2堆堆文文件件记录记录1 1记录记录3 3记录记录5 5记录记录7 7记录记录8 8集

8、中删除集中删除记录，并记录，并进展记录进展记录重排重排 处理方法处理方法Student(SNO,SNAME,SEX,BIRTHDATE,DEPT)Student(SNO,SNAME,SEX,BIRTHDATE,DEPT)散列函数散列函数 H(SNO)=Address900412900412李林李林计算机系计算机系 H(900412)=addraddr存储空间存储空间900412900412李林李林计算机系计算机系 索引相当于一个映射机构，把关系中相应记录索引相当于一个映射机构，把关系中相应记录的某个些属性的键值转换为该记录的存储地的某个些属性的键值转换为该记录的存储地址或地址集。址或地址集。a

9、ddr1addr2addr3SNOSNOAddressAddress学生表的索引文件学生表的索引文件900412900412addr2900417900417addr1900418900418addr3存储空间存储空间900418900418周力周力计算机系计算机系900412900412李林李林计算机系计算机系900417900417陈燕陈燕计算机系计算机系 针对非散列键和非索引属性的访问，都不能有效发扬直针对非散列键和非索引属性的访问，都不能有效发扬直接文件或索引文件的优势。散列或索引失效时，两者谁的访接文件或索引文件的优势。散列或索引失效时，两者谁的访问代价更大？问代价更大？n非稠密索引

10、与稠密索引非稠密索引与稠密索引1.1.不为每个键值设立索引项的索引不为每个键值设立索引项的索引非稠密索引非稠密索引2.2.可以节省索引的存储空间，代价是文件要按索引可以节省索引的存储空间，代价是文件要按索引键排序键排序3.3.对一个文件，只能为一个索引键普通为主键对一个文件，只能为一个索引键普通为主键建立非稠密索引为什么？建立非稠密索引为什么？例如例如查找索引键为查找索引键为211的记录的存储地址的记录的存储地址2117211 稠密索引稠密索引dense indexdense index 从数据构造角度看：静态索引是个多分树；动态索从数据构造角度看：静态索引是个多分树；动态索引是一种平衡多分树

11、即引是一种平衡多分树即B-B-树，常用树，常用B+B+树。树。 B+树的限制和规定：树的限制和规定：q 每个节点最多有每个节点最多有2k个键值，个键值，k称为称为B+树的秩树的秩(Order);q 根节点至少有一个键值，其它节点至少有根节点至少有一个键值，其它节点至少有k个键值个键值,节点内，键值有序存放节点内，键值有序存放;q 除叶节点无子女外，其它节点假设有除叶节点无子女外，其它节点假设有J个键值，那个键值，那么有么有J+1个子女个子女;q 一切叶节点都处于树的同一层，即树一直坚持平衡。一切叶节点都处于树的同一层，即树一直坚持平衡。102015 从根向叶搜索，直至相应从根向叶搜索，直至相应

12、叶节点，假设该叶节点不满，叶节点，假设该叶节点不满，那么将键值插入叶节点中；如那么将键值插入叶节点中；如叶节点已满即曾经有叶节点已满即曾经有2K2K个键个键值，那么将此叶节点分裂为值，那么将此叶节点分裂为二，叶节点分裂后，其双亲节二，叶节点分裂后，其双亲节点也必需添加一个键值，假设点也必需添加一个键值，假设双亲节点不满，插入过程终了双亲节点不满，插入过程终了；否那么双亲节点继续分裂为；否那么双亲节点继续分裂为两个节点，如此继续直到插入两个节点，如此继续直到插入过程中止。过程中止。插入算法：插入算法：(K=1): 10，15，20，25，30，35，40，50101510, 15202520,2

13、5301015203025201015,253015253510203040,50 先从根节点出发，找到先从根节点出发，找到待删除键值所在叶节点；假待删除键值所在叶节点；假设删除该键值后，叶节点中设删除该键值后，叶节点中键值数减为键值数减为K-1K-1个，那么向个，那么向其左右兄弟叶节点借一个键其左右兄弟叶节点借一个键值，以坚持每个叶节点存放值，以坚持每个叶节点存放键值不少于键值不少于K K个；假设其左个；假设其左右叶节点都只需右叶节点都只需K K个键值，个键值，那么可将该叶节点与其左那么可将该叶节点与其左或右叶节点合并成包含或右叶节点合并成包含2K-12K-1个键值的叶节点，合并个键值的叶节

14、点，合并后，其双亲节点要减少一个后，其双亲节点要减少一个键值，有能够导致双亲节点键值，有能够导致双亲节点的合并。的合并。删除算法：删除算法：15253510203040,501010,153525,3510,153040,50 SHST索引集索引集顺序集顺序集节点类型节点类型块中索引键数块中索引键数0P0K1P1K1nKnP索引集节索引集节点点0K0tid1K1tidnKntid顺序集节顺序集节点点注：注：1.1.节点普通是一个物理块。节点普通是一个物理块。2.2.元组标识符元组标识符tidtid，实践上是记录的地址，由块号和记录在块中，实践上是记录的地址，由块号和记录在块中的指针号组成运用记

15、录在块中的指针号表示记录在块中的位置，的指针号组成运用记录在块中的指针号表示记录在块中的位置，好于直接用记录在块中的地址，方便记录在块内挪动。好于直接用记录在块中的地址，方便记录在块内挪动。 P0K0Ki-1PiKiKn-1PnKxKxKx留意：索引集节点中的键值不一定是文件中留意：索引集节点中的键值不一定是文件中当前存在的键值仅起当前存在的键值仅起“导航路标的作导航路标的作用。在搜索过程中，即使发现索引集节点用。在搜索过程中，即使发现索引集节点中的键值等于要找的键值，查找仍要按上述中的键值等于要找的键值，查找仍要按上述规那么进展下去。规那么进展下去。问题：假设在某个索引集结点中找到了待查问题

16、：假设在某个索引集结点中找到了待查找记录相应的索引键值，能否还要继续遍历找记录相应的索引键值，能否还要继续遍历B+B+树，为什么？树，为什么？0P0KiP1iKiKnP1nK0sK0tidsjKjtid)1( nsK1ntid顺序集节点中的键值要满足如下关系：顺序集节点中的键值要满足如下关系：假设假设Pi=P0Pi=P0，那么，那么Ks0Ks1Ks(n-1)K0;Ks0Ks1Ks1Ks0Kn-1;Ks(n-1)Ks1Ks0Kn-1;否那么：否那么：Ki-1Ks0Ks1Ks(n-1)Ki .Ki-1Ks0Ks1Ks(n-1)Ki .nB+B+树实现的主索引稍加修正后也可用于次索引把顺树实现的主索

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