Deletion markers and record visibility

Separate visibility, durability, and reclamation

For one key, a tombstone in a newer layer hides a value in an older layer:

newer layer: 42 -> deletion marker
older layer: 42 -> "Ada"
normal read: key 42 is not found

A delete returning successfully does not imply that old bytes have already been removed or that the storage device has flushed the write. See WAL modes for the persistence boundary.

Choose a marker that is not application data

With many primitive value types, the default value represents deletion. For references it is null; for Memory<byte> it is an empty value. A custom value type uses default equality unless you configure another rule.

If zero is a valid integer value, reserve a different marker. This complete program uses -1 as the tombstone:

using ZoneTree;

using var tree = new ZoneTreeFactory<int, int>()
    .SetDataDirectory("data/deletion-example")
    .SetIsDeletedDelegate((in int key, in int value) => value == -1)
    .SetMarkValueDeletedDelegate((ref int value) => value = -1)
    .OpenOrCreate();
using var maintainer = tree.CreateMaintainer();

tree.Upsert(42, 0);
Console.WriteLine(tree.TryGet(42, out var value));
Console.WriteLine(value);
tree.TryDelete(42, out _);
Console.WriteLine(tree.ContainsKey(42));

It prints True, 0, then False. Configure both delegates together:

Your serializer must round-trip the marker as well as live values. Changing deletion rules on an existing tree can change what becomes visible without changing any stored bytes; preserve the rules across reopen or migrate deliberately.

Delete APIs and tombstone writes

The check and write in TryDelete are not a serialized conditional action against competing writers. See reads and writes for coordination choices.

Ordinary iterators hide deleted records. includeDeletedRecords: true exposes them for a workflow that understands tombstones. That option alone does not supply the ordering, metadata, or lifecycle guarantees of a complete backup or replication protocol.

Model TTL as a visibility predicate

Store the expiration time in the value and test it from IsDeleted. This complete example uses an unmanaged value and supplies its serializer explicitly:

using ZoneTree;
using ZoneTree.Serializers;

using var tree = new ZoneTreeFactory<int, ExpiringValue>()
    .SetDataDirectory("data/ttl-example")
    .SetValueSerializer(new StructSerializer<ExpiringValue>())
    .SetIsDeletedDelegate((in int key, in ExpiringValue value) =>
        value.ExpiresAtUnixMilliseconds <= DateTimeOffset.UtcNow.ToUnixTimeMilliseconds())
    .SetMarkValueDeletedDelegate((ref ExpiringValue value) =>
        value.ExpiresAtUnixMilliseconds = 0)
    .OpenOrCreate();
using var maintainer = tree.CreateMaintainer();

var now = DateTimeOffset.UtcNow;
tree.Upsert(1, new ExpiringValue(99, now.AddMinutes(5).ToUnixTimeMilliseconds()));
tree.Upsert(2, new ExpiringValue(88, now.AddMinutes(-5).ToUnixTimeMilliseconds()));
Console.WriteLine(tree.ContainsKey(1));
Console.WriteLine(tree.ContainsKey(2));

public record struct ExpiringValue(long Payload, long ExpiresAtUnixMilliseconds);

Under a stable clock, the first record is live and the second is expired. Use a stable, deliberate clock policy in an application whose expiration correctness depends on time. Raw struct serialization also requires preserving the value's layout; see serializers.

Treat expiration as a one-way visibility decision for records that maintenance may discard. If a clock or policy change makes an expired value live again, a record already reclaimed by compaction cannot be reconstructed by reversing that predicate.

Remove whole parts only with a proof

SetIsRangeDeletedDelegate enables an optional merge optimization. The delegate receives a part's first and last key/value pairs in comparer order. Returning true lets the merge skip the whole part without inspecting interior records.

Checking only that the endpoints have expired is not sufficient: a live record can lie between them. Return true only when application invariants prove every record in the part is deleted according to IsDeleted; return false when that cannot be established.

For example, permanently retiring the complete ID interval [1000, 1999] makes every part wholly contained in that interval removable:

using ZoneTree;

const int firstRetiredId = 1000;
const int lastRetiredId = 1999;

using var tree = new ZoneTreeFactory<int, string?>()
    .SetDataDirectory("data/retired-ids-example")
    .SetIsDeletedDelegate((in int id, in string? value) =>
        value is null || (id >= firstRetiredId && id <= lastRetiredId))
    .SetMarkValueDeletedDelegate((ref string? value) => value = null)
    .SetIsRangeDeletedDelegate((in int firstId, in string? firstValue,
        in int lastId, in string? lastValue) =>
        firstId >= firstRetiredId && lastId <= lastRetiredId)
    .OpenOrCreate();
using var maintainer = tree.CreateMaintainer();

tree.Upsert(1200, "Retired");
tree.Upsert(2000, "Active");
Console.WriteLine(tree.ContainsKey(1200));
Console.WriteLine(tree.ContainsKey(2000));

The range test works because the integer comparer is ascending and the entire retired interval is covered by the record-level rule. Both delegate endpoints are inclusive. Keep these delegates safe for concurrent merge calls.

Preserve tombstones while older values still exist

The engine applies whole-part deletion only where dropping markers cannot expose an older version:

Newer inputs are still processed normally, including records whose keys overlap a skipped part. Single-part inputs use the ordinary record merge path. Skipping a part retires it from the result; actual file deletion still follows segment ownership and active-reader lifetimes.

Disable deletion only when no record needs it

using ZoneTree;

using var tree = new ZoneTreeFactory<int, int>()
    .SetDataDirectory("data/no-deletion-example")
    .DisableDeletion()
    .OpenOrCreate();
using var maintainer = tree.CreateMaintainer();

tree.Upsert(42, 0);
Console.WriteLine(tree.ContainsKey(42));

With deletion disabled, every stored value is treated as live, including the default. Do not use delete APIs expecting a key to become absent: the configured marker operation no longer produces a deleted value.