Catalog My learning Blog
LLM System Design Course: RAG, Vector Databases, Cost · Phase 3 · Lesson 11 · 8 min read

What Is a Vector Database?

On this page
  1. Learning Objective
  2. Concept Explanation
  3. Worked Example: Sizing an Index Before Building Anything
  4. Real-World Examples
  5. Review Questions & Answers

Learning Objective

Explain why a B-tree, a hash index, and an inverted index are all structurally incapable of answering a nearest-neighbor query, what a vector index provides instead, and which parts of a vector database are genuinely novel versus ordinary database machinery wearing a new label.

Concept Explanation

Every familiar database index answers a question about equality or ordering along a single dimension. A hash index answers "where is the row whose key equals this value" by computing a bucket. A B-tree answers "which rows fall in this range" by exploiting a total ordering, which is exactly why range scans and sorted output come for free. An inverted index answers "which documents contain this term" by keeping a posting list per term. All three work because the data has a structure - a hash bucket, an ordering, a discrete vocabulary - that lets the index eliminate most of the data without examining it.

A nearest-neighbor query has none of that structure. "Find the twenty vectors closest to this 1024-dimensional point" cannot be decomposed into equality tests or range scans, because closeness is a property of all 1024 dimensions jointly and no single dimension constrains the answer. You could index each dimension separately and you would gain nothing, because a point can be nearest overall while ranking unremarkably on every individual axis. The exact answer requires computing the distance to every stored vector, which is a full scan, and at ten million vectors of 1024 dimensions that is roughly forty gigabytes of floating point arithmetic per query. Correct, and useless at interactive latency.

The escape is to give up exactness. Approximate nearest neighbor search accepts that you will usually, not always, get the true top-k, and in exchange it runs in something close to logarithmic rather than linear time. This is the genuinely novel component of a vector database, and it is worth being clear that it is a different kind of guarantee than databases normally offer. A B-tree lookup is exact; an ANN lookup has a recall figure, typically quoted as recall at ten, which might be 0.95, meaning on average nineteen of the true top twenty are returned. Recall is tunable against latency at query time and against build time and memory at index time, which makes it a design parameter rather than a defect - but it is a parameter that must be measured, because nothing in the system reports that it silently returned the twenty-first-best result.

It is worth deflating the category a little, because "vector database" describes a feature more than a fundamentally new kind of system. Storage, replication, backup, transactions, access control, and query planning in a vector database are ordinary database problems solved in ordinary ways, and several of the dedicated products were slower to solve them well than mature relational engines were. What is actually distinctive is the index structure, the memory profile it demands, and the operational characteristics that follow from both: the index typically wants to be resident in RAM, rebuilding it is expensive, deletes are often soft with periodic compaction rather than immediate, and filtering interacts with the index in ways that have no equivalent in a B-tree world, which is the subject of a later lesson in this phase.

The practical consequence for a systems designer is that the memory footprint is usually the binding constraint and is easy to compute in advance. Ten million chunks at 1024 dimensions in 32-bit floats is roughly forty gigabytes for the raw vectors alone, before the graph or partition structure the index adds on top, which for a graph index commonly adds a substantial further fraction. That arithmetic, done on a whiteboard before anything is built, frequently changes the design: it argues for smaller embedding dimensions, for quantization, for filtering the corpus rather than indexing everything, and occasionally for the realization that the corpus is small enough that a brute-force scan over a few hundred thousand vectors is entirely fine and needs no specialized system at all.

Index TypeQuestion It AnswersStructure ExploitedGuarantee
HashWhich row has exactly this key?Deterministic bucket assignmentExact
B-treeWhich rows fall in this range, in order?Total ordering on one dimensionExact
InvertedWhich documents contain this term?Discrete vocabulary with posting listsExact
Vector (ANN)Which vectors are closest to this point?Geometric proximity in many dimensions at onceApproximate, with a tunable recall

Worked Example: Sizing an Index Before Building Anything

This arithmetic takes two minutes and routinely changes the architecture, because the memory number is usually the constraint that decides between a Postgres extension, a managed service, and a redesign of the corpus itself.

Code
# Corpus: 4 million documents, average 12 chunks each -> 48M chunks

RAW VECTOR MEMORY
  48,000,000 vectors x 1024 dims x 4 bytes (float32)  = 196 GB
  + HNSW graph overhead (M=16, roughly 30-50% on top) =  ~78 GB
  -------------------------------------------------------------
  total resident memory needed                        ~274 GB

