BTreeMap Iteration Follows Key Order, Not Insertion Order

BTreeMap is ordered, but “ordered” means sorted by keys. It does not preserve the time at which entries were inserted. The failing fixture inserts key two before key one and shows iteration returning one, then two.

Ord defines the traversal

The BTreeMap documentation guarantees items in key order with logarithmic expected/worst-case map operations as documented. The repaired fixture asserts ascending keys.

For a composite key, derived Ord compares fields lexicographically in declaration order. Reordering fields or changing a manual implementation can therefore change map traversal and range behaviour.

I treat key ordering as part of the data model, not a presentation coincidence.

Chronology must be represented

If users need insertion order, I use a collection designed for it or keep a sequence beside key lookup. Another option is a key containing a monotonic sequence number or timestamp plus tie-breaker, but then lookup by domain ID may need a second index.

Timestamps alone are often insufficient: clocks can repeat, move backwards, or differ across nodes. A (timestamp, sequence, id) key can define total order if its generation rules are sound.

For queues, a map is not automatically the right abstraction. A VecDeque, binary heap, or durable log may state consumption and duplicate semantics better.

Sorted maps are excellent for ranges

The range method can visit keys inside bounds without scanning the full map. This is useful for time windows, prefix-like composite ranges, and nearest-neighbour navigation under one ordering.

Bounds must match the key’s Ord semantics. Text sorting by Unicode code points or bytes may not match locale-sensitive human collation. Version strings sorted lexically put 10 before 2 unless parsed structurally.

I define a key newtype with reviewed comparison when domain order differs from default field order. Eq and Ord must remain consistent.

Mutating keys can corrupt logical expectations

The docs call it a logic error to change a key’s ordering relative to others while it is in the map. Interior mutability can make this possible even in safe code. Resulting behaviour is encapsulated but may include panics, wrong results, or leaks.

I keep ordering fields immutable and store changing status in the value. If priority changes, I remove the old key and insert a new one as one domain transition.

Concurrent access adds synchronization; it does not change the ordering model. A lock around BTreeMap protects mutation but does not make insertion chronology visible.

Determinism can be useful

Sorted iteration gives deterministic serialisation and tests when key Ord is stable. HashMap iteration intentionally has no stable order and may vary with hashing state. I choose BTreeMap when deterministic key order or range access is worth its costs.

I do not expose internal map iteration as an API unless clients should depend on that ordering. Once consumers rely on it for pagination or signatures, changing the key comparator or collection becomes a compatibility event.

Pagination needs a stable unique cursor. If keys can be equal under a partial business sort, the actual map key must include a tie-breaker so no item is skipped between pages.

Test the ordering contract

I insert values in several permutations and assert the same sorted output. Composite-key tests cover ties and boundary ranges. Property tests compare traversal with a separately sorted list using the same intended comparator.

For user-facing text I test real multilingual examples under the selected collation layer, which may be outside BTreeMap itself. For time order I include equal timestamps and clock anomalies.

My BTreeMap ordering checklist

• Does the requirement mean key order, insertion order, priority, or chronology?
• What exact Ord implementation controls traversal?
• Are composite fields declared in the intended comparison order?
• Does a timestamp key have a stable uniqueness tie-breaker?
• Would range queries benefit from the sorted index?
• Can any ordering field mutate through interior mutability?
• Are consumers accidentally depending on an internal iteration order?
• Do permutation, tie, range, and pagination tests prove the contract?

The core principle is that an ordered map needs an explicit ordering relation. BTreeMap uses key Ord, not history. I encode the product order in the key or choose a data structure which owns chronology directly.