数据库系统实现实现技术

第九章数据库系统实现实现技术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-101

100028sp2李先生M67-5-2213146北京市海淀区玉泉路甲19号100049sp3何女士F62-9-7352210山东省日照市276534数据库的存储结构下述文件存储是字符串格式0sp1│刘女士│F│70-1-20北京市宣武区牛街街道双槐里小区22楼2-101│1370100028

1│┴│1sp2│李先生│M│67-5-22北京市海淀区玉泉路甲19号100049│┴│2sp3│何女士│F│62-9-7山东省日照市276534│┴│字符串格式的缺点被删除的位置难以重新利用。某记录要伸长很困难(移动大量记录)。改进：分槽式页结构(shottedpagestructure)记录从块的尾部邻接存放。中间是自由空间(伸长记录用)。块的开始是块首部，记录块中记录数、每个记录大小和位置。分槽式变长记录结构变长记录的定长表示预留空间(按最大)固定块+溢出块格式数据库的存储结构sp1刘女士F70-1-20082354sp2李先生M67-5-2213146sp3何女士F62-9-7352210北京市宣武区牛街街道双槐里小区22楼2-101

100028┴北京市海淀区玉泉路甲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，经常进行自然连接查询操作，如SELECT

S.S#,Sname,C#,Grade

FROMS,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性质？回滚机制和故障恢复机制保证了事务的原子性。如果一个事务没有执行到commit，前面的操作不反映到数据库数据中。只要事务定义的合理，其原子性能保证结果得一致性。持久性需要数据库的故障恢复系统将发生故障时尚未将操作结果体现到数据库中的操作进行适当处理，以确保操作结果正确。关于持久性，与数据库文件系统的缓存机制密切相关。因为数据的读写操作是在缓冲区进行的，在还没有写回磁盘文件前发生故障，就出现了持久性问题。故障恢复机制：在事务的执行过程中，如果发生了故障，系统采取适当措施取消一个未完成的事务对数据库的影响，或将已经执行完的事务结果反映的数据库存储文件中。事务的隔离性需要复杂的并发控制机制来实现。第九章数据库系统实现实现技术9.3并发控制为什么需要并发事务为有效响应多用户实时数据库操作，提高吞吐量，数据库事务内的操作都是交错执行的，即并发执行事务。因为提高吞吐量：事务的吞吐量是指单位时间内平均完成的事务个数。一个事务设计两类操作：一类I/O操作，如从磁盘读写数据，速度较慢；一类是CPU操作，速度较快。如果允许不同事务的读、写、CPU运算、网络传输等操作并行执行，则可有效提高事务的吞吐量。进程调度都是这样做的。有利于短事务的快速执行：事务交错执行有利于短事务的快速完成，从而缩短事务的平均完成时间。并发控制并发事务调度调度：多个事务包含的操作之间，按照一定的顺序执行的方式称为一种调度。调度类型：如果每个事务的草阿诺与其它事务的操作的执行顺序没有交错，则称为串行调度；反之，称为并发调度。假设事务的定义是正确的，即可保证数据库从一个一致状态转换为另一个一致的状态，

那么，串行调度的最终结果

一定是一致状态。但并发调度若不加适当控制，

则有可能出现异常，使

数据库的一致性遭到破坏。T1T2Read(A)A:=A-1Read(A)A:=A-1Write(A)Write(A)Read(C)并发控制并发调度异常丢失更新异常-写写(ww)冲突即重写未提交数据(overwritinguncommitteddata)，指的是事务T1修改了对象A的值，在T1尚未提交前，事务T2页修改了A的值，将T1对A的修改覆盖了。设A是库存，初值500，T1和T2

分别销售100、200，正确的结

果是200。但右图的调度执行结

果为300。T1T2Read(A)A:=A-100Read(A)A:=A-200Write(A)Write(A)commitWrite(A)commit并发控制读脏数据异常-写读(WR)异常即读未提交的数据(readinguncommitteddata)，指的是事务T2读取了被T1修改但尚未提交的数据。设A是库存、B是销量，T1完

成销售100，A初值100，B初值500；T2统计库存量加销量(应与

进货量平衡)。T2正确结果(串行顺序不同，结果可不同)：先T1后T2，A=0,B=600;先T2后T1，A=100,B=500。C都是600。但右图的调度C=500，A=0，B=500。T1T2Read(A)A:=A-100Write(A)Read(A)Read(B)C:=A+BCommitRead(B)B:=B+100Write(B)Commit并发控制不能重复读异常-读写(RW)冲突是由读写(RW)冲突导致的。指的是一个事务T1读取某个数据对象A，但是在T1尚未提交时，A被另外一个事务T2修改。若T1再读A得到的是与前一次不同的值。读脏数据和不可恢复调度读脏数据异常也可能由于回滚造成。T1将销量A(初值500)增加100，T2读取销售数据加到总销量B(初值1000)上。T1对A的修改被取消，但回滚前被T2

