External Memory Hashing
Memory Hashing involves utilizing hash-based indices for efficient data retrieval on disk storage systems. It discusses the concepts of B+-trees, hashing techniques, indexing strategies, and design decisions for optimal performance. Explore the complexities, query types, and dynamic hashing schemes in disk-based computation models.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Model of Computation Data stored on disk(s) Minimum transfer unit: a page = b bytes or B records (or block) N records -> N/B = n pages I/O complexity: in number of pages CPU Memory Disk
I/O complexity An ideal index has space O(N/B), update overhead O(1) or O(logB(N/B)) and search complexity O(a/B) or O(logB(N/B) + a/B) where a is the number of records in the answer But, sometimes CPU performance is also important minimize cache misses -> don t waste CPU cycles
B+-tree Records must be ordered over an attribute, SSN, Name, etc. Queries: exact match and range queries over the indexed attribute: find the name of the student with ID=087-34-7892 or find all students with gpa between 3.00 and 3.5
Hashing Hash-based indices are best for exact match queries. Faster than B+-tree! Typically 1-2 I/Os per query where a B+- tree requires 4-5 I/Os But, cannot answer range queries
Idea Use a function to direct a record to a page h(k) mod M = bucket to which data entry with key k belongs. (M = # of buckets) 0 h(key) mod N 1 key h M-1 Primary bucket pages
Design decisions: Functions - h(x) = ((a*x+b) mod p )mod M a>0, a,b <p, p is a prime, and p>M (this is a Universal Hash family for different (a,b) values) - h(x) = [ fractional-part-of ( x * ) ] * M, : golden ratio ( 0.618... = ( sqrt(5)-1)/2 ) Size of hash table M Overflow handling: open addressing or chaining : problem in dynamic databases
Dynamic hashing schemes Extensible hashing: uses a directory that grows or shrinks depending on the data distribution. No overflow buckets Linear hashing: No directory. Splits buckets in linear order, uses overflow buckets
Extensible Hashing Bucket (primary page) becomes full. Why not re- organize file by doubling # of buckets (changing the hash function)? Reading and writing all pages is expensive! Idea: Use directory of pointers to buckets, double # of buckets by doubling the directory, splitting just the bucket that overflowed! Directory much smaller than file, so doubling it is much cheaper. Only one page of data entries is split. Trick lies in how hash function is adjusted!
Insert h(k) = 20 10100 00 2 3 LOCAL DEPTH GLOBAL DEPTH LOCAL DEPTH Bucket A 4* 12* 32*16* 32* 16* Bucket A GLOBAL DEPTH 2 2 2 3 Bucket B 00 1* 5* 21*13* 1* 5* 21*13* 000 Bucket B 01 001 010 2 Bucket C 10 2 10* 11 10* 011 Bucket C 100 2 2 101 DIRECTORY Bucket D 15* 7* 19* 15* 7* 19* Bucket D 110 111 3 DIRECTORY 12* 20* Bucket A2 (`split image' of Bucket A) 4*
Linear Hashing This is another dynamic hashing scheme, alternative to Extensible Hashing. Motivation: Ext. Hashing uses a directory that grows by doubling Can we do better? (smoother growth) LH: split buckets from left to right, regardless of which one overflowed (simple, but it works!!)
Linear Hashing (Contd.) Directory avoided in LH by using overflow pages. (chaining approach) Splitting proceeds in `rounds . Round ends when all MR initial (for round R) buckets are split. Buckets 0 to Next-1 have been split; Next to MR yet to be split. Current round number is Level. Search: To find bucket for data entry r, find hLevel(r): If hLevel(r) in range `Next to MR , r belongs here. Else, r could belong to bucket hLevel(r) or bucket hLevel(r) + MR; must apply hLevel+1(r) to find out.
Linear Hashing: Example Initially: h(x) = x mod M (M=4 here) Assume 3 records/bucket Insert 17 = 17 mod 4 1 Bucket id 0 1 2 3 13 4 8 5 9 6 7 11 hi(x) = x mod 2Level * M Level=0
Linear Hashing: Example Initially: h(x) = x mod N (N=4 here) Assume 3 records/bucket Insert 17 = 17 mod 4 1 Overflow for Bucket 1 Bucket id 0 1 2 3 13 4 8 5 9 6 7 11 Split bucket 0, anyway!!
Linear Hashing: Example To split bucket 0, use another function h1(x): h0(x) = x mod N , h1(x) = x mod (2*N) Split pointer 17 0 1 2 3 13 4 8 5 9 6 7 11
Linear Hashing: Example To split bucket 0, use another function h1(x): h0(x) = x mod N , h1(x) = x mod (2*N) Split pointer 17 Bucket id 0 1 2 3 4 13 8 5 9 6 7 11 4
Linear Hashing: Example To split bucket 0, use another function h1(x): h0(x) = x mod N , h1(x) = x mod (2*N) Bucket id 0 1 2 3 4 13 8 5 9 6 7 11 4 17
Linear Hashing: Example h0(x) = x mod N , h1(x) = x mod (2*N) Insert 15 and 3 Bucket id 0 1 2 3 4 13 8 5 9 6 7 11 4 17
Linear Hashing: Example h0(x) = x mod N , h1(x) = x mod (2*N) Bucket id 0 1 2 3 4 5 17 15 8 9 6 7 11 4 13 5 3
Linear Hashing: Search h0(x) = x mod N (for the un-split buckets) h1(x) = x mod (2*N) (for the split ones) Bucket id 0 1 2 3 4 5 17 15 8 9 6 7 11 4 13 5 3
Linear Hashing: Search h1(x) = x mod 8 (for the un-split buckets) h2(x) = x mod 16 (for the split ones) 0 1 2 3 4 5 6 7 17 8 9 6 3 11 4 13 5 15 7 After we split the Nth bucket (3), we reset the Next pointer to 0 and we start a new round. The two hash functions are now h1 and h2. Level =1
Linear Hashing: Search Algorithm for Search: Search(k) 1 b = h0(k) 2 if b < split-pointer then 3 b = h1(k) 4 read bucket b and search there
References [Litwin80] Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 http://www.cs.bu.edu/faculty/gkollios/ada01/Papers/linear-hashing.PDF
