数据库教学课件：第3章 存储与文件结构

第3章存储与文件结构本章内容参考:数据库概念(第四版)byA.SilberschatzChapter11存储与文件结构简介+自学补充内容本章内容特色:涉及硬件设备相关知识在多年学习中已经有所了解有关技术规范和设备信息较多内容较多，较杂，理论较少，难度较小重点是系统地梳理本章关键问题：如何正确地实现逻辑地址空间到物理地址空间的映射如何消除存储设备性能瓶颈如何管理存储空间主要内容物理存储介质概述物理存储分层存储器访问存储空间管理缓冲区管理器文件组织(自学)文件中的记录组织(自学)数据字典存储(略)对象到文件的映射(略)持久性指针的管理(略)物理存储介质概述(复习)MagneticDisks磁盘RAID磁盘阵列TertiaryStorage第三级存储注:这部分内容主要涉及硬件设备，对其工作原理和性能指标有一般了解即可物理存储介质分类SpeedwithwhichdatacanbeaccessedCostperunitofdataReliabilitydatalossonpowerfailureorsystemcrashphysicalfailureofthestoragedeviceCandifferentiatestorageinto:volatilestorage:losescontentswhenpowerisswitched

off易逝，挥发non-volatilestorage:Contentspersistevenwhenpowerisswitchedoff.Includessecondaryandtertiarystorage,aswellasbatterbacked

upmain-memory.磁盘，光盘，磁带，闪存物理存储分层(复习)返回MemorySystemCPURegistersL1CacheCPUDieL2CacheMainMemoryHarddiskMemoryHierarchyTime= SeekTime+ RotationalDelay+ TransferTime

RuleofThumb

RandomI/O:Expensive20msSequentialI/O:Muchless1-5msAccessTime存储空间管理GoalsEnableefficientstorageandmaintenanceofrecordsEnablefastandefficientaccesstodataGoodstorageutilizationandefficientspacereclamation多,快,好,省ImprovingAccessTimeofSecondaryStorageOrganizationofdataondiskDiskschedulingalgorithmse.g.,elevatoralgorithmMultiple/MirroreddisksPrefetchingandlarge-scalebuffering存储器存取(10/9)数据库文件被分割成若干定长的存储器单位(称为块)块是存储器分配和数据传输的单位数据库系统应尽量减少磁盘与内存间的块传输次数可以通过将尽可能多的块保持在主存中以减少磁盘存取次数缓冲区–用于保存读入的磁盘块的主存空间缓冲区管理器–负责分配缓冲区空间的子系统存储器存取DatamustbeinRAMforDBMStooperateonit!Tableof<frame#,pageId>pairsismaintainedDBMAINMEMORYDISKdiskpagefreeframePageRequestsfromHigherLevelsBUFFERPOOLChoiceofframedictatedbyreplacementpolicy缓冲区管理器当程序请求某磁盘块时即调用缓冲区管理器如果该块已经在缓冲区中,则程序得到该块在主存中的地址如果该块不在缓冲区中,则:缓冲区管理器为该块分配缓冲区空间,如果有必要需换出其他块来为这个新块腾出空间如果被换出的块自从最近一次写回磁盘或从磁盘读入之后做过修改,则需写回磁盘，否则直接替换一旦在缓冲区中分配了空间，

缓冲区管理器就从磁盘将该块读入缓冲区，

并将该块在主存中的地址传给请求者缓冲区替换策略多数操作系统采用最近未使用(LRU)策略来替换块LRU背后的想法–利用过去的块引用模式来预测将来的引用查询有良定义的存取样式(如顺序扫描)，系统可利用用户查询中的信息来预测将来的引用LRU对某些涉及重复扫描数据的存取样式来说是很差的策略例如当用嵌套循环算法计算两个关系r与s的连接时

foreachtuple

trofrdo

foreachtuple

tsofsdo

ifthetuples

