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.
On this page
JavaScript arrays and Map.
- Compare scanning an array for a row with looking it up in a Map keyed by id.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
Code example
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));user900 after 900 rows scanned user900 after 1 index lookup missing id: undefined, scan finds null
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
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));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
| Step / line | 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 |
Behind the scenes
How JavaScript processes this code
A JavaScript engine parses and runs the source. A function body runs when the function is called. console.log writes to the console.
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.