Tensions in Practice: Equality-focused lookup in tension with ordered queries¶

One indexed key · equality, range and successor queries

An index over keys 3, 6 and 9 can organize them by hash buckets or by order. Both can locate key 6. But knowing its hash bucket does not say which keys lie between 6 and 9, or which key comes next. An ordered index retains those relationships; a hash-only layout must do additional searching to answer them.

Optimize direct key lookup

Use a structure tailored to equality queries without maintaining key order.

Support range and successor queries

Retain relationships among keys so adjacent results can be traversed together.

Why these aims pull against each other

The same indexed field does not imply the same access capabilities. The auxiliary structure must preserve the relationship the query needs.

Compare the arrangements

Organize by hash

Use a hash-based index for the fixed keys. For these range and successor queries, inspect candidates outside the equality lookup route.

Fixed keys: 3, 6 and 9 · a hash index.
	Lookup route	Matching keys
Equal to 6	Hash key 6	6
From 6 to 9	Scan and filterHash order gives no range	6, 9
Next after 6	Inspect candidatesNo successor ordering	9

What it protects: Equality lookups can use the key-to-bucket mapping directly.
What it costs: The hash layout supplies no usable key order; range and successor work requires a scan or an additional structure.
When it fits: Fits an equality-dominated workload where maintaining a separate ordered structure would not justify its cost.

Illustration note: The table does not say a range query is impossible. It says the hash access path alone does not provide an ordered range traversal.

Maintain key order

Maintain an ordered index and use its lookup and successor relationships.

The same keys · an ordered index.
	Lookup route	Matching keys
Equal to 6	Find key 6	6
From 6 to 9	Find 6; walk to 9	6, 9
Next after 6	Follow successor	9

What it protects: Range and next-key queries can follow stored ordering after reaching their starting position.
What it costs: The ordering structure must be maintained on updates, including its implementation’s balancing or page-management work.
When it fits: Fits frequent range, sorting or successor queries whose benefit warrants ordered-index maintenance.

Illustration note: No measured lookup speed or exact comparison count is claimed. Both structures need collision, storage or balancing machinery appropriate to their implementation.

What this illustration does—and does not—establish

Index: Ordered versus Hashed Structure supplies the access-shape distinction; Index: Read Speedup versus Write Amplification supplies maintenance cost. The fixed three-key example makes the missing successor relation explicit.

The table lists keys, not the data records. Following an index result to content remains a separate fetch.
Key ordering and collation must match the application’s requested order.