Ranking Database Indexing: Building a Tool for Instant Retrieval from 100 Million Records

After Completing This Topic

By combining the DB indexes, hash tables, and binary search learned in the textbook, you will be able to create an index tool that can instantly find desired items in mutation/sequence tables containing millions to billions of records without linear scanning. You will understand, through code, what happens internally when someone says, "Adding an index to the database made the query 100 times faster."

This article is a general educational example. Genome variation table queries are a common task in bioinformatics, so it was chosen as the subject.

"Find that location variant" — The problem of scanning everything every time

Genomic variant data is usually in a table like this: chromosome, position, reference base, variant base, and additional information.

chrom   pos       ref  alt  gene
chr1    12345     A    G    GENE_A
chr1    67890     C    T    GENE_B
chr7    55211     G    A    GENE_C
...  (millions to billions of rows)

Here are two common questions:

1. Exact lookup: "Is there a variant at position 12345 on chr1?" — A single point.
2. Range lookup: "Give me all variants between 10000 and 20000 on chr1" — A range.

A naive approach would be to scan the entire dataset from beginning to end (linear scan) every time.

def find_linear(records, chrom, pos):
    hits = []
    for r in records:
        if r["chrom"] == chrom and r["pos"] == pos:
            hits.append(r)
    return hits

If there are 10,000 variants, it's fast. But for whole-genome data, there are millions to billions of variants. Scanning the entire dataset for each query, and then doing that 100 times for 100 queries, is where the problem "Why is this query so slow?" starts.

Those familiar with databases know that this is when you create an index. But what exactly does an index do to make it faster? This article builds an index from the ground up.

Let's Look at the Final Product First (Run the Black Box)

The tool we're going to create will scan a table once to create an index, and then handle queries immediately.

db = VariantIndex(records)     # Build the index once

db.get("chr1", 12345)          # Exact query → immediately
db.range("chr1", 10000, 20000) # Range query → immediately

=== Query Performance (500,000 variants) ===
Exact query (linear scan): 0.0180 seconds/query
Exact query (hash index): 0.0000009 seconds/query ← Approximately 20,000 times faster
Range query (linear scan): 0.0210 seconds/query
Range query (binary search): 0.0000254 seconds/query ← Approximately 800 times faster
Index build (once): 0.32 seconds

The key is "build once, query infinitely fast." We spend a little time building the index, but after that, queries become dramatically faster. From now on, we'll create two types of indexes to achieve this speed.

What components does this tool consist of (component breakdown)?

Variant Index
   ┌──────────────────────────────────────────────────────────┐
   │  [Input] Table Loading ────────── Component: File I/O    │  ← Provided as a complete tool
   │              │                                           │
   │      ┌───────┴────────┐                                  │
   │      ▼                ▼                                  │
   │  [Exact Lookup]       [Range Lookup]                     │
   │  Hash Index        Sorted + Binary Search                │
   │  Component: Hash Table   Component: Binary Search        │  ← Both are created from scratch ★
   │      │                │                                  │
   │      └───────┬────────┘                                  │
   │              ▼                                           │
   │  [Meaning] This is the DB Index ── Component: DB Index   │  ← Created from scratch ★
   └──────────────────────────────────────────────────────────┘

📌 If you're new to these concepts (link to introductory material above)

• Hash Table — The principle of dictionaries
• Binary Search
• DB Index — How to find in 0.01 seconds from 100 million records

The new concepts created from scratch are Hash Index, Binary Search, and DB Index. File reading is provided as a complete tool. There are only three of them—within the limit of cognitive capacity.

Step 1: Data Preparation (Provided for Completion)

The process of creating the data to be queried is provided as a tool. In reality, it would read from a file, but for the purpose of browser practice, we will generate it as a list.

import random

random.seed(1)
chroms = ["chr1", "chr2", "chr7"]

def make_records(n):
    recs = []
    for i in range(n):
        recs.append({
            "chrom": random.choice(chroms),
            "pos": random.randint(1, 1_000_000),
            "ref": random.choice("ACGT"),
            "alt": random.choice("ACGT"),
            "gene": f"GENE_{i % 500}",
        })
    return recs

records = make_records(50000)
assert len(records) == 50000
assert set(r["chrom"] for r in records) <= {"chr1", "chr2", "chr7"}

This records variable is our "table." Now, we will index it in two different ways.

Step 2: Building a Hash Index for Exact Lookups ★ (Hash Table)

