vectra

I wanted to understand how vector databases handle search under the hood, so I built Vectra without relying on existing approximate nearest-neighbour libraries like FAISS. You give it embedding vectors, and it can search them either exactly or approximately using an HNSW graph implemented in NumPy.

The library supports cosine similarity, Euclidean distance, and dot product, all using float32 vectors.

The main API is a single VectorIndex class. It supports adding batches of vectors, searching, deleting entries, rebuilding the index, and filtering results using metadata. Queries can also be run asynchronously or in batches. I added a CLI for building indexes, inspecting them, and running benchmarks.

HNSW

The main part of the project is the approximate search implementation. I implemented the Hierarchical Navigable Small World (HNSW) algorithm directly in NumPy.

The index uses randomly assigned levels to build a multi-layer graph. Searches start at the upper layers, where the graph helps narrow down the search area, before moving to a more detailed search at the bottom layer.

I also implemented the neighbour selection heuristic used when building the graph, along with the main HNSW parameters: M, ef_construction, and ef_search.

One thing I wanted to support was adjusting the search quality without having to rebuild the index. You can pass a different ef_search value for an individual query, trading search speed for recall depending on what you need.

I also wrote a benchmark script to measure recall, query latency, and memory usage using clustered datasets.

Storage and quantization

I wanted indexes to be usable beyond what could comfortably fit in memory, so I built a custom binary storage format called .vdb.

The file is split into sections, with a header and a table describing where each section is stored. These include the configuration, IDs, raw vectors, deletion bitmask, metadata, quantization codes, and serialized HNSW graph.

I also implemented memory-mapped loading through VectorIndex.mmap(). This maps the vector section directly from disk, allowing a large flat index to be searched without loading the entire vector data into memory first.

I added two quantization methods to reduce how much space the vectors take up.

Scalar quantization maps each dimension to a uint8 value, reducing vector storage by roughly 4x. Product quantization takes a different approach: it splits each vector into smaller subspaces and learns a separate k-means codebook for each one. Vectors can then be represented using compact codes instead of storing their original values.

Both quantization methods, including the clustering used to build the codebooks, are implemented directly in the library.