Indexes and Query Performance

If B-trees offer O(log N) lookups, and hash tables offer O(1) lookups, why would anyone use B-trees? This seemingly obvious question leads to a nuanced understanding of database indexing that separates superficial knowledge from deep expertise.

Hash indexes leverage hash tables—the same data structure you use for dictionaries and maps in application code—to provide constant-time exact-match lookups. In theory, this makes them the fastest possible index type for equality queries. In practice, their adoption in database systems is surprisingly limited.

This page explores hash indexes comprehensively: their internal mechanics, their compelling strengths, their critical limitations, and the specific scenarios where they represent the optimal indexing choice.

A hash index is built on a hash table data structure. Understanding how hash tables work is essential for understanding hash index behavior.

The Hash Function:

At the core of any hash index is a hash function that maps keys to bucket locations:

hash(key) → bucket_number

Good hash functions have these properties:

• Deterministic: Same key always produces same hash
• Uniform distribution: Keys spread evenly across buckets
• Fast computation: O(1) to compute the hash
• Avalanche effect: Small key changes produce very different hashes

Databases typically use cryptographic-strength or near-cryptographic hash functions (like MurmurHash, CityHash, or xxHash) to ensure good distribution.

Bucket Structure:

The hash table consists of an array of buckets (also called slots). Each bucket can store one or more entries. The number of buckets is typically a power of 2 to enable fast modulo operations:

bucket_number = hash(key) mod num_buckets

Collision Handling:

When two different keys hash to the same bucket, we have a collision. Databases handle collisions through chaining or open addressing:

Chaining (most common in databases):

• Each bucket stores a linked list of entries
• Colliding keys are added to the list
• Lookup scans the list after finding the bucket

Open Addressing (less common):

• Colliding entries probe for the next empty bucket
• Requires more complex deletion handling
• Can have better cache performance for sparse tables

Load Factor:

The load factor (entries / buckets) determines collision probability:

• Load factor 0.5: ~50% of buckets have entries, collisions are rare
• Load factor 1.0: All buckets used, many collisions likely
• Load factor 2.0+: Significant chaining, degraded performance

Databases typically resize the hash table to maintain a load factor between 0.5 and 0.75.

Understanding the exact lookup process reveals why hash indexes are so fast for equality queries.

Step-by-Step Lookup:

Why O(1) vs O(log N) Doesn't Matter as Much as You'd Think:

Let's compare hash vs B-tree for a 1-billion row table:

The hash index saves 2-3 I/O operations per query. At 100μs per SSD read:

• Hash: 100μs
• B-tree: 300-400μs

This is a 3-4x improvement—significant, but not the orders-of-magnitude difference that "O(1) vs O(log N)" might suggest. The logarithm grows so slowly that for practical database sizes, it's effectively a small constant.

When Cache Matters:

With good caching (buffer pool holds hot pages):

• B-tree root and internal nodes: nearly always cached
• Only leaf node + heap access might hit disk
• Effective B-tree cost: ~1-2 I/O

Hash indexes also benefit from caching, but B-tree's upper levels are reused across all queries, while hash buckets are more dispersed.

The fundamental limitation of hash indexes is their inability to support range queries, ordering, or prefix matching. This single limitation explains why B-trees dominate despite their theoretical inferiority for point lookups.

Why Hash Indexes Can't Support Ranges:

Hash functions are designed to produce pseudo-random output. Two similar keys will hash to completely different buckets:

hash('alice') → bucket 42
hash('aliceb') → bucket 7
hash('alicea') → bucket 128

There's no relationship between key proximity and bucket location. To find all keys between 'alice' and 'bob', you'd need to scan every bucket—which defeats the purpose of indexing entirely.

The Practical Impact:

Most real-world queries involve more than pure equality:

-- Dashboard query: needs ranges and ordering
SELECT * FROM orders 
WHERE created_at > CURRENT_DATE - INTERVAL '30 days'
ORDER BY created_at DESC
LIMIT 100;

-- Analytics query: needs aggregation with ordering
SELECT status, COUNT(*) 
FROM orders 
GROUP BY status 
ORDER BY COUNT(*) DESC;

-- Search query: needs prefix matching
SELECT * FROM products
WHERE name LIKE 'Apple%';

None of these queries can use a hash index effectively. A single B-tree index on created_at or name handles all of them.

The Versatility Tax:

B-trees pay a small performance tax on equality queries (3x slower than hash) but support every query pattern. Hash indexes are faster for one pattern but useless for everything else. For most systems, B-tree versatility wins.

Hash index maintenance involves different trade-offs compared to B-trees. Understanding these helps evaluate the total cost of hash index ownership.

Insert Operations:

Hash index inserts are typically O(1):

1. Compute hash of new key
2. Locate target bucket
3. Add entry to bucket chain

However, if the table needs resizing (load factor too high), the cost spikes dramatically:

Resizing (Rehashing):

When the hash table grows past its load factor threshold, it must:

1. Allocate a new bucket array (typically 2x size)
2. Rehash every existing entry to new bucket locations
3. This is O(N) and blocks concurrent operations

This resize operation is expensive and causes latency spikes. Some hash implementations use incremental resizing (rehash a few entries per operation) to amortize this cost.

Space Utilization:

Hash indexes can have significant space overhead:

• Empty buckets: At load factor 0.5, half the buckets are empty
• Bucket pointers: The bucket array itself consumes space
• Collision chains: Long chains waste pointer space

The total space is often similar to or greater than B-trees, despite storing the same information.