THE LEVERS, APPLIED IN ORDER OF LEAST DAMAGE TO QUALITY
  1. Reduce dimensions 1024 -> 512 (Matryoshka-style truncation)
       raw: 98 GB   total: ~137 GB     quality cost: small, MEASURE IT
  2. Scalar-quantize float32 -> int8
       raw: 25 GB   total:  ~65 GB     quality cost: small, recoverable by
                                        rescoring top candidates on full vectors
  3. Binary-quantize (1 bit per dim)
       raw:  3 GB   total:  ~12 GB     quality cost: real, mandatory rescoring
  4. Shard by tenant so no single index holds all 48M
       each shard fits in RAM; cross-tenant search is not a requirement anyway

EXACT SEARCH SANITY CHECK (do this first)
  200,000 vectors x 1024 dims x 4 bytes = 0.8 GB, brute force ~15 ms
  -> below roughly this scale, an ANN index is complexity with no benefit.
Three conventional index types each collapsing a query to a small candidate set using an exploitable structure, contrasted with a nearest-neighbor query where no single dimension constrains the answer, motivating an approximate graph or partition index with a tunable recall.
Three conventional index types each collapsing a query to a small candidate set using an exploitable structure, contrasted with a nearest-neighbor query where no single dimension constrains the answer, motivating an approximate graph or partition index with a tunable recall.

Real-World Examples

  • FAISS, open-sourced by Facebook AI Research in 2017, is the library that made billion-scale similarity search practical on commodity hardware, and it is the engine underneath a large number of products and several vector databases. Its design makes the tradeoff explicit by offering a family of index types from exact flat search through inverted-file partitioning to product quantization, each with a different position on the recall, memory, and speed surface.
  • Apache Lucene added native HNSW-based vector search in Lucene 9, which is what brought approximate nearest neighbor search into Elasticsearch and OpenSearch as a first-class query type alongside BM25. That integration is direct evidence that vector search is best understood as an index type a database can support rather than as a category of system that must be purchased separately.
Key TakeawaysCompute the resident memory footprint of your vector index before choosing any technology: vector count multiplied by dimensions multiplied by bytes per component, plus graph overhead. That single number decides between an extension on your existing database, a dedicated service, dimension reduction, quantization, or sharding, and it frequently reveals that the corpus is small enough for exact search, where an approximate index adds complexity and no benefit at all.

Review Questions & Answers

Because proximity is a joint property of all dimensions at once, not a conjunction of per-dimension conditions. A vector can be the nearest overall while sitting at an entirely unremarkable position on every individual axis, and conversely a vector that matches closely on a handful of axes can be far away overall. Per-dimension indexes can only express range or equality constraints on single axes, so they cannot prune candidates without risking the elimination of the true nearest neighbor. The pruning has to be done in the joint space, which is exactly what a graph or partition-based vector index does.

It means that on average, across a set of test queries, the index returns nineteen of the twenty true nearest neighbors, or in the ten case nine and a half of the true top ten, with the remainder replaced by slightly worse but usually still relevant results. It needs measuring because nothing in the system signals a miss: the query returns the requested number of results with plausible scores whether or not the true best neighbor was among them. Recall is also a function of index build parameters, query-time search effort, and corpus distribution, so a figure measured on one dataset does not transfer, which makes a ground-truth comparison against exact search on a sample the only reliable way to know it.

Storage, durability, replication, backup, access control, and query planning in a vector database are conventional database problems solved with conventional techniques, and mature relational engines had already solved several of them better than early dedicated vector products did. The genuinely distinctive element is the approximate index structure and the operational profile that follows from it: a strong preference for resident memory, expensive index rebuilds, soft deletes with periodic compaction, and filtering that interacts with the index in ways no B-tree ever does. That is why an extension such as pgvector can be a legitimate competitor to a purpose-built service rather than an obvious compromise.

When a brute-force scan over the full corpus already meets the latency budget, which for a few hundred thousand vectors of moderate dimensionality is often a matter of tens of milliseconds using vectorized distance computation. Below that point the approximate index adds build time, memory overhead, tuning parameters, recall uncertainty, and an extra operational component, while delivering a latency improvement the product cannot perceive and giving up exactness that costs nothing to keep. Running the brute-force sanity check first is also the only way to obtain the ground truth that any later recall measurement has to be compared against.