Hash File Organization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/*
 * Common Hash Functions for File Organization
 */
 
// Simple modulo hash (for integer keys)
function hash_mod(key: int, num_buckets: int) -> int {
    return key % num_buckets;
}
 
// Division method with prime number
// Using a prime number for num_buckets improves distribution
function hash_prime_mod(key: int, num_buckets: int) -> int {
    // Choose num_buckets as a prime not close to powers of 2
    // Good primes: 97, 997, 9973, 99991, 999983
    return key % num_buckets;
}
 
// Multiplication method (Knuth's suggestion)
function hash_multiply(key: int, num_buckets: int) -> int {
    const A = 0.6180339887;  // (sqrt(5) - 1) / 2, golden ratio
    double fractional_part = (key * A) - floor(key * A);
    return floor(num_buckets * fractional_part);
}
 
// String hashing (polynomial rolling hash)
function hash_string(key: string, num_buckets: int) -> int {
    const int BASE = 31;  // Small prime
    const int MOD = 1000000007;  // Large prime
    
    int64 hash_value = 0;
    int64 power = 1;
    
    for (char c in key) {
        hash_value = (hash_value + (c - 'a' + 1) * power) % MOD;
        power = (power * BASE) % MOD;
    }
    
    return hash_value % num_buckets;
}
 
