课程资源复试数据库chindexing

Chapter8

Indexing2023/11/8Indexing2Indexing8.1TheConceptofIndexing8.2DiskStorage8.3TheB-TreeIndex8.4ClusteredandNon-ClusteredIndexes8.5AHashPrimaryIndex8.6ThrowingDartsatRandomSlots2023/11/8Indexing38.1TheConceptofIndexingIndexanindexislikeacardcataloginalibrary.Eachcard(entry)has:(keyvalue,row-pointer)keyvalueisforlookuprow-pointer(ROWID)isenoughtolocaterowondisk(oneI/O)2023/11/8Indexing48.1TheConceptofIndexingIndex:(keyvalue,row-pointer)EntriesareplacedinAlphabeticalorderbylookupkeyin"B-tree"(usually),alsomightbehashed.Anindexisalotlikememoryresidentstructures.Butindexisdiskresident.Likethedataitself,oftenwon'tallfitinmemoryatonce.Indexcanberegardedasatablewithtwocolumns:keyvalueandrow-pointer2023/11/8Indexing58.1TheConceptofIndexingFigure8.1:theSQLCreateIndexStatementCREATE[UNIQUE]INDEXindexname

ONtablename(colname

[ASC|DESC]{,colname

[ASC|DESC]...});DROPINDEXindexname;UNIQUEkeyvalueandrowisone-to-onewecanuseUNIQUEINDEXtoimplementUNIQUEconstraintsinCreateTableStatement.2023/11/8Indexing68.1TheConceptofIndexingExample8.1.1createindexcitiesxoncustomers(city);eachindexkeyvalue(i.e.,cityname)inthecitiesxindexcancorrespondtoalargenumberofdifferentcustomersrows.2023/11/8Indexing78.1TheConceptofIndexingExample8.1.2createuniqueindexcidxoncustomers(cid);eachindexkeyvalueinthecidxindexonlycorrespondtoacustomersrows.Indexkeyisquitedifferentfromrelationalconceptofprimarykeyorcandidatekey.But,wecanuseUNIQUEINDEXandNOTNULLtoimplementprimarykeyorcandidatekey.2023/11/8Indexing88.1TheConceptofIndexingIndexingAfterbeingcreated,indexissortedandplacedondisk.Sortisbycolumnvalueascordesc,asinSORTBYdescriptionofSelectstatement.NOTELATERCHANGEStoatableareimmediatelyreflectedintheindex,don'thavetocreateanewindex.2023/11/8Indexing98.2DiskStorageDatabaseStorageComputermemoryveryfastbutVolatile(挥发性的)storage.Diskstorageveryslowbutnon-volatileandverycheap.2023/11/8Indexing108.2DiskStoragemainmemorysecondarystoragetertiarystoragecachememorytapeCDdisksizesmallbigspeedfastslowcosthighlow2023/11/8Indexing118.2DiskStorageDiskAccessSeektime .008secondsThediskarmmovesinorouttothepropercylinderposition.Rotationallatency .004secondsThediskplatterrotatestotheproperangularposition.Transfertime .0005secondsThediskarmreads/writesthediskpageontheappropriatesurface.accessmemory:10-8~10-7seconds2023/11/8Indexing128.2DiskStorageMemoryBuffer(Figure8.2,pg.472)Readpagesintomemorybuffersocanaccessthem.Oncetorightplaceondisk,transfertimeischeap.Everytimewantapagefromdisk,hashondkpgaddr,h(dkpgaddr)toentryinHashlookasidetabletoseeifthatpageisalreadyinbuffer.2023/11/8Indexing138.2DiskStorageMemoryBuffer(cont.)AdvantagessaveddiskI/OfindsomethingforCPUtodowhilewaitingforI/O.Thisisoneoftheadvantagesofmulti-usertimesharing.CandoCPUworkforotheruserswhilewaitingforthisdiskI/O.2023/11/8Indexing148.2DiskStorageCreateTablespaceinORACLEFigure8.3,pg.476TablespacemadeupofOSfilescross2023/11/8Indexing158.2DiskStorageDataStoragePagesandRowPointers(Figure8.6,pg.480)Arowonmostarchitecturesisacontiguoussequenceofbytes.Nrowsplacedononepage(calledaBlockinORACLE).Headerinfonamesthekindofpage(datasegment,indexsegment),andthepagenumber(inORACLEtheOSfileandpagenumber).2023/11/8Indexing168.2DiskStorageROWsinpageRowsaddedrighttoleftfromrightendonblock.RowDirectoryentrieslefttorightonleftafterheader.Giveoffsetsofcorrespondingrowbeginnings.Providenumberofrowslotonpage.2023/11/8Indexing178.2DiskStorageWhennewrowadded,tellimmediatelyifwehavefreespacefornewdirectoryentryandnewrow.Conceptually,allspaceinmiddle,implieswhendeleterowandreclaimspacemustshifttofillingap.Alsomighthave"TableDirectory"inblockwhenhaveCLUSTER.2023/11/8Indexing188.2DiskStorageDiskPointerArowinatablecanbeuniquelyspecifiedwiththepagenumber(P)andslotnumber(S).RowsExtendingOverSeveralPagesProductVariations2023/11/8Indexing19Indexing8.1TheConceptofIndexing8.2DiskStorage8.3TheB-TreeIndex8.4ClusteredandNon-ClusteredIndexes8.5AHashPrimaryIndex8.6ThrowingDartsatRandomSlots2023/11/8Indexing208.3TheB-TreeIndexTheB-TreeEachnodeofthetreetakesupafulldiskpagehasalotoffanout2023/11/8Indexing21CreateIndexstatementinORACLECREATE[UNIQUE|BITMAP]INDEX[schema.]indexnameONtablename(colname

