Vector DB & ANN · advanced
Index Updates & Tombstones
Deleting and updating vectors in a graph index without rebuilding it.
Mental model
A proximity graph has no cheap delete: removing a node severs the edges other nodes rely on for connectivity, so implementations mark it deleted and filter it at query time instead. Tombstones are therefore a debt — they still occupy memory, still get traversed, and gradually degrade both recall and latency until a compaction rebuilds the affected region. An update is a delete plus an insert, so a workload that rewrites embeddings frequently accumulates that debt much faster than its row count suggests.
How to study Index Updates & Tombstones
Begin by restating the mental model in your own words, then connect it to a concrete system you have built or operated. Name the mechanism, the constraint it addresses, and the trade-off it introduces. Use the linked roadmap and primary implementation references to check details, but close the source before writing your explanation. Retrieval is the learning step; rereading is only preparation.
Next, compare Index Updates & Tombstones with Compaction, Disk-Based ANN. Ask what changes in correctness, latency, resource use, operability, and failure recovery. Complete Tombstones erode recall and preserve the command, input, output, and one failed attempt as evidence. Finish by explaining the idea without jargon to someone who has not studied the track.
Proof of understanding
- Explain the mechanism from first principles and identify the state it reads or changes.
- Give one situation where the concept is the right choice and one where it is not.
- Predict a realistic failure mode before running the drill, then compare the prediction with evidence.
- Connect the result to a roadmap or build artifact instead of treating the concept as isolated trivia.
Where it matters
Any vector store backing mutable documents, and the reason re-embedding is usually a rebuild-and-swap.
Common mistakes
- Assuming delete is O(1) and free; it is a filter plus deferred compaction
- Letting the tombstone ratio grow unbounded, so recall drifts down with no obvious cause
- Re-embedding a whole corpus in place rather than building a new index and swapping
- Measuring recall only on a freshly built index, which never shows the degradation
Learn from primary sources
Use the linked roadmap context and practice prompt.
Practice and explain it back
Tombstones erode recall
Implement search(graph, deleted, entry, query, k, budget) — a greedy walk over an adjacency map. Visit at most `budget` nodes; tombstoned nodes (in `deleted`) are traversed and count against the budget but must NOT appear in results. Return the ids of up to k live nodes with the smallest |value - query|, best first.
Expected evidence: With tombstones present the same budget returns fewer live results.
Open the interactive drill →Review prompts
- Why can a proximity-graph index not simply remove a deleted node, and what does the tombstone cost you over time?
Build evidence
Use a roadmap capstone to turn this concept into working evidence.