Skip to main content

Module posting_list

vector::serde

Module posting_list 

Source
Expand description

PostingList value encoding/decoding.

Maps centroid IDs to the list of vectors assigned to that cluster, including their full vector data.

§Role in SPANN Index

In a SPANN-style vector index, vectors are clustered around centroids. Each centroid has an associated posting list containing the vectors assigned to that cluster.

During search:

  1. Find the k nearest centroids to the query vector
  2. Load the posting lists for those centroids
  3. Compute exact distances using the embedded vectors
  4. Return top results

§Value Format

The value is a FixedElementArray of PostingUpdate entries, sorted by id. Each entry contains:

  • posting_type: 0x0 for Append, 0x1 for Delete
  • id: Internal vector ID (u64)
  • vector: The full vector data (dimensions * f32)

§Merge Operators

Posting lists use SlateDB merge operators with sort-merge semantics:

  • Both existing and new values are sorted by id
  • Merge performs a sort-merge, keeping the newer entry when ids match
  • Output remains sorted by id

Structs§

PostingListValue
PostingList value storing vector updates for a centroid cluster.

Enums§

PostingUpdate
A single posting update entry containing vector data.