trandtsmatch…由查询优化器提供的带有替换策略指导线索的混合策略更可取缓冲区替换策略受制(Pinned)块–不允许写回磁盘的内存块立即替换(Toss-immediate)策略–一旦块中最后一条元组被处理完就释放被该块所占用的空间最近使用(MRU)策略–系统必须牵制(pin)当前正被处理的块，当处理完该块的最后一条元组，该块被解除牵制(unpinned)并成为最近使用的块缓冲区管理器可利用关于某请求会引用特定关系的概率的统计信息例如,数据字典被频繁存取启示:将数据字典块保存在缓冲区中为恢复目的，缓冲区管理器还支持块的强制输出Choiceofpre-definedtypesFewpre-definedtypes(e.g.,varcharandnumeric)Highlyportable,butrequirescomplexconversionsButcancreateexcessivestorageoverheadManypre-definedtypes(e.g.,allthosesupportedbyaprogramminglanguageandmore)Simple,efficient,fewconversionsButnotportablePhysicalrepresentationofattributesMachine-independentrepresentationStoreattributevaluessothattheycanbecomparedonbothLittlemachinesandBigmachinesPhysicalrepresentationofattributesPhysicalrepresentationofattributesRepresentingNULLvaluesSpecial-valueapproachHighlycomplexandleadstoa"loss"ofcertainvaluesfromadomainMissing-valueapproach(fieldlengthof0indicatingnull)Cannotbeusedinalltuplerepresentations,sincenotallofthemmaintainthe"fieldlength"Doesnotdifferentiatebetween"valuedoesnotexist“and"valuemissing"semanticsasmandatedbySQLRecordbitmap(位图)approach(0bitindicatingnull)RelativelysimpleandflexiblePhysicalRepresentationofTuplesDescribestheinternalstructureofatupleQuestions:Shoulddatastoreaccommodatedynamicupdates?Isstoragereuseanimportantfactor?Shouldaccesstoanyrecord'sfieldbeequallyfast?Arelongtuplesrequired?Alternatives:Fixed-lengthrecordswithfixed-lengthfieldsVariable-lengthrecordswithself-describingfieldsVariable-lengthrecordswithfixedrecordmapsVariable-lengthrecordswithfixedandvariableportionsPhysicalRepresentationofTuplesExampleusedthroughout:r(A1,A2,A3,A4,A5),whereA1-char(4)A2-varchar(20)A3-numeric(10,3)A4-integerA5-varchar(15)InternalDataOrganizationRecordidentifiersPurposeDistinguishrecordsfromoneanotherLocatearecordviaitsidasquicklyaspossibleAllowrecoverytocorrelatelogentrieswithrecordsAllowreplicationservicestodeterminewhethertworecordsare,infact,replicasofthesameobjectRecordidentifiersAlternativesDirectbyteaddressesUser-definedkeysSystem-definedkeysIndirectrecordaddressesRecordidentifiersDirectbyteaddressesStructure:(fileid,pageid,byteaddressoftherecord)Allowsfastdirectaccess,butprohibitsrelocationandreplication,limitstheabilitytoupdatearecord,createssevereexternalfragmentationofstorage,etcGenerallyconsideredbadideaRecordidentifiersUser-definedkeysStructure:(tableid,primarykey);note,bothcomponentsarelogicalobjects,ratherthanphysicalAdvantages:Manyrelationalsystemsrequiretablestohaveprimarykeys(noadditionaladdressingschemerequired)Recordscanfreelybemovedandreplicatedatwill，withnoartificialrestriction(provideshigherdegreesofdataindependence)RecordidentifiersUser-definedkeysDisadvantages:Primarykeysforarelationcanbeverylarge(hence,maycreateexcessivestorageoverhead,e.g.ifusingtheseaspointerswithinthesecondaryindexes)Requiresanassociativesearchthroughaprimaryindextolocatearecord(hence,performancedeteriorates)NotallDBMSsrequiretheirlogicalcollectionstohaveprimarykeys，Inthiscase,either:theschemewillnotwork,oritwillrequirecreationofanartificialprimarykey,whichmaybecostly(forcescreationandmaintenanceofanadditionaldatabaseindex)RecordidentifiersSystem-definedkeysStructure:(tableid,system-definedrecordnumber)Recordidisasystemmaintained,auto-incrementnumber,assignedtoeachnewlyinsertedrecordAccesstoarecordgoeseitherthroughaprimaryindexonrecordidsorthroughatranslationtable--maprecordidsontorecordaddressesthelaterisdifficulttomaintainRecordidentifiersSystem-definedkeysAdvantages:RecordscanfreelybemovedandreplicatedCreatesrelativelysmallstorageoverhead(comparedtoprimary-keyapproach)Disadvantages:Duetoindirection,increasednumberofdiskaccessestofetcharecordviaitsrecordnumberSlowsdownbrowsingthroughatableinanindexorderRecordidentifiersIndirectrecordaddresses(RIDs)Structure:

