《數(shù)據(jù)庫系統(tǒng)》教學(xué)課件

數(shù)據(jù)庫系統(tǒng)教學(xué)課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),教學(xué),課件 Hash-Based IndexesJianlin FengSchool of SoftwareSUN YAT-SEN UNIVERSITYIntroductionnAs for any index,3 alternatives for data entries k*:qData record with key value kqqqChoice orthogonal to the indexing techniquenHash-based indexes are best for equality selections.Cannot support range searches.nStatic and dynamic hashing techniques exist;trade-offs similar to ISAM vs.B+trees.Static HashingnThe number of primary pages is fixed.nPrimary pages are allocated sequentially,never de-allocated;qoverflow pages if needed.nh(k)mod N=bucket to which data entry with key k belongs.(N=number of buckets)Static Hashing(Contd.)nBuckets contain data entries.nHash function works on search key field of record r.Must distribute values over range 0.N-1.qh(key)=(a*key+b)usually works well.qa and b are constants;lots known about how to tune h.nLong overflow chains can develop and degrade performance.qExtendible and Linear Hashing:Dynamic techniques to fix this problem.Extendible HashingnSituation:Bucket(primary page)becomes full.Why not re-organize file by doubling the number of buckets?qReading and writing all pages is expensive!nIdea of Extendible Hashing:qUse directory of pointers to buckets,double the number of buckets by doubling the directory,qsplitting just the bucket that overflowed!Extendible Hashing(Contd.)nDirectory is much smaller than file,so doubling it is much cheaper.nOnly one page of data entries is split.No overflow page!nTrick lies in how hash function is adjusted!Points to Noten20=binary 10100.Last 2 bits(00)tell us r belongs in A or A2.Last 3 bits needed to tell which.qGlobal depth of directory:Max number of bits needed to tell which bucket an entry belongs to.qLocal depth of a bucket:number of bits used to determine if an entry belongs to this bucket.nWhen does bucket split cause directory doubling?qBefore insert,local depth of bucket=global depth.Insert causes local depth to become global depth.Equality Search in Extendible HashingnIf directory fits in memory,equality search answered with one disk access;else two.q100MB file,100 bytes/rec,4K pages contains 1,000,000 records(as data entries)and 25,000 directory elements;qchances are high that directory will fit in memory.Delete in Extendible HashingnIf removal of data entry makes a bucket empty,the bucket can be merged with its split image.nIf each directory element points to same bucket as its split image,we can halve the directory.Linear Hashing(LH)nThis is another dynamic hashing scheme,an alternative to Extendible Hashing.nLH handles the problem of long overflow chains without using a directory,and handles duplicates.qWhat problem will duplicates cause in Extendible Hashing?The Idea of Linear HashingnUse a family of hash functions h0,h1,h2,.,where hi+1 doubles the range of hi(similar to directory doubling)qhi(key)=h(key)mod(2iN);N=initial#bucketsqh is some hash function(range is not 0 to N-1)qIf N=2d0,for some d0,hi consists of applying h and looking at the last di bits,where di=d0+i.The Idea of Linear Hashing(Contd.)nDirectory avoided in LH by using overflow pages,and choosing bucket to split round-robin.qSplitting proceeds in rounds.Round ends when all NR initial(for round R)buckets are split.Buckets 0 to Next-1 have been split;Next to NR yet to be split.qCurrent round number is Level.Overview of LH File:in the Middle of the Level th RoundSearch in Linear HashingnTo find bucket for data entry r,find hLevel(r):qIf hLevel(r)in range Next to NR,r belongs here.qElse,r could belong to bucket hLevel(r)or bucket hLevel(r)+NR;must apply hLevel+1(r)to find out.Inserting a Data Entry in LHnFind bucket by applying hLevel/hLevel+1:qIf the bucket to insert into is full:nAdd overflow page and insert data entry.n(Maybe)split Next bucket and increment Next.qElse simply insert the data entry into the bucket.Bucket SplitnA split can be triggered byqthe addition of a new overflow pageqconditions such as space utilizationnWhenever a split is triggered,qthe Next bucket is split,qand hash function hLevel+1 redistributes entries between this bucket(say bucket number b)and its split image;qthe split image is therefore bucket number b+NLevel.qNext Next+1.Example of Linear HashingInsert data entry of 43*After Inserting Data Entry of 37*After Inserting Data Entry of 29*After Inserting Data Entries of 22*,66*and 34*Example:End of a Round,After Inserting Data Entry 50*.Extendible VS.Linear HashingnImagine that we also have a directory in LH with elements 0 to N-1.qThe first split is at bucket 0,and so we add directory element N.qImagine directory being doubled at this point,but elements,.are the same.So,we can avoid copying elements from 1 to N-1.qWe process subsequent splits in the same way,qAnd at the end of the round,all the orginal N buckets are split,and the directory is doubled in size.ni.e.,LH doubles the imaginary directory gradually.SummarynHash-based indexes:best for equality searches,cannot support range searches.nStatic Hashing can lead to long overflow chains.nExtendible Hashing avoids overflow pages by splitting a full bucket when a new data entry is to be added to it.nLinear Hashing avoids directory by splitting buckets round-robin,and using overflow pages.