Hash Index Insertion and Deletion
You'll learn how hash indexes handle adding and removing records, and what happens when buckets become too full or too empty.
When you insert or delete records in a hash-indexed database table, the underlying hash index must be updated to maintain fast lookups. Understanding this process reveals the practical challenges of hash index management.
Insertion Process
When inserting a new record:
- Apply the hash function to the indexed key
- Navigate to the corresponding bucket
- Add the record reference to that bucket
Bucket Overflow occurs when a bucket becomes full. Think of it like a filing cabinet drawer that's crammed with too many folders. Solutions include:
- Chaining: Allow the bucket to grow by linking to overflow pages (like attaching an extension drawer)
- Linear Probing: Place the record in the next available bucket
- Rehashing: Rebuild the entire index with more buckets and a new hash function
Overflow degrades performance from O(1) toward O(n) as chains grow longer, requiring more disk I/O to traverse.
Deletion Process
Deleting is conceptually simpler:
- Hash the key to find the bucket
- Locate and remove the record reference
Underutilization happens when many deletions leave buckets mostly empty, wasting memory. The hash index may become sparse—like a library with many empty shelves. Some databases periodically compact or rebuild indexes to reclaim space, though this is expensive.
Unlike B-Trees, hash indexes don't automatically rebalance. You must monitor load factors (percentage of filled slots) and trigger maintenance when thresholds are crossed.
Key Takeaway:
Hash index insertions can cause bucket overflow requiring chaining or rehashing, while deletions lead to underutilization and wasted space—neither operation self-balances like B-Trees.