(fileid,pageid,indexintothepagedirectory)Advantages:Providesfastaccesstoarecord(almostdirect)AllowsrelocationwithinthepageRelativelysmalloverheadFastbrowsinginbothindexedandnon-indexedorderNicelyfitsintotheconcernsofloggingandlockingRecordidentifiersIndirectrecordaddresses(RIDs)Disadvantages:DifficultrelocationfromonepagetoanotherExtremelydifficultandcostlyreorganizationDoesnotsatisfytheneedsofreplicationDespiteitsdrawbacks,usedinalmostallmajorDBMSsbut,theyusuallysupportotheraddressingschemestooMappingShortRecordstoPagesForfastaccess,limitedtofitapageInsertionsanddeletionsarerelativelyeasyUpdateshaveacomplexcase:Ifanupdateextendsarecordsothatitcannolongerfitinthepage,thenmovetheentirerecordtoadifferentpageandleaveapointerintheoldpagetellingwheretherecordisnow(“forward-address(转发)pointer")Forward-addresspointerisrequiredsothattheoriginalRIDisnotinvalidatedNote,thatatmosttwopageaccessesaresufficienttolocateanyrecord:Ifarecordneedstobemovedmorethanonce,onecanuseitsRIDtoupdatetheoriginalforward-addresspointertoindicatethenewlocationMappingLongRecordstoPagesAlternatives:

Longpages

Separatepagesforlongfields

Continuation延长pagesMappingLongRecordstoPagesLongPages

Allowslongpages(upto64Kbytes)Internally,longrecordsaremanagedjustasshortonesSimplesolution,butinadequateforverylargerecordsUsedinDB2andOracleSeparatePagesforLongFieldsInsteadofkeepingentirelongfieldinarecordmaintainsonlyapointertothelongfieldstoredinanotherpageThemainrecordisthentreatedasashorttupleGoodresultsiflongattributesareaccessedinfrequentlyUnfortunately,performancesuffersinsituationswhenlongattributesareaccessedfrequentlyMappingShortRecordstoPagesMappingLongRecordstoPagesAllocationandFree-SpaceManagement

Free-SpaceInformationPages

Advantages:FSIPsneednotalwaysbeupdatedduringallocationanddeallocationDeallocationsarerelativelyfastandsimpleProvidesgoodstorageutilizationandreclamation(回收)offreeandunusedspace

Disadvantages:Allocationsmayrequireseveraldiskaccesses文件组织(自学)数据库保存为若干文件的集合文件是记录的序列记录是字段的序列方法:定长记录变长记录指针法

定长记录简单方法:记录i

从字节n(i–1)开始存储,其中n是记录大小记录存取简单,但记录可能跨块变化:不允许记录跨越块边界删除记录i:

可选方法:将记录

i+1,...,n

前移成i,...,n–1将记录n前移成i不移动记录,而是将所有自由

记录链成一条自由链表自由链表在文件头中存储第一条被删记录的地址.在第一条被删记录中存储第二条被删记录的地址,等等这些存储的地址可视为指针,因为它们“指向”记录的位置.是更有效利用空间的表示法:重新利用自由记录的正常字段空间来存储指针.(使用中的记录则不存储指针)变长记录数据库系统中在多种情况下需要变长记录:一个文件中存储多种记录类型允许一个或多个变长字段的记录类型允许重复字段的记录类型(用于某些老式数据模型)字节串表示法在每条记录末尾附加控制字符end-of-record()缺点难以删除难以增长变长记录的字节串表示法变长记录:SlottedPage结构Slottedpage

页头包含:记录登记项数目块中自由空间末端每条记录的位置和大小记录可以在页内移动以便保持记录间的连续存储，但页头中的登记项必须更新指针不能直接指向记录—而是应该指向该记录在页头中的登记项变长记录(续)定长表示法:预留空间法指针法预留空间法–利用具有已知最大长度的定长记录，

较小记录中的未用空间用null或end-of-record符号填充指针法指针法变长记录用若干通过指针链在一起的定长记录表示即使最大记录长度未知也可用指针法(续)指针结构的缺点:

除了链中首记录,其他所有记录中都可能有空间浪费解决方法是文件中采用两种块:锚块–包含链中的首记录溢出块–包含链中其他记录文件中的记录组织堆

–记录可置于文件中的任何有空间的地方顺序

–记录按顺序存储,基于每条记录在搜索键上的值散列–对记录的某些属性k计算散列函数h(k);计算结果决定该记录应该置于文件的哪个块中每个关系的记录可存储在单独的文件中,但在聚簇文件组织下,多个关系的记录可存储于同一文件中动机:相关联的记录存储在同一块中可减少磁盘I/O顺序文件组织适用于需要顺序处理整个文件的应用文件中的记录按搜索键排序返回顺序文件组织(续)删除–利用指针链插入–确定待插入记录的位置若有自由空间则在该处插入若无自由空间,插入到溢出块两种情况都要更新指针链需要不时重组文件以恢复

物理存储顺序聚簇文件组织简单的文件结构将每个关系存储在一个单独的文件中利用聚簇文件组织可以将多个关系存储在一个文件中例如,customer与depositor的聚簇组织:有利于涉及depositorcustomer的查询,以及涉及单个客户和他的账户的查询对只涉及customer的查询不好(可用指针链,见下图)导致变长记录带有指针链的聚簇文件结构数据字典的存储(略)关系的信息关系名关系的属性名和属性类型视图名及其定义完整性约束用户及账号信息,包括口令统计与描述数据每个关系的元组数目物理文件组织信息关系如何存储(顺序/散列/…)关系的物理位置操作系统文件名包含关系记录的磁盘块地址索引信息

数据字典(也称为系统目录)保存元数据:即关于数据的数据,如:数据字典的存储(续)目录结构:可采用为高效存取而设计的专门的数据结构,或者关系集合,利用现有系统特性保证高效存取通常采用后者一种可能的目录结构:Relation-metadata=(relation-name,number-of-attributes,

storage-organization,location)

Attribute-metadata=(attribute-name,relation-name,domain-type,

position,length)User-metadata=(user-name,encrypted-password,group)Index-metadata=(index-name,relation-name,index-type,

index-attributes)View-metadata=(view-name,definition)对象到文件的映射(略)将对象映射到文件类似于关系系统中将元组映射到文件，可以用文件结构存储对象数据OO数据库中的对象可能缺少一致性并可能非常大，管理这种对象必须不同于管理关系系统中的记录只有少量元素的集合字段可以用链表之类的数据结构实现

具有大量元素的集合字段可以实现为数据库中单独的关系还可以通过规范化在存储层消除重复字段类似于E-R图中的多值属性转换到关系对象到文件的映射(续)对象是通过对象标识符(OID)来标识的，存储系统需要一个机制来根据给定的OID定位对象，此动作称为引用解析(dereferences)逻辑标识符不直接指明对象的物理位置，必须维护一个索引将OID映射到对象的实际位置物理标识符编码了对象的位置信息，因此可以直接找到对象典型的物理OID由以下部分组成 1.卷或文件标识符 2.卷或文件内的页标识符 3.页内偏移量ManagementofPersistentPointersPhysicalOIDsmaybeauniqueidentifier,

Thisidentifierisstoredintheobjectalsoandisusedtodetectreferencesviadangling(悬挂)pointersManagementofPersistentPointersImplementpersistentpointersusingOIDs;persistentpointersaresubstantiallylongerthanarein-memorypointersPointerswizzling(调整)cutsdownoncostoflocatingpersistentobjectsalreadyin-memorySoftwareswizzlingswizzlingonpointerdeferenceWhenapersistentpointerisfirstdereferenced,thepointerisswizzled(replacedbyanin-memorypointer)aftertheobjectislocatedinmemorySubsequentdereferencesofofthesamepointerbecomecheapThephysicallocationofanobjectinmemorymustnotchangeifaswizzledpointersponttoit，thesolutionistopinpagesinmemoryWhenanobjectiswrittenbacktodisk,anyswizzledpointersitcontainsneedtobeunswizzledHardwareSwizzlingWithhardwareswizzling,persistentpointersinobjectsneedthesameamountofspaceasin-memorypointers—extrastorageexternaltotheobjectisusedtostorerestofpointerinformationUsesvirtualmemorytranslationmechanismtoefficientlyandtransparentlyconvertbetweenpersistentpointersandin-memorypointersHardwareSwizzlingAllpersistentpointersinapageareswizzledwhenthepageisfirstreadinthusprogrammershavetoworkwithjustonetypeofpointer,i.e.,in-memorypointersomeoftheswizzledpointersmaypointtovirtualmemoryaddressesthatarecurrentlynotallocatedanyrealmemory(anddonotcontainvaliddata)HardwareSwizzlingPersistentpointerisconceptuallysplitintotwoparts:apageidentifier,andanoffset(偏移)withinthepageThepageidentifierinapointerisashortindirectpointerEachpagehasatranslationtablethatprovidesamappingfromtheshortpageidentifierstofulldatabasepageidentifiersTranslationtableforapageissmall(atmost10↑32pointersina4096bytepagewith4bytepointer)MultiplepointersinpagetothesamepagesharesameentryinthetranslationtableHardwareSwizzling(Cont.)Pageimagebeforeswizzling(pagelocatedondisk)HardwareSwizzlingWhensystemloadsapageintomemorythepersistentpointersinthepageareswizzledasdescribedbelowPersistentpointersineachobjectinthepagearelocatedusingobjecttypeinformationForeachpersistentpointer(pi,oi)finditsfullpageIDPiIfPidoesnotalreadyhaveavirtualmemorypageallocatedtoit,allocateavirtualmemorypagetoPiandread-protectthepageNote:thereneednotbeanyphysicalspace(whetherinmemoryorondiskswap-space)allocatedforthevirtualmemorypageatthispoint.Spacecanbeallocatedlaterif(andwhen)Piisaccessed.Inthiscaseread-protectionisnotrequiredAccessingamemorylocationinthepagewillresultinasegmentationviolation,whichishandledasdescribedlaterLetvibethevirtualpageallocatedtoPi(eitherearlierorabove)Replace(pi,oi)by(vi,oi)Replaceeachentry(pi,Pi)inthetranslationtable,by(vi,Pi)HardwareSwizzlingWhenanin-memorypointerisdereferenced,iftheoperatingsystemdetectsthepageitpointstohasnotyetbeenallocatedstorage,orisread-protected,asegmentationviolationoccurs.Themmap()callinUnixisusedtospecifyafunctiontobeinvokedonsegmentationviolationThefunctiondoesthefollowingwhenitisinvokedAllocatestorage(swap-space)forthepagecontainingthereferencedaddress,ifstoragehasnotbeenallocatedearlier.Turnoffread-protectionReadinthepagefromdiskPerformpointerswizzlingforeachpersistentpointerinthepage,asdescribedearlierHardwareSwizzlingPagewithshortpageidentifier2395wasallocatedaddress5001.Observechangeinpointersandtranslationtable.Pagewithshortpageidentifier4867hasbeenallocatedaddress4867.Nochangeinpointerandtranslationtable.PageimageafterswizzlingHardwareSwizzlingAfterswizzling,allshortpageidentifierspointtovirtualmemoryaddressesallocatedforthecorrespondingpagesfunctionsaccessingtheobjectsarenotevenawarethatithaspersistentpointers,anddonotneedtobechangedinanyway!canreuseexistingcodeandlibrariesthatusein-memorypointersAfterthis,thepointerdereferencethattriggeredtheswizzlingcancontinueHardwareSwizzlingOptimizations:Ifallpagesareallocatedthesameaddressasintheshortpageidentifier,nochangesrequiredinthepage!Noneedfordeswizzling—swizzledpagecanbesavedas-istodiskAsetofpages(segment)canshareonetranslationtable，Pagescanstillbeswizzledasandwhenfetched(oldcopyoftranslationtableisneeded).Aprocessshouldnotaccessmorepagesthansizeofvirtualmemory—reuseofvirtualmemoryaddressesf