How Database Indexes Work Under the Hood

// Published On: Jun 11, 2026

#databases

#indexing

#performance

#java

Every developer has heard the advice: add an index to speed up your queries. But what is actually happening when a database uses an index? To answer that, I built a toy database from scratch in Java that demonstrates the core mechanics. Let’s walk through it.

The problem: the full table scan

Imagine you have 1 million user records stored across thousands of files. You want to find everyone named “Alice”. Without any index, you have no choice but to open every single file and check every single record. This is called a full table scan, and it is brutal for large datasets.

The toy project makes this concrete. Records are stored in flat files called pages, each holding up to 10 records:

data/
  page_0_data.records
  page_1_data.records
  page_2_data.records
  ...

Each file looks like this:

name,email,address
Alice Martin,alice@example.com,42 Elm Street
Bob Chen,bob@example.com,7 Oak Avenue
...

The DataReader class has a findMatchingRecordsWithoutIndex method that does exactly what you fear — it reads every page, every record, comparing field by field. With thousands of pages, that is a lot of disk I/O just to find one person.

The solution: an index file

The fix is to maintain a separate data structure that tells you which page a value lives on, so you can jump straight there. The IndexManager keeps this in memory as a nested map:

field → value (lowercase) → Set<page numbers>

So after writing a few records, the in-memory index might look like:

name  → alice martin → {0, 3}
name  → bob chen     → {0}
email → alice@example.com → {0, 3}
...

This is persisted to index/index_data.txt in a simple line-based format:

name:alice martin -> 0,3
name:bob chen -> 0
email:alice@example.com -> 0,3

Now a search for name = "Alice" becomes a two-step operation:

Consult the index → find pages {0, 3}
Read only those two pages and verify the matches

Instead of scanning all 100 pages, we read 2. That is the entire point of an index.

How writes update the index

The critical insight is that the index must be updated every time a record is written. In DataWriter.writeData(), both things happen together:

// 1. Write the record to the current page file
try (FileWriter writer = new FileWriter(filePath.toFile(), true)) {
    writer.write(record.getData());
    writer.write(System.lineSeparator());
}

// 2. Immediately update the index
indexManager.addToIndex(record.getHeader(), record.getData(), currentPageNumber);

The addToIndex method splits the header (name,email,address) and data (Alice,alice@example.com,...) by comma, then maps each field-value pair to the current page number. Values are lowercased so searches are case-insensitive.

Page rotation happens automatically: once a page hits 10 records, the writer moves to the next page number. This keeps individual files small, which matters because we only want to load the pages the index tells us about.

The search path with an index

Here is DataReader.findMatchingRecords() at a high level:

// Step 1: ask the index which pages to look at
Set<Integer> relevantPages = indexManager.getPagesContaining(field, value);

// Step 2: read only those pages
for (int pageNumber : relevantPages) {
    PageData page = readPageByNumber(pageNumber);
    // ... filter records in the page
}

getPagesContaining does a partial-match scan over the index values — any stored value that contains the search string is a hit. This is why searching for "alice" also returns "alice.smith". It is more like a LIKE '%alice%' than an exact = match, which is a deliberate design choice for this toy.

Rebuilding the index

What if the index file gets deleted, or the data and index drift out of sync? The --rebuild-index command handles this by scanning every data page from scratch and re-populating the index:

indexManager.clearIndex();
List<PageData> allPages = reader.readAllPages();

for (PageData page : allPages) {
    for (Record record : page.getRecords()) {
        indexManager.addToIndex(record.getHeader(), record.getData(), page.getPageNumber());
    }
}

indexManager.saveIndexToDisk();

This is exactly what real databases do during crash recovery — they replay their write-ahead log to reconstruct the index.

What this simplifies (and what real databases do)

This toy captures the essential idea, but real database indexes are far more sophisticated:

B-trees instead of flat files. Real indexes use balanced tree structures so that inserts, deletes, and range queries are all O(log n). Our flat index file would need a full rewrite on every change if we wanted to keep it sorted.
Partial index updates. We always rewrite the entire index file on save. Real databases update index pages in-place and use write-ahead logging for durability.
Multi-column and composite indexes. Our index is per-field. Real databases can index combinations of columns and optimize query plans accordingly.
Index selectivity. Not all indexes are useful. An index on a boolean column with two possible values is nearly pointless. Real query planners estimate selectivity and decide whether to use an index at all.

Despite these simplifications, the core trade-off is identical: indexes make reads faster at the cost of slower writes and extra storage. Every write must update both the data and the index. Every read benefits by skipping pages that cannot possibly match.

Running it yourself

