Core data structures

Core data structures are the concrete containers behind an HNSW implementation: heaps and priority queues for candidates, sets for visited nodes, adjacency lists for edges, and skip-list-like layering ideas.
Created: Updated: 3 min read

These are the topics in this section, each on its own page with a stable path you can bookmark or share.

What topics are covered in this section?

Core data structures are the concrete containers behind an HNSW implementation: heaps and priority queues for candidates, sets for visited nodes, adjacency lists for edges, and skip-list intuition for the layered layout.

Which structures does a graph ANN search actually touch?

Search maintains a candidate priority queue – often a bounded top-k min-heap or dual-queue pattern – and a visited set so nodes are not expanded twice. Neighbor storage is an adjacency list per node per layer, sometimes with fixed-width IDs for cache density. Bitsets can accelerate visited tracking or filter allow-lists. Hash tables and hash sets show up in ID maps and deduplication. Skip lists are the conceptual ancestor of random level promotion. Generation counters appear in concurrent or reused buffers. Arrays versus linked lists matter when layouts chase contiguous scans instead of pointer chasing.

Knowing these pieces makes construction and search pseudocode readable instead of abstract.

How does this connect to performance and Weaviate?

Heap and visited-set efficiency dominate per-query overhead beyond distance math. Contiguous adjacency and sensible ID widths reduce cache misses – themes expanded in the memory and systems hubs. Weaviate’s HNSW implementation uses these same families of structures inside a durable, concurrent engine; when you tune ef, you are resizing the search beam those queues hold. Debugging a slow query often starts with counting distance calls and queue operations, not only graph degree.

Data-structure fluency turns HNSW from a black box into a program you can reason about.

What reading order works best?

Start with priority queues, min-heaps, bounded top-k, visited sets, and adjacency lists. Add skip lists when studying layers, then bitsets and hash sets for filters and dedupe. Continue into HNSW search concepts and Part IV’s implementation chapters for how they are wired together.

This section catalogs the building blocks under the algorithm. Next, read “What is a priority queue?” and “What is an adjacency list?”, then the HNSW search glossary for how those structures drive a walk.