读出，这是脏数据。(1500→1600)T1T2Read(A)Read(A)A:=A+500Write(A)CommitRead(A)CommitT1T2Read(A)A:=A+100Write(A)Read(A)Read(B)B:=B+AWrite(B)Commitrollback并发控制基于封锁的并发控制技术为了避免并发调度带来的各种异常以及不可恢复调度情况的发生，可以使用基于封锁(lock)的并发控制机制对事务之间的相互作用加以控制。封锁可以看作是对一个数据库对象进行操作的许可。一个事务在对某对象进行操作之前必须按照某种封锁协议先获得该对象的某种封锁，而能否获得封锁要根据对同一对象的操作是否存在冲突决定。封锁的类型及相容矩阵共享锁(sharelock,S锁)

通常是对读对象加的锁排他锁(exclusivelock,X锁)

对要写的对象施加的锁S锁X锁S锁truefalseX锁falsefalse并发控制严格的两段锁协议(strict2PL)如果一个事务T需要读取一个数据库对象，那么它必须首先获得对该对象的共享锁；如果T要修改一个数据库对象，它必须首先获得对该对象的排他锁。T申请到的所有封锁一直拥有，直到T结束才释放。定义：如果事务的某一并行调度对数据库作用的结果与某一串行调度相同，则认为此调度是正确的，称为可串行化调度。严格的两段锁协议可保证调度的可串行化。例：前例不能重复读异常，实施严格

两段锁的结果是T1、T2完全串行。T1T2Slock(A)Xlock(A)Read(A)Read(A)CommitXlock(A)Read(A)A:=A+500Write(A)Commit并发控制如果两个事务的操作不存在冲突，两段锁协议仍然可以使操作交错执行。例但严格两段锁协议使并发度降低了。两段锁协议(可提前释放封锁)如果一个事务T需要读取一个数据库

对象，那么它必须首先获得对该对象

的共享锁；如果T要修改一个数据库对

象，它必须首先获得对该对象的排他锁。T释放了一个封锁后，就不能在获得

新的封锁。两段锁协议也可以使调度串行化，

但可能引发级联回滚。T1T2Slock(A)Read(A)Slock(A)Read(A)Xlock(B)Read(B)Write(B)commitXlock(C)Read(C)Write(C)commit并发控制两段锁协议例子T1没有结束，unlock(A)后T2即可取得A的X锁，从而并发执行。但若T2执行完write(A)后，T1发生故障需要回滚，则

引发T2的级联回滚。封锁粒度申请封锁的数据库对象的大小

称为封锁粒度。封锁粒度有数据库锁、表级锁、页面锁(物理单元)、行级锁、和列级锁。封锁粒度越小，并发度越高，管理封锁代价越高。T1T2Xlock(A)Read(A)Slock(B)Read(B)Write(A)Unlock(A)Xlock(C)…Xlock(A)Read(A)Write(A)Commit并发控制幻像问题幻象问题发生在表中的元组被插入或删除的情况。例:T1查询足球类产品的总销量A(初值100)和健美类产品的总销量B(200)；T2首先插入一行健美类产品的销售记录(20)，然后再插入一条足球类产品销售记录(10)。串行结果:T1T2=100,200;T2T1=110,220行级锁结果：100,220，与任一串行结果不同。原因是T1读取了一个之前并不存在的行(不存在插入操作不加锁)，即所谓幻行。T1T2Slock(A)Read(A)Insert(t1)Slock(B)Read(B)Insert(t2)CommitCommit幻像问题可采用表级锁或对索引加锁解决并发控制SQL-92规定的并发级别及可解决的并发调度异常Serializable:可保证调度的可串行化，默认级别。Repeatableread:允许重复读，两次读之间其它事务不能修改。Readcommitted:只能读取已提交的数据。Readuncommitted:允许读未提交数据。数据封锁的申请和释放是由DBMS自动加入到事务中的。但SQL提供了设置某并发级别的命令。例：SQLServerSettransactionisolationlevelreadcommitted调度可解决异常丢失更新读脏数据不可重复读幻像SerializableYYYYRepeatablereadYYYNReadcommittedYYNNReaduncommittedYNNN并发控制Upgrade机制为了提高并发度，一种广泛使用的加锁、解锁机制为：T对A进行读操作时，申请S锁；当要写该对象时，首先检查T在A上是否有S锁，若有，则用upgrade升级为X锁，否则，直接申请排他锁。例:T1T2Xlock(A)Read(A)Slock(B)Read(B)…Write(A)Unlock(A)Slock(A)Read(A)T1T2Slock(A)Read(A)Slock(B)Read(B)…Upgrade(A)Write(A)Unlock(A)Slock(A)Read(A)Unlock(A)提高了并发度第九章数据库系统实现实现技术9.4数据库的恢复缓冲区工作原理事务开始执行时在内存都有一个专用的工作区，用于存放它访问和修改的数据。事务结束时释放该缓冲区。一个事务要存取数据项X的值，首先需要将其读到工作区相应的变量x中，即read(X)。读操作的步骤：检查缓冲区中是否包含X的物理块Bx，若无，发出input(Bx)输入操作命令，将物理块读入缓存。读Bx内的X值到工作变量x中。Write(X)写操作的步骤：检查缓冲区中是否包含X的物理块Bx，若无，发出input(Bx)输入操作命令，将物理块读入缓存。将工作变量的值x送入Bx的X数据项。数据库的恢复何时写回外存(output(Bx))Write(X)并未将X写回外存。为什么？

