Hashing & File Organization

While B+ Trees are great for range queries, Hashing is the fastest way to find a unique record — O(1) average time complexity.

This chapter covers how records are physically organized on disk and how hash-based indexing works.

---

Learning Objectives

After completing this chapter, you will be able to:

• Describe different file organization methods (Heap, Sequential, Hash).
• Explain Static and Dynamic Hashing.
• Understand bucket overflow and how it’s handled.
• Compare Hashing vs B+ Trees for different query types.
• Understand extendible hashing.
• Answer interview questions on file organization and hashing.

---

File Organization Methods

How records are physically stored in data files:

1. Heap File Organization

Records are placed wherever there is free space. New records are appended at the end.

Feature	Behavior
Insert	Fast (append)
Search by key	Slow (must scan entire file)
Delete	Mark as deleted (or compact)
Storage	No ordering overhead

Use case: Log tables, temporary tables — where you always read by timestamp order.

2. Sequential File Organization

Records are stored in order based on a search key.

Feature	Behavior
Insert	Slow (must find correct position, shift data)
Search by key	Fast (binary search — O(log N))
Range scan	Very fast (sequential read)
Storage	Needs periodic reorganization

Use case: Tables where range scans are common and inserts are batch-processed.

3. Hash File Organization

Records are placed in buckets based on a hash function applied to the search key.

Feature	Behavior
Insert	Fast (hash → bucket → append)
Search by key	O(1) average
Range scan	Terrible (hashing scatters data)
Storage	Buckets may have overflow chains

Use case: Equality lookups — “find user by ID.”

---

Comparison Table

Method	Point Search	Range Search	Insertion	Deletion
Heap	O(N)	O(N)	O(1)	O(1) + mark
Sequential	O(log N)	O(log N + results)	O(N)	O(N)
Hash	O(1) avg	O(N)	O(1)	O(1)

---

Static Hashing

Concept: A fixed number of buckets is allocated. A hash function maps each search key to a bucket number.

Hash Function h(K) = K mod N (N = number of buckets)

Key 101 → 101 mod 5 = 1 → Bucket 1
Key 107 → 107 mod 5 = 2 → Bucket 2
Key 103 → 103 mod 5 = 3 → Bucket 3

Bucket Overflow

Occurs when a bucket is full and a new record needs to be inserted.

Handling overflow:

• Overflow Chaining: Link to an overflow block (like a linked list)
• Open Addressing: Find the next empty bucket

Problem with Static Hashing

As the database grows, buckets fill up. More overflow chains = slower queries. To fix this, you need Rehashing — creating a new hash table with more buckets and copying all data. This is expensive and requires downtime.

---

Dynamic Hashing (Extendible Hashing)

Concept: The number of buckets grows and shrinks dynamically as data is added or deleted.

How It Works

1. A directory of pointers maps logical bucket numbers to physical buckets
2. When a bucket overflows, it splits into two, and the directory is updated
3. The hash function uses a global depth and local depth to determine bucket assignment

Directory                  Buckets
┌─────┐                   ┌───────────────┐
│ 00  │ ─────────────────→│ Bucket A      │
├─────┤                   │ (Keys ending  │
│ 01  │ ─────────────┐   │  in 00)       │
├─────┤              │   └───────────────┘
│ 10  │ ──────────┐  │   ┌───────────────┐
├─────┤           │  └──→│ Bucket B      │
│ 11  │ ───────┐  │      │ (Keys ending  │
└─────┘        │  │      │  in 01)       │
               │  │      └───────────────┘
               │  │      ┌───────────────┐
               │  └─────→│ Bucket C      │
               │         │ (Keys ending  │
               │         │  in 10)       │
               │         └───────────────┘
               │         ┌───────────────┐
               └────────→│ Bucket D      │
                         │ (Keys ending  │
                         │  in 11)       │
                         └───────────────┘

Advantages

• Grows incrementally without stopping the database
• No expensive rehashing — only the overflowing bucket is split
• Directory size adjusts automatically

---

Hashing vs B+ Tree

Factor	Hash Index	B+ Tree Index
Point query	O(1) — fastest	O(log N)
Range query	Terrible (scatter)	Fast (linked leaves)
Sorting	No order preserved	Sorted order
Partial key search	Not supported	Supported
R树 size	Fixed/variable	Grows predictably

When to use each:

• Hash Index: High-volume equality lookups (cache tables, key-value stores)
• B+ Tree Index: Range queries, sorting, partial key searches, general purpose

---

Interview Deep Dive

---

Key Takeaways

• Heap: Fast insert, slow search — for temporary data.
• Sequential: Good for range scans — requires periodic reorganization.
• Hash: O(1) point queries — terrible for ranges.
• Static Hashing: Fixed buckets → overflow issues → requires expensive rehashing.
• Dynamic Hashing: Buckets split on overflow → grows incrementally.
• Overflow Chaining: Linked list of overflow blocks for static hashing.
• Hash indexes are ideal for equality lookups; B+ Trees are better for ranges and general purpose.