Fragmentation:

Hash indexes can fragment when:

• Many entries are deleted, leaving empty slots
• Chains become unbalanced due to skewed access patterns
• The hash function produces poor distribution for the actual data

Unlike B-trees (where REINDEX is well-understood), hash index maintenance is less standardized across databases.

To address the resize problem, database systems use sophisticated hashing schemes that grow incrementally.

Extendible Hashing:

Extendible hashing uses a directory that doubles in size independently of the bucket pages:

1. Directory entries point to bucket pages
2. Multiple directory entries can point to the same bucket (before split)
3. When a bucket overflows, only that bucket splits
4. Directory doubles only when needed

This approach:

• Avoids full table rehashing
• Splits work proportional to bucket size, not table size
• Provides more gradual growth

Linear Hashing:

Linear hashing provides even smoother growth:

1. Split one bucket at a time in round-robin order
2. Use two hash functions: h₀(k) for unsplit buckets, h₁(k) for split buckets
3. After full round, all buckets are split and h₀ becomes h₁
4. No directory needed—split point is tracked with a single pointer

Advantages:

• Constant-time splits (one bucket at a time)
• No directory overhead
• Predictable memory usage

Trade-offs:

• Slightly more complex lookup logic
• May split buckets that don't need splitting

Database Usage:

These techniques are used in:

• PostgreSQL hash indexes (modified extendible hashing)
• In-memory hash joins and aggregations
• Hash-based temporary structures

Hash index support varies significantly across database systems, reflecting different design philosophies and use cases.

PostgreSQL Hash Indexes:

PostgreSQL provides explicit hash index support:

-- Create hash index
CREATE INDEX idx_users_email_hash 
    ON users USING HASH (email);

-- Only useful for equality
SELECT * FROM users WHERE email = 'alice@example.com';  -- Uses hash
SELECT * FROM users WHERE email LIKE 'alice%';          -- Can't use hash

When to Use (PostgreSQL):

• Very high-volume equality lookups
• Column has high cardinality (many unique values)
• Never need range queries on this column
• Benchmarks show measurable improvement over B-tree

MySQL/InnoDB Workaround:

Since InnoDB doesn't support hash indexes, you can simulate them:

-- Add a hash column
ALTER TABLE users ADD COLUMN email_hash BIGINT UNSIGNED;
UPDATE users SET email_hash = CRC32(email);
CREATE INDEX idx_email_hash ON users(email_hash);

-- Query using hash (still need email check for collision handling)
SELECT * FROM users 
WHERE email_hash = CRC32('alice@example.com') 
  AND email = 'alice@example.com';

This gives hash-like performance with B-tree storage.

Given the trade-offs, when should you choose a hash index over a B-tree? The decision should be based on clear, measurable criteria.

Real-World Hash Index Use Cases:

1. Session Lookup Tables:

-- Session ID lookup is always exact match
CREATE TABLE sessions (
    session_id VARCHAR(64) PRIMARY KEY,
    user_id INTEGER,
    created_at TIMESTAMP
);
CREATE INDEX idx_session_hash ON sessions USING HASH (session_id);

-- Query pattern: always equality
SELECT * FROM sessions WHERE session_id = 'abc123...';

2. Cache Key Tables:

-- Cache keys are arbitrary strings, looked up by exact match
CREATE TABLE cache (
    cache_key VARCHAR(255) PRIMARY KEY,
    value JSONB,
    expires_at TIMESTAMP
);
CREATE INDEX idx_cache_key_hash ON cache USING HASH (cache_key);

3. UUID/GUID Lookups:

-- UUIDs are random, equality-only, high cardinality
CREATE TABLE documents (
    doc_id UUID PRIMARY KEY,
    content JSONB
);
CREATE INDEX idx_doc_hash ON documents USING HASH (doc_id);

In distributed databases, hashing plays a crucial role beyond indexing—it determines data distribution across nodes.

Hash Partitioning (Sharding):

Distributed databases use hash functions to determine which node stores each record:

node = hash(shard_key) mod num_nodes

This ensures even data distribution across the cluster. Examples:

• DynamoDB: Partition key is hashed to determine partition
• Cassandra: Partition key hashed using murmur3
• MongoDB: Hashed shard key distributes across shards

Consistent Hashing:

Basic modulo hashing has a problem: when you add a node, every record potentially moves. Consistent hashing solves this:

1. Arrange nodes on a hash ring (0 to 2³²)
2. Each key hashes to a point on the ring
3. Key is stored on the first node clockwise from its hash point
4. Adding a node only affects keys between it and its predecessor

Hash Indexes vs Hash Partitioning:

These are related but distinct concepts:

Query Routing with Hash Partitioning:

When data is hash-partitioned:

1. Point queries (WHERE shard_key = X): Route directly to one node. O(1) nodes contacted.
2. Range queries (WHERE shard_key > X): Must fan out to ALL nodes. O(N) nodes contacted.
3. Queries on non-shard-key: Must fan out to ALL nodes. O(N) nodes contacted.

This is why hash-partitioned systems (DynamoDB, Cassandra) have excellent single-key performance but struggle with range queries—the limitation mirrors local hash indexes.

We've explored hash indexes comprehensively, from their theoretical advantages through their practical limitations. Let's consolidate the essential insights:

What's Next:

With single-column indexes covered (B-tree and hash), we move to a more complex topic in the next page: Composite indexes. You'll learn how to design indexes on multiple columns, understand column order importance, and master the prefix rule that governs composite index usage.