Module tombstone 

Shared tombstone set implementations for efficient storage of deleted keys.

This module provides specialized tombstone storage implementations that can be used with both crate::set_union_with_tombstones::SetUnionWithTombstones and crate::map_union_with_tombstones::MapUnionWithTombstones.

Choosing a Tombstone Implementation

This module provides several specialized tombstone storage implementations optimized for different key types:

For Integer Keys (u64)

Use RoaringTombstoneSet:

• Extremely space-efficient bitmap compression
• Fast O(1) lookups and efficient bitmap OR operations during merge
• Works with u64 keys (other integer types can be cast to u64)

For String Keys

Use FstTombstoneSet<String>:

• Compressed finite state transducer storage
• Zero false positives (collision-free)
• Efficient union operations for merging
• Maintains sorted order
• Note: For arbitrary byte sequences, encode them as hex or base64 strings first

For Other Types

Use std::collections::HashSet for tombstones:

• Works with any Hash + Eq key type
• No compression, but simple and flexible

Alternatively, you can hash to 64-bit integers and follow instructions for that case above, understanding there’s a tiny risk of hash collision which could result in keys being tombstoned (deleted) incorrectly.

Performance Characteristics

Implementation	Space Efficiency	Merge Speed	Lookup Speed	False Positives
RoaringBitmap	Excellent	Excellent	Excellent	None
FST	Very Good	Good	Very Good	None
HashSet	Poor	Good	Excellent	None

Performance Considerations

• RoaringBitmap: Optimized for dense integer sets. Very fast for all operations.
• FST: The extend() operation rebuilds the entire FST, so batch your insertions. Use from_iter() when possible for better performance.

Thread Safety

Both implementations are Send and Sync when their contained types are. They do not use interior mutability.

Structs

FstTombstoneSet

A tombstone set backed by FST (Finite State Transducer) for byte string keys. This provides space-efficient storage with zero false positives for any type that can be serialized to bytes (strings, serialized structs, etc.). FST maintains keys in sorted order and supports efficient set operations.

RoaringTombstoneSet

A tombstone set backed by [RoaringTreemap] for u64 integer keys. This provides space-efficient bitmap compression for integer tombstones.

Traits

AsBytes

Helper trait to convert keys to byte slices for FST operations.

TombstoneSet

Trait for tombstone set implementations that support efficient union operations.