7.10 Ordered Maps

Arrays are excellent when data rarely changes. Binary search provides fast lookups, but insertion and deletion are expensive because elements must be shifted to preserve ordering.

Many real systems require both efficient searches and efficient updates. Databases insert records continuously. Schedulers add and remove tasks. Caches expire entries. Financial systems process streams of orders. In these environments, rebuilding or resorting an array after every modification is impractical.

Ordered maps solve this problem by maintaining key-value pairs in sorted order while supporting efficient insertion, deletion, and lookup operations.

Unlike hash tables, which prioritize average-case lookup speed, ordered maps preserve ordering relationships between keys. This additional structure enables range queries, predecessor searches, successor searches, ordered iteration, and interval operations.

Most balanced search trees exist primarily to implement ordered maps.

Problem

Suppose you need to store user information indexed by user ID.

A simple array-based approach might look like:

type User struct {
	ID   int
	Name string
}

Store users in a sorted slice:

users := []User{
	{100, "Alice"},
	{200, "Bob"},
	{300, "Charlie"},
}

Lookup can use binary search.

func FindUser(
	users []User,
	id int,
) int {

	lo, hi := 0, len(users)

	for lo < hi {
		mid := lo + (hi-lo)/2

		if users[mid].ID >= id {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

Searching is efficient:

O(log n)

Insertion is not.

Adding:

requires:

[100, 200, 300]

to become:

[100, 150, 200, 300]

which may require moving many elements.

Insertion cost:

O(n)

This becomes problematic for large collections.

Solution

Use an ordered map implemented with a balanced search tree.

Conceptually:

       200
      /   \\n   100     300

Each node stores:

A key
A value
References to child nodes

Search follows the ordering relationship.

Target = 300

300 > 200
Move right

300 == 300
Found

Only a logarithmic number of nodes are visited.

Operations become:

Operation	Complexity
Lookup	O(log n)
Insert	O(log n)
Delete	O(log n)

This combination makes ordered maps one of the most important data structures in computer science.

The Ordered Map Abstraction

Conceptually, an ordered map provides:

type OrderedMap interface {
	Put(key, value)
	Get(key)
	Delete(key)
}

Unlike a hash map, keys remain sorted.

Example:

100 -> Alice
200 -> Bob
300 -> Charlie

Iterating over the map produces:

100
200
300

in key order.

This property enables operations that are impossible or expensive with hash tables.

Lookup

Search begins at the root.

Example:

        50
       /  \\n     25    75
    / \    / \\n   10 40 60 90

Search for:

Path:

50 -> 75 -> 60

Only three nodes are visited.

The search space is reduced at each step in the same way binary search reduces an array.

This similarity is not accidental. Balanced trees are essentially binary search generalized to dynamic collections.

Insertion

Suppose:

        50
       /  \\n     25    75

Insert:

Search path:

50 -> 75

Since:

60 < 75

insert as the left child.

Result:

        50
       /  \\n     25    75
          /
        60

The insertion location is found in logarithmic time.

The challenge is maintaining balance after many insertions.

Later sections address this problem using self-balancing trees.

Deletion

Deletion is more complicated.

Three cases exist:

Leaf node

      50
     /
   25

Delete:

Simply remove the node.

One child

      50
     /
   25
     \\n      40

Delete:

Promote the child.

      50
     /
   40

Two children

       50
      /  \\n    25    75

Delete:

Replace with predecessor or successor.

The exact details depend on the tree implementation.

Balanced tree structures automate this process while preserving ordering properties.

Why Not Use Hash Maps?

Hash maps provide:

Average lookup: O(1)

which appears superior.

However, consider:

Find all keys between
1000 and 5000

A hash map has no notion of order.

The only solution is scanning every entry.

O(n)

An ordered map can locate:

LowerBound(1000)

and iterate until:

The cost becomes:

O(log n + k)

where:

is the number of returned records.

For range queries, ordered maps are often dramatically faster.

Predecessor and Successor Searches

Given:

Find the largest value less than:

Result:

Find the smallest value greater than:

Result:

These operations are known as:

Predecessor
Successor

Ordered maps support them naturally.

Hash maps do not.

This capability is important in scheduling, event processing, memory allocation, and database indexing.

Range Queries

Suppose a time-series system stores:

Query:

09:20 - 10:00

An ordered map can quickly locate:

09:30

and iterate forward until:

10:00

No unrelated records are examined.

This is one of the primary reasons databases rely heavily on ordered indexes.

Ordered Maps in Practice

Many systems expose ordered maps under different names.

Examples include:

TreeMap (Java)
std::map (C++)
BTreeMap (Rust)
SortedDictionary (.NET)
B-tree indexes in databases
Filesystem directory indexes
Key-value storage engines

Although implementations differ, the abstraction remains similar.

Each structure maintains ordered keys while supporting efficient updates.

Arrays Versus Ordered Maps

Feature	Sorted Array	Ordered Map
Lookup	O(log n)	O(log n)
Insert	O(n)	O(log n)
Delete	O(n)	O(log n)
Ordered iteration	Yes	Yes
Range queries	Yes	Yes
Cache locality	Excellent	Moderate
Dynamic updates	Poor	Excellent

Arrays often outperform trees for read-heavy workloads because of superior cache behavior.

Ordered maps excel when updates occur frequently.

Choosing between them depends on workload characteristics.

Database Perspective

Consider a table indexed by customer ID.

A query asks:

SELECT *
FROM customers
WHERE customer_id
BETWEEN 1010 AND 1025

The index performs:

LowerBound(1010)

and then scans forward until:

This is fundamentally an ordered-map operation.

Most database indexing techniques are specialized forms of ordered maps optimized for disk and memory hierarchies.

Complexity Analysis

Assuming the structure remains balanced:

Operation	Complexity
Lookup	O(log n)
Insert	O(log n)
Delete	O(log n)
Lower bound	O(log n)
Upper bound	O(log n)
Range query	O(log n + k)

where:

is the number of returned elements.

Balance is essential. Without it, performance can degrade significantly.

Common Mistakes

A common misconception is that hash maps are always superior because of constant-time lookups.

Hash maps optimize exact lookups. Ordered maps optimize ordered operations.

Another mistake is ignoring workload characteristics. If updates are rare, a sorted array may outperform an ordered map because of better memory locality.

A third mistake is assuming balanced trees maintain themselves automatically. Balancing algorithms are responsible for preserving logarithmic performance. Without balancing, an ordered map can degenerate into a linked list.

Takeaway

Ordered maps combine the ordering benefits of sorted arrays with the update efficiency of balanced trees. They support logarithmic-time lookup, insertion, deletion, predecessor searches, successor searches, and range queries while preserving key order. Many higher-level data structures, database indexes, schedulers, storage engines, and search systems are ultimately specialized ordered maps designed for particular performance and storage requirements. In the following sections, we will examine the balanced tree structures that make these guarantees possible.