// FNV-1a hash (commonly used in practice)
function fnv1a_hash(key: bytes, num_buckets: int) -> int {
    const int64 FNV_OFFSET = 14695981039346656037;
    const int64 FNV_PRIME = 1099511628211;
    
    int64 hash = FNV_OFFSET;
    for (byte b in key) {
        hash = hash XOR b;
        hash = hash * FNV_PRIME;
    }
    
    return hash % num_buckets;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

/*
 * Static Hash File Structure
 * 
 * ┌─────────────────────────────────────────────────────────────────┐
 * │                        FILE HEADER                               │
 * │  - Number of buckets (N)                                         │
 * │  - Hash function identifier                                      │
 * │  - Records per bucket                                            │
 * │  - Total record count                                            │
 * └─────────────────────────────────────────────────────────────────┘
 * 
 * ┌─────────────────────────────────────────────────────────────────┐
 * │                    BUCKET DIRECTORY                              │
 * │  Bucket 0  →  Page 10                                           │
 * │  Bucket 1  →  Page 23                                           │
 * │  Bucket 2  →  Page 5                                            │
 * │  Bucket 3  →  Page 17                                           │
 * │  ...                                                            │
 * │  Bucket N-1 → Page 42                                           │
 * └─────────────────────────────────────────────────────────────────┘
 * 
 *         Bucket 0                    Bucket 1                  
 * ┌─────────────────────┐     ┌─────────────────────┐
 * │ Primary Page        │     │ Primary Page        │
 * │ Record (key=100)    │     │ Record (key=7)      │
 * │ Record (key=300)    │     │ Record (key=107)    │
 * │ Record (key=700)    │     │ Record (key=207)    │
 * │ ...                 │     │ ...                 │
 * │ Overflow ptr → ────────┐  │ Overflow ptr → NULL │
 * └─────────────────────┘  │  └─────────────────────┘
 *                          ▼
 *                ┌─────────────────────┐
 *                │ Overflow Page       │
 *                │ Record (key=500)    │
 *                │ Record (key=900)    │
 *                │ Overflow ptr → NULL │
 *                └─────────────────────┘
 */
 
struct HashFileHeader {
    int32   magic_number;
    int32   version;
    int64   num_buckets;           // N - fixed at creation
    int64   records_per_bucket;    // Capacity before overflow
    int64   total_records;
    int64   overflow_records;      // Records in overflow chains
    int32   hash_function_id;      // Which hash function to use
    int32   key_offset;            // Offset of key within record
    int32   key_length;            // Length of key field
    byte    reserved[200];
}
 
struct BucketDirectory {
    PageID  entries[NUM_BUCKETS];  // Direct mapping: bucket # → page ID
}
 
struct BucketPage {
    int32   bucket_id;             // Which bucket this page belongs to
    int32   record_count;          // Records currently in this page
    int32   free_space;            // Available space
    PageID  overflow_ptr;          // Link to next page in chain (or NULL)
    Record  records[];             // Actual record data
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

function hash_search(HashFile file, Key target) -> Record? {
    // Step 1: Compute bucket address
    int bucket_num = hash(target) % file.header.num_buckets;
    
    // Step 2: Get primary page for this bucket
    PageID page_id = file.directory.entries[bucket_num];
    
    // Step 3: Search within bucket (including overflow chain)
    while (page_id != NULL) {
        Page page = buffer_pool.get_page(file.file_id, page_id);
        
        // Linear search within page (records are unordered in bucket)
        for (int i = 0; i < page.record_count; i++) {
            Record record = page.get_record(i);
            if (extract_key(record) == target) {
                return record;  // Found!
            }
        }
        
        // Move to overflow page if exists
        page_id = page.overflow_ptr;
    }
    
    return null;  // Not found in this bucket
}
 
/*
 * Complexity Analysis:
 * 
 * Best case (no overflow, found in first check):
 *   - Hash computation: O(1)
 *   - Directory lookup: O(1) 
 *   - Page read: 1 I/O
 *   - Search within page: O(records per page)
 *   - Total: O(1) I/O, O(r) comparisons
 * 
 * Average case (short overflow chain):
 *   - Pages in chain: 1 + (overflow_records / bucket_capacity)
 *   - Total: O(1 + m) I/Os where m = overflow chain length
 * 
 * Worst case (severe overflow, all records in one bucket):
 *   - Degenerates to O(n) if all records hash to same bucket
 *   - This is why good hash functions matter!
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

function hash_insert(HashFile file, Record new_record) -> RID {
    Key key = extract_key(new_record);
    
    // Step 1: Compute bucket
    int bucket_num = hash(key) % file.header.num_buckets;
    
    // Step 2: Get primary page for bucket
    PageID page_id = file.directory.entries[bucket_num];
    Page page = buffer_pool.get_page(file.file_id, page_id);
    
    // Step 3: Find page with space (follow chain if needed)
    PageID last_page_id = page_id;
    while (page.is_full() && page.overflow_ptr != NULL) {
        last_page_id = page.overflow_ptr;
        page = buffer_pool.get_page(file.file_id, page.overflow_ptr);
    }
    
    // Step 4: Insert into page or create overflow
    if (page.has_space_for(new_record)) {
        int slot = page.add_record(new_record);
        buffer_pool.mark_dirty(page);
        file.header.total_records++;
        return RID(page.page_id, slot);
    }
    
    // Step 5: Need overflow page
    PageID new_page_id = allocate_overflow_page(file, bucket_num);
    Page new_page = buffer_pool.get_page(file.file_id, new_page_id);
    
    // Link from last page in chain
    page.overflow_ptr = new_page_id;
    buffer_pool.mark_dirty(page);
    
    // Insert into new overflow page
    int slot = new_page.add_record(new_record);
    buffer_pool.mark_dirty(new_page);
    
    file.header.total_records++;
    file.header.overflow_records++;
    
    return RID(new_page_id, slot);
}
 
/*
 * Complexity:
 * - Best case: Hash + 1 I/O to read, 1 I/O to write = O(1) I/O
 * - Average case: O(1 + chain_length) I/Os
 * - Worst case: O(chain_length) to traverse + 1 to write
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

function hash_delete(HashFile file, Key target) -> bool {
    // Step 1: Find the bucket
    int bucket_num = hash(target) % file.header.num_buckets;
    PageID page_id = file.directory.entries[bucket_num];
    
    // Step 2: Search and delete
    PageID prev_page_id = NULL;
    
    while (page_id != NULL) {
        Page page = buffer_pool.get_page(file.file_id, page_id);
        
        for (int i = 0; i < page.record_count; i++) {
            Record record = page.get_record(i);
            if (extract_key(record) == target) {
                // Found! Delete the record
                page.delete_record(i);
                buffer_pool.mark_dirty(page);
                file.header.total_records--;
                
                // Optional: Coalesce empty overflow pages
                if (page.is_empty() && prev_page_id != NULL) {
                    coalesce_overflow_chain(file, bucket_num, prev_page_id, page_id);
                }
                
                return true;
            }
        }
        
        prev_page_id = page_id;
        page_id = page.overflow_ptr;
    }
    
    return false;  // Key not found
}
 
function coalesce_overflow_chain(HashFile file, int bucket, 
                                  PageID prev_id, PageID empty_id) {
    Page prev_page = buffer_pool.get_page(file.file_id, prev_id);
    Page empty_page = buffer_pool.get_page(file.file_id, empty_id);
    
    // Skip over the empty page
    prev_page.overflow_ptr = empty_page.overflow_ptr;
    buffer_pool.mark_dirty(prev_page);
    
    // Return empty page to free list
    file.free_page(empty_id);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/*
 * Overflow Chain Analysis
 * 
 * Given:
 *   - N = number of buckets
 *   - n = number of records
 *   - b = records per page (bucket capacity)
 *   - α = load factor = n / (N × b)
 * 
 * Expected chain length (with good hash function):
 *   E[chain length] ≈ max(1, α)
 * 
 * Example:
 *   N = 1000 buckets
 *   b = 40 records per page
 *   Capacity = 40,000 records
 *   
 *   If n = 40,000: α = 1.0, average 1 page per bucket (ideal)
 *   If n = 80,000: α = 2.0, average 2 pages per bucket
 *   If n = 400,000: α = 10.0, average 10 pages per bucket (severe overflow!)
 * 
 * Search cost with overflow chains:
 *   Average pages read = 1 + (α - 1)/2 = (α + 1)/2  if α > 1
 *   For α = 10: average 5.5 page reads per search
 *   
 * This is why static hashing struggles with growth!
 */
 
// Overflow statistics collector
function analyze_overflow(HashFile file) -> OverflowStats {
    int total_buckets = file.header.num_buckets;
    int total_overflow_pages = 0;
    int max_chain_length = 0;
    int empty_buckets = 0;
    
    for (int i = 0; i < total_buckets; i++) {
        int chain_length = 0;
        PageID page_id = file.directory.entries[i];
        
        while (page_id != NULL) {
            chain_length++;
            Page page = buffer_pool.get_page(file.file_id, page_id);
            
            if (chain_length == 1 && page.record_count == 0) {
                empty_buckets++;
            }
            
            page_id = page.overflow_ptr;
        }
        
        total_overflow_pages += max(0, chain_length - 1);
        max_chain_length = max(max_chain_length, chain_length);
    }
    
    return OverflowStats {
        avg_chain_length: (total_buckets + total_overflow_pages) / total_buckets,
        max_chain_length: max_chain_length,
        empty_bucket_ratio: empty_buckets / total_buckets,
        overflow_page_ratio: total_overflow_pages / total_buckets
    };
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

/*
 * Range Query: WHERE key BETWEEN low AND high
 */
 
// Sorted File: Efficient
function range_query_sorted(SortedFile file, Key low, Key high) -> List<Record> {
    PageID start = binary_search_pages(file, low);
    List<Record> results;
    
    for (page in pages from start until max_key > high) {
        for (record in page where low <= key <= high) {
            results.add(record);
        }
    }
    // Cost: log(B) + number of pages containing matching records
    return results;
}
 
// Hash File: Must scan everything
function range_query_hash(HashFile file, Key low, Key high) -> List<Record> {
    List<Record> results;
    
    // Must check EVERY bucket - no way to know which contain matching keys
    for (bucket in 0 to file.header.num_buckets - 1) {
        PageID page_id = file.directory.entries[bucket];
        
        while (page_id != NULL) {
            Page page = buffer_pool.get_page(file.file_id, page_id);
            
            for (int i = 0; i < page.record_count; i++) {
                Record record = page.get_record(i);
                Key key = extract_key(record);
                
                if (key >= low && key <= high) {
                    results.add(record);
                }
            }
            
            page_id = page.overflow_ptr;
        }
    }
    // Cost: ALL pages in the file (worse than sorted, same as heap)
    return results;
}
 
/*
 * Performance Comparison for Range Query (10% selectivity):
 * 
 * File: 250,000 pages, 10 million records
 * Range: 1 million matching records (10%)
 * 
 * Sorted File: ~25,000 page reads (matching pages only)
 * Hash File: ~250,000 page reads (all pages)
 * Heap File: ~250,000 page reads (all pages)
 * 
 * Hash file is NO BETTER than heap for range queries!
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

-- PostgreSQL: Create a hash index
CREATE INDEX idx_users_email_hash ON users USING hash (email);
 
-- This index accelerates:
SELECT * FROM users WHERE email = 'user@example.com';  -- Fast!
 
-- But NOT:
SELECT * FROM users WHERE email LIKE 'user%';          -- Full scan
SELECT * FROM users WHERE email > 'a@';                -- Full scan
SELECT * FROM users ORDER BY email;                    -- No help
 
-- When to use hash index:
-- 1. Column used ONLY for equality comparisons
-- 2. Cardinality too high for bitmap index
-- 3. Value distribution is uniform
-- 4. Saving a few I/Os matters (very high throughput)
 
-- Hash index limitations in PostgreSQL:
-- - Not WAL-logged (before v10), possible data loss
-- - Cannot be used for unique constraints
-- - Cannot include additional columns (covering index)
-- - Generally, B-tree is preferred unless proven otherwise