Range Query Analysis: The Tree Index Advantage

If point queries are the battleground where hash and tree indexes compete closely, range queries are the terrain where the battle is decided before it begins. Hash indexes simply cannot perform range queries efficiently—not because of poor implementation, but because of fundamental mathematical properties of hash functions.

This limitation isn't a minor inconvenience. Range queries are ubiquitous in real-world database applications: finding all orders placed between two dates, all employees with salaries in a specific band, all products priced below a threshold. Understanding why hash indexes fail here—and how B+trees excel—is essential for practical index design.

To understand why hash indexes cannot support range queries, we must examine what hash functions do to key ordering.

The Purpose of Hashing

Hash functions are designed to uniformly distribute keys across buckets. A good hash function achieves this by deliberately scrambling the relationship between similar keys. If consecutive keys mapped to consecutive buckets, the distribution would be poor—all hot data would cluster in adjacent buckets.

Consider what happens to a sequence of integer keys:

Key     Hash Value (mod 8 buckets)
100  →  3
101  →  7
102  →  1
103  →  4
104  →  0
105  →  6
106  →  2
107  →  5

Notice that consecutive keys (100, 101, 102, ...) map to seemingly random buckets (3, 7, 1, ...). This is by design—it's exactly what makes hash indexes efficient for point lookups.

Mathematical Formalization

A hash function h: K → B maps keys from key space K to bucket space B. For range queries on [a, b], we need all keys k where a ≤ k ≤ b.

Given keys k₁ < k₂:

• Tree index guarantee: k₁ and k₂ are stored in relative order; everything between them is located between them
• Hash index non-guarantee: h(k₁) and h(k₂) have no predictable relationship; h(k₁) might be greater than, less than, or equal to h(k₂)

To support range queries, we would need a hash function where:

• If k₁ < k₂, then h(k₁) ≤ h(k₂)

But this is precisely what makes a hash function poor—keys would cluster based on their natural ordering, defeating the purpose of hashing for uniform distribution.

Let's quantify the performance difference for range queries between hash and tree indexes.

Hash Index Range Query 'Algorithm'

Since hash indexes provide no ordering, a range query on a hash-indexed column requires:

1. Full table/index scan: Examine every bucket
2. Filter application: Check each entry against range predicate
3. Result collection: Gather matching entries

Cost: O(n) where n is total number of entries—independent of how selective the range is.

B+Tree Range Query Algorithm

B+trees exploit their ordered structure to efficiently locate and scan range results:

1. Locate start: Traverse from root to leaf containing lower bound (O(log n))
2. Sequential scan: Follow leaf sibling pointers, collecting entries in range
3. Terminate: Stop when upper bound exceeded or end of index reached

Cost: O(log n + k) where k is the number of matching entries

Range queries come in several forms, all of which B+trees handle efficiently and hash indexes cannot support:

Bounded Range Queries

SELECT * FROM orders WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31'
SELECT * FROM products WHERE price >= 10.00 AND price <= 50.00
SELECT * FROM employees WHERE hire_date >= '2020-01-01'

Unbounded Range Queries (One-Sided)

SELECT * FROM transactions WHERE amount > 10000  -- Find high-value transactions
SELECT * FROM inventory WHERE quantity < 10      -- Find low-stock items
SELECT * FROM users WHERE last_login < NOW() - INTERVAL '90 days'  -- Inactive users

Prefix Queries (String Ranges)

Prefix matching is a special case of range query:

SELECT * FROM customers WHERE name LIKE 'Smith%'
SELECT * FROM products WHERE sku LIKE 'ELEC-%'

These translate to range queries:

• 'Smith%' → BETWEEN 'Smith' AND 'Smithzzz...' (conceptually)

B+trees support this naturally through sorted string ordering. Hash indexes cannot—hashing 'Smith' and 'Smithson' produces unrelated bucket addresses.

Min/Max Queries

