Key Ordering and Cursor Semantics in IndexedDB

An IndexedDB object store is an ordered map from key to value, and every read operation is defined in terms of that ordering. getAll with a range, a cursor walking a store, an index lookup, and the boundary cases of continue all reduce to comparisons on keys. The comparison rules are stricter than JavaScript’s == or <, and they are the reason a store can return records in an order that looks arbitrary until the type lattice is taken into account.

The key type lattice

Only five kinds of value are valid keys: numbers, dates, strings, binary data (ArrayBuffer and its views), and arrays of valid keys. null, undefined, booleans, plain objects, and functions are not keys; attempting to use one throws a DataError. An invalid key extracted from an object store’s key path also throws DataError; only an index entry is skipped when its key path yields an invalid key. NaN is not a valid key either, although infinities are.

The five kinds are totally ordered against each other, and the ordering is by type first:

number < date < string < binary < array

Within a type the rules are natural. Numbers compare numerically, so -Infinity precedes every finite value and Infinity follows them. Dates compare by their time value, which means a date before the epoch is ordered before a later one, correctly. Strings compare by UTF-16 code unit, not by locale: "Z" sorts before "a", and "é" sorts after "z" because its code unit is larger. This is the same comparison JavaScript performs with < on strings, and it is not what a user means by alphabetical order. Binary keys compare byte-wise as unsigned values, shorter prefixes first.

The consequence is that a store keyed by a mixed-type value is ordered by kind before content: every number precedes every date, which precedes every string, regardless of the individual values. Stores that mix key types still behave deterministically, but any assumption that a numeric key and a string key with the same digits are near each other is wrong.

Compound keys and lexicographic recursion

An array key compares element by element, using the same rules, and stops at the first difference. If one array is a prefix of the other, the shorter one sorts first. So ["a"] precedes ["a", 1], which precedes ["a", 2], which precedes ["b"]. The array’s elements themselves obey the type lattice, so [1, 99] precedes [2, 0] and precedes ["a"] because a number is less than a string.

This is the mechanism that makes a compound key usable as a prefix index. A store keyed by [userId, timestamp] groups records by user in the outer position, and within a user orders them by time, so a range query for one user is a contiguous scan:

const store = db.transaction('events').objectStore('events');
const range = IDBKeyRange.bound(
  [userId, -Infinity],
  [userId, Infinity]
);
// Both bounds are the same user; only the second element varies.
store.getAll(range).onsuccess = (e) => render(e.target.result);

The bound values must be the same type at each position for this to work. A timestamp stored as an ISO string in one code path and as a Date in another lands in two different regions of the key space, and no range covers both.

The key generator behind autoIncrement produces numbers and advances monotonically. When a record is added with an explicit numeric key at least as large as the current generator value, the generator is moved past it, which prevents a key produced later by the generator from colliding with a value already in the store. Explicit keys of other types, and numeric keys below 1, do not affect the generator.

Indexes are a second ordered sequence

An index does not copy values. It records, for each entry, the index key derived from the record’s key path, paired with the record’s primary key. Entries in an index are sorted by index key first and primary key second, which gives every index a deterministic total order even when many records share the same index key.

A non-unique index therefore produces one sequence in which duplicates of the index key are adjacent and internally sorted by primary key. That internal order is not necessarily the order in which records were inserted: if primary keys are strings, duplicates sort by those strings. A nextunique cursor skips from the first record of each index key to the first record of the next, and the record it returns for a duplicated key is the one with the smallest primary key in the index’s ordering, not the newest.

A record whose key path does not resolve to a valid key is simply absent from that index. There is no error and no tombstone; the record exists in the store and answers primary-key lookups while being invisible to the index. Data validation has to happen before the write, because the index gives no signal afterwards.

An index created with multiEntry treats an array index key as several keys: one entry per element, each paired with the same primary key. A non-array key is indexed normally. Arrays nested inside the index key are not expanded further, and the expansion happens per element of the top-level array only.

Ranges, seek, and the cost of continue

An IDBKeyRange is a pair of bounds, either of which may be open or closed. Comparisons inside the bounds use the same key comparison as the store ordering, so IDBKeyRange.lowerBound("a") on a store with mixed keys includes every string at or after "a", and every binary and array key, since those types sort above strings. The range is a predicate on the ordering, not a filter on values.

Cursor traversal is an in-order walk of the underlying ordered structure, and continue(target) is not an increment: it seeks to the first record at or after target (the last record at or before it for a prev cursor). The target must lie strictly ahead of the current position — a target at or behind it in the direction of travel throws DataError — so passing the next key to visit turns a full scan into a logarithmic seek. Calling continue() without an argument advances by one position.

const req = store.openCursor(range, 'prev');
req.onsuccess = (e) => {
  const cursor = e.target.result;
  if (!cursor) return;
  // Seek backwards past everything already rendered.
  cursor.continue(olderThanLastRendered);
};

Direction changes the meaning of the bounds: a prev cursor started on a range still visits only records inside that range, but walks them from the top down, and prevunique skips duplicates from the other end.

Bulk reads and the cost they hide

getAll(range, count) returns an array of values in key order, and getAllKeys(range, count) returns just the keys. Both are convenience wrappers over the same ordered walk, but they materialise the whole result into memory, deserialising one record per element, so a range that covers a hundred thousand records builds a hundred thousand objects before the success handler runs. The count argument caps how many records are returned, which makes paging possible without a cursor, at the cost of re-scanning from the lower bound on each page.

A cursor does the same traversal incrementally: one record is deserialised per success event, and the caller can stop at any point by not calling continue. For a bounded range the bulk call is fewer round trips through the event loop; for an unbounded scan the cursor keeps peak memory proportional to one record. Neither changes the asymptotics: implementations back the store with an ordered structure, the standard names a persistent B-tree as one option, and a range scan costs a logarithmic descent plus the number of records visited.

Where the ordering does not help

The ordering is fixed at the key level and cannot be changed without changing keys. Text search, case-insensitive matching, and locale-aware sorting cannot be expressed as a range over a raw string index; the standard technique is to store a normalised form of the string (lowercased, folded, or prefixed with a collation key computed at write time) in a separate index and query that. Similarly, a query that filters on a non-indexed property has to scan.

Cursors hold a transaction open. A traversal that yields to the event loop between records — for example by awaiting something unrelated — risks the transaction committing underneath it, a hazard covered in transaction lifetime and durability. And because keys are compared structurally, values that survive the trip into a key are limited to the five kinds above; richer objects must be reduced to a key at write time. That restriction comes from the key type lattice, not from the structured clone boundary that governs the stored value, although both sit between an in-memory object and a record at rest.