Lesson 4: Implementing Indexing and Searching

From storage to finding

In Lesson 2: Building a Basic Key-Value Store, we built the core API: put, get, and delete.

In Lesson 3: Adding Persistence to the Key-Value Store, we made that store survive restarts.

Now we hit the next real datastore problem: finding data when you don't already know the key.

A plain key-value store is great when you ask:

• “What is stored at key user:42?”
• “What is the value for order:abc?”

But applications often ask:

• “Which users have plan pro?”
• “Which trades are for symbol AAPL?”
• “Which prices are between 100 and 200?”

Without an index, those questions require scanning every record. Indexes trade extra write work and memory for much faster reads.

An index is a shortcut table

An index is a derived data structure that points from a searchable attribute to the records that contain it.

Imagine records like this:

key        value
-----------------------------
u1         {"plan": "free"}
u2         {"plan": "pro"}
u3         {"plan": "pro"}

A secondary index on plan could look like:

plan       keys
----------------
free       {u1}
pro        {u2, u3}

Now search(plan="pro") does not need to inspect every user. It jumps directly to the matching keys.

The core tradeoff

Indexes are not free:

• Reads get faster for supported search patterns.
• Writes get slower because indexes must be updated.
• Memory/disk usage increases because indexes duplicate some information.

This is the same tradeoff behind indexes in PostgreSQL, MongoDB, Redis modules, and search engines.

You have 1,000,000 records and frequently need to answer: “Which records have status == "open"?”

Which approach is usually best for repeated queries of this kind?

Fast equality search

The simplest useful index is a hash index.

It maps an exact value to the set of keys containing that value:

value       keys
----------------------
"pro"      {"u2", "u3"}
"free"     {"u1"}

This is excellent for equality queries like:

• plan == "pro"
• symbol == "AAPL"
• currency == "USD"

But a hash index is not good for range queries like price between 100 and 200, because hashes do not preserve order.

Let's build a tiny store that indexes whole values. Later in the lesson, we'll index fields inside dictionary values.

```python
class HashIndexedKV:
    def __init__(self):
        self.data = {}
        self.value_index = {}  # value -> set of keys

    def put(self, key, value):
        # If the key already exists, remove it from the old index bucket.
        if key in self.data:
            old_value = self.data[key]
            self.value_index[old_value].discard(key)
            if not self.value_index[old_value]:
                del self.value_index[old_value]

        self.data[key] = value
        self.value_index.setdefault(value, set()).add(key)

    def get(self, key):
        return self.data.get(key)

    def search_by_value(self, value):
        keys = self.value_index.get(value, set())
        return {key: self.data[key] for key in keys}


store = HashIndexedKV()
store.put("u1", "free")
store.put("u2", "pro")
store.put("u3", "pro")

print("Users on pro:", store.search_by_value("pro"))

store.put("u1", "pro")
print("After upgrade:", store.search_by_value("pro"))
print("Index:", {k: sorted(v) for k, v in store.value_index.items()})
```

True or false: If a key is updated from one indexed value to another, the store must remove the key from the old index entry and add it to the new one.

Searching inside records

Real records are usually structured objects, not just simple strings.

For example:

user:1 -> {"name": "Ada", "plan": "pro", "region": "us"}
user:2 -> {"name": "Lin", "plan": "free", "region": "eu"}
user:3 -> {"name": "Sam", "plan": "pro", "region": "us"}

A primary key lookup uses the key directly: get("user:1").

A secondary index is built on something else, such as:

• plan
• region
• symbol
• customer_id

One index per access pattern

If your app often asks for users by plan, index plan.

If it often asks for users by region, index region.

If it often asks for both, you may maintain both indexes.

This connects back to Lesson 1: Introduction to Datastores: datastore design starts with access patterns.

An index built on something other than the primary key is called a _____.

When order matters

Hash indexes are great for exact matches, but many useful queries are ordered:

• “Find prices between 100 and 200.”
• “Find events after timestamp T.”
• “Find the next 10 records alphabetically.”

For these, datastores often use ordered index structures such as B-trees.

