tailieunhanh - Principles of Database Management Systems - Notes 5: Hashing and More

Principles of Database Management Systems - Notes 5: Hashing and More presents about Two alternatives, Example hash function, Within a bucket, Rule of thumb, overflow chains, Extensible hashing, Linear hashing. | Principles of Database Management Systems Notes 5: Hashing and More Based on lecture notes by Hector Garcia-Molina 1 Hashing key h(key) . . . Buckets (typically 1 disk block) 2 Two alternatives . . . (1) key h(key) records . . . 3 Two alternatives (2) key h(key) key 1 record Index Option 2 for “secondary” search key 4 Example hash function Key = ‘x1 x2 xn’ n byte character string Have b buckets h: add x1 + x2 + + xn compute Good hash function: sum modulo b Expected number of keys/bucket is the same for all .