CMPT 454 Lecture Notes - Lecture 7: Binary Search Algorithm, Query Optimization, Bitmap Index
30 May 2016
School
Department
Course
Professor
Document Summary
Number of buckets (n) is selected such that the average occupancy is set. Full buckets are not always split, overflow is allowed. But the average number of overflow blocks per bucket is < 1 i. e. less total overflow buckets than n. Number of bits used to number the entries in the bucket array is ceil (log2 (n)) Hash function determines which bucket to put record in. Primary blocks of the buckets are stored sequentially. E. g. bucket m can be found by m + address(first bucket) Like extensible hashing, only the rightmost (i) bits of h(k) are used to determine bucket. If the record should go to 110 bucket but the max bucket is 101, with n = 6, just drop the first bit, so make it go to bucket 010. Whenever records/buckets ratio exceeds a limit, a new bucket is created. When a new bucket is added (m), redistribute related buckets. When n > 2^i, i is incremented by one.
