Fill in the missing term in this description of how HNSW handles deletes.
The answer is tombstone: a logical-delete marker that leaves the node in the graph until compaction reclaims it.
Think of a cemetery. The person is gone but their stone is still standing on the same plot. Anyone walking through the cemetery sees the marker but knows nobody is home. Vector databases use the same trick: deletions get a marker that says nothing live is here, but the structure stays in place because pulling it out would mean redoing the paths every other stone takes. A groundskeeper comes by occasionally and reorganizes whole sections, which is the compaction step that finally reclaims the space.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Vocabulary tests in interviews are usually a proxy for something larger. The interviewer is not really asking whether the candidate knows the word tombstone; they are asking whether the candidate has seen the concept in production database design and can connect it to the operational consequences it implies.
Tombstone is a term shared across log-structured merge tree databases, distributed key-value stores, and modern vector databases. The mechanism is the same in each: a logical-deletion marker that leaves the underlying data in place until compaction reclaims it. The operational consequences are also the same: deletes are cheap, but the cost shows up at search time and in memory until cleanup runs.
This deep dive walks through the mechanism, the LSM heritage, the production consequences in vector databases specifically, and what an interviewer is actually probing for when they ask the term.
Why HNSW chose logical deletion
HNSW is a graph where each node has a set of neighbors at each level, typically M = 16 neighbors per level over 3-5 levels. The graph's small-world property depends on each node's neighbor list being saturated with live, well-chosen nodes; that property is what makes search fast.
A physical deletion would require finding every node whose neighbor list includes the deleted one and rewriting that list. The set of incoming edges to a node in a small-world graph is typically dozens; some popular hub nodes have hundreds. Each delete becomes dozens of memory writes plus (for persistent indexes) dozens of disk writes, each requiring a pointer chase and a synchronization step.
The alternative chosen by HNSW and similar graph indexes is logical deletion: mark the node as deleted, leave the structure intact, and pay the cost at search time. Search visits the tombstoned node, sees the flag, discards the candidate, and continues. The cost is a small per-tombstone tax on every traversal, but it is bounded and predictable, and it can be amortized away by periodic compaction.
The tradeoff is straightforward: physical deletion is expensive per delete and cheap per query; logical deletion is cheap per delete and slightly more expensive per query. For workloads with high delete rates relative to query rates (think churning user-data products), logical deletion wins by orders of magnitude.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- Cassandra writes tombstone cells for deletes; the same term and pattern are inherited by Milvus and Qdrant for vector deletions
- RocksDB merges tombstones during compaction; vector engines that wrap RocksDB inherit the behavior for delete reclamation
What an interviewer would ask next. Try answering before peeking at the approach.
QHow does the tombstone pattern interact with strong-consistency reads in a replicated cluster?
Tombstones must propagate to all replicas before a deleted id is safe to consider dropped. Otherwise a read that hits a lagging replica still returns the dead id. Cassandra solves this with read repair and gc grace period; vector databases solve it via segment replication and consistency-level configuration.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Calling the marker a delete flag and stopping there. The interview word is tombstone, and naming it correctly is a signal you have seen the term in production database design, not just in a tutorial.
60 second bullets to scan on the way to the call.
Why HNSW uses logical deletion via tombstones rather than physical deletion
Where the term tombstone originates and which storage systems use it
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.