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.
Detailed answer & concept explanation~2 min readEverything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.
Everything important, quickly.
4 minutes: name the term, explain why HNSW uses logical deletion, connect to LSM heritage, and finish with the operational consequences.
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
- Weaviate emits a tombstone-count metric per shard so operators can monitor accumulation before recall degrades
- Vespa documentation describes attribute and document-store tombstones with explicit guidance on compaction tuning for write-heavy feeds
What an interviewer would ask next. Try answering before peeking at the approach.
Don't say thisRed flags and common mistakes that signal junior thinking. Click to expand.
Red flags and common mistakes 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.
The night-before-the-interview bullets. Scan these on the way to the call.
Primary sources. Skim if you want the original framing.
Same topic, related formats. Practice these next.