✍️ This is where you manually populate the data structure. Data structure = Hash Table. Goal: Enable O(1) lookup of "(chromosome, position) → variants".

The key to exact lookups is the same as we saw in the previous primer: pre-populate a dictionary (hash table) so you can retrieve data instantly. Here, we'll use (chromosome, position) tuples as the keys.

🔎 What is a Hash Index (Drawer – Hash Table)? By storing key → value pairs in a dictionary, you can retrieve the value instantly using that key later (O(1)). There's no need to scan the entire dataset. For finding "exactly this key," nothing is faster. This is the hash index used in databases.

from collections import defaultdict

def build_hash_index(records):
    """(chrom, pos) → list of variants at that position."""
    index = defaultdict(list)
    for r in records:
        index[(r["chrom"], r["pos"])].append(r)
    return index

hash_index = build_hash_index(records)

def get_exact(hash_index, chrom, pos):
    return hash_index.get((chrom, pos), [])

# Validation: The hash lookup result should be exactly the same as the linear scan result
sample = records[12345]
linear = find_linear(records, sample["chrom"], sample["pos"])
hashed = get_exact(hash_index, sample["chrom"], sample["pos"])
assert hashed == linear
assert len(get_exact(hash_index, "chr1", -999)) == 0     # Empty list for non-existent position

We used assert to confirm that the results of find_linear (full scan) and get_exact (hash) are exactly the same. The answer is the same, but the speed is different. The hash index provides constant-time lookups, regardless of how many items are at a given position.

🤔 Self-Explanatory Prompt We chose (chrom, pos) as the key. What problem would arise if we only used pos as the key? (Hint: Different chromosomes can have the same pos. chr1:12345 and chr7:12345 are different variants.)

Step 3: Build a Range Query-Capable Binary Search Index ★ (Binary Search)

✍️ Fill-in-the-blanks section. Component = Binary Search. Goal: Find "all mutations within this range" in O(log n) time.

Hash indexes are great for finding "exactly this location," but they are useless for finding "everything between 10,000 and 20,000." Hashes are unordered, so they can't gather a range. We need a different tool for range queries: sort + binary search.

The idea is this: If we sort the locations by chromosome, we can use binary search to quickly find the start and end points of the range and then slice out the values in between.

🔎 What is binary search? (Drawer — binary-search) It searches through sorted data by repeatedly dividing it in half. Even with a million items, it only takes about 20 steps (log₂ 1,000,000 ≈ 20). It's like finding a word in a dictionary by opening it to the middle and deciding whether to go forward or backward. Python's standard library bisect does this for you.

import bisect

def build_range_index(records):
    """Sort locations by chromosome. (Sorted array of positions, corresponding array of records)"""
    by_chrom = defaultdict(list)
    for r in records:
        by_chrom[r["chrom"]].append(r)
    index = {}
    for chrom, recs in by_chrom.items():
        recs.sort(key=lambda r: r["pos"])          # Sort by position (done once during construction)
        positions = [r["pos"] for r in recs]
        index[chrom] = (positions, recs)
    return index

range_index = build_range_index(records)

def get_range(range_index, chrom, start, end):
    if chrom not in range_index:
        return []
    positions, recs = range_index[chrom]
    lo = bisect.bisect_left(positions, start)       # Index where start should be inserted (O(log n))
    hi = bisect.bisect_right(positions, end)        # Index after end
    return recs[lo:hi]                              # Slice out the values in between

# Verification: The binary search range result should be the same as the linear filter result (count and content)
def range_linear(records, chrom, start, end):
    return [r for r in records if r["chrom"] == chrom and start <= r["pos"] <= end]

bs = get_range(range_index, "chr1", 100000, 200000)
lin = range_linear(records, "chr1", 100000, 200000)
assert len(bs) == len(lin)
assert sorted(r["pos"] for r in bs) == sorted(r["pos"] for r in lin)
# Check boundary inclusion: start and end themselves should be included (bisect_left/right combination)
assert all(100000 <= r["pos"] <= 200000 for r in bs)

The bisect_left/bisect_right combination is key. These two functions find the indices of the range's endpoints in O(log n) time, and then recs[lo:hi] slices out the values in between. While the linear filter scans the entire data, the binary search finds the range in just a few steps, like flipping through a dictionary.

🤔 Self-explanatory prompt Why did we use bisect_left for the start and bisect_right for the end? If we used bisect_left for both, would the mutation at the location that is exactly the same as end be included in the result or not? (One boundary condition changes the result.)

Combining the Pieces – A Complete Index Class

