What is a structure-of-arrays memory layout?

A structure-of-arrays memory layout stores each field of a collection in its own contiguous array — all values of field A together, all values of field B together — so scanning or SIMD-processing one attribute touches tightly packed memory instead of striding through whole records.

How does structure-of-arrays arrange the same data differently from array-of-structures?

Where array-of-structures keeps one record per item with every field inside that record, structure-of-arrays flips the nesting: you hold a “structure” whose members are arrays, one array per field. For N HNSW nodes you might have an array of N maximum-layer bytes, a separate array of N neighbor-list offsets, a separate array of N flags, and so on. Reading node 7’s offset means indexing the offsets array at 7; reading every flag in the graph means walking the flags array sequentially with no other fields interleaved. The logical node still exists as “the set of values at index i across those arrays,” but physically those values may sit far apart. That is the trade: superb locality when a loop cares about one field for many nodes, extra gathers when one hop needs several fields of the same node at once.

HNSW already uses structure-of-arrays thinking for the heaviest data it owns — the vectors — even when node metadata stays record-shaped.

Why are vector stores in HNSW almost always structure-of-arrays in spirit?

A distance kernel wants every dimension of one vector, then every dimension of the next candidate, in contiguous order for wide SIMD loads. Storing all coordinates of vector i back-to-back in a big float array — often conceptually a matrix with one row per vector — is exactly “one array of components,” not “a struct that mixes coordinates with neighbor pointers and layer IDs.” Neighbor-ID lists are the same idea: a dense array (or slab) of IDs scanned during a hop, not IDs sprinkled inside fat node objects next to unrelated fields. Serious implementations, including the in-memory graphs behind systems like Weaviate, keep vectors and edge storage in these contiguous side structures so arithmetic and list scans hit the memory hierarchy cleanly. Calling that structure-of-arrays highlights why pulling vectors out of an AoS node record is not an optional polish — it is how you give the distance kernel a layout it can use.

Pushing every metadata field into separate arrays is more debatable, and that is where HNSW layouts usually go hybrid.

When does full structure-of-arrays help HNSW metadata — and when does it hurt?

A pass that scans only tombstone flags, only degrees, or only layer values across the whole index loves SoA: each cache line is nearly 100% useful, and SIMD compares or filters run over contiguous bytes. Bulk serialization and checksumming of one column at a time benefit similarly. A search hop that must read layer, degree, and neighbor-offset for the same node before chasing edges hurts: three arrays mean three potentially cold lines instead of one co-located record. Random graph traversal already struggles with pointer chasing; multiplying metadata misses per hop makes that worse. SoA also complicates allocation and growth — several arrays must stay the same length — and can increase TLB pressure if the working set now spans more distant pages for one logical node. The win appears on column-shaped work; the loss appears on row-shaped hops.

Practical HNSW indexes therefore pick SoA where scans and SIMD dominate, and AoS where multi-field node touches dominate.

How should you apply structure-of-arrays when laying out an HNSW index?

Keep vectors in a contiguous SoA-style store sized for SIMD distances. Keep neighbor IDs in dense contiguous arrays or slabs. For small control fields that search always reads together, prefer a compact AoS node record that fits in a cache line. Split out into parallel arrays any field that hot maintenance or filter loops scan alone. Measure: if a hop’s metadata stage shows multiple cache misses per node after a layout change to pure SoA, regroup those fields; if a flag scan is bandwidth-bound under AoS, extract the column. Alignment and padding still apply inside each array — SoA does not remove the need for aligned base addresses. Hybrid layout is the steady engineering answer, not ideological purity about AoS versus SoA.

Structure-of-arrays packs one field for all items contiguously, which is why HNSW vectors and neighbor lists live that way, while multi-field hops often keep a small AoS record beside them. From here, the array-of-structures page covers the complementary shape, vectorized distance computation and SIMD explain why contiguous columns matter, the memory-layout chapter for HNSW shows concrete hybrids, and contiguous layout and alignment entries detail how to keep each array efficient.