1 The Problem
We want a database that does not just store records, but indexes them — so finding a record by a field is fast even with millions of rows. We will build a hash index and show the dramatic difference versus scanning every row. It teaches indexing — the single most important reason databases are fast.
Where this shows up: every database (the
CREATE INDEX you have seen), search engines, caches, file systems. Indexing is why a query over a billion rows can return instantly — and why a missing index makes it crawl. Building one makes the concept permanent.2 How to Think About It
Think about why scanning is slow, before any code:
The plan — in plain English
1. Without an index, finding records where email = X means checking every row — slow as data grows. → 2. An index is a second structure: a map from each field value straight to the matching records. → 3. On insert, we update both the records and the index. → 4. A lookup uses the index for an instant jump, no scanning. The index trades a little memory and write-time for huge read speed.
3 The Build — explained part by part
Here is a complete indexed database. Each part is explained below.
Pythondatabase.py
from collections import defaultdict
class Database:
def __init__(self, index_field):
self.records = []
self.index_field = index_field
self.index = defaultdict(list) # value -> list of record positions
def insert(self, record):
position = len(self.records)
self.records.append(record)
# Update the index: map this field's value to the record's position.
key = record[self.index_field]
self.index[key].append(position)
def find_indexed(self, value):
# Fast: jump straight to matching positions via the index.
return [self.records[i] for i in self.index.get(value, [])]
def find_scan(self, value):
# Slow: check every record (what happens without an index).
return [r for r in self.records if r[self.index_field] == value]
if __name__ == "__main__":
db = Database(index_field="city")
db.insert({"name": "Alice", "city": "Mumbai"})
db.insert({"name": "Bob", "city": "Delhi"})
db.insert({"name": "Carol", "city": "Mumbai"})
print("Indexed lookup:", db.find_indexed("Mumbai"))
What each part does — in plain words
self.index = defaultdict(list) — the index: a map from each field value to the list of positions where matching records live. Multiple records can share a value, so each key maps to a list.insert — store the record, then update the index: append this record’s position under its field value. We pay a tiny cost on every write to make reads fast.
find_indexed(value) — the payoff: look up the value in the index to get positions, and fetch just those records. No scanning — this stays fast no matter how many records exist.
find_scan(value) — the slow alternative, shown for contrast: check every record. This is what a database does without an index, and why it slows down as data grows.
the trade-off — the index uses extra memory and makes writes slightly slower, in exchange for dramatically faster reads. That trade is at the heart of database design.
Common mistakes — and how to avoid them
✗ Forgetting to update the index on insert — lookups miss new records.
✓ Update the index every time you insert a record.
✗ Indexing by value but storing the whole record in the index too — wasteful duplication.
✓ Store positions (or references) in the index, not full copies.
✗ Assuming one record per value — many records can share a value.
✓ Map each index key to a list of records.
4 Test & Prove Each Part
We test that indexed and scan lookups return the same results — the index must be correct, not just fast.
Indexed lookup finds the matching records
Indexed and scan lookups agree
A value with no records returns empty
Pythontest_database.py
from collections import defaultdict
class Database:
def __init__(self, index_field):
self.records = []
self.index_field = index_field
self.index = defaultdict(list)
def insert(self, record):
position = len(self.records)
self.records.append(record)
self.index[record[self.index_field]].append(position)
def find_indexed(self, value):
return [self.records[i] for i in self.index.get(value, [])]
def find_scan(self, value):
return [r for r in self.records if r[self.index_field] == value]
def make_db():
db = Database("city")
db.insert({"name": "Alice", "city": "Mumbai"})
db.insert({"name": "Bob", "city": "Delhi"})
db.insert({"name": "Carol", "city": "Mumbai"})
return db
def test_indexed_finds():
"""Indexed lookup finds both Mumbai records."""
assert len(make_db().find_indexed("Mumbai")) == 2
def test_indexed_matches_scan():
"""Indexed and scan results agree."""
db = make_db()
assert db.find_indexed("Mumbai") == db.find_scan("Mumbai")
def test_no_match_empty():
"""A value with no records returns an empty list."""
assert make_db().find_indexed("Paris") == []
Run with pytest -v. The test_indexed_matches_scan test is the key correctness check: the fast path and the slow path must return identical results. An index that is fast but wrong is worse than useless.
5 The Interface
insertdb.insert(record)store + index
finddb.find_indexed(value)instant lookup via index
Returns
[{"name": "Alice", "city": "Mumbai"},
{"name": "Carol", "city": "Mumbai"}]6 Run It & Automate It
Run it locally
python3 database.pyCompare
find_indexed with find_scan. Add thousands of records and time both to feel the difference.Jenkins runs the tests automatically — each line explained below.
What you should see when it works
Terminala real run
Indexed lookup: [{'name': 'Alice', 'city': 'Mumbai'}, {'name': 'Carol', 'city': 'Mumbai'}]If it breaks — how to fix it
🚨 Indexed lookups miss records that scan finds.
Your index is out of sync — ensure insert updates it every time.
🚨
KeyError on lookup.Use
self.index.get(value, []) so unknown values return empty.GroovyJenkinsfile
// Jenkinsfile — automated tests on every change.
pipeline {
agent any
stages {
stage('Get the code') { steps { checkout scm } } // download the code
stage('Install') { steps { sh 'python3 -m venv venv && . venv/bin/activate && pip install pytest' } } // test tool
stage('Test') { steps { sh '. venv/bin/activate && pytest -v' } } // run every test
}
post {
success { echo 'All tests passed.' }
failure { echo 'A test failed — look above.' }
}
}
🎯 Try this next — make it yours
- Time it. Insert 100k records and compare indexed vs scan speed. (Teaches: the real payoff.)
- Range queries. Use a sorted structure for “greater than” lookups. (Teaches: B-tree ideas.)
- Delete + reindex. Handle removing records cleanly. (Teaches: index maintenance.)
What you learned
You built a database index and saw why databases are fast: an index maps values straight to records, avoiding a full scan. This is what CREATE INDEX really does, and why the right index turns a slow query instant. Related: collections, sqlite3.