Frontend System Design · Lesson 76 of 86 · 5 min
Indexing Large Datasets in the Browser
This topic separates candidates who can build a UI from those who can design a performant data-driven application.
When you're asked to design a feature like a searchable product grid or a filterable dashboard, the naive solution is to fetch an array and use Array.prototype.filter. This works for a few hundred items. It fails completely when you have 10,000, 50,000, or more. A linear scan that takes 50ms will drop frames and make your app feel broken.
The goal is to answer queries without iterating. You do this by pre-processing the data into specialized lookup structures called indexes. With the right index, you can find any item or group of items in sub-millisecond time, regardless of dataset size.
When Array.filter Is Too Slow
A linear scan over an array has a time complexity of O(N). For 50,000 items, every single keystroke in a search bar could trigger a 50,000-iteration loop. This can easily exceed the 16ms budget for a 60fps refresh rate, causing UI jank.
Indexing is a trade-off. You accept an upfront cost—CPU time to build the index and memory to store it—in exchange for near-instantaneous reads. You only pay this cost when the data is first loaded and whenever it changes.
If your dataset is small (under ~1,000 items) or doesn't require fast, repetitive lookups, you don't need an index. Don't over-engineer. But once you cross a certain threshold, indexing becomes non-negotiable for a good user experience.
The Two Indexes You Actually Need
For most frontend use cases, you only need to master two types of indexes. Don't get lost in complex database theory.
1. Hash Index (for O(1) exact lookups)
This is for finding a single item by a unique identifier. The perfect tool for this in JavaScript is a Map. You map a unique key (like a userId or productId) to the object itself or its location.
Use it for: getItemById(someId).
2. Sorted Index (for O(log N) range queries)
This is for finding items that fall within a range (numbers, dates, alphabet) or for retrieving items in a specific order. The structure is a simple sorted array of values or pointers, which you can query with a binary search algorithm.
Use it for: getItemsByPriceRange(min, max), getUsersRegisteredAfter(date).
The trap: A common interview mistake is using the wrong tool for the job. Using a sorted array to find an item by ID forces a slow O(log N) search when you could have had an O(1) map lookup. Conversely, trying to query a price range with a hash map is impossible without iterating over all the values.
Building and Using an Index
Let's build both index types from a single dataset. We'll create a hash index for product IDs and a sorted index for prices.
Notice the sorted index stores only the price and id. This is a memory optimization: the index is small, and we use the id to retrieve the full object from the id index, which acts as our single source of truth.
interface Product {
id: string;
name:string;
price: number;
}
// The two index structures
const idIndex = new Map<string, Product>();
const priceIndex: { price: number; id: string }[] = [];
// The raw data array
const products: Product[] = [
{ id: 'a1', name: 'Keyboard', price: 150 },
{ id: 'b2', name: 'Mouse', price: 75 },
{ id: 'c3', name: 'Monitor', price: 400 },
// ... thousands more
];
// Build the indexes once, on load
function buildIndexes(data: Product[]) {
for (const product of data) {
// Hash index for O(1) ID lookup
idIndex.set(product.id, product);
// Data for the sorted index
priceIndex.push({ price: product.price, id: product.id });
}
// Sort the price index for O(log N) range queries
priceIndex.sort((a, b) => a.price - b.price);
}
buildIndexes(products);
// --- Querying ---
// O(1) lookup using the hash index
function getProductById(id: string): Product | undefined {
return idIndex.get(id);
}
// O(log N) + O(K) lookup using the sorted index
// (K is the number of items in the result)
function getProductsInPriceRange(min: number, max: number): Product[] {
// In a real implementation, you'd use binary search here to find
// the start and end indices efficiently.
const ids = priceIndex
.filter(item => item.price >= min && item.price <= max)
.map(item => item.id);
// Retrieve full objects using the fast ID index
return ids.map(id => idIndex.get(id)).filter(Boolean) as Product[];
}
In an interview, you must talk about the trade-offs. Building an index consumes memory. For a dataset of 100,000 objects, an index mapping IDs to objects effectively duplicates your data in memory. Storing only pointers (like the original array index or the object ID) in your secondary indexes is a critical optimization.
The Cost of Updates
Indexes are fast for reads, but they make writes more expensive. If you add, remove, or update an item in your original dataset, your indexes become stale.
You have two main strategies for keeping them in sync:
- Rebuild: The simplest way. Throw away the old indexes and build new ones from the updated dataset. This is inefficient for frequent, small changes but acceptable for infrequent bulk updates.
- Incremental Update: Manually add, remove, or modify entries in your index structures. This is more complex to implement but far more performant for frequent changes. For example, adding a product requires one
idIndex.set()and a sorted insertion into thepriceIndex.
The trap: Candidates often design a perfect read-only system. The interviewer will then ask, "What happens when the data changes?" Be ready to discuss the cost of writes and the trade-off between rebuilding and incremental updates.
Don't Block the Main Thread
Building an index for 100,000 items is a heavy computation. It can take hundreds of milliseconds. If you do this on the main thread, your UI will freeze.
This is a non-starter.
The solution is to perform all index construction and maintenance inside a Web Worker. The main thread's only job is to send the raw data to the worker, and later, send queries and receive results. This keeps the UI perfectly responsive, even during the initial, expensive indexing phase.
This diagram shows the decision flow for when and what to index. For any large dataset, the process should be offloaded to a worker.
The communication is asynchronous. The main thread sends the data and can immediately render a loading state. When the worker messages back that the indexes are ready, the UI can enable the search and filter controls.
Try it
Find a public JSON API that returns an array of at least 1,000 items (e.g., a list of countries, cities, or products). Fetch the data and build two indexes in your browser's console: a hash index on a unique string field and a sorted index on a numeric field. Use console.time and console.timeEnd to measure how long it takes to find an item using your index versus using Array.find or Array.filter.
Next: Search Performance: Debouncing and Web Workers.
Lock it in — apply this lesson under interview conditions.