The project uses Gradle. Let’s walk through the exact sequence that makes the index value obvious.

Step 1 — generate 500 records across 50 pages:

./gradlew run --args="-g 500"

Generating 500 fake records...
Successfully generated 500 records.

No index is saved after generation — the data exists on disk but there is nothing to look it up with.

Step 2 — search without an index:

./gradlew run --args="-f name Smith"

Searching for records where name contains 'Smith'...
Querying index for field 'name' with value 'Smith'...
No index found. Falling back to full table scan...
Searching through 50 page(s)...
Opening page_0_data.records (10 records)...
Opening page_1_data.records (10 records)...
Opening page_2_data.records (10 records)...
Opening page_3_data.records (10 records)...
Opening page_4_data.records (10 records)...
Opening page_5_data.records (10 records)...
Opening page_6_data.records (10 records)...
Opening page_7_data.records (10 records)...
Opening page_8_data.records (10 records)...
Opening page_9_data.records (10 records)...
Opening page_10_data.records (10 records)...
Opening page_11_data.records (10 records)...
Opening page_12_data.records (10 records)...
Opening page_13_data.records (10 records)...
Opening page_14_data.records (10 records)...
Opening page_15_data.records (10 records)...
Opening page_16_data.records (10 records)...
Opening page_17_data.records (10 records)...
Opening page_18_data.records (10 records)...
Opening page_19_data.records (10 records)...
Opening page_20_data.records (10 records)...
Opening page_21_data.records (10 records)...
Opening page_22_data.records (10 records)...
Opening page_23_data.records (10 records)...
Opening page_24_data.records (10 records)...
Opening page_25_data.records (10 records)...
Opening page_26_data.records (10 records)...
Opening page_27_data.records (10 records)...
Opening page_28_data.records (10 records)...
Opening page_29_data.records (10 records)...
Opening page_30_data.records (10 records)...
Opening page_31_data.records (10 records)...
Opening page_32_data.records (10 records)...
Opening page_33_data.records (10 records)...
Opening page_34_data.records (10 records)...
Opening page_35_data.records (10 records)...
Opening page_36_data.records (10 records)...
Opening page_37_data.records (10 records)...
Opening page_38_data.records (10 records)...
Opening page_39_data.records (10 records)...
Opening page_40_data.records (10 records)...
  Found 1 match(es) in page 40
Opening page_41_data.records (10 records)...
Opening page_42_data.records (10 records)...
Opening page_43_data.records (10 records)...
Opening page_44_data.records (10 records)...
Opening page_45_data.records (10 records)...
Opening page_46_data.records (10 records)...
Opening page_47_data.records (10 records)...
Opening page_48_data.records (10 records)...
Opening page_49_data.records (10 records)...
Search complete. Total matches: 1

Found 1 record(s):
================================================================================
name           : Roxane Smith
email          : porter.daniel@hotmail.com
address        : Suite 875 7536 Jamel Motorway, Lake Doreenchester, WV 27490
--------------------------------------------------------------------------------

Every page file is opened in sequence regardless of whether it can possibly contain a match. All 500 records are checked to find 1.

Step 3 — build the index:

./gradlew run --args="-i"

Rebuilding index from existing data files...
Indexing page 0 (10 records)...
Indexing page 1 (10 records)...
...
Indexing page 49 (10 records)...
Index saved to disk.
Index Statistics:
  Fields indexed: [address, name, email]
  Total entries: 1500

Index rebuilt successfully!
Total records indexed: 500
Total pages indexed: 50

One full scan to build the index — a cost paid once so every future search can avoid it.

Step 4 — run the same search with the index:

./gradlew run --args="-f name Smith"

Index loaded successfully from disk.
Searching for records where name contains 'Smith'...
Querying index for field 'name' with value 'Smith'...
Index found 1 relevant page(s): [40]
Reading only relevant pages...
Searching page 40 (10 records)...
  Found 1 match(es) in page 40
Search complete. Total matches: 1

Found 1 record(s):
================================================================================
name           : Roxane Smith
email          : porter.daniel@hotmail.com
address        : Suite 875 7536 Jamel Motorway, Lake Doreenchester, WV 27490
--------------------------------------------------------------------------------

Same result. The index jumped directly to page 40 without touching the other 49.

The numbers side by side

	Without index	With index
Pages read	50 of 50	1 of 50
Records scanned	500	10
How it works	Opens every page file sequentially	Looks up the page from index, reads only that

50x fewer pages read. As the dataset grows, the indexed search stays constant — the full scan keeps growing linearly with every record you add.

The source is at github.com/rupinr/db-index-example if you want to dig in.