A B+ tree (previous chapter, B-Tree & B+ Tree) finds a record in 3 or 4 block accesses. That is already excellent. But what if we could find it in about one?
That is the promise of hashing. Instead of walking down a tree, the DBMS feeds the search key into a hash function, which directly computes the address of the block (bucket) where the record should be. No tree, no levels: just compute and jump.
Hashing in DBMS is a technique that uses a hash function on a search key to compute the address of the disk bucket where the record is stored, allowing equality searches in close to one block access.
You may already know hash tables from data structures (where slots are in memory). In a database the idea is the same, but the "slots" are disk blocks called buckets, each holding several records. The chapter File Organization introduced hash file organization; here we study it as an indexing technique in depth, including how hash structures grow.
Basic Terms
Term | Meaning |
|---|---|
Bucket | A unit of storage (usually one disk block) that holds one or more records or index entries. |
Hash function h | A function from the set of search-key values to the set of bucket addresses, e.g. h(K) = K mod M. |
Bucket overflow | A record hashes to a bucket that is already full. |
Hash file organization | The table's records themselves are stored in buckets chosen by h. |
Hash index | Only index entries (key, record pointer) are stored in buckets; records live elsewhere. |
What Makes a Good Hash Function?
Uniform: each bucket should receive about the same number of key values from the set of all possible values.
Random-looking: on real data, records should spread evenly regardless of patterns in the keys (e.g. many roll numbers ending in 0).
Fast to compute.
Bad example: hashing employee names by their first letter into 26 buckets. Far more names start with "S" or "A" than with "X" or "Q", so some buckets overflow while others stay almost empty.
Common choice: h(K) = K mod M, where M (the number of buckets) is often chosen as a prime, because a prime M reduces the chance that patterns in the keys (like all multiples of 10) pile up in a few buckets.
Static Hashing
In static hashing, the number of buckets M is fixed when the file is created.
Example
M = 5 buckets, each bucket holds 2 records, h(K) = K mod 5. Insert keys 12, 7, 15, 23, 40, 17, 9, 31.
Key K mod 5 Bucket
12 2 2
7 2 2
15 0 0
23 3 3
40 0 0
17 2 2 <-- bucket 2 already has 12 and 7: OVERFLOW
9 4 4
31 1 1
Bucket 0: [15, 40]
Bucket 1: [31, ]
Bucket 2: [12, 7] --> overflow block: [17, ]
Bucket 3: [23, ]
Bucket 4: [ 9, ]
Operations
Search K: compute h(K), read that bucket (1 block access), and follow its overflow chain if the key is not found there. Searching for 17 costs 2 block accesses (bucket 2 + its overflow block); searching for 23 costs 1.
Insert K: compute h(K) and put the record in that bucket; if it is full, put it in an overflow block.
Delete K: search, then remove.
Why Do Buckets Overflow?
Insufficient buckets: M is too small for the number of records.
Skew: some buckets get many more records than others, either because many records share the same search-key value (e.g. hashing on
citywhen half the customers live in Mumbai) or because the hash function distributes keys poorly.
Even with a perfect hash function, skew from duplicate key values cannot be removed: all records with the same key must go to the same bucket.
Handling Overflow
Overflow chaining: a full bucket gets a linked list of overflow blocks (as above). This is the usual approach in databases. Textbooks also call this closed addressing, because a key always stays in its own bucket's chain.
Open addressing: put the record in the next available bucket (linear probing, quadratic probing, etc.). Deletion becomes messy, so this is used less often for database files. (Careful with names: data-structure books call open addressing "closed hashing", while Silberschatz's DBMS textbook does the opposite and calls overflow chaining "closed hashing" and open addressing "open hashing". Just remember the two mechanisms.)
The Big Problem with Static Hashing
Databases grow and shrink, but M is fixed:
If M is chosen for today's size, long overflow chains appear as the table grows, and searches slow down from 1 block access to many.
If M is chosen for the future size, a lot of space is wasted today.
Rehashing into a new, bigger table means reading and rewriting every record, which is very expensive on a large table and blocks normal work while it runs.
The solution is dynamic hashing: hash structures that grow and shrink gradually, one bucket at a time. The two classic schemes are extendible hashing and linear hashing.
Extendible Hashing
Extendible hashing adds a level of indirection: a directory (an array of bucket pointers).
The hash function produces a long bit string. Only the last d bits are used to index the directory. d is the global depth, and the directory has 2d entries.
Each bucket has a local depth d' ≤ d: the number of bits that all keys in that bucket actually share.
Several directory entries can point to the same bucket when d' < d. In fact exactly 2d − d' entries point to it.
Insertion Rules
Use the last d bits of h(K) to find the directory entry, and go to its bucket.
If the bucket has space, insert. Done.
If the bucket is full and local depth < global depth: split the bucket only. Increase its local depth by 1, create a new bucket, redistribute the keys using one more bit, and update the directory pointers that pointed to the old bucket. The directory does not change size.
If the bucket is full and local depth = global depth: first double the directory (global depth + 1; each new entry copies the pointer of its "twin"), then split the bucket as in step 3.
Retry the insert (in rare cases a split must be repeated if all keys still land in the same bucket).
Worked Example
Bucket capacity = 2, h(K) = K (use the key's binary form), start with global depth 1 (two directory entries, 0 and 1, pointing to two buckets of local depth 1). Insert 4, 8, 5, 7, 10, 3, 15.
Binary (last 3 bits): 4 = 100 8 = 000 5 = 101 7 = 111
10 = 010 3 = 011 15 = 111
Insert 4, 8, 5, 7 (last bit 0 goes to entry 0, last bit 1 goes to entry 1): all fit.
Global depth 1
0 -> [4, 8] local depth 1
1 -> [5, 7] local depth 1
Insert 10 (last bit 0): bucket [4, 8] is full, and local depth 1 = global depth 1. So double the directory to global depth 2, then split using 2 bits: 4 = …00, 8 = …00 stay; 10 = …10 goes to the new bucket.
Global depth 2
00 -> [4, 8] local depth 2
01 -> [5, 7] local depth 1 (shared)
10 -> [10] local depth 2
11 -> [5, 7] local depth 1 (same bucket as 01)
Insert 3 (last two bits 11): the bucket [5, 7] is full, but its local depth 1 < global depth 2. So split the bucket without touching the directory size: 5 = …01 stays, 7 = …11 and 3 = …11 move to the new bucket.
Global depth 2
00 -> [4, 8] local depth 2
01 -> [5] local depth 2
10 -> [10] local depth 2
11 -> [7, 3] local depth 2
Insert 15 (…11): bucket [7, 3] is full and local depth 2 = global depth 2, so the directory doubles to global depth 3 and the bucket splits on the third-last bit: 3 = 011 goes to entry 011, while 7 = 111 and 15 = 111 go to entry 111.
Global depth 3
000 -> [4, 8] local depth 2
001 -> [5] local depth 2
010 -> [10] local depth 2
011 -> [3] local depth 3
100 -> [4, 8] (same bucket as 000)
101 -> [5] (same bucket as 001)
110 -> [10] (same bucket as 010)
111 -> [7, 15] local depth 3
Only one bucket was actually split each time. The other buckets were not touched at all: their directory entries were simply copied. That is why extendible hashing grows smoothly.
Pros and Cons
Pro: a search needs 1 directory lookup + 1 bucket read (and the directory is often small enough to stay in memory).
Pro: no overflow chains (for distinct keys) and no full rehash.
Con: doubling the directory is a sudden, larger operation, and with skewed hash values the directory can grow much bigger than the number of buckets.
Linear Hashing
Linear hashing grows without any directory. Buckets are split in a fixed, round-robin order, one at a time, using a pointer usually called next (or the split pointer).
Start with N buckets and hash function h0(K) = K mod N. At the next level, h1(K) = K mod 2N, and so on.
When a split is triggered (for example, whenever any insert causes an overflow), the bucket pointed to by next is split, not necessarily the bucket that overflowed. Its records are rehashed with h1 into itself and a new bucket at the end. Then next moves forward by one.
Overflowing buckets use temporary overflow blocks until their turn to be split comes.
Address rule: compute a = h0(K). If a < next, that bucket has already been split in this round, so use h1(K) instead.
Small trace: N = 2, bucket capacity 2, split whenever an insert overflows. Insert 8, 3, 12, 5, 7, 10, 15.
Insert 8, 3, 12, 5: next = 0 B0: [8, 12] B1: [3, 5]
Insert 7 -> 7 mod 2 = 1, B1 overflows (7 goes to an overflow block).
Split bucket next = 0 (NOT bucket 1!) using K mod 4:
8 mod 4 = 0, 12 mod 4 = 0 -> both stay in B0, new B2 is empty.
next = 1
B0: [8, 12] B1: [3, 5 | 7] B2: [ ]
Insert 10 -> 10 mod 2 = 0, and 0 < next, so use 10 mod 4 = 2 -> B2
B0: [8, 12] B1: [3, 5 | 7] B2: [10]
Insert 15 -> 15 mod 2 = 1 -> B1, overflows again. Split bucket next = 1 with K mod 4:
5 mod 4 = 1 stays; 3, 7, 15 mod 4 = 3 go to new B3.
next reaches 2 = N, so the round ends: next = 0, now h0 = K mod 4
B0: [8, 12] B1: [5] B2: [10] B3: [3, 7 | 15]
Bucket 3 still has an overflow record. That is normal in linear hashing: overflow chains stay short because every bucket gets split in turn. The win is that growth is perfectly gradual, one bucket per split, with no directory to double.
Hash Index vs B+ Tree Index
Feature | Hash Index | B+ Tree Index |
|---|---|---|
Equality search ( | Excellent, about 1 to 2 block accesses | Very good, height of tree (3 to 4) |
Range search ( | Useless: neighbouring keys hash to random buckets | Excellent: walk the linked leaves |
ORDER BY / sorted output | No | Yes |
Prefix search ( | No | Yes |
Behaviour with heavy duplicates / skew | Long overflow chains | Handles well |
Growth | Static: needs rehash. Dynamic: extendible/linear | Always gradual (splits) |
Why can't a hash index do ranges? A good hash function deliberately scatters keys. 20 and 21 may land in buckets 7 and 2. There is no order to follow, so the DBMS would have to check every bucket.
This is why relational databases use B+ trees as the default index, and hash indexes only where queries are purely equality lookups.
Hashing in a Real DBMS (MySQL 8.4)
Let us check what MySQL actually does. In a scratch database:
InnoDB Does Not Build Hash Indexes
CREATE TABLE city_lookup (
city VARCHAR(50),
pin CHAR(6),
INDEX idx_city USING HASH (city)
) ENGINE=InnoDB;
SHOW WARNINGS;
+-------+------+---------------------------------------------------------------------------------------------------------+
| Level | Code | Message |
+-------+------+---------------------------------------------------------------------------------------------------------+
| Note | 3502 | This storage engine does not support the HASH index algorithm, storage engine default was used instead. |
+-------+------+---------------------------------------------------------------------------------------------------------+
SELECT INDEX_NAME, INDEX_TYPE FROM information_schema.STATISTICS
WHERE TABLE_NAME = 'city_lookup';
+------------+------------+
| INDEX_NAME | INDEX_TYPE |
+------------+------------+
| idx_city | BTREE |
+------------+------------+
MySQL quietly built a B+ tree instead. InnoDB, the default storage engine, supports only B-tree (B+ tree) indexes for normal columns (plus special full-text and spatial indexes).
The MEMORY Engine Uses Hash Indexes
CREATE TABLE session_cache (
session_id CHAR(8) PRIMARY KEY,
user_id INT
) ENGINE=MEMORY;
SELECT INDEX_NAME, INDEX_TYPE FROM information_schema.STATISTICS
WHERE TABLE_NAME = 'session_cache';
+------------+------------+
| INDEX_NAME | INDEX_TYPE |
+------------+------------+
| PRIMARY | HASH |
+------------+------------+
Insert three sessions, then compare an equality lookup with a range condition:
INSERT INTO session_cache VALUES ('a1b2c3d4', 1), ('e5f6g7h8', 2), ('i9j0k1l2', 3);
EXPLAIN SELECT user_id FROM session_cache WHERE session_id = 'e5f6g7h8';
+----+-------------+---------------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
| 1 | SIMPLE | session_cache | NULL | const | PRIMARY | PRIMARY | 32 | const | 1 | 100.00 | NULL |
+----+-------------+---------------+------------+-------+---------------+---------+---------+-------+------+----------+-------+
EXPLAIN SELECT user_id FROM session_cache WHERE session_id > 'e';
+----+-------------+---------------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+---------------+------------+------+---------------+------+---------+------+------+----------+-------------+
| 1 | SIMPLE | session_cache | NULL | ALL | PRIMARY | NULL | NULL | NULL | 3 | 33.33 | Using where |
+----+-------------+---------------+------------+------+---------------+------+---------+------+------+----------+-------------+
The equality lookup uses the hash index (key = PRIMARY). The range condition cannot (key = NULL, type = ALL, a full scan), exactly as the theory predicts.
Adaptive Hash Index
InnoDB has an internal feature called the adaptive hash index: it can automatically build an in-memory hash table over frequently accessed B+ tree pages to speed up repeated equality lookups. You never create it yourself. In MySQL 8.4 it is disabled by default (it was enabled by default in older versions):
SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';
+----------------------------+-------+
| Variable_name | Value |
+----------------------------+-------+
| innodb_adaptive_hash_index | OFF |
+----------------------------+-------+
Hashing also appears inside query execution: MySQL 8 uses the hash join algorithm for many joins. That is hashing used temporarily during a query, not a stored index. We will meet it in Query Processing & Optimization.
Common Mistakes
Expecting a hash index to help range queries, ORDER BY or LIKE 'abc%'. It only helps equality.
Thinking a perfect hash function prevents all overflow. Duplicate key values always go to the same bucket.
In extendible hashing, doubling the directory on every split. Double only when the full bucket's local depth equals the global depth.
Using the first bits instead of the last bits (or vice versa) inconsistently. Either convention is fine; textbooks differ. Pick one and stick to it.
In linear hashing, splitting the overflowing bucket. The bucket at the split pointer is split, which may be a different bucket.
Assuming
USING HASHcreates a hash index in InnoDB. It creates a B+ tree, with only a Note-level warning.
Interview Questions
1. What is hashing in DBMS?
A technique that applies a hash function to a search key to compute the address of the bucket (disk block) holding the record, giving near one-block-access equality search.
2. What is bucket overflow and how is it handled?
It occurs when a record hashes to a full bucket, due to too few buckets or skew. It is usually handled with overflow chaining (a linked list of overflow blocks); open addressing is an alternative.
3. Static vs dynamic hashing?
Static hashing fixes the number of buckets, so growth causes long overflow chains or expensive rehashing. Dynamic hashing (extendible, linear) adds buckets gradually as data grows.
4. Explain global depth and local depth in extendible hashing.
Global depth d is the number of hash bits used to index the directory (2d entries). Local depth of a bucket is the number of bits its keys share. If a full bucket has local depth less than d, it is split without growing the directory; if equal, the directory doubles first.
5. When would you prefer a hash index over a B+ tree?
When the workload is only exact-match lookups on a key (e.g. session ID, cache key) and range or sorted access is never needed.
6. Why is a prime number often used as the number of buckets in mod hashing?
A prime modulus reduces the chance that regular patterns in keys (such as many multiples of 10) cluster into a few buckets, spreading keys more evenly.
7. Does MySQL InnoDB support hash indexes?
Not as user-created indexes; USING HASH is ignored and a B-tree is built. The MEMORY engine supports hash indexes, and InnoDB has an internal adaptive hash index (off by default in MySQL 8.4).
Summary
Hashing computes a bucket address from the key: about one block access for equality search.
A good hash function is uniform and random-looking; h(K) = K mod (prime) is a common choice.
Static hashing has a fixed number of buckets; growth leads to overflow chains or costly rehashing.
Extendible hashing uses a directory of 2d pointers; buckets split one at a time and the directory doubles only when needed.
Linear hashing has no directory; buckets split in round-robin order using a split pointer.
Hash indexes cannot do range queries or sorting, which is why B+ trees are the default in relational databases.
In MySQL: InnoDB uses B+ trees, the MEMORY engine supports hash indexes, and the adaptive hash index is off by default in 8.4.
Hashing is the fastest way to answer "where is exactly this key?" and the worst way to answer "which keys are between these two?"