SELECT MIN(price), MAX(price) FROM products WHERE category = 'Electronics'
SELECT * FROM orders ORDER BY order_date DESC LIMIT 10

These leverage the ordering of B+trees:

• MIN: Navigate to leftmost leaf (O(log n))
• MAX: Navigate to rightmost leaf (O(log n))
• ORDER BY: Follow leaf chain in order (no sorting needed)

Hash indexes require full scans for all of these.

Beyond algorithmic complexity, B+trees provide a crucial I/O efficiency advantage for range queries: sequential access at the leaf level.

Leaf Node Linking

B+tree leaf nodes are linked via sibling pointers, forming a doubly-linked list:

[Leaf₀] ↔ [Leaf₁] ↔ [Leaf₂] ↔ [Leaf₃] ↔ [Leaf₄] ↔ ...

This structure enables sequential scanning after locating the range start. On traditional spinning disks, sequential reads are dramatically faster than random reads:

• Random disk seek: 5-10 ms
• Sequential read (per page after initial seek): 0.1 ms

A range query reading 100 consecutive pages:

• Random access: 100 × 5ms = 500ms
• Sequential access: 5ms + 99 × 0.1ms ≈ 15ms

The difference can be 30x or more for disk-based systems.

Physical Clustering

B+trees often exhibit good physical clustering on disk:

• Leaf nodes created around the same time are often physically adjacent
• Sequential inserts produce sequential disk layout
• Range scans benefit from read-ahead/prefetching

Modern storage systems exploit this:

• OS read-ahead: Pre-fetches pages anticipated to be needed
• SSD internal parallelism: Sequential reads maximize channel utilization
• Database prefetching: Explicitly requests upcoming pages during scans

Range queries are pervasive in production databases. Let's examine common scenarios where the hash vs tree index decision has direct performance implications.

E-Commerce: Order Date Ranges

Financial Systems: Transaction Ranges

Analytics and Logging: Time-Series Data

The range query limitation of hash indexes has profound implications for index selection strategy.

The Mix Problem

Most real workloads combine point and range queries on the same columns:

-- Point query: Specific customer lookup
SELECT * FROM customers WHERE customer_id = 12345;

-- Range query: Customers in region
SELECT * FROM customers WHERE region = 'WEST' AND created_at > '2024-01-01';

With a hash index on customer_id:

• First query: O(1) excellent
• Second query: Full scan (cannot use hash index at all)

With a B+tree index on customer_id:

• First query: O(log n) very good
• Other indexes can be created for range queries

The hash index provides marginal point-query benefit but blocks any range capability on that column.

Range queries often benefit from covering indexes—indexes that contain all columns needed to satisfy a query without accessing the base table. This optimization interacts differently with hash and tree structures.

B+Tree Covering Indexes

B+tree indexes can include additional columns beyond the search key:

CREATE INDEX idx_orders_covering ON orders (order_date, customer_id, total_amount);

-- This query can be answered entirely from the index:
SELECT customer_id, total_amount FROM orders
WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';

Benefits:

• Index-only scans avoid table lookups entirely
• Leaves contain all needed data in sorted order
• Sequential scan through index is highly efficient

Hash Index Covering Limitations

Hash indexes can theoretically store additional columns in bucket entries, but the utility is limited:

• Random bucket access means no sequential scan benefit
• Range queries still require full index scan
• The scenario where hash + covering helps is extremely narrow (pure equality + need included columns)

Practical Example

Consider an analytics query:

SELECT product_category, SUM(quantity), SUM(revenue)
FROM order_items
WHERE order_date BETWEEN '2024-01-01' AND '2024-12-31'
GROUP BY product_category;

With B+tree covering index on (order_date, product_category, quantity, revenue):

1. Seek to order_date = '2024-01-01' (O(log n))
2. Sequential scan through year's data in index
3. Aggregate as scanning—no table access
4. All data in sorted date order

With hash index: Cannot use index for range; falls back to table scan.