A production B-tree stores sorted keys in disk-friendly pages. We will not build a full B-tree here, but we can capture the core idea with a sorted list plus binary search.

That gives us the key mental model:

sorted indexed values -> jump to range start -> walk until range end

This is why B-tree-style indexes are common in relational databases: they support equality search, range search, and ordered traversal.

```python
from bisect import bisect_left, bisect_right, insort

class SortedPriceIndex:
    def __init__(self):
        self.records = {}       # key -> record
        self.price_index = []   # sorted list of (price, key)

    def put(self, key, record):
        if key in self.records:
            old_price = self.records[key]["price"]
            self.price_index.remove((old_price, key))

        self.records[key] = record
        insort(self.price_index, (record["price"], key))

    def range_search(self, low, high):
        left = bisect_left(self.price_index, (low, ""))
        right = bisect_right(self.price_index, (high, chr(10**6)))
        pairs = self.price_index[left:right]
        return {key: self.records[key] for price, key in pairs}


market = SortedPriceIndex()
market.put("asset:btc", {"symbol": "BTC", "price": 65000})
market.put("asset:eth", {"symbol": "ETH", "price": 3200})
market.put("asset:sol", {"symbol": "SOL", "price": 145})
market.put("asset:cash", {"symbol": "USD", "price": 1})

print("Index:", market.price_index)
print("Assets priced from 100 to 5000:", market.range_search(100, 5000))
```

Which index type is the better conceptual fit for efficiently answering created_at BETWEEN start AND end?

Indexes and persistence

In Lesson 3, our key-value store learned to save and load its main data.

Indexes add a design question:

Should we persist indexes too, or rebuild them from stored records?

For a small datastore, rebuilding indexes on startup is simple and reliable:

1. Load the persisted records.
2. Start with empty indexes.
3. Reinsert each record into the index structures.

This avoids storing duplicate index files and reduces the chance that data and indexes disagree.

Larger systems may persist indexes for faster startup, but then they need stronger recovery logic. We'll stay with the simple version here.

```python
import json
import os
import tempfile

class PersistentIndexedKV:
    def __init__(self, path):
        self.path = path
        self.data = {}
        self.plan_index = {}  # plan -> set of keys

    def put(self, key, record):
        if key in self.data:
            old_plan = self.data[key].get("plan")
            self.plan_index.get(old_plan, set()).discard(key)

        self.data[key] = record
        plan = record.get("plan")
        self.plan_index.setdefault(plan, set()).add(key)

    def search_by_plan(self, plan):
        return {key: self.data[key] for key in self.plan_index.get(plan, set())}

    def save(self):
        with open(self.path, "w", encoding="utf-8") as f:
            json.dump(self.data, f)

    def load(self):
        with open(self.path, "r", encoding="utf-8") as f:
            loaded = json.load(f)

        self.data = {}
        self.plan_index = {}
        for key, record in loaded.items():
            self.put(key, record)


fd, path = tempfile.mkstemp()
os.close(fd)

store = PersistentIndexedKV(path)
store.put("u1", {"name": "Ada", "plan": "pro"})
store.put("u2", {"name": "Lin", "plan": "free"})
store.save()

restarted = PersistentIndexedKV(path)
restarted.load()
print("Loaded data:", restarted.data)
print("Rebuilt index:", {k: sorted(v) for k, v in restarted.plan_index.items()})
print("Pro users:", restarted.search_by_plan("pro"))

os.remove(path)
```

What you can build now

You started this course with a plain in-memory map, then made it persistent. Now your datastore can support search patterns beyond direct key lookup.

Key takeaways

• A plain key-value store is fast when you already know the key.
• Indexes make non-key searches efficient.
• Hash indexes are ideal for equality queries.
• Ordered indexes, like B-tree-style structures, support range queries.
• Indexes must be updated whenever records change.
• For a simple persistent store, rebuilding indexes on startup is often the cleanest design.

The datastore designer's question

Before adding an index, ask:

What query is this index meant to accelerate?

That question keeps your implementation practical instead of adding complexity for its own sake.

Next, we will zoom out from single-node behavior and look at what changes when a datastore needs to handle more traffic and survive machine failures.