Course contentsShow
← Computer Science
Lesson 1694 of 2,87238. Database Transactions and IndexingFree lesson

Hash Index Insertion and Deletion

Explore how insertions and deletions work in hash indexes and the impact of bucket overflow or underutilization.

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:

  1. Apply the hash function to the indexed key
  2. Navigate to the corresponding bucket
  3. 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:

  1. Hash the key to find the bucket
  2. 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.