數(shù)據(jù)庫(kù)管理系統(tǒng)概述英文版課件：tutorial8 Indices

1、Tutorial 8: IndicesReview: IndexB+-treeDynamic HashingBitmap indicesGrid filesReview: B+-treeBalanced treeUse pointer, no need for sequential storageThe depth of the tree is in logarithmic orderSpace overheadInsertion and deletion overhead. However, can be handled in logarithmic time.Review: Extendi

2、ble HashingAllow the number of buckets to be modified dynamicallyInsert: If bucket is full, split itIf necessary, double the directoryBefore inserting, local depth of bucket = global depthInsert causes local depth global depthRemoval of data entry makes bucket emptyMerge “split image”Each directory

3、element points to same bucket as its split imageHalve directoryReview: Linear HashingHandles the problem of long overflow chains without using a directory, and handles duplicatesDirectory avoided in Linear Hashing by using overflow pagesChoose bucket to split in a round-robin wayReview: Bitmap Indic

4、esBitmap has as many bits as recordsBitmap indices are useful for queries on multiple attributesQueries are answered using bitmap operationsIntersection (AND)Union (OR)Complementation (NOT) Review: Grid FilesSpeed up multi-dimensional range searchA grid file on two attributes A and B can handle quer

5、ies of all following forms with reasonable efficiency(a1 A a2)(b1 B b2)(a1 A a2 b1 B b2)Review: Merge SortAlgorithm:Create sorted runsN-way merge:Read the first page of each run into buffer pageREPEATSelect the first record (in sorted order) among all buffer pagesWrite the record to the output buffe

6、r. If the output buffer is full write it to disk.Delete the record from its input buffer page.IF the buffer page becomes empty THENread the next page (if any) of the run into the buffer. UNTIL all input buffer pages are emptyExercise 1: B+-treeGiven a B+-tree:Draw the tree afterInserting 8Deleting 2

7、Deleting 32440191457321614222019292724995040Exercise 1 : B+-tree (1/3)2440191457321614222019292724995040Inserting 8145328751614222019292724402419995040Exercise 1 : B+-tree (2/3)Deleting 214753871614222019292724402419995040145328751614222019292724402419995040Exercise 1 : B+-tree (3/3)Deleting 3244019

8、14875161422201929272499504014753871614222019292724402419995040Given the following directory and buckets.Using extendible hashing, what will they be after:Inserting 22Inserting 3Inserting 9Exercise 2: Extendible Hashing20100128251141821110local depthglobal depthExercise 2 : Extendible Hashing (1/3)In

9、serting 22 (00010110)14 (0000 1110)18 (0001 0010)20100128251141821110300100012825118301101014223100101110111Exercise 2 : Extendible Hashing (2/3)Inserting 3 (0000 0011)3001000128253118301101014223100101110111300100012825118301101014223100101110111Exercise 2 : Extendible Hashing (3/3)Inserting 9 (000

10、0 1001)3001000128253118301101014223100101110111300100012825921830110101422310010111011132Exercise 3: Linear HashingGiven the following buckets:hi(key) = h(key) mod (2i*4)Level = 0Using linear hashing, what will they be after:Inserting 9Inserting 12Inserting 59h0h100011011000001010011primary pagesove

11、rflow pages48next=01352517735438362638Inserting 9Exercise 3 : Linear Hashing (1/3)h0h100011011000001010011primary pagesoverflow pages8next=113525177354383626389001004h0h100011011000001010011primary pagesoverflow pages48next=01352517735438362638Exercise 3 : Linear Hashing (2/3)Inserting 12h0h10001101

12、1000001010011primary pagesoverflow pages8next=11352517735438362638900100412h0h100011011000001010011primary pagesoverflow pages8next=113525177354383626389001004Exercise 3 : Linear Hashing (3/3)Inserting 59h0h100011011000001010011primary pagesoverflow pages8next=291725735438362638590010001101412513h0h

13、100011011000001010011primary pagesoverflow pages8next=11352517735438362638900100412Exercise 4: Merge SortGiven:800 pages of a file10 pages of main memorySort this file by mergingHow many passes you need at least?What is the total cost (page access)?How many pages of main memory you need at least, in

14、 order to sort this file in two passes?Exercise 4: Merge Sort (1/3)Given:800 pages of a file10 pages of main memoryHow many passes you need at least?1210111220791792800sorted run 1sorted run 2sorted run 80pass0pass1run 1run 2run 910*9 pagessorted run 110*8 pagessorted run 9pass2sorted file800 pagesExercise 4 : Merge Sort (2/3)Given:800 pages of a file10 pages of main memoryWhat is the total cost (page access)?Cost = br(2logM-1(br/M)+1)= 800 * (2 * log9(800/10) + 1)= 4,000Exercise 4 : Merge Sort (3/3)Given:800 pages of a fileHow