数据库系统实现实现技术.

第九章数据库系统实现实现技术9.1数据库的存储结构存储介质内外存数据交换数据库引擎中的存储管理器，主要两个部件：缓冲区管理器和文件管理器。数据库运行时，内外存间要频繁地进行数据交换，每交换一次数据称为一次I/O操作。数据库系统需OS支持进行I/O。I/O操作是很慢的，数据调出外存要缓存在缓冲区中供后续的操作使用(读/写)。读不命中或写结果按策略更新时进行I/O。每次交换的数据量称为一个数据块，一个块可以等于一个或几个磁盘块。块大对顺序访问有利，对随机访问不利。内存中缓冲区的大是若干个数据块。数据库的存储结构磁盘冗余阵列(RAID)RAID是数据库服务器最常用的外存储介质，有若干同样的磁盘组成的阵列，从RAID0-RAID8有多种组合方式。通过冗余改善可靠性。同一数据同时写入两个磁盘若干个磁盘数据用一个磁盘保存校验位。通过数据条块化提高速度数据大体均匀地存放于若干磁盘上。当多用户请求数据库数据时，I/O操作可以随机地落在不同的磁盘，磁盘阵列并行I/O从而提高速度。备份数据和历史数据通过网络存储存放到物理上分离的地方(防火、水、震等)移动硬盘或光盘、磁带等大容量离线存储设备。数据库的存储结构文件内记录的存储数据库数据以文件形式在外存中存储。数据库的逻辑记录在物理文件中如何实现，是记录的存储方法问题。定长记录格式：每个数据库记录占有定长文件记录。例：Employer(Enamechar(10),eNochar(10),Salaryreal)设一个实数占8字节，则一个记录28字节，文件的逻辑机构为：删除操作空位处理其它记录依次上移最后记录填补空位被删空位链接、插入时用记录0LiuA-1026000记录1WenB-3067000记录2HeF-2578000记录3ZhangA-2146000记录4ZhouC-3437500记录5LiuB-2158000数据库的存储结构变长纪录：每条数据库记录长度不同例：Salsepson的属性adress是变长的Salseperson(empID:char(3),empName:char(8),sex:char(1),birthday:date,spTelNo:number(12),address:varchar(50))字符串格式：把每个数据库记录看作是连续的字节串，尾部加记录尾标记符。(大多数操作系统支持按行存取文件)下面的关系empIDempNamesexBirthdayspTelNoaddresssp1刘女士F70-1-20082354北京市宣武区牛街街道双槐里小区22楼2-101100028sp2李先生M67-5-2213146北京市海淀区玉泉路甲19号100049sp3何女士F62-9-7352210山东省日照市276534数据库的存储结构下述文件存储是字符串格式0sp1│刘女士│F│70-1-20│13900823542│北京市宣武区牛街街道双槐里小区22楼2-101│13701000281│┴│1sp2│李先生│M│67-5-22│13146092228│北京市海淀区玉泉路甲19号100049│┴│2sp3│何女士│F│62-9-7│13352210756│山东省日照市276534│┴│字符串格式的缺点被删除的位置难以重新利用。某记录要伸长很困难(移动大量记录)。改进：分槽式页结构(shottedpagestructure)记录从块的尾部邻接存放。中间是自由空间(伸长记录用)。块的开始是块首部，记录块中记录数、每个记录大小和位置。分槽式变长记录结构变长记录的定长表示预留空间(按最大)固定块+溢出块格式数据库的存储结构sp1刘女士F70-1-20082354sp2李先生M67-5-2213146sp3何女士F62-9-7352210北京市宣武区牛街街道双槐里小区22楼2-101100028┴北京市海淀区玉泉路甲19号100049┴山东省日照市276534┴固定块溢出块数据库的存储结构文件内记录的组织一个文件包含了成千上万个记录，这些记录按什么顺序或方式安排，是数据库记录在文件内的组织问题。对某种组织的文件怎样去查找、插入和删除，是文件中记录的存取方法问题。不同的组织方式存取效率有很大差别。记录的组织方式堆文件组织：记录可以放在文件的任何位置，以输入顺序为序。删除、插入操作不需移动数据。顺序文件组织：记录按查找键值的升序或降序的顺序逻辑存储的。一般使用指针链结构。散列文件组织(hashingfile)：某个属性值通过哈希函数求得的值作为记录的存储地址。聚类文件组织：一个文件可存储多个有联系的关系，有联系的记录存储在同一块内，以提高I/O速度。数据库的存储结构顺序文件组织记录的物理顺序和查找键值一致：插入、删除需移动数据。用指针逻辑链接：插入：找到键值位置；插入到空闲位置；修改指针；删除：修改指针；回收空闲位置。记录0HeF-257800记录1LiuB-2158000记录2LiuA-1026000记录3WenB-3067000记录4ZhangA-2146000记录5ZhouC-3437500记录0HeF-257800记录1LiuB-2158000记录2LiuA-1026000记录4WenB-3067000记录5ZhangA-2146000记录6ZhouC-3437500记录3MaB-547500数据库的存储结构聚类文件组织聚类文件的组织方式与查询的类型有关，一个文件内有两个或多个关系的记录类型。例：教学数据库中的关系S和SC，经常进行自然连接查询操作，如SELECTS.S#,Sname,C#,GradeFROMS,SCWHERES.S#=SC.S#当数据量很大时，两个文件内记录的连接操作是很慢的。聚类文件格式如右图：关系S和SCS#SnameAgeSexS1Liu21FS2Wang20MS3Chen22MS#C#GradeS1C180S1C270S3C190S3C285S3C395记录0S1Liu21FS1C180S1C270记录1S2Wang20M记录2S3Chen22MS3C190S3C285S3C395聚类文件数据库的存储结构索引技术当文件中记录的数目和数据量很大时，直接查找速度会很慢。必须建立索引机制。索引是独立于主文件记录的一个只含索引属性的小的文件，且按索引值排序，查找速度可很快。常用的索引或一、二级索引可以读入缓冲区以加快速度。索引分类有序索引：根据记录中某种排序顺序建立的索引。散列索引：根据记录中某个属性值，通过散列函数得到值作为存储空间的桶号。有序索引分类：主文件可建立几个索引文件。主索引(聚类索引)：索引的查找键值的顺序与主文件顺序一致。这种文件称作索引顺序文件。主索引只有一个。非聚类索引：索引的查找键值的顺序与主文件顺序不一致。数据库的存储结构主索引稠密索引：对于主文件中的每一个查找键值建立一个索引记录(索引项)，索引记录包括查找键值和指向具有该值的主文件中第一个记录的指针。例：稀疏索引：在主文件中，若个个查找键值才建立一个所以记录，索引记录的内容与稠密索引相同。例：要找到Liu，先找到He指向的主文件然后顺链找到Liu。HeF-2577000LiuB-2158000LiuA-1026000WenB-3067000ZhangA-2146000ZhangB-4676000ZhouC-3438000HeLiuWenZhangZhouHeZhang数据库的存储结构多级索引：即使采用稀疏索引，可能建成的索引还是很大，以致于查询效率不高。例：主文件100000个记录，每块可存储10个记录，需10000个数据块。若以块为单位建立稀疏索引，索引需10000项。虽然索引记录比主记录小得多，如每块可存100个索引项，索引块仍需100块，缓冲区就很难放得下。解决的办法是对主索引再建立一级索引，如图所示的二级索引。如果外层索引数据量还是太大，可建立3级、4级索引。多级索引可用B+树或B树实现。数据库的存储结构索引的更新删除：为了在主文件中删除一条记录，需①找到主文件记录，删除。②如果符合索引键值的记录有多个，索引不用修改。③否则，对稠密索引，删除相应的索引项；对稀疏索引，如果被删记录的索引值在索引块中出现，则用主文件被删记录的下一个记录的查找键A替换，若A已出现在索引块，则删除被删记录的对应多音键。插入：①用插入记录的查找键找到插入位置，执行主文件插入。②对稠密索引且查找键未在索引块出现，在索引中插入。③对稀疏索引，每块数据对应一个索引项。若数据块有空闲放得下新数据，不用修改索引；否则，加入新数据块，在索引块中插入一个新索引项。数据库的存储结构辅助索引在其他属性上建立索引，也可以提高以这些属性为查找键值的查找速度，称为辅助索引。但由于相同查找键值的记录分散在主文件中(已按主索引顺序存储)，辅助索引需新的结构。辅助索引的指针不直接指向主文件记录，而是指向一个桶，桶内存放指向具有同一查找键值的主记录指针。辅助索引(最末级)不能是稀疏索引。例：在Salary建索引HeF-2577000LiuB-2158000LiuA-1026000WenB-3067000ZhangA-2146000ZhangB-4676000ZhouC-3438000600070008000数据库的存储结构B+树索引B+树的结构：一颗M阶的B+树，按下列方式组织：①每个结点至多有m-1个查找键值和m个指针。如下图②叶结点指针指向主文件中的记录或桶。③非叶结点指针数m/2≤n≤m，Pi指向的子树中所有键值均小于Ki，而大于等于Ki-1。例：下图是一颗三阶B+树P1K1P2…Pn-1Kn-1Pn对于m阶、K个键的B+树，查找次数≤logm/2K第九章数据库系统实现实现技术9.2事务事务(Transaction)的概念定义：事务是DBMS中一个逻辑工作单元，通常由一组数据库的操作组成，满足原子性、一致性、隔离性和持久性四个性质。事务的ACID性质原子性(Atomic)：构成事务的所有操作要么全部执行，反映到数据库中；要么全部不执行，没有对数据库中的数据造成影响。一致性(Consistency)：事务的操作使数据库从一个一致状态(所有对象满足各自的约束)转变为另一个一致状态。隔离性(Isolation)：在多用户环境下，事务的执行不受同时执行的其它事务的影响。例：多售票点售票的例子。持久性(Durability)：一个事务如果成功执行，其对数据库的影响是持久的，不因故障而失效。事务事务的例子例1：向客户1003销售pCode=101的产品10个UpdateProductsetqty=qty-10wherepCode=‘101’;InsertintoOrder(‘25’,’1002’,2016-3-11,2016-3-12);InsertintoOrderdetail(‘25’,’101’,10,0.05);Commit;例2：银行数据库的转账事务，从账号A转50元到账户BRead(A);A:=A-50;Write(A);Read(B);B:=B+50;Write(B);Commit;事务事务的标识由begintransaction语句和endtransection显式定义事务的开始和结束。隐式定义：从一个读写语句开始，遇到rollback或commit语句时终止(SQL-92)。Commit：提交，确认事务执行。Rollback：回滚，将此前的执行的操作影响恢复到操作前。事务的大小与回滚机制事务执行过程中出现错误、或不可执行的操作(如订单已插入、结账时发现账户余额不足)需回滚。因此DBMS将事务的执行缓存在回滚段(表空间一个区域)，执行rollback或commit后清除。回滚段大小、回滚缓冲区大小影响事务的大小、并发事务数和执行效率。事务如何保证上述事务满足ACID性质？回滚机制和故障恢复机制保证了事务的