# Range Tombstone Conversion: Faster Scans Over Long Runs of Deletes

DevFeed: [Range Tombstone Conversion: Faster Scans Over Long Runs of Deletes](<https://devfeed.tech/articles/range-tombstone-conversion-faster-scans-over-long-runs-of-deletes-22402.md>)

Original publisher: [Read original article](<http://rocksdb.org/blog/2026/06/22/range-tombstone-conversion.html>)

Author: Josh Kang

Published: 2026-06-22T00:00:00Z

Content type: article

Language: en

Sources: [RocksDB](<https://devfeed.tech/sources/rocksdb.md>)

Topics: [Optimization](<https://devfeed.tech/topics/optimization.md>), [rocksdb](<https://devfeed.tech/topics/rocksdb.md>)

Tags: [blog](<https://devfeed.tech/tags/blog.md>), [conversion](<https://devfeed.tech/tags/conversion.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [performance](<https://devfeed.tech/tags/performance.md>), [range](<https://devfeed.tech/tags/range.md>), [rocksdb](<https://devfeed.tech/tags/rocksdb.md>)

## AI overview

This article explains a RocksDB optimization that converts contiguous point tombstones into a range tombstone during scans. The approach allows scans to skip a run of deleted entries in one step instead of processing each tombstone individually.

## Source excerpt

RocksDB has historically been known for poor performance when tombstones accumulate. This has become a common problem within Meta, and the community has raised it as well. Here, we introduce an optimization that attempts to convert contiguous tombstones into a range tombstone during scans. As a result, instead of skipping through N tombstones, we only need to skip through a single range tombstone. Background: point tombstones and range tombstones RocksDB is an LSM-tree, so a delete does not erase data in place. It writes a tombstone: a marker that shadows older values. A point tombstone (from Delete or SingleDelete) shadows exactly one key, while a range tombstone (from DeleteRange) shadows an entire half-open key range [start, end) with a single entry. Because newer data (usually) sits above older data in the tree, a read merges from the top down and takes the first entry it finds for a key, so a tombstone at an upper level hides any value for that key, or for any key in a range tombstone's span, at the levels below. Point and range tombstones hide the values below them. The scan steps over each point tombstone but skips the range tombstone in one hop, and only the live keys (a, e, j) are returned to the user. In both cases the space is reclaimed only later, during compaction, and only once the tombstone reaches the bottommost level with no live snapshot still needing it. Until then the tombstones sit in the way of reads. A scan never returns a deleted key, but to work out which keys are live it still has to step through every entry in key order. A point tombstone is just an ordinary entry, so the scan walks each one individually, and a run of N point tombstones costs N steps. A range tombstone is different: it is a single entry that covers the whole span, so when a scan reaches it, it can skip straight to the end of the range in one step instead of walking every key inside. Existing solutions A bulk delete leaves a region of the key space full of tombstones, and u