JavaScript: an index turns a scan into a lookup

Compare scanning an array for a row with looking it up in a Map keyed by id.

JavaScript

const users = Array.from({ length: 1000 }, (_, i) => ({ id: i + 1, name: "user" + (i + 1) }));

let scanSteps = 0;
function findByScan(id) {
  for (const user of users) {
    scanSteps++;
    if (user.id === id) return user;
  }
  return null;
}

const byId = new Map(users.map((user) => [user.id, user]));

console.log(findByScan(900).name + " after " + scanSteps + " rows scanned");
console.log(byId.get(900).name + " after 1 index lookup");
console.log("missing id: " + byId.get(5000) + ", scan finds " + findByScan(5000));

Output

user900 after 900 rows scanned
user900 after 1 index lookup
missing id: undefined, scan finds null

Explanation

Without an index, a database finds a row by scanning the table and testing every row, which takes time proportional to the table size. An index is an extra structure that maps a column value to the row, so the same query needs only a lookup.

The array of 1000 users plays the role of a table. findByScan examines rows one by one and counts them. The Map built from the same rows plays the role of a hash index on id. The index costs extra memory and must be kept up to date when rows change, which is why databases do not index every column.

Explore the dry run

Guided walkthroughReady

1const users = Array.from({ length: 1000 }, (_, i) => ({ id: i + 1, name: "user" + (i + 1) }));

3let scanSteps = 0;

4function findByScan(id) {

5 for (const user of users) {

6 scanSteps++;

7 if (user.id === id) return user;

8 }

9 return null;

10}

12const byId = new Map(users.map((user) => [user.id, user]));

14console.log(findByScan(900).name + " after " + scanSteps + " rows scanned");

15console.log(byId.get(900).name + " after 1 index lookup");

16console.log("missing id: " + byId.get(5000) + ", scan finds " + findByScan(5000));

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Each row examined adds one to the count.	`—`	—
Build the index once: id → row.	`byId has 1000 entries`	—
Row 900 is the 900th row, so 900 rows are examined.	`scanSteps = 900`	user900 after 900 rows scanned
The Map reaches it in one average O(1) step.	`scanSteps = 900`	user900 after 900 rows scanned user900 after 1 index lookup
A missing key is reported at once by the index, while the scan has to look at every row to be sure.	`scanSteps = 900`	user900 after 900 rows scanned user900 after 1 index lookup missing id: undefined, scan finds null

Cost and common mistakes

Scan: O(n) per query. Index: O(1) average per lookup, with O(n) extra space and an upfront O(n) build.

An index is only correct while it matches the table. Updating a row without updating the index returns stale or missing results.
A hash index handles equality only. Range queries need an ordered structure such as a B-tree.

Try it yourself

What happens to the index when a user is deleted?

Reveal answer and reasoning

The entry must also be removed from the Map, with byId.delete(id), or lookups would still find the deleted user.

JavaScript: an index turns a scan into a lookup

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading