Demo Understanding Indexing in Vector Database

Welcome back. In this hands-on demo you’ll see how indexing changes the behavior and efficiency of search in a vector database. We’ll compare a brute-force linear scan with a very small toy index and count how many distance checks each approach performs.

The image features the text "Understanding indexing in vector DB" on a white background, with the word "Demo" highlighted in white against a blue shape on the right.

What you’ll run (environment)

This demo is intended for a Jupyter notebook but works in any Python REPL.
Key goals:
- Build a tiny deterministic embedding function (no ML).
- Store embeddings (optionally) in ChromaDB.
- Compare a linear (brute-force) search vs. a pruned (indexed) search.
- Measure and compare the number of distance computations.

Quick plan (steps)

Step	Description	Example file
1	Minimal environment imports	`demo_setup.py`
2	Create dataset and deterministic embedder	`data_and_embed.py`
3	(Optional) Upsert vectors into ChromaDB	`store_in_chroma.py`
4	Linear (brute-force) search and measurement	`linear_search.py`
5	Build a toy index (3 buckets)	`build_index.py`
6	Indexed (pruned) search and comparison	`indexed_search.py`, `compare_results.py`

Code and explanations follow. Each code block is labeled to help reproducibility.

# demo_setup.py
import chromadb
import numpy as np

Dataset and deterministic embedding

We use 6 short documents to keep the demo compact.
The embedding is a 3-dimensional count vector that measures matches against three small keyword buckets: travel, policy, and service.
This deterministic embedder makes results reproducible and easy to reason about.

# data_and_embed.py
docs = [
    "book flight ticket",
    "cancel booking refund",
    "hotel room reservation",
    "baggage allowance policy",
    "airport security rules",
    "meal options onboard",
]
ids = [f"d{i}" for i in range(len(docs))]

# Small deterministic vocabulary: three buckets
vocab = {
    "travel": {"flight", "ticket", "airport", "booking", "reservation"},
    "policy": {"policy", "rules", "allowance", "security"},
    "service": {"meal", "onboard", "refund", "cancel", "hotel"},
}

def embed(text: str):
    """
    Return a 3-d embedding as counts of words matching each bucket.
    Order: [travel, policy, service]
    """
    words = text.lower().split()
    vec = [
        sum(w in vocab[k] for w in words)
        for k in ("travel", "policy", "service")
    ]
    return np.array(vec, dtype=float)

# Precompute embeddings for the documents
embeddings = [embed(d).tolist() for d in docs]

Store vectors in ChromaDB (optional)

This demonstrates how to upsert a list of vectors into a Chroma collection.
Many production vector DBs perform indexing in the background; we still build a toy index here to illustrate pruning.

# store_in_chroma.py
client = chromadb.Client()
collection = client.get_or_create_collection(name="simple_index_demo")

# Upsert embeddings into the collection.
# chromadb expects lists, so embeddings is a list of lists.
collection.upsert(ids=ids, documents=docs, embeddings=embeddings)

# Confirm count
print("Stored", collection.count(), "vectors in ChromaDB")

# Example: load them back (if needed)
data = collection.get(include=["documents", "embeddings"])
docs = data["documents"]
embeddings = data["embeddings"]

Linear (brute-force) search

Linear scanning computes the Euclidean (L2) distance from the query embedding to every stored embedding.
We count how many distance computations (“checks”) occur.

# linear_search.py
def linear_search(query: str, top_k: int = 2):
    q = embed(query)
    scores = []
    checks = 0
    # Linear scan = compute distance to every stored vector
    for i, e in enumerate(embeddings):
        checks += 1
        dist = np.linalg.norm(q - np.array(e))  # Euclidean distance
        scores.append((dist, docs[i]))

    scores.sort(key=lambda x: x[0])
    return scores[:top_k], checks

query = "flight rules"
linear_top, linear_checks = linear_search(query)
print("Query:", query)
print("Top results:", linear_top)
print("Distance checks:", linear_checks)

Expected linear-search behavior (example)

Query: “flight rules”
Top results (approx): ('airport security rules', distance 1.0), ('book flight ticket', distance ~1.4142)
Distance checks: 6
Note: exact tuple formatting may vary, but distances and counts are deterministic for this embedder.

Why indexing matters

Linear scans grow linearly with dataset size — for millions or billions of vectors this becomes infeasible.
Indexing partitions or prunes the search space, so the system computes distances only for a small subset of candidates.

Toy index (pre-partition into 3 buckets)

We build a very small index by grouping documents based on argmax of their 3-d embedding.
This produces three buckets: 0 = travel-ish, 1 = policy-ish, 2 = service-ish.

# build_index.py
index_groups = {0: [], 1: [], 2: []}

# Pre-partition vectors into 3 buckets using the dimension with the largest value.
for i, e in enumerate(embeddings):
    group = int(np.argmax(e))  # 0=travel-ish, 1=policy-ish, 2=service-ish
    index_groups[group].append(i)

# Inspect group membership (optional)
print("Index groups:", index_groups)

Indexed (pruned) search

For a query, compute its embedding, pick the target bucket with argmax, and compute distances only inside that bucket.

# indexed_search.py
def indexed_search(query: str, top_k: int = 2):
    q = embed(query)
    target_group = int(np.argmax(q))

    # Compare only against vectors inside the selected group.
    candidate_ids = index_groups[target_group]
    scores = []
    checks = 0
    for i in candidate_ids:
        checks += 1
        dist = np.linalg.norm(q - np.array(embeddings[i]))
        scores.append((dist, docs[i]))

    scores.sort(key=lambda x: x[0])
    return scores[:top_k], checks, target_group

indexed_top, indexed_checks, used_group = indexed_search(query)
print("Used group:", used_group)
print("Top results:", indexed_top)
print("Distance checks:", indexed_checks)

Compare linear vs indexed search

The linear scan checks every vector (6 checks in this demo).
The toy index prunes to the selected bucket; for our example it checks only the vectors in that bucket (2 checks), saving work.

# compare_results.py
print("\nComparison")
print("-- Linear scan checks:", linear_checks)
print("-- Indexed search checks:", indexed_checks)
print("-- Saved checks:", linear_checks - indexed_checks)

Example outputs for this demo

Used group: 0
Top results (indexed): ('book flight ticket', distance ~1.4142), ('hotel room reservation', distance ~1.4142)
Distance checks (indexed): 2
Comparison:
- Linear scan checks: 6
- Indexed search checks: 2
- Saved checks: 4

This toy index is intentionally simple to demonstrate pruning. Production vector databases use much more advanced indexing strategies (examples: IVF, HNSW, PQ) and often manage indexing automatically behind the scenes.

Summary and takeaway

Linear (brute-force) search computes distances against every stored vector and does not scale well.
Indexing partitions or prunes candidate vectors so queries require far fewer distance checks.
Even a trivial 3-bucket partition illustrates how pruning reduces checks from 6 to 2 in this example.
Understanding indexing (and index types) is crucial when designing large-scale vector search systems.

Introduction to Vector Databases and Generative AI

Vector Database Foundations

From Data to Vectors: The Embedding Layer

Vector Similarity Explained

Building Vector Storage on AWS S3

Vector Database Landscape

Vector Database Internals

Demo Understanding Indexing in Vector Database

Watch Video