Bx是一个数据块，还包含其它数据，不急于I/O以提高系统性能。这是缓冲区的主要目的。当缓冲区满了，某read(X)不能在缓冲区命中时，才按一定算法将某个缓冲数据块Bx写回外存，调入所需新数据块。问题如果一个事务在write(X)后提交了，在output(Bx)之前系统发生故障，则X得新值没有反应到数据库内，事务的持久性被破坏。一个事务执行了Write(X)，但事务尚未提交，由于缓冲区替换导致output(Bx)执行，半个事务的结果持久反应到数据库中，数据库处于不一致状态，事务的原子性被破坏。解决：强制写和未提交事务的缓存不能写来避免，但缓冲的意义就没有了。事实上这正是数据库恢复技术要解决的问题。数据库的恢复故障类型系统故障(systemcrash)又称为软故障，是由软、硬件原因导致当前运行的一个或多个事务无法正常进行，但并未导致物理介质上的数据遭到破坏。常见系统故障：断电、程序逻辑错误(如溢出)、死机等。系统故障导致的问题是当前和最近运行的事务的状态有可能丢失，为保证事务的原子性和持久性，需要采取相应的恢复措施。介质故障(mediafailure)又称硬故障，指的是由于磁盘等数据库外存损坏导致的数据库的一部分或全部数据无法访问。介质故障影响正在访问这些数据的事务的正常执行，使数据库处于不一致状态。除事务异常外，数据库系统不能工作，导致整个应用系统瘫痪。数据库的恢复日志(log、trail、journal)常用的数据库故障恢复方法是基于日志的恢复技术。日志是有关DBMS所执行的操作的一个历史记录。日志文件是一个记录该历史的物理文件，由若干日志记录构成。日志记录的信息日志序列号；操作信息：如事务开始、更新操作、事务提交、事务取消、事务终止等。例：更新日志记录，包含事务标识符、要更新数据项的标识符(磁盘位置)、更新前的值(前像)、更新后的值(后像)等。先写日志原则为确保主要操作都被记录在日志中，防止故障发生时丢失。任何对数据库的更新(包括缓冲块)被写回磁盘之前，必须保证其更新日志已写到日志文件(写到磁盘上)。数据库的恢复循环日志：循环使用固定数目的日志文件来记录日志。设日志文件数为n，日志依次写入这n个文件。n个文件写满后循环使用，新日志记录覆盖旧记录。n的大小应保证被覆盖的日志文件记录的事务已经结束且更新数据块已写回外存。循环日志可恢复故障发生时涉及事务的完整性。但对介质故障，无法恢复到故障发生时的状态。归档日志：将循环日志覆盖的日志文件归档保存。如保存到磁带、移动磁盘、网络存储等。数据库的恢复系统故障的恢复系统故障可能导致的数据库不一致状态故障发生时尚未结束的事务，它们的某些更新操作已经写回外存。故障发生前已结束的事务，它们对数据库的更新还未从缓冲区写回外存。恢复技术UNDO：撤销事务外化(externalized)了的数据库更新操作，使得从数据库状态看，这些操作好像从未执行过。REDO：重复某些数据库更新操作。如何确定哪些事务需要UNDO或REDO?比较耗时。一般使用检查点机制。数据库的恢复检查点(checkpoint)机制系统按一定周期执行检查点操作：①将缓冲区中的数据强制写回磁盘的物理数据库存储中。②记录检查点日志记录，其描述此时正在执行的事务列表。基于检查点的UNDO、REDO事务确认从日志文件尾部向前搜索直到遇到第一个检查点记录，将该记录中记录的事务列表初