搜索
CHAPTER10StorageandFileStructureThischapterpresentsbasicfilestructureconcepts.Thechapterreallyconsistsoftwoparts—thefirstdealingwithrelationaldatabases,andthesecondwithobject-orienteddatabases.Thesecondpartcanbeomittedwithoutlossofcontinuityforlaterchapters.Manycomputerscienceundergraduateshavecoveredsomeofthematerialinthischapterinapriorcourseondatastructuresoronfilestructures.Evenifstudents’backgroundsareprimarilyindatastructures,thischapterisstillimpor-tantsinceitaddressesdatastructureissuesastheypertaintodiskstorage.Buffermanagementissues,coveredinSection10.8.1shouldbefamiliartostudentswhohavetakenanoperatingsystemscourse.However,therearedatabase-specificas-pectsofbuffermanagementthatmakethissectionworthwhileevenforstudentswithanoperatingsystembackground.Exercises10.10Listthephysicalstoragemediaavailableonthecomputersyouuserou-tinely.Givethespeedwithwhichdatacanbeaccessedoneachmedium.Answer:Youranswerwillbebasedonthecomputersandstoragemediathatyouuse.Typicalexampleswouldbeharddisk,CDandDVDdisks,andflashmemoryintheformofUSBkeys,memorycardsorsolidstatedisks.Thefollowingtableshowsthetypicaltransferspeedsfortheabovemen-tionedstoragemedia,asofearly2010.StorageMediaSpeed(inMB/s)CDDrive8DVDDrive20USBKeys30MemoryCards1-40HardDisk100SolidStateDisks1009192Chapter10StorageandFileStructureNotethatspeedsofflashmemorycardscanvarysignificantly,withsomelowendcardsgivinglowtransferspeeds,althoughbetteronesgivemuchhighertransferspeeds.10.11Howdoestheremappingofbadsectorsbydiskcontrollersaffectdata-retrievalrates?Answer:Remappingofbadsectorsbydiskcontrollersdoesreducedataretrievalratesbecauseofthelossofsequentialityamongstthesectors.Butthatisbetterthanthelossofdataincaseofnoremapping!10.12RAIDsystemstypicallyallowyoutoreplacefaileddiskswithoutstoppingaccesstothesystem.Thus,thedatainthefaileddiskmustberebuiltandwrittentothereplacementdiskwhilethesystemisinoperation.WhichoftheRAIDlevelsyieldstheleastamountofinterferencebetweentherebuildandongoingdiskaccesses?Explainyouranswer.Answer:RAIDlevel1(mirroring)istheonewhichfacilitatesrebuildingofafaileddiskwithminimuminterferencewiththeon-goingdiskaccesses.Thisisbecauserebuildinginthiscaseinvolvescopyingdatafromjustthefaileddisk’smirror.IntheotherRAIDlevels,rebuildinginvolvesreadingtheentirecontentsofalltheotherdisks.10.13Whatisscrubbing,inthecontextofRAIDsystems,andwhyisscrubbingimportant?Answer:Successfullywrittensectorswhicharesubsequentlydamaged,butwherethedamagehasnotbeendetected,arereferredtoaslatentsectorerrors.InRAIDsystems,latenterrorscanleadtodatalossevenonasinglediskfailure,ifthelatenterrorexistsononeoftheotherdisks.Diskscrubbingisabackgroundprocessthatreadsdisksectorsduringidleperiods,withthegoalofdetectinglatentsectorerrors.Ifasectorerrorisfound,thesectorcaneitherberewrittenifthemediahasnotbeendamaged,orremappedtoasparesectorinthedisk.ThedatainthesectorcanberecoveredfromtheotherdisksintheRAIDarray.10.14Inthevariable-lengthrecordrepresentation,anullbitmapisusedtoindicateifanattributehasthenullvalue.a.Forvariablelengthfields,ifthevalueisnull,whatwouldbestoredintheoffsetandlengthfields?b.Insomeapplications,tupleshaveaverylargenumberofattributes,mostofwhicharenull.Canyoumodifytherecordrepresentationsuchthattheonlyoverheadforanullattributeisthesinglebitinthenullbitmap.Answer:a.Itdoesnotmatteronwhatwestoreintheoffsetandlengthfieldssinceweareusinganullbitmaptoidentifynullentries.Butitwouldmakesensetosettheoffsetandlengthtozerotoavoidhavingarbitraryvalues.Exercises93b.Weshouldbeabletolocatethenullbitmapandtheoffsetandlengthvaluesofnon-nullattributesusingthenullbitmap.Thiscanbedonebystoringthenullbitmapatthebeginningandthenfornon-nullattributes,storethevalue(forfixedsizeattributes),oroffsetandlengthvalues(forvariablesizedattributes)inthesameorderasinthebitmap,followedbythevaluesfornon-nullvariablesizedattributes.Thisrepresentationisspaceefficientbutneedsextraworktoretrievetheattributes.10.15Explainwhytheallocationofrecordstoblocksaffectsdatabase-systemperformancesignificantly.Answer:Ifweallocaterelatedrecordstoblocks,wecanoftenretrievemost,orall,oftherequestedrecordsbyaquerywithonediskaccess.Diskaccessestendtobethebottlenecksindatabases;sincethisallocationstrategyreducesthenumberofdiskaccessesforagivenoperation,itsignificantlyimprovesperformance.10.16Ifpossible,determinethebuffer-managementstrategyusedbytheoperat-ingsystemrunningonyourlocalcomputersystemandwhatmechanismsitprovidestocontrolreplacementofpages.Discusshowthecontrolonreplacementthatitprovideswouldbeusefulfortheimplementationofdatabasesystems.Answer:ThetypicalOSusesvariantsofLRU,whicharecheapertoimplementthanLRU,forbufferreplacement.LRUanditsvariantsareoftenabadstrategyfordatabases.AsexplainedinSection10.8.2ofthetext,MRUisthebeststrategyfornestedloopjoin.Ingeneralnosinglestrategyhandlesallscenarioswell,andthedatabasesystemshouldbeabletomanageitsownbuffercacheforwhichthereplacementpolicytakesintoaccountalltheperformancerelatedissues.Manyoperatingsystemsprovidemechanismstolockpagesinmemory,whichcanbeusedtoensurebufferpagesstayinme