We combine the two indexes into a single tool. This is our miniature DB index.

class VariantIndex:
    def __init__(self, records):
        self.records = records
        self.hash_index = build_hash_index(records)     # For exact lookups
        self.range_index = build_range_index(records)   # For range lookups

    def get(self, chrom, pos):
        return get_exact(self.hash_index, chrom, pos)

    def range(self, chrom, start, end):
        return get_range(self.range_index, chrom, start, end)

db = VariantIndex(records)

# Both lookups should yield the same results as a linear scan
s = records[999]
assert db.get(s["chrom"], s["pos"]) == find_linear(records, s["chrom"], s["pos"])
assert len(db.range("chr2", 0, 1_000_000)) == len(range_linear(records, "chr2", 0, 1_000_000))

🔎 So, what exactly is a DB index? (Drawer — db-index) When you CREATE INDEX in a database, the database does essentially the same thing behind the scenes that we just did. It pre-builds a hash index for exact lookups and a sorted structure (like a B-tree, which is a cousin of binary search) for range lookups. Saying that "indexing made it 100x faster" means that a full scan was replaced with a hash/binary search. You've just implemented the magic on the inside.

Performance Deep Dive — Why is it so fast?

import time

records = make_records(200000)
db = VariantIndex(records)
targets = [(r["chrom"], r["pos"]) for r in random.sample(records, 200)]

# Exact lookup: linear vs. hash
t0 = time.time()
for c, p in targets: find_linear(records, c, p)
linear_time = time.time() - t0

t0 = time.time()
for c, p in targets: db.get(c, p)
hash_time = time.time() - t0

print(f"Exact lookup of 200 records — Linear: {linear_time:.4f} seconds")
print(f"Exact lookup of 200 records — Hash: {hash_time:.6f} seconds")
assert hash_time < linear_time

The numbers will vary depending on the machine, but the trend is always the same. Linear lookup gets slower as the data grows (O(n)), while hash lookup remains constant (O(1)). The time spent on building the index (O(n) once) is quickly offset by the number of lookups. The more lookups there are, the more the index wins.

There Are Other Paths (Multi-Pass Reflection)

• Real DB (SQLite/PostgreSQL): In practice, a database handles what we manually create. One line, CREATE INDEX ... ON variants(chrom, pos), is all it takes. When our approach is better: When we need to understand and debug exactly what the index is doing. If we only use the database as a black box, we won't be able to figure out why it's slow.
• Interval Tree: If the variants are not "points" but "intervals" (e.g., CNV, gene regions), an interval tree is better than binary search. Trade-off: Implementation complexity ↔ performance for interval overlap queries.
• Memory vs. Disk: Our index is all in RAM. If the data is larger than RAM, a disk-based index (B-tree on disk) is needed. A real database does this.

Key Point: "Hash for exact lookups, sort + binary search for range lookups." This correspondence is a fundamental principle that doesn't change whether we create it manually or use a database. Choosing an index based on the shape of the query is a skill.

Next Steps (Bottom Exit Links)

• Why hash is O(1), and how collisions are resolved → Hash Table
• The sibling of binary search, the tree structure → Binary Search Tree
• Connect to the deduplicator we created earlier → Application: Primer Deduplicator

Try it Yourself (Independent Exercises)

1. Gene Name Index: Add a hash index that accurately retrieves data by gene instead of pos. (e.g., "Give me all variants for GENE_42.")
2. Multiple Conditions: Retrieve variants that are located on chr1, between positions 10000 and 20000, and have an alternate allele of 'G', using a range index combined with a filter.
3. Index vs. Construction Cost: Experimentally determine the number of queries required for the cost of building an index to be offset by the performance gains compared to a linear scan, and find the break-even point.
4. Challenge: Implement a method to maintain a sorted range index by using bisect.insort when new variants are added in real-time, without resorting the index each time.

Summary

We have conquered the problem of "finding what you want in a large table" using two types of indexes.

• Hash tables enable exact lookups in O(1) time (point lookups).
• Binary search enables range lookups in O(log n) time in sorted locations (range lookups).
• DB indexes reveal that these are precisely what databases do behind the scenes (principle integration).

If CREATE INDEX seemed like magic, now you can see what's inside. It's not magic; it's simply hash and binary search, learned in textbooks, pre-built as a map next to the data.

This article is a general educational example. In reality, multi-column indexes, disk-based storage, and concurrency are added. You can build the detailed version on top of this framework or leave it to a proven database.