[ASC|DESC]{,colname

[ASC|DESC]…})[TABLESPACEtblespace

]

[STORAGE...][PCTFREEn

][

][NOSORT]UNIQUE|BITMAPASC|DESCTABLESPACEPCTFREENOSORT2023/11/8Indexing228.3TheB-TreeIndexCreatingIndexreadsthroughallrowsondisk(assumeN)pullsout(keyvalue,rowid)pairsforeachrowGetfollowinglist(inorderbykeyvals)putoutondisk(keyval1,rowid1)(keyval2,rowid2)...(keyvalN,rowidN)IfhaveNOSORTclause,rowsareinrightorder,sodon’thavetosort.2023/11/8Indexing23createuniqueindexsdxonS(sno)NOSORT;createindexndxonS(name)PCTFREE25;18PHShenS8817MASenS7717CSWangS6619PHLinS5518CSLoS4418MAXuS3317CSLiS2218CSLuS11agedeptnamesnoROWID8S87S76S65S54S43S32S21S1ROWIDsnoTableSIndexsdxIndexndxnameROWIDLi2Lin5Lo4Lu1Sen7Shen8Wang6Xu32023/11/8Indexing24Example8.3.1(pg.486)IdeaofBinarySearch/*binsearch:returnKsothatarr[K].keyval==x,or-1ifnomatch;*/intbinsearch(intx){intprobe=3,diff=2;while(diff>0){ /*loopuntilKtoreturn*/if(probe<=6&&x>arr[probe].keyval)probe=probe+diff;elseprobe=probe-diff;diff=diff/2;} /*wehavereachedfinalK*/if(probe<=6&&x==arr[probe].keyval)returnprobe;elseif(probe+1<=6&&x==arr[probe+1].keyval)returnprobe+1;elsereturn-1;}2023/11/8Indexing258.3TheB-TreeIndexExp8.3.2BinaryofaMillionIndexEntriesnumberofentries:1000000(106)sizeofentry:8bytessizeofdiskpage:2kbytesnumberofentriesineachdiskpage:250totalnumberofdiskpages:4000log24000

+1

≈13averagenumberofdiskI/O2023/11/8Indexing268.3TheB-TreeIndexExample8.3.3B-TreeStructureLayoutallentriesonleafnodesLevel1:RootNodeLevel2~LevelN-1:DirectoryNodesLevel2~LevelN-1:DirectoryNodesLevelN:LeafNode2023/11/8Indexing278.3TheB-TreeIndexTheStructureofB-TreeNodeK1,K2,…,Kmarekeyvalues,andK1<K2<…<Kmnismaximumnumberofkeyvalueinanode

LeafNode:

(n+1)/2

m

nPiisaROWIDwhichkeyvalueisKi(i=1,2,…,m)Pm+1isapointertonextleafnodeP1K1P2K2……PmKmPm+12023/11/8Indexing288.3TheB-TreeIndexRootNode:1

m

nInterNode：

(n-1)/2

m

nPiisapointertochildnode(rootnodeofsub-treeTi)foreachkeyvalueKonsub-treeTi,wehaveIfi=1: K<K1If1<i

m: Ki-1

K<KiIfi=m+1: K

KmP1K1P2K2……PmKmPm+12023/11/8Indexing298.3TheB-TreeIndexExample:leafnode(n=3)2023/11/8Indexing308.3TheB-TreeIndexExample:directoryorrootnode(n=3)2023/11/8Indexing31Example8.3.3(cont.)numberofentries:1000000(106)sizeofentry:8bytessizeofdiskpage:2kbytesnumberofentriesineachnode(diskpage)2k/8≈250totalnumberofleafnode1000000/250=4000totalnumberofdirectorynode:4000/250=16rootnodeaveragenumberofdiskI/O3(depthoftheB-Tree)

+1=4(rootnode)+(directorynode)+(leafnode)2023/11/8Indexing328.3TheB-TreeIndexHowtocreateanindexsortallentriesonleafnodescreatedirectory,anddirectorytodirectoryFanoutfofB-TreethemaximumnumberofentriesonaB-TreenodeDepthofB-TreeIftotalnumberofrowsisN,thendepth=logf(N)2023/11/8Indexing338.3TheB-TreeIndexDynamicchangesintheB-treeFigure8.12(pg.491)InsertfollowingkeyvaluesintoB-Tree(n=3)7,96,41,39,88,65,55,62Ideaof[PCTFREEn]2023/11/8Indexing34Def8.3.1:PropertiesoftheB-Tree(B+Tree)Everynodeisdisksizedandresidesinawell-definedlocationonthedisk.Nodesabovetheleaflevelcontaindirectoryentries,with(n–1)separatorkeysandndiskpointerstolower-levelB-treenodes.Nodesattheleaflevelcontainentrieswith(keyval,ROWID)pairspointingtoindividualrowsindexed.Allnodesbelowtherootareatleasthalffullwithentryinformation.Thisisnotoftenenforcedaftermultipledeletes.Therootnodecontainsatleasttwoentries(onekeyvalue).exceptwhenonlyonerowisindexedandtherootisaleafnode.2023/11/8Indexing358.3TheB-TreeIndexAlgorithmonB-Treesearchinsertdeleteupdate=delete+insert2023/11/8Indexing368.3TheB-TreeIndexTheORACLEBitmapIndexAbitmapindexusesONEbitmapforeachdistinctkeyval.AbitmaptakestheplaceofaROWIDlist,specifyingasetofrows.onebitvsaROWID(row)1:therowhavethekeyval0:therowdon’thavethekeyvalExampleFigure8.18(pg.501)2023/11/8Indexing378.4ClusteredandNon-ClusteredIndexesTheideaofaclusteredindexTherowsofthetableareinthesameorderastheindexentries—bykeyvalue.Inmostdatabaseproducts,defaultplacemenofrowsondatapagesondiskisinorderby