Freshness, Deletes and Index Maintenance
Why approximate indexes are built for static data, what insertion and deletion do to their structure over time, and the segment architecture that reconciles freshness with query performance.
Approximate nearest-neighbour indexes were designed for a static collection: build once, query many times. Production collections change continuously, and every index family degrades under mutation in its own way. Managing that degradation is most of what a vector database does beyond the search itself.
What mutation does
Graph indexes such as HNSW support insertion natively, since a new point connects to its neighbours. Repeated insertion still degrades the graph, because the connectivity that made early points well-linked reflects a distribution that has since changed, and long-lived graphs drift toward worse recall than a freshly built one on the same data.
Deletion is the harder half. Removing a node breaks paths that routed through it, and repairing the graph properly is expensive, so implementations mark nodes deleted and skip them at query time. Those tombstones still occupy memory, still consume traversal steps, and still degrade recall, so a collection with heavy churn accumulates a growing tax until it is rebuilt.
Partition-based indexes such as IVF assign points to clusters learned from a sample. New points join their nearest existing cluster, so as the distribution drifts the clusters describe an older data distribution and become unbalanced, concentrating points in a few partitions and destroying the pruning that made the index fast. Re-clustering restores it and requires a full rebuild.
The segment architecture
The pattern that resolves this borrows from log-structured storage. Writes go to a small in-memory structure searched by brute force, which is fast because it is small and always current. Periodically it is sealed and built into an immutable indexed segment. A query searches every segment and merges results. Background compaction merges small segments into larger ones and physically removes tombstoned points.
This gives immediate freshness, since new data is searchable in the write buffer, with efficient search over the bulk, since sealed segments are properly indexed. The costs are that query cost grows with segment count, so compaction must keep pace, and that results must be merged across segments, which requires each to return more candidates than the final \(k\).
When it breaks
Compaction competes with queries. Rebuilding an index segment is IO- and CPU-intensive, and doing it under load degrades latency exactly when the system is busiest. Scheduling it into quiet periods works until there are none.
Recall drifts without anyone noticing. Index quality degrades gradually with churn, and there is no error to alert on. Periodic recall measurement against a ground-truth sample is the only way to detect it, and it is rarely instrumented.
Rebuild cost scales with collection size. A hundred-million-vector index takes hours to build, during which the old one must keep serving, so the system needs capacity for two copies. This is a capacity planning fact that surprises teams at the point they can least afford it.
Updates are delete plus insert. Changing a vector means removing the old point and adding a new one, so an embedding model upgrade that re-embeds everything is a complete rebuild rather than an update, and it should be planned as a migration.
12 flashcards for this concept
Click a card to reveal the answer.