lsm_tree/tree/

mod.rs

// SPDX-License-Identifier: Apache-2.0
// Copyright (c) 2024-present, fjall-rs
// Copyright (c) 2026-present, Dmitry Prudnikov

#[cfg(feature = "columnar")]
pub(crate) mod columnar_scan;
mod data_stage;
pub(crate) mod ingest;
pub(crate) mod inner;
mod level_resolve;
mod level_stages;
mod multi_get_read;
pub(crate) mod read_job;
pub mod resumable;
pub(crate) mod sealed;
mod tables_read;

use crate::path::Path;
use crate::{
    AbstractTree, Checksum, KvPair, SeqNo, SequenceNumberCounter, TableId, UserKey, UserValue,
    ValueType,
    compaction::{CompactionStrategy, state::CompactionState},
    config::Config,
    format_version::FormatVersion,
    fs::Fs,
    iter_guard::{IterGuard, IterGuardImpl},
    key::InternalKey,
    manifest::Manifest,
    memtable::Memtable,
    range_tombstone::RangeTombstone,
    scan_since::ScanSinceEvent,
    slice::Slice,
    table::{Table, probe_stats::PlanCounts},
    value::InternalValue,
    version::{SuperVersion, SuperVersions, Version, recovery::recover},
    vlog::BlobFile,
};
use alloc::sync::Arc;
#[cfg(not(feature = "std"))]
use alloc::{boxed::Box, string::ToString, vec::Vec};
use core::ops::{Bound, RangeBounds};
use inner::{FlushGuard, TreeId, TreeInner, VersionsWriteGuard};
// no-std: spin mirrors parking_lot's Mutex/RwLock API without an allocator.
// parking_lot wins on the std hot path, so keep it for std.
#[cfg(feature = "std")]
use parking_lot::{Mutex, RwLock};
#[cfg(not(feature = "std"))]
use spin::{Mutex, RwLock};

#[cfg(feature = "metrics")]
use crate::metrics::Metrics;

/// Floor for the storage-admission reserved headroom band (see
/// [`Tree::compute_write_admission`]). Even with an empty active memtable the
/// gate keeps at least this much room below the budget so the next writes and a
/// space-reclaiming compaction have somewhere to land. 1 MiB.
pub(crate) const MIN_RESERVED_HEADROOM: u64 = 1024 * 1024;

/// How long a cached disk-free sample stays valid before the admission gate
/// re-probes. Bounds how stale the physical free-space figure can be when the
/// filesystem fills from another process between flushes, without issuing a
/// `statfs`/`statvfs` syscall on every gated write. 1 second.
const ADMISSION_DISK_FREE_TTL: core::time::Duration = core::time::Duration::from_secs(1);

/// Iterator value guard
pub struct Guard(crate::Result<(UserKey, UserValue)>);

impl IterGuard for Guard {
    fn into_inner_if(
        self,
        pred: impl Fn(&UserKey) -> bool,
    ) -> crate::Result<(UserKey, Option<UserValue>)> {
        let (k, v) = self.0?;

        if pred(&k) {
            Ok((k, Some(v)))
        } else {
            Ok((k, None))
        }
    }

    fn key(self) -> crate::Result<UserKey> {
        self.0.map(|(k, _)| k)
    }

    fn size(self) -> crate::Result<u32> {
        #[expect(clippy::cast_possible_truncation, reason = "values are u32 length max")]
        self.into_inner().map(|(_, v)| v.len() as u32)
    }

    fn into_inner(self) -> crate::Result<(UserKey, UserValue)> {
        self.0
    }
}

/// Trait for monomorphized table point-read results.
///
/// Allows `find_in_tables` to operate generically over `InternalValue` (for
/// `get`) and `(InternalValue, Block)` (for `get_pinned`), generating optimal
/// code for each path without runtime dispatch or extra refcount overhead.
trait TablePointLookup: Sized {
    fn lookup(
        table: &Table,
        key: &[u8],
        seqno: SeqNo,
        key_hash: u64,
    ) -> crate::Result<Option<Self>>;
    fn entry_seqno(&self) -> SeqNo;
    fn filter_tombstone(self) -> Option<Self>;
}

/// Lookup result for standard `get()` — entry only, no block retained.
type TableEntry = InternalValue;

/// One covered key in a batched run resolution: `(input index, key hash,
/// resolved item)`. Aliased to keep `resolve_run_batched`'s return readable.
type CoveredKey = (usize, u64, Option<InternalValue>);

/// `(miss_keys, duplicates)` from [`Tree::dedup_sorted_miss_keys`]: `miss_keys`
/// is `(key_index, bloom_hash)` for the strictly-sorted-unique batched resolver,
/// `duplicates` is `(duplicate_index, representative_index)` for the fan-out.
type DedupedMissKeys = (Vec<(usize, u64)>, Vec<(usize, usize)>);

/// The outcome of resolving a key batch against one run (see `resolve_run_batched`).
struct RunResolve {
    /// Covered, non-skipped keys with their resolved item, in input order.
    covered: Vec<CoveredKey>,
    /// Keys this run does not cover, in input order, for the next run or level.
    not_covered: Vec<(usize, u64)>,
}

/// One data block the chunked `multi_get` resolver will read (see
/// `resolve_level_chunked`): the block, the SST it lives in, the table-local
/// read seqno, whether it needs the special load path (Page-ECC / columnar),
/// and the ORIGINAL key indices that fall in this block, each with its key's
/// hash. The table's file is opened when the block's chunk is read, so a
/// level holds open only the files of the chunk it is reading.
struct BlockTask<'a> {
    table: &'a crate::Table,
    /// The table's place in the version, by which a job names it.
    at: read_job::TableAt,
    handle: crate::table::BlockHandle,
    table_seqno: SeqNo,
    special: bool,
    keys: Vec<(usize, u64)>,
}

/// A level's block tasks, and per table the filter probes planning them took,
/// not yet counted.
type LevelTasks<'a> = (Vec<BlockTask<'a>>, Vec<(&'a Table, PlanCounts)>);

/// One table of a level being planned for a key batch: the keys it covers,
/// and how it is read.
struct LevelTable<'a> {
    table: &'a Table,
    /// The table's place in the version, by which a job names it.
    at: read_job::TableAt,
    /// Its keys: a span of the level's batch, which every run of the level
    /// walks in the same order, so no table holds a copy of its keys.
    keys: core::ops::Range<usize>,
    read: LevelRead<'a>,
    /// The file the first stage opened, held for every later stage: on a
    /// level wider than the descriptor cache, the cache has evicted it by
    /// then, and opening it again is a cold open per stage. It is let go once
    /// the table's stages are over.
    file: Option<Arc<dyn crate::fs::FsFile>>,
}

/// How a table of a level is read for its keys.
enum LevelRead<'a> {
    /// Not begun: nothing past its span of keys is built until it has a
    /// place to read in, so a level wider than the descriptor cache holds the
    /// key positions of no more tables than it holds files.
    Pending,
    /// Read in stages.
    Staged(crate::table::staged::StagedRead<'a>),
    /// To be planned serially: a Page-ECC table, whose every block needs the
    /// load path's recovery, or a table a stage of which failed.
    Serial,
    /// Planned serially: its read seqno, the blocks it reads with the
    /// positions of their keys in its span, and the filter probes planning
    /// took.
    Planned(
        SeqNo,
        Vec<(crate::table::BlockHandle, Vec<usize>)>,
        PlanCounts,
    ),
    /// No key of the batch reads anything in it.
    Nothing,
}

impl LevelRead<'_> {
    /// Whether the table needs no more stages: planned, or left to the
    /// serial planner, or with nothing to read.
    fn is_over(&self) -> bool {
        match self {
            Self::Pending => false,
            Self::Staged(read) => read.is_done(),
            Self::Serial | Self::Planned(..) | Self::Nothing => true,
        }
    }
}

/// A data block task's block before its chunk is read.
enum TaskBlock {
    /// At hand: taken from the cache.
    Held(crate::table::DataBlock),
    /// To be read in the chunk's batch.
    Read,
    /// To be loaded when its chunk is read, through a Page-ECC or columnar
    /// table's own path, which heals or reconstructs it; held only while its
    /// keys are read.
    Load,
}

/// The read queue of one backend a level's tables were opened through.
struct LevelQueue<'a> {
    fs: &'a Arc<dyn crate::fs::Fs>,
    queue: Box<dyn crate::fs::ReadQueue + 'a>,
    /// Whether the queue wakes the level's [`LevelWake`] as its reads come
    /// back, so the level can sleep on all its queues at once.
    wakes: bool,
}

/// Where the blocking driver takes a read's asks: a block read straight into
/// the queue of its backend, so no list stands between the read and the
/// queue; a job until the pass that asked for it is over, since running it
/// hands its result back to the read.
struct DriveSink<'a> {
    /// One queue per backend, opened when a table first asks it for a block,
    /// so a read answered from the cache opens none.
    queues: Vec<LevelQueue<'a>>,
    #[cfg(feature = "std")]
    wake: Arc<LevelWake>,
    jobs: Vec<read_job::Job>,
    /// The cache of the first table a block was read for, which the waits
    /// on the queues are timed into for the estimate that decides whether
    /// misses share loads.
    cache: Option<&'a crate::cache::Cache>,
}

impl<'a> read_job::ReadSink<'a> for DriveSink<'a> {
    fn job(&mut self, job: read_job::Job) {
        self.jobs.push(job);
    }

    /// The blocking driver completes every read itself, on the calling
    /// thread, and runs its jobs there too.
    fn leads_loads(&self) -> bool {
        crate::inflight::batches_may_lead()
    }

    #[expect(clippy::indexing_slicing, reason = "a slot is a position in `queues`")]
    fn read(&mut self, read: read_job::BlockRequest<'a>) {
        if self.cache.is_none() {
            self.cache = Some(read.cache);
        }
        let slot = if let Some(slot) = self.queues.iter().position(|q| Arc::ptr_eq(q.fs, read.fs)) {
            slot
        } else {
            #[cfg_attr(not(feature = "std"), expect(unused_mut))]
            let mut queue = read.fs.read_queue();
            #[cfg(feature = "std")]
            let wakes = queue.set_wake(Arc::clone(&self.wake) as Arc<dyn crate::fs::ReadWake>);
            #[cfg(not(feature = "std"))]
            let wakes = false;
            self.queues.push(LevelQueue {
                fs: read.fs,
                queue,
                wakes,
            });
            self.queues.len() - 1
        };
        self.queues[slot].queue.submit(crate::fs::QueuedRead {
            tag: read.tag,
            file: read.file,
            offset: read.offset,
            buf: read.buf,
        });
    }
}

/// The filter and index bytes each table of a staged level read holds, and
/// their sum: the buffers of its blocks in flight, at the size they are read
/// as, and the blocks its read holds, at their decoded size.
struct MetaHeld {
    in_flight: Vec<u64>,
    held: Vec<u64>,
    total: u64,
}

impl MetaHeld {
    fn new(tables: usize) -> Self {
        Self {
            in_flight: vec![0; tables],
            held: vec![0; tables],
            total: 0,
        }
    }

    /// Counts the table at `at` anew, its read holding `read_held` bytes.
    #[expect(
        clippy::indexing_slicing,
        reason = "`at` indexes the level's tables, which both vectors are sized to"
    )]
    fn settle(&mut self, at: usize, read_held: u64) {
        let now = self.in_flight[at] + read_held;
        // `total` sums `held`, so it is at least the share replaced here.
        self.total = self.total - self.held[at] + now;
        self.held[at] = now;
    }
}

/// Woken by any queue of a level when one of its reads is back: each wake
/// moves the generation on, so a wake landing between the driver's look at
/// the queues and its park is not lost, and unparks the driving thread only
/// while it sleeps on the wake. A driver waiting inside one queue is parked
/// by that queue's own channel, which an unpark of ours would only wake
/// spuriously, a context switch per read for nothing.
// no-std: without a thread to park, the level waits on one queue at a time.
#[cfg(feature = "std")]
struct LevelWake {
    generation: core::sync::atomic::AtomicU64,
    /// Whether the driver sleeps on this wake. Set before it looks at the
    /// generation and read after a wake moves it, both sequentially
    /// consistent: either the driver sees the new generation and does not
    /// park, or the wake sees it asleep and unparks it.
    sleeping: core::sync::atomic::AtomicBool,
    thread: std::thread::Thread,
}

#[cfg(feature = "std")]
impl crate::fs::ReadWake for LevelWake {
    fn wake(&self) {
        self.generation
            .fetch_add(1, core::sync::atomic::Ordering::SeqCst);
        if self.sleeping.load(core::sync::atomic::Ordering::SeqCst) {
            self.thread.unpark();
        }
    }
}

impl TablePointLookup for TableEntry {
    fn lookup(
        table: &Table,
        key: &[u8],
        seqno: SeqNo,
        key_hash: u64,
    ) -> crate::Result<Option<Self>> {
        table.get(key, seqno, key_hash)
    }

    fn entry_seqno(&self) -> SeqNo {
        self.key.seqno
    }

    fn filter_tombstone(self) -> Option<Self> {
        ignore_tombstone_value(self)
    }
}

/// Lookup result for `get_pinned()` — entry + block for zero-copy pinning.
type TableEntryWithBlock = (InternalValue, crate::table::Block);

impl TablePointLookup for TableEntryWithBlock {
    fn lookup(
        table: &Table,
        key: &[u8],
        seqno: SeqNo,
        key_hash: u64,
    ) -> crate::Result<Option<Self>> {
        table.get_with_block(key, seqno, key_hash)
    }

    fn entry_seqno(&self) -> SeqNo {
        self.0.key.seqno
    }

    fn filter_tombstone(self) -> Option<Self> {
        ignore_tombstone_value(self.0).map(|iv| (iv, self.1))
    }
}

/// Lookup result for the value-returning `get()` path: `(value_type, seqno,
/// value)`, no key reconstruction (the caller has the needle).
type TableValue = (ValueType, SeqNo, crate::Slice);

impl TablePointLookup for TableValue {
    fn lookup(
        table: &Table,
        key: &[u8],
        seqno: SeqNo,
        key_hash: u64,
    ) -> crate::Result<Option<Self>> {
        table.get_value(key, seqno, key_hash)
    }

    fn entry_seqno(&self) -> SeqNo {
        self.1
    }

    fn filter_tombstone(self) -> Option<Self> {
        if self.0.is_tombstone() {
            None
        } else {
            Some(self)
        }
    }
}

fn ignore_tombstone_value(item: InternalValue) -> Option<InternalValue> {
    if item.is_tombstone() {
        None
    } else {
        Some(item)
    }
}

/// A log-structured merge tree (LSM-tree/LSMT)
///
/// Clones share one tree. Background work of the tree (the table file pool,
/// the file deleter) may still touch its directory after a handle drops; to
/// remove the directory, [`close`](Self::close) the tree and wait for the
/// returned [`TreeClose`](crate::TreeClose): once it fires, the tree writes
/// nothing into its directory any more.
#[derive(Clone)]
pub struct Tree(#[doc(hidden)] pub Arc<TreeInner>);

impl core::ops::Deref for Tree {
    type Target = TreeInner;

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl crate::abstract_tree::sealed::Sealed for Tree {}

impl Tree {
    /// A handle that does not keep the tree open; see [`WeakTree`](crate::WeakTree).
    #[must_use]
    pub fn downgrade(&self) -> crate::WeakTree {
        crate::WeakTree::of(self, None)
    }

    /// Gives up this handle and returns the signal of the tree being closed.
    ///
    /// The tree is closed once nothing of it owns a file of its directory or
    /// works in it any more: other strong handles, iterators, snapshots and
    /// pins keep it open until they drop, and the table file pool and the
    /// background deleter finish what they started. Once closed, the tree
    /// writes nothing into its directory and removing the directory is safe.
    ///
    /// From this call on no [`WeakTree`](crate::WeakTree) raises the tree
    /// again; strong handles already held keep working until dropped.
    ///
    /// # Examples
    ///
    /// ```
    /// # let folder = tempfile::tempdir()?;
    /// use lsm_tree::{AbstractTree, AnyTree};
    ///
    /// let AnyTree::Standard(tree) = lsm_tree::Config::new(
    ///     folder.path(),
    ///     lsm_tree::SequenceNumberCounter::default(),
    ///     lsm_tree::SequenceNumberCounter::default(),
    /// )
    /// .open()?
    /// else {
    ///     unreachable!("no key-value separation configured");
    /// };
    /// let monitor = tree.downgrade();
    ///
    /// let closed = tree.close();
    /// assert!(monitor.upgrade().is_none());
    /// closed.wait();
    /// std::fs::remove_dir_all(folder.path())?;
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn close(self) -> crate::TreeClose {
        crate::close::close(self)
    }
}

/// Maps a raw merge-pipeline item into a standard-tree iterator guard.
fn standard_guard(item: crate::Result<InternalValue>) -> IterGuardImpl {
    IterGuardImpl::Standard(Guard(item.map(|iv| (iv.key.user_key, iv.value))))
}

/// A guard carrying only an error: the single item an iterator surface yields
/// when it fails before it can open a snapshot (no row, no version to bind a
/// blob guard to), so the failure reaches the consumer through the same
/// `Result` it already handles per row.
pub(crate) fn error_guard(e: crate::Error) -> IterGuardImpl {
    IterGuardImpl::Standard(Guard(Err(e)))
}

/// The bytes an install keeps, for each counter set they go to: the set of
/// the backend each file was written through (see
/// [`Fs::write_io_stats`]), so a route on
/// another medium is charged to that medium's set. Files on a backend that
/// counts nothing are not looked at.
///
/// Read before the install publishes the files, recorded once it has
/// ([`Self::charge`]): an install that fails keeps nothing.
#[derive(Default)]
pub(crate) struct InstalledCharge(Vec<(Arc<crate::fs::WriteIoStats>, crate::fs::WriteOrigin, u64)>);

impl InstalledCharge {
    /// Adds the files of `tables`, written for `table_origin`, and of
    /// `blob_files`, written for `blob_origin`.
    ///
    /// # Errors
    ///
    /// A counted blob file whose length cannot be read.
    pub(crate) fn add(
        &mut self,
        tables: &[Table],
        blob_files: &[crate::BlobFile],
        table_origin: crate::fs::WriteOrigin,
        blob_origin: crate::fs::WriteOrigin,
    ) -> crate::Result<()> {
        for table in tables {
            if let Some(stats) = table.fs.write_io_stats() {
                self.push(stats, table_origin, table.file_len());
            }
        }
        for blob_file in blob_files {
            if let Some(stats) = blob_file.0.fs.write_io_stats() {
                self.push(stats, blob_origin, blob_file.physical_size()?);
            }
        }
        Ok(())
    }

    fn push(
        &mut self,
        stats: &Arc<crate::fs::WriteIoStats>,
        origin: crate::fs::WriteOrigin,
        bytes: u64,
    ) {
        for (set, slot, sum) in &mut self.0 {
            if *slot == origin && Arc::ptr_eq(set, stats) {
                *sum += bytes;
                return;
            }
        }
        self.0.push((Arc::clone(stats), origin, bytes));
    }

    /// Records the bytes, once the install that keeps them is published.
    pub(crate) fn charge(self) {
        for (stats, origin, bytes) in self.0 {
            stats.installed(origin, bytes);
        }
    }
}

/// The highest seqno the memtables of `snapshot` hold, active and sealed.
fn highest_memtable_seqno(snapshot: &SuperVersion) -> Option<SeqNo> {
    let sealed = snapshot
        .sealed_memtables
        .iter()
        .map(|mt| mt.get_highest_seqno())
        .max()
        .flatten();
    snapshot.active_memtable.get_highest_seqno().max(sealed)
}

/// Extract owned user-key bounds from any range.
pub(crate) fn range_to_user_bounds<K: AsRef<[u8]>, R: RangeBounds<K>>(
    range: &R,
) -> (Bound<UserKey>, Bound<UserKey>) {
    use core::ops::Bound::{Excluded, Included, Unbounded};
    let lo = match range.start_bound() {
        Included(x) => Included(x.as_ref().into()),
        Excluded(x) => Excluded(x.as_ref().into()),
        Unbounded => Unbounded,
    };
    let hi = match range.end_bound() {
        Included(x) => Included(x.as_ref().into()),
        Excluded(x) => Excluded(x.as_ref().into()),
        Unbounded => Unbounded,
    };
    (lo, hi)
}

/// Wraps a [`SeekableTreeIter`](crate::range::SeekableTreeIter) so a standard
/// tree can expose it as a [`SeekableGuardIter`](crate::iter_guard::SeekableGuardIter).
struct StandardSeekable {
    inner: crate::range::SeekableTreeIter,
}

impl Iterator for StandardSeekable {
    type Item = IterGuardImpl;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().map(standard_guard)
    }
}

impl DoubleEndedIterator for StandardSeekable {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.inner.next_back().map(standard_guard)
    }
}

impl crate::iter_guard::SeekableGuardIter for StandardSeekable {
    fn seek_to(&mut self, key: &[u8]) {
        self.inner.seek_to(key);
    }

    fn seek_to_for_prev(&mut self, key: &[u8]) {
        self.inner.seek_to_for_prev(key);
    }

    fn peek_key(&mut self) -> Option<crate::Result<crate::UserKey>> {
        self.inner.peek_key()
    }
}

impl AbstractTree for Tree {
    fn table_file_cache_size(&self) -> usize {
        self.config
            .descriptor_table
            .as_ref()
            .map_or(0, |dt| dt.len())
    }

    fn get_version_history_lock(&self) -> VersionsWriteGuard<'_> {
        self.version_history.write()
    }

    fn persist_flushes(&self) -> crate::Result<()> {
        self.0.persist_flushes()
    }

    fn next_table_id(&self) -> TableId {
        self.0.table_id_counter.get()
    }

    fn id(&self) -> TreeId {
        self.id
    }

    fn blob_file_count(&self) -> usize {
        0
    }

    #[cfg(feature = "std")]
    fn create_checkpoint(
        &self,
        target_path: &crate::path::Path,
    ) -> crate::Result<crate::CheckpointInfo> {
        crate::checkpoint::run_checkpoint(
            self,
            &crate::checkpoint::CheckpointParams {
                target_root: target_path,
                target_fs: &self.config.fs,
                src_root: &self.config.path,
                src_fs: &self.config.fs,
                deletion_pause: &self.deletion_pause,
                visible_seqno: &self.config.visible_seqno,
                include_blobs: false,
                runtime_config: self.0.runtime_config.load_full(),
                encryption: self.0.config.encryption.clone(),
                source: &self.0,
            },
        )
    }

    #[cfg(feature = "std")]
    fn pin(&self) -> crate::PinnedVersion {
        crate::PinnedVersion::take(self)
    }

    #[cfg(feature = "std")]
    fn acknowledge_repair_report(&self, id: u128) -> crate::Result<bool> {
        Self::acknowledge_repair_report(self, id)
    }

    fn print_trace(&self, key: &[u8]) -> crate::Result<()> {
        let super_version = self.version_history.read().latest_version();

        let key = Slice::from(key);

        for kv in super_version.active_memtable.range_internal((
            Bound::Included(InternalKey::bound(
                key.clone(),
                SeqNo::MAX,
                ValueType::Value,
            )),
            Bound::Unbounded,
        )) {
            log::info!("[Active] {kv:?}");
        }

        for mt in super_version.sealed_memtables.iter().rev() {
            for kv in mt.range_internal((
                Bound::Included(InternalKey::bound(
                    key.clone(),
                    SeqNo::MAX,
                    ValueType::Value,
                )),
                Bound::Unbounded,
            )) {
                log::info!("[Sealed #{}] {kv:?}", mt.id());
            }
        }

        for table in super_version
            .version
            .iter_levels()
            .flat_map(|lvl| lvl.iter())
            .filter_map(|run| run.get_for_key_cmp(&key, self.config.comparator.as_ref()))
        {
            for kv in table.range(..) {
                let kv = kv?;

                if kv.key.user_key != key {
                    break;
                }

                log::info!("[Table #{}] {kv:?}", table.id());
            }
        }

        Ok(())
    }

    fn get_internal_entry(&self, key: &[u8], seqno: SeqNo) -> crate::Result<Option<InternalValue>> {
        let super_version = self.snapshot_for_read(seqno)?;
        // Counted where a caller asks, not in the lookup, which a read that
        // counts itself makes as well.
        super_version.version.read_mix().note_points(1);

        Self::get_internal_entry_from_version(
            &super_version,
            key,
            seqno,
            self.config.comparator.as_ref(),
        )
    }

    fn current_version(&self) -> Version {
        self.version_history
            .read()
            .latest_version_ref()
            .version
            .clone()
    }

    #[cfg(feature = "std")]
    fn refresh_table_checksum(
        &self,
        table_id: TableId,
        checksum: crate::checksum::Checksum,
        expected_restriction: Option<&crate::UserKey>,
    ) -> crate::Result<crate::abstract_tree::ChecksumRefreshOutcome> {
        use crate::abstract_tree::ChecksumRefreshOutcome;
        // Same lock order as flush / compaction version installs: compaction
        // state first, then the version history write lock. But the caller (the
        // patrol reconcile) holds this table's HEAL LOCK across this call, and a
        // concurrent tight-space compaction acquires that heal lock WHILE holding
        // `compaction_state`. Blocking on `compaction_state` here would invert the
        // order (heal_lock -> compaction_state on this path vs
        // compaction_state -> heal_lock on the compaction path) and deadlock
        // permanently. `try_lock` instead: a failed acquire means a compaction is
        // mid-install, so skip this refresh — but report the skip as CONTENDED,
        // not as a benign no-op: the healed bytes are durable while the manifest
        // digest stays stale, so a "clean" report would mislead a later
        // integrity check / checkpoint. The caller keeps the attestation and
        // surfaces a finding; the next patrol retries once the compaction
        // releases the state.
        let Some(mut _compaction_state) = self.compaction_state.try_lock() else {
            return Ok(ChecksumRefreshOutcome::Contended);
        };
        let mut version_lock = self.version_history.write();

        // Under the install lock, resolve the CURRENT view of this table and
        // reject the refresh if either it is gone (compacted away — nothing to
        // refresh) or its restriction no longer matches the one `checksum` was
        // computed for. A tight-space compaction can swap the captured view for a
        // restricted same-id view (punching its prefix) between the caller's read
        // and this lock; installing the caller's digest against a different
        // restriction would record one the punched file can never match. Skipping
        // leaves the current view's own (compaction-installed) digest in place for
        // the next patrol to reconcile.
        let restriction_matches = version_lock
            .latest_version_ref()
            .version
            .iter_tables()
            .find(|t| t.id() == table_id)
            .is_some_and(|t| t.restrict_lower_bound() == expected_restriction);
        if !restriction_matches {
            // No-op: the manifest digest is unchanged, so the caller must keep the
            // attestation for the next patrol.
            return Ok(ChecksumRefreshOutcome::Stale);
        }

        version_lock
            .upgrade_version(
                &self.config.path,
                |current| {
                    let mut copy = current.clone();
                    if let Some(next) = copy
                        .version
                        .with_refreshed_table_checksum(table_id, checksum)
                    {
                        copy.version = next;
                    }
                    Ok(copy)
                },
                &self.config.seqno,
                &self.config.visible_seqno,
                &*self.config.fs,
                self.0.runtime_config.load_full(),
                self.0.config.encryption.clone(),
                crate::version::RetentionEffect::Keep,
            )
            .map(|()| ChecksumRefreshOutcome::Refreshed)
    }

    fn sync_mode(&self) -> crate::fs::SyncMode {
        self.config.sync_mode
    }

    fn wait_for_table_file_refills(&self) {
        self.table_files.wait_for_refills();
    }

    fn prefix_extractor(&self) -> Option<alloc::sync::Arc<dyn crate::prefix::PrefixExtractor>> {
        self.config.prefix_extractor.clone()
    }

    fn storage_stats(&self) -> crate::Result<crate::StorageStats> {
        // One version snapshot reused for the footprint and the full-compaction
        // estimate below: a second `current_version()` could race a concurrent
        // flush / compaction and mix two snapshots.
        let version = self.current_version();
        // Standard tree: SST values ARE user values (no KV separation).
        let mut stats =
            crate::storage_stats::compute_storage_stats(&version, self.is_compacting(), true)?;
        // Fill the disk-aware capacity figures (quota + free-space probe) the
        // version-only computation can't know.
        let (capacity, available, compaction_possible) = self.admission_capacity(stats.used_bytes);
        stats.capacity_bytes = capacity;
        stats.available_bytes = available;
        stats.compaction_possible = compaction_possible;
        // When admission gating is active and a compaction is not already
        // running, surface whether a full compaction has working room through the
        // SAME two-layer check the compaction space gate enforces (logical quota +
        // physical free per destination volume), so the reported status matches
        // what the gate will admit. With gating off the gate never runs, so the
        // status stays `Healthy` even though the backend can report a finite
        // capacity.
        if self.storage_admission_enabled()
            && capacity.is_some()
            && stats.status == crate::StorageStatus::Healthy
        {
            // A full compaction's transient output is bounded by the largest
            // level's on-disk size, but it LANDS in the last configured level's
            // volume (`level_count - 1`), which under tiered routing can be a
            // different filesystem than the largest level. A standard tree has no
            // blob relocation. Using the per-volume gate (not `available >=
            // full_compaction_bytes` against the min-volume free) keeps the status
            // from reporting tight when a routed merge would actually be admitted.
            let sst_need = crate::storage_stats::full_compaction_demand_bytes(&version)?;
            // `saturating_sub`: `level_count >= 1` always, so this is the last
            // level index; the clamp only guards a degenerate zero-level config.
            let sst_dest_level = self.0.config.level_count.saturating_sub(1);
            let quota_headroom = self.quota_headroom(stats.used_bytes);
            let full_fits = crate::compaction::worker::merge_would_fit(
                &self.0.compaction_capacity,
                self.0.id,
                &self.0.config,
                quota_headroom,
                (sst_need, 0),
                sst_dest_level,
            );
            stats.status = if full_fits {
                crate::StorageStatus::FullCompactionAvailable
            } else {
                crate::StorageStatus::TightCompactionAvailable
            };
        }
        // A closed admission gate is the operator-actionable state, so it takes
        // precedence over the others (a read-only tree may well be compacting to
        // reclaim space).
        if self.is_read_only() {
            stats.status = crate::StorageStatus::ReadOnlyOutOfSpace;
        }
        Ok(stats)
    }

    fn write_admission(&self) -> crate::Result<()> {
        self.compute_write_admission()
    }

    fn write_backpressure(
        &self,
        strategy: &dyn crate::compaction::CompactionStrategy,
    ) -> crate::Backpressure {
        // Copy the thresholds out (BackpressureThresholds is Copy) so the
        // arc-swap guard drops immediately; the off check short-circuits before
        // touching the version, keeping the disabled path free.
        let thresholds = self.0.runtime_config.load().backpressure;
        if thresholds.is_off() {
            return crate::Backpressure::None;
        }
        let version = self.current_version();
        let signals = crate::BackpressureSignals {
            // L0's run count is what a read pays there and what the leveled
            // trigger counts.
            l0_runs: version.l0().run_count(),
            pending_compaction_bytes: strategy.pending_compaction_bytes(&version),
            // Summed over a shared budget's members, so read only when an
            // axis compares it.
            unflushed_memtable_bytes: if thresholds.memtable_slowdown.is_some()
                || thresholds.memtable_stop.is_some()
            {
                self.unflushed_memtable_bytes()
            } else {
                0
            },
        };
        crate::Backpressure::compute(&signals, &thresholds)
    }

    fn get_flush_lock(&self) -> FlushGuard<'_> {
        self.flush_lock.lock()
    }

    #[cfg(feature = "metrics")]
    fn metrics(&self) -> &Arc<crate::Metrics> {
        &self.0.metrics
    }

    #[cfg(feature = "metrics")]
    fn cache_stats(&self) -> crate::CacheStats {
        let cache = &self.0.config.cache;
        self.metrics().cache_stats(cache.size(), cache.capacity())
    }

    fn prefix<K: AsRef<[u8]>>(
        &self,
        prefix: K,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static> {
        match self.create_prefix(&prefix, seqno, index) {
            Ok(iter) => Box::new(iter.map(|kv| IterGuardImpl::Standard(Guard(kv)))),
            Err(e) => Box::new(core::iter::once(error_guard(e))),
        }
    }

    fn range<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        range: R,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static> {
        match self.create_range(&range, seqno, index) {
            Ok(iter) => Box::new(iter.map(|kv| IterGuardImpl::Standard(Guard(kv)))),
            Err(e) => Box::new(core::iter::once(error_guard(e))),
        }
    }

    fn range_seekable<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        range: R,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Box<dyn crate::iter_guard::SeekableGuardIter + 'static> {
        let (lo, hi) = range_to_user_bounds(&range);
        match self.create_seekable_range_bounds(lo, hi, seqno, index) {
            Ok(inner) => Box::new(StandardSeekable { inner }),
            Err(e) => Box::new(crate::iter_guard::FailedSeekable::new(e)),
        }
    }

    fn batch_range_scan<K: AsRef<[u8]>, R: RangeBounds<K> + 'static, I: IntoIterator<Item = R>>(
        &self,
        intervals: I,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> Box<dyn Iterator<Item = IterGuardImpl> + Send + 'static>
    where
        I::IntoIter: Send + 'static,
    {
        // Open the seekable iterator over the whole keyspace once; each interval
        // is served by repositioning it (single per-SST setup, amortized).
        let inner = match self.create_seekable_range_bounds(
            Bound::Unbounded,
            Bound::Unbounded,
            seqno,
            index,
        ) {
            Ok(inner) => inner,
            Err(e) => return Box::new(core::iter::once(error_guard(e))),
        };
        let intervals = intervals.into_iter().map(|r| range_to_user_bounds(&r));
        Box::new(crate::range::BatchRangeScan::new(inner, intervals).map(standard_guard))
    }

    /// Returns the number of tombstones in the tree.
    fn tombstone_count(&self) -> u64 {
        self.current_version()
            .iter_tables()
            .map(Table::tombstone_count)
            .sum()
    }

    /// Returns the number of weak tombstones (single deletes) in the tree.
    fn weak_tombstone_count(&self) -> u64 {
        self.current_version()
            .iter_tables()
            .map(Table::weak_tombstone_count)
            .sum()
    }

    /// Returns the number of value entries that become reclaimable once weak tombstones can be GC'd.
    fn weak_tombstone_reclaimable_count(&self) -> u64 {
        self.current_version()
            .iter_tables()
            .map(Table::weak_tombstone_reclaimable)
            .sum()
    }

    fn clear(&self) -> crate::Result<()> {
        let config = self.tree_config();
        let mut versions = self.get_version_history_lock();

        // Pre-clear snapshot: every table + blob file it references becomes
        // garbage the moment the new empty version is installed.
        let prior = versions.latest_version();

        #[cfg(zstd_any)]
        let still_written = self.write_referenced_dict_ids();
        #[cfg(not(zstd_any))]
        let still_written: Vec<crate::file::DictId> = Vec::new();

        versions.upgrade_version(
            &config.path,
            |v| {
                let mut copy = v.clone();
                copy.active_memtable = Arc::new(Memtable::new(
                    self.memtable_id_counter.next(),
                    self.config.comparator.clone(),
                ));
                copy.sealed_memtables = Arc::default();
                copy.version = v.version.cleared(&still_written);
                Ok(copy)
            },
            &config.seqno,
            &config.visible_seqno,
            &*config.fs,
            self.0.runtime_config.load_full(),
            self.0.config.encryption.clone(),
            // Every table goes: no snapshot up to this install is servable.
            crate::version::RetentionEffect::DropsData,
        )?;
        // `prior` still holds the replaced version, so nothing reaches refcount
        // zero yet.
        drop(versions); // release the version-history lock before any fs work

        // Mark every obsolete table / blob file deleted so the file is
        // reclaimed (Inner::Drop) once its last reference is released. A
        // concurrent reader still holding the pre-clear snapshot keeps its own
        // clone alive, deferring physical deletion until it finishes — the
        // version-history Arc refcount is the MVCC guard, so reclaim never
        // races a live read. Tables with no other live reference are reclaimed
        // as `prior` drops at the end of this call.
        for table in prior.version.iter_tables() {
            table.mark_as_deleted();
        }
        for blob_file in prior.version.blob_files.iter() {
            blob_file.mark_as_deleted();
        }

        Ok(())
    }

    #[doc(hidden)]
    fn major_compact(
        &self,
        target_size: u64,
        gc_watermark: SeqNo,
    ) -> crate::Result<crate::compaction::CompactionResult> {
        let strategy = Arc::new(crate::compaction::major::Strategy::new(target_size));

        // IMPORTANT: Write lock so we can be the only compaction going on
        let _lock = self.0.major_compaction_lock.write();

        log::info!("Starting major compaction");
        self.inner_compact(strategy, gc_watermark)
    }

    fn l0_run_count(&self) -> usize {
        self.current_version()
            .level(0)
            .map(|x| x.run_count())
            .unwrap_or_default()
    }

    fn size_of<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> crate::Result<Option<u32>> {
        #[expect(clippy::cast_possible_truncation, reason = "values are u32 length max")]
        Ok(self.get(key, seqno)?.map(|x| x.len() as u32))
    }

    fn filter_size(&self) -> u64 {
        self.current_version()
            .iter_tables()
            .map(Table::filter_size)
            .map(u64::from)
            .sum()
    }

    fn pinned_filter_size(&self) -> usize {
        self.current_version()
            .iter_tables()
            .map(Table::pinned_filter_size)
            .sum()
    }

    fn filter_memory(&self) -> crate::FilterMemory {
        let version = self.current_version();
        let serialised_bytes = version
            .iter_tables()
            .map(|table| u64::from(table.filter_size()))
            .sum();
        let budget_bytes = self
            .config
            .filter_advisor
            .as_ref()
            .map(crate::config::FilterAdvisor::budget_bytes);
        crate::FilterMemory {
            serialised_bytes,
            resident_bytes: version
                .iter_tables()
                .map(Table::resident_filter_bytes)
                .sum(),
            budget_bytes,
            over_budget: budget_bytes.is_some_and(|budget| serialised_bytes > budget),
        }
    }

    fn pinned_block_index_size(&self) -> usize {
        self.current_version()
            .iter_tables()
            .map(Table::pinned_block_index_size)
            .sum()
    }

    fn sealed_memtable_count(&self) -> usize {
        self.version_history
            .read()
            .latest_version()
            .sealed_memtables
            .len()
    }

    fn flush_to_tables_with_rt(
        &self,
        stream: impl Iterator<Item = crate::Result<InternalValue>>,
        range_tombstones: Vec<crate::range_tombstone::RangeTombstone>,
        keys: u64,
        hashes: u64,
        // A standard tree separates no values, so it has nothing to place.
        _overwritten: Option<&crate::blob_tree::overwritten::OverwrittenKeys>,
    ) -> crate::Result<
        Option<(
            Vec<Table>,
            Option<Vec<BlobFile>>,
            crate::runtime_config::WritePin,
        )>,
    > {
        use crate::table::multi_writer::MultiWriter;
        use crate::time::Instant;

        let start = Instant::now();

        let (folder, level_fs) = self.config.tables_folder_for_level(0);

        let data_block_size = self.config.data_block_size_policy.get(0);

        let data_block_restart_interval = self.config.data_block_restart_interval_policy.get(0);
        let index_block_restart_interval = self.config.index_block_restart_interval_policy.get(0);

        // One runtime-config snapshot for the whole flush writer setup. The
        // compression policies, the index spill threshold, `seqno_in_index`,
        // and the per-KV checksum policy are all live (toggleable via
        // `update_runtime_config`); reading `load_full()` per field could
        // straddle a concurrent update and mix two snapshots into one SST.
        // Compaction is the migration mechanism, so a toggle takes effect on
        // the next flush / compaction.
        let rc = self.0.runtime_config.load_full();

        let data_block_compression = rc.data_block_compression_policy.get(0);
        let index_block_compression = rc.index_block_compression_policy.get(0);

        let data_block_hash_ratio = self.config.data_block_hash_ratio_policy.get(0);

        let index_partitioning = self.config.index_block_partitioning_policy.get(0);
        let filter_partitioning = self.config.filter_block_partitioning_policy.get(0);

        log::debug!(
            "Flushing memtable(s) to {}, data_block_restart_interval={data_block_restart_interval}, index_block_restart_interval={index_block_restart_interval}, data_block_size={data_block_size}, data_block_compression={data_block_compression:?}, index_block_compression={index_block_compression:?}",
            folder.display(),
        );

        let table_writer = MultiWriter::from_pool(
            folder.clone(),
            Arc::clone(&self.table_files),
            None,
            self.config.table_target_size,
            0,
            level_fs.clone(),
            crate::fs::WriteOrigin::FlushTable,
        )?;
        // The flush's L0 recency, taken once its first file is: flushes are
        // serialized, so it is above every table already flushed and below
        // every one flushed later. A pooled file's id was taken when its batch
        // was made and says nothing about when the table was written; a file
        // made now carries an id taken now, which serves.
        let recency = table_writer
            .first_made_now()
            .unwrap_or_else(|| self.table_id_counter.next());
        let mut table_writer = table_writer
            .set_comparator(self.config.comparator.clone())
            .use_recency(Some(recency))
            .use_data_block_restart_interval(data_block_restart_interval)
            .use_index_block_restart_interval(index_block_restart_interval)
            .use_data_block_compression(data_block_compression)
            .use_index_block_compression(index_block_compression)
            .use_data_block_size(data_block_size)
            .use_index_partition_size(self.config.index_block_partition_size_policy.get(0))
            .use_filter_partition_size(self.config.filter_block_partition_size_policy.get(0))
            .use_row_group_size(self.config.columnar_row_group_size_policy.get(0))
            .use_columnar_page_size(self.config.columnar_page_size_policy.get(0))
            .use_column_encoding(self.config.column_encoding_policy.get(0))
            .use_data_block_hash_ratio(data_block_hash_ratio);

        let bloom_policy = {
            use crate::config::FilterPolicyEntry::{Bloom, None};
            use crate::table::filter::BloomConstructionPolicy;

            match self.config.filter_policy.get(0) {
                Bloom(policy) => policy,
                None => BloomConstructionPolicy::BitsPerKey(0.0),
            }
        };
        table_writer = table_writer.use_bloom_policy(bloom_policy);
        let filter_sizing = self.new_data_filter_sizing(
            0,
            bloom_policy,
            crate::filter_budget::FilterCount { keys, hashes },
            rc.ecc_scheme,
        );
        table_writer = table_writer.use_filter_sizing(filter_sizing.clone());

        if index_partitioning {
            // Size-adaptive: single-level index for small SSTs (where pinning
            // the whole index is cheap and a two-level lookup is pure overhead),
            // spilling to a partitioned index only once the index grows past the
            // threshold. Recovers the point-read cost of an unconditional
            // two-level index on small/medium SSTs.
            table_writer = table_writer.use_adaptive_index(rc.index_partition_spill_threshold);
        }
        if filter_partitioning {
            table_writer = table_writer.use_partitioned_filter();
        }

        table_writer = table_writer.use_prefix_extractor(self.config.prefix_extractor.clone());
        table_writer = table_writer.use_key_domains(self.config.key_domains.clone());
        table_writer = table_writer.use_encryption(self.config.encryption.clone());
        table_writer = table_writer.use_clock(self.config.clock.clone());
        // ECC scheme from the live runtime snapshot (same as `seqno_in_index`
        // / `kv_checksums` below), so a flush after a scheme change writes the
        // SST with the current scheme rather than the startup one.
        table_writer = table_writer.use_page_ecc(self.config.page_ecc, rc.ecc_scheme);
        table_writer = table_writer
            .use_sync_mode(self.config.sync_mode)
            .use_durability(self.config.flush_durability)
            .use_writeback_bytes(self.config.writeback_bytes);

        table_writer = table_writer.use_seqno_in_index(rc.seqno_in_index);
        table_writer = table_writer.use_zone_map(rc.zone_map);
        table_writer = table_writer.use_columnar(rc.columnar);
        table_writer = table_writer.use_disable_cow_on_sst(rc.disable_cow_on_sst_files);
        // `Off` (default) emits no per-KV footer and leaves the data-block
        // payload encoding unchanged (the V5 header carries a block_flags byte
        // and the meta block a descriptor key regardless, so the on-disk bytes
        // are not identical to a pre-V5 table).
        table_writer = table_writer.use_kv_checksums(rc.kv_checksums, rc.kv_checksum_algo);
        // Flush writes level 0; resolve that level's locator policy entry.
        table_writer = table_writer.use_locator(self.config.locator_policy.get(0));

        // The dictionary THIS snapshot's policy names. The flush holds the
        // snapshot until its tables are installed: a collection spares what a
        // held snapshot names, however the policy has changed since.
        #[cfg(zstd_any)]
        {
            table_writer = table_writer
                .use_zstd_dictionary(
                    self.config
                        .current_zstd_dictionaries()
                        .for_compression(data_block_compression)?,
                )
                .use_zstd_two_pass_seed(rc.zstd_two_pass_seed);
        }
        let write_pin = crate::runtime_config::WritePin::new(&rc).with_filter_sizing(filter_sizing);

        // Parallel block compression for the flush writer, on the same pool the
        // compaction writers use. Engaged only when the per-block transform does
        // real CPU work (a codec, encryption, or page ECC): with the identity
        // transform the pipeline's owned buffer + queue hop per block buys
        // nothing over the serial reusable-buffer path. Safe wherever the host
        // runs this flush — even on a thread of an injected pool — because the
        // pipeline's help-first drain executes queued jobs inline instead of
        // waiting on a saturated pool (see `parallel_compressor`).
        #[cfg(feature = "std")]
        {
            let transform_does_work = data_block_compression != crate::CompressionType::None
                || self.config.encryption.is_some()
                || self.config.page_ecc;
            if transform_does_work {
                table_writer =
                    table_writer.use_parallel_compression(self.config.parallel_compression());
            }
        }

        // Set range tombstones BEFORE writing KV items so that if MultiWriter
        // rotates to a new table during the write loop, earlier tables already
        // carry the RT metadata.
        table_writer.set_range_tombstones(range_tombstones);

        for item in stream {
            table_writer.write(item?)?;
        }

        let written = table_writer.finish()?;
        let entries_durable = written.entries_durable;

        log::debug!("Flushed memtable(s) in {:?}", start.elapsed());

        let pin_filter = self.config.filter_block_pinning_policy.get(0);
        let pin_index = self.config.index_block_pinning_policy.get(0);

        // Load tables
        let tables = written
            .tables
            .into_iter()
            .map(|(table_id, checksum)| -> crate::Result<Table> {
                let mut params = crate::table::RecoverParams::new(
                    folder.join(table_id.to_string()),
                    checksum,
                    table_id,
                    level_fs.clone(),
                    self.config.comparator.clone(),
                    self.config.cache.clone(),
                );
                params.tree_id = self.id;
                params
                    .descriptor_table
                    .clone_from(&self.config.descriptor_table);
                params.pin_filter = pin_filter;
                params.pin_index = pin_index;
                params.encryption.clone_from(&self.config.encryption);
                params
                    .prefix_extractor
                    .clone_from(&self.config.prefix_extractor);
                #[cfg(zstd_any)]
                {
                    params.zstd_dictionaries = self.config.current_zstd_dictionaries();
                }
                #[cfg(feature = "metrics")]
                {
                    params.metrics = self.metrics.clone();
                }
                let table = Table::recover(params)?;
                if entries_durable {
                    table.mark_entry_durable();
                }
                Ok(table)
            })
            .collect::<crate::Result<Vec<_>>>()?;

        // Return Some even when tables is empty (RT-only flush): the caller
        // (AbstractTree::flush) handles empty tables by re-inserting RTs into
        // the active memtable and still needs to delete sealed memtables.
        Ok(Some((tables, None, write_pin)))
    }

    #[expect(clippy::significant_drop_tightening)]
    fn register_tables(
        &self,
        tables: &[Table],
        blob_files: Option<&[BlobFile]>,
        frag_map: Option<crate::blob_tree::FragmentationMap>,
        sealed_memtables_to_delete: &[crate::tree::inner::MemtableId],
        gc_watermark: SeqNo,
        collected_below_watermark: bool,
    ) -> crate::Result<()> {
        log::trace!(
            "Registering {} tables, {} blob files",
            tables.len(),
            blob_files.map(<[BlobFile]>::len).unwrap_or_default(),
        );

        // Wire the tree-wide deletion pause into every fresh table / blob
        // file so an in-flight checkpoint defers their cleanup if they
        // later get marked `is_deleted` by compaction.
        let sinks = crate::table::TableSinks {
            deletion_pause: &self.deletion_pause,
            heal_hints: &self.heal_hints,
            read_budget: self.config.columnar_read_budget,
            #[cfg(feature = "std")]
            background_deleter: &self.background_deleter,
            track_filter_probes: self.config.filter_advisor.is_some(),
        };
        for table in tables {
            table.bind_to_tree(&sinks);
        }
        for bf in blob_files.unwrap_or(&[]) {
            bf.bind_to_tree(&sinks);
        }

        let mut installed = InstalledCharge::default();
        installed.add(
            tables,
            blob_files.unwrap_or(&[]),
            crate::fs::WriteOrigin::FlushTable,
            crate::fs::WriteOrigin::FlushBlob,
        )?;

        let mut _compaction_state = self.compaction_state.lock();
        let mut version_lock = self.version_history.write();

        // A sealed memtable that left the version while it was flushed was
        // removed with its data (a `clear`): the tables written from it hold
        // that data, and are dropped rather than installed.
        let sealed = &version_lock.latest_version_ref().sealed_memtables;
        if !sealed_memtables_to_delete
            .iter()
            .all(|&id| sealed.iter().any(|mt| mt.id() == id))
        {
            log::warn!(
                "Flushed memtables left the version before the install, declining the flush"
            );
            drop(version_lock);
            for table in tables {
                table.mark_as_deleted();
            }
            for blob_file in blob_files.unwrap_or(&[]) {
                blob_file.mark_as_deleted();
            }
            return Ok(());
        }

        // A deferred flush wrote its files unsynced: installed in memory only,
        // they are synced and written to the manifest by the next persist.
        let deferred = (self.config.flush_durability == crate::config::FlushDurability::Deferred)
            .then(|| {
                tables
                    .iter()
                    .cloned()
                    .map(crate::version::UnsyncedFile::Table)
                    .chain(
                        blob_files
                            .unwrap_or(&[])
                            .iter()
                            .cloned()
                            .map(crate::version::UnsyncedFile::Blob),
                    )
                    .collect()
            });
        version_lock.upgrade_version_deferring(
            &self.config.path,
            |current| {
                let mut copy = current.clone();

                let ctx = crate::version::TransformContext::new(self.config.comparator.as_ref());
                copy.version = copy.version.with_new_l0_run(
                    tables,
                    blob_files,
                    frag_map.filter(|x| !x.is_empty()),
                    &ctx,
                );

                for &table_id in sealed_memtables_to_delete {
                    log::trace!("releasing sealed memtable #{table_id}");
                    copy.sealed_memtables = Arc::new(copy.sealed_memtables.remove(table_id));
                }

                Ok(copy)
            },
            &self.config.seqno,
            &self.config.visible_seqno,
            &*self.config.fs,
            self.0.runtime_config.load_full(),
            self.0.config.encryption.clone(),
            // A flush adds a run, but it does not only add: `AbstractTree::flush`
            // feeds the sealed memtables through the same `CompactionStream`
            // with this same watermark, so it collects the versions below it
            // exactly as a compaction does, and owes older snapshots the same
            // accounting. Same rule, evaluated in the same place, because a
            // flush and a compaction disagreeing about it is how a floor came
            // to promise data the output no longer held.
            //
            // `false` for the filter: the flush stream carries no user
            // compaction filter, so `DropsData` is unreachable here.
            crate::version::RetentionEffect::of_run(false, collected_below_watermark, gc_watermark),
            deferred,
        )?;
        installed.charge();

        Ok(())
    }

    fn clear_active_memtable(&self) {
        use crate::tree::sealed::SealedMemtables;

        let mut version_history_lock = self.version_history.write();
        let super_version = version_history_lock.latest_version();

        if super_version.active_memtable.is_empty() {
            return;
        }

        let mut copy = version_history_lock.latest_version();
        copy.active_memtable = Arc::new(Memtable::new(
            self.memtable_id_counter.next(),
            self.config.comparator.clone(),
        ));
        copy.sealed_memtables = Arc::new(SealedMemtables::default());

        // Rotate does not modify the memtable, so it cannot break snapshots
        copy.seqno = super_version.seqno;

        version_history_lock.replace_latest_version(copy);

        log::trace!("cleared active memtable");
    }

    fn compact(
        &self,
        strategy: Arc<dyn CompactionStrategy>,
        gc_watermark: SeqNo,
    ) -> crate::Result<crate::compaction::CompactionResult> {
        // NOTE: Read lock major compaction lock
        // That way, if a major compaction is running, we cannot proceed
        // But in general, parallel (non-major) compactions can occur
        let _lock = self.0.major_compaction_lock.read();

        self.inner_compact(strategy, gc_watermark)
    }

    fn get_next_table_id(&self) -> TableId {
        self.0.get_next_table_id()
    }

    fn tree_config(&self) -> &Config {
        &self.config
    }

    fn active_memtable(&self) -> Arc<Memtable> {
        self.version_history
            .read()
            .latest_version_ref()
            .active_memtable
            .clone()
    }

    fn rotate_memtable(&self) -> Option<Arc<Memtable>> {
        self.rotate_memtable_locked(&mut self.version_history.write())
    }

    fn table_count(&self) -> usize {
        self.current_version().table_count()
    }

    fn level_table_count(&self, idx: usize) -> Option<usize> {
        self.current_version().level(idx).map(|x| x.table_count())
    }

    fn approximate_len(&self) -> usize {
        let super_version = self.version_history.read().latest_version();

        let tables_item_count = self
            .current_version()
            .iter_tables()
            .map(|x| x.metadata.item_count)
            .sum::<u64>();

        let memtable_count = super_version.active_memtable.len() as u64;
        let sealed_count = super_version
            .sealed_memtables
            .iter()
            .map(|mt| mt.len())
            .sum::<usize>() as u64;

        #[expect(clippy::expect_used, reason = "result should fit into usize")]
        (memtable_count + sealed_count + tables_item_count)
            .try_into()
            .expect("approximate_len too large for usize")
    }

    fn disk_space(&self) -> u64 {
        self.current_version()
            .iter_levels()
            .map(super::version::Level::size)
            .sum()
    }

    fn approximate_range_stats<K: AsRef<[u8]>, R: core::ops::RangeBounds<K>>(
        &self,
        range: R,
        seqno: SeqNo,
    ) -> crate::Result<crate::ApproximateRangeStats> {
        use core::ops::Bound;

        // A query planner asks for this estimate as part of the query it
        // plans, so the index walks below are the query's reads and stay
        // counted. A monitoring report's reads are the ones kept out of the
        // counters (see `Table::live_item_count`).
        let lo: Bound<&[u8]> = match range.start_bound() {
            Bound::Included(k) => Bound::Included(k.as_ref()),
            Bound::Excluded(k) => Bound::Excluded(k.as_ref()),
            Bound::Unbounded => Bound::Unbounded,
        };
        let hi: Bound<&[u8]> = match range.end_bound() {
            Bound::Included(k) => Bound::Included(k.as_ref()),
            Bound::Excluded(k) => Bound::Excluded(k.as_ref()),
            Bound::Unbounded => Bound::Unbounded,
        };
        let bounds = (lo, hi);

        let mut bytes: u64 = 0;
        let mut key_count: u64 = 0;

        // Use ONE snapshot at the requested seqno for both the SST and memtable
        // contributions, so the estimate is taken against a read's view at
        // `seqno`: one consistent TABLE set even during a concurrent flush or
        // compaction, and memtable entries filtered by the snapshot. Neither
        // half is exact, and the two paragraphs below say how.
        //
        // What "the same visibility as a read" does and does not mean here.
        //
        // It uses the FILE SET a read at `seqno` resolves to, which is the
        // current one for every snapshot above the floor, and filters the
        // memtables by `seqno`. It is not a per-row mask: a table whose seqno
        // range straddles `seqno` is classified `Partial` and then apportioned
        // whole by byte offsets, so its share can include rows the snapshot
        // cannot read. The estimate is an estimate, and this is one of the ways
        // it is approximate.
        //
        // Nor does resolving once freeze the tree. The clone pins the version's
        // tables, but the active memtable behind it is the live one every
        // writer mutates, so a write landing mid-call can be counted by the
        // memtable half after the table half was read. And a compaction
        // installing after the clone is what the NEXT read at that seqno
        // resolves to: the layout described here is one compaction is free to
        // change the moment this returns.
        let comparator = self.config.comparator.as_ref();
        let super_version = self.get_version_for_snapshot(seqno)?;

        // SST contribution: interpolate data-block offsets at the boundaries
        // (block granularity), no data-block reads. For a KV-separated SST the
        // referenced blob bytes are apportioned by the same in-range fraction.
        for table in super_version.version.iter_tables() {
            // Comparator-aware overlap: a custom user comparator orders keys
            // differently from raw bytes, so use the same comparison the read
            // path does instead of default byte ordering.
            if !table
                .metadata
                .key_range
                .overlaps_with_bounds_cmp(&bounds, comparator)
            {
                continue;
            }
            // The block index is keyed by the table-LOCAL seqno; a bulk-ingested
            // table carries a non-zero global seqno, so translate the snapshot
            // seqno the same way the read path does before seeking it. A snapshot
            // below the table's base means the table postdates it and contributes
            // nothing to the estimate, so skip it (`checked_sub` yields `None`).
            let Some(table_seqno) = seqno.checked_sub(table.global_seqno()) else {
                continue;
            };
            // The translation alone is not the visibility rule: a table with
            // `global_seqno == 0` passes it whatever its entries hold, so one
            // holding nothing but seqno 100 would charge rows and bytes to a
            // query at seqno 50 that reads none of them. Ask the same
            // classification the read path uses.
            if table.seqno_visibility(seqno) == crate::table::SeqnoVisibility::None {
                continue;
            }

            // A restricted view's punched-out prefix is served by its
            // replacement table, so the span starts past it and the prefix is
            // not double-counted (matching how scans skip it).
            let Some(span) = table.data_span(bounds, table_seqno, crate::table::SpanEdge::Whole)?
            else {
                continue;
            };
            let (idx_bytes, data_end) = (span.covered, span.data_end);
            if idx_bytes == 0 {
                continue;
            }

            // fraction = idx_bytes / data_end, in u128 to avoid overflow. For a
            // standard tree `idx_bytes` already includes the inline values. For a
            // KV-separated SST it covers only the key + pointer bytes, so the
            // SST's referenced blob bytes (recorded per-SST at both flush and
            // compaction) are apportioned by the same in-range fraction; blob
            // files are not key-indexed, so this fraction is the finest estimate
            // possible without reading data blocks.
            let num = u128::from(idx_bytes);
            let den = u128::from(data_end);
            let blob_bytes = table.referenced_blob_bytes()?;
            // `num <= den` (both offsets are bounded by `data_end`), so
            // `x * num / den <= x` and the u128 -> u64 narrowing is total —
            // no fallback value to mask a range error with.
            #[expect(
                clippy::cast_possible_truncation,
                reason = "num <= den, so the quotient never exceeds the u64 input"
            )]
            let sst_blob = (u128::from(blob_bytes) * num / den) as u64;
            // Round up to at least one entry: a non-empty byte span over a
            // non-empty SST always covers at least one row, so a narrow range
            // never reports bytes with a zero key count.
            #[expect(
                clippy::cast_possible_truncation,
                reason = "num <= den, so the quotient never exceeds the u64 input"
            )]
            let in_range_entries =
                ((u128::from(table.metadata.item_count) * num / den) as u64).max(1);
            bytes = bytes.saturating_add(idx_bytes).saturating_add(sst_blob);
            key_count = key_count.saturating_add(in_range_entries);
        }

        // Memtable contribution: the in-range fraction of each memtable's
        // approximate size. Built from the SAME snapshot and the SAME
        // `range_internal` + internal-key bounds the read path uses (range.rs),
        // so the counted slice matches what a read at `seqno` would traverse.
        let mt_range =
            crate::range::internal_bounds(&lo.map(UserKey::from), &hi.map(UserKey::from));
        let estimate = |mt: &crate::Memtable| -> (u64, u64) {
            let total = mt.len() as u64;
            if total == 0 {
                return (0, 0);
            }
            // Count only entries visible at the snapshot (the same seqno cutoff
            // reads apply), so the estimate excludes writes newer than `seqno`.
            let count = mt
                .range_internal(mt_range.clone())
                .filter(|kv| kv.key.seqno < seqno)
                .count() as u64;
            if count == 0 {
                return (0, 0);
            }
            // `count <= total` (the counted entries are a filtered subset of
            // the memtable), so the quotient never exceeds the u64 `size()`
            // and the narrowing is total.
            #[expect(
                clippy::cast_possible_truncation,
                reason = "count <= total, so the quotient never exceeds the u64 input"
            )]
            let mt_bytes = (u128::from(mt.size()) * u128::from(count) / u128::from(total)) as u64;
            (mt_bytes, count)
        };
        let (b, c) = estimate(&super_version.active_memtable);
        bytes = bytes.saturating_add(b);
        key_count = key_count.saturating_add(c);
        for mt in super_version.sealed_memtables.iter() {
            let (b, c) = estimate(mt);
            bytes = bytes.saturating_add(b);
            key_count = key_count.saturating_add(c);
        }

        Ok(crate::ApproximateRangeStats { bytes, key_count })
    }

    fn approximate_range_cardinality<K: AsRef<[u8]>, R: core::ops::RangeBounds<K>>(
        &self,
        range: R,
        seqno: SeqNo,
    ) -> crate::Result<crate::RangeCardinality> {
        use crate::table::block_index::BlockIndex;
        use core::cmp::Ordering;
        use core::ops::Bound;

        let lo: Bound<&[u8]> = match range.start_bound() {
            Bound::Included(k) => Bound::Included(k.as_ref()),
            Bound::Excluded(k) => Bound::Excluded(k.as_ref()),
            Bound::Unbounded => Bound::Unbounded,
        };
        let hi: Bound<&[u8]> = match range.end_bound() {
            Bound::Included(k) => Bound::Included(k.as_ref()),
            Bound::Excluded(k) => Bound::Excluded(k.as_ref()),
            Bound::Unbounded => Bound::Unbounded,
        };
        let bounds = (lo, hi);
        let comparator = self.config.comparator.as_ref();
        let super_version = self.get_version_for_snapshot(seqno)?;

        let mut rows: u64 = 0;
        let mut total_rows: u64 = 0;

        for table in super_version.version.iter_tables() {
            // Snapshot visibility is settled BEFORE the denominator grows. A
            // table no read at `seqno` can see is not part of the dataset the
            // selectivity describes, and counting it there while excluding it
            // from `rows` reports a full-keyspace query as selecting half the
            // tree. Out-of-RANGE tables do belong in the denominator, which is
            // why that check stays below it.
            //
            // A snapshot below the table's base means the table postdates it
            // (`checked_sub` yields `None`).
            let Some(table_seqno) = seqno.checked_sub(table.global_seqno()) else {
                continue;
            };
            // Wholly above the snapshot: invisible to a read at `seqno`, so it
            // contributes nothing here either (mirrors approximate_range_stats).
            if table.seqno_visibility(seqno) == crate::table::SeqnoVisibility::None {
                continue;
            }
            // What this VIEW serves, not what the file holds: a tight-space
            // restricted table's metadata still counts the punched-out prefix
            // its replacement now owns, while the numerator below starts at the
            // restriction — so charging the prefix here would report a
            // full-keyspace query as selecting a fraction of the tree.
            // The planner's estimate is part of the query it plans, so the
            // reads it makes are the query's and are counted, like the index
            // walks below.
            total_rows = total_rows
                .saturating_add(table.live_item_count(crate::table::util::ReadCharge::Foreground)?);
            if !table
                .metadata
                .key_range
                .overlaps_with_bounds_cmp(&bounds, comparator)
            {
                continue;
            }
            // Honor a tight-space restricted view: keys below
            // `restrict_lower_bound()` are the punched-out prefix served by the
            // replacement table, so raise this table's effective lower bound to
            // it (mirrors approximate_range_stats) and never charge that prefix.
            let eff_lo = effective_lower_bound(
                lo,
                table.restrict_lower_bound().map(AsRef::as_ref),
                comparator,
            );
            let zone_map = &table.zone_map;
            // A COLUMNAR block's per-column bounds are recorded in BYTE order,
            // which is the only ordering a value column has. Comparing them
            // with a non-lexicographic user comparator reads the recorded
            // minimum as a comparator maximum, so the walk stops before blocks
            // that overlap the query: the shortcut is skipped for such trees
            // and the byte-fraction estimate below answers instead. A row
            // block's bounds are the block's first and last key, already in
            // comparator order, so the default path is unaffected.
            let zone_bounds_ordered = comparator.is_lexicographic() || !table.metadata.columnar;
            if !zone_map.is_empty() && zone_bounds_ordered {
                // Zone map present: sum the per-block row counts of blocks whose
                // key range overlaps the query. A block is past the range once its
                // minimum key is above the upper bound; the boundary block at the
                // effective lower bound is counted in full (block granularity). A
                // range that lands in a key-space gap legitimately yields zero, so
                // this path is authoritative and never falls back to the byte fraction.
                let reader = match eff_lo {
                    Bound::Included(k) | Bound::Excluded(k) => {
                        table.block_index.forward_reader(k, table_seqno)
                    }
                    Bound::Unbounded => Some(table.block_index.iter()),
                };
                if let Some(reader) = reader {
                    for handle in reader {
                        let handle = handle?;
                        let Some(col) = zone_map
                            .columns_for(*handle.offset())
                            .and_then(|c| c.first())
                        else {
                            continue;
                        };
                        let above_hi = match hi {
                            Bound::Included(hk) => {
                                comparator.compare(&col.min, hk) == Ordering::Greater
                            }
                            Bound::Excluded(hk) => {
                                comparator.compare(&col.min, hk) != Ordering::Less
                            }
                            Bound::Unbounded => false,
                        };
                        if above_hi {
                            break;
                        }
                        rows = rows.saturating_add(u64::from(col.row_count));
                    }
                }
            } else if let Some(last) = table.block_index.iter().next_back() {
                // No zone map: apportion item_count by the in-range
                // data-block byte fraction, mirroring approximate_range_stats.
                let last = last?;
                let data_end = *last.offset() + u64::from(last.size());
                if data_end > 0 {
                    let off = |key: &[u8], end: bool| -> crate::Result<u64> {
                        match table.block_index.forward_reader(key, table_seqno) {
                            Some(mut it) => match it.next() {
                                Some(h) => {
                                    let h = h?;
                                    Ok(if end {
                                        (*h.offset() + u64::from(h.size())).min(data_end)
                                    } else {
                                        *h.offset()
                                    })
                                }
                                None => Ok(data_end),
                            },
                            None => Ok(data_end),
                        }
                    };
                    let off_lo = match eff_lo {
                        Bound::Included(k) | Bound::Excluded(k) => off(k, false)?,
                        Bound::Unbounded => 0,
                    };
                    let off_hi = match hi {
                        Bound::Included(k) | Bound::Excluded(k) => off(k, true)?,
                        Bound::Unbounded => data_end,
                    };
                    let idx_bytes = off_hi.saturating_sub(off_lo);
                    if idx_bytes > 0 {
                        // `idx_bytes <= data_end` (both offsets are bounded by
                        // `data_end`), so the quotient never exceeds the u64
                        // `item_count` and the narrowing is total.
                        #[expect(
                            clippy::cast_possible_truncation,
                            reason = "idx_bytes <= data_end, so the quotient never exceeds the u64 input"
                        )]
                        let est = ((u128::from(table.metadata.item_count) * u128::from(idx_bytes)
                            / u128::from(data_end)) as u64)
                            .max(1);
                        rows = rows.saturating_add(est);
                    }
                }
            }
        }

        // Memtables: count the in-range, snapshot-visible entries and add them to
        // both the matched rows and the total (matching the SST accounting).
        let mt_range =
            crate::range::internal_bounds(&lo.map(UserKey::from), &hi.map(UserKey::from));
        let mut add_memtable = |mt: &crate::Memtable| {
            // The denominator counts what a read at this snapshot can SEE, the
            // same rule the SST loop applies: an entry at or above `seqno` is
            // filtered out of the numerator below, so counting it here would
            // report a full-keyspace query as selecting half of what it sees.
            let visible = mt.iter().filter(|kv| kv.key.seqno < seqno).count() as u64;
            total_rows = total_rows.saturating_add(visible);
            let in_range = mt
                .range_internal(mt_range.clone())
                .filter(|kv| kv.key.seqno < seqno)
                .count() as u64;
            rows = rows.saturating_add(in_range);
        };
        add_memtable(&super_version.active_memtable);
        for mt in super_version.sealed_memtables.iter() {
            add_memtable(mt);
        }

        // selectivity is an approximate ratio; u64 row counts are well within
        // f64's exact-integer range (2^52) for any realistic table.
        #[expect(
            clippy::cast_precision_loss,
            reason = "row counts never approach 2^52; the ratio is approximate anyway"
        )]
        let selectivity = if total_rows == 0 {
            0.0
        } else {
            (rows.min(total_rows) as f64) / (total_rows as f64)
        };
        Ok(crate::RangeCardinality { rows, selectivity })
    }

    fn get_highest_memtable_seqno(&self) -> Option<SeqNo> {
        highest_memtable_seqno(&self.version_history.read().latest_version())
    }

    fn get_highest_seqno(&self) -> Option<SeqNo> {
        // One snapshot for the tables and the memtables: a flush installed
        // between two reads would leave its writes in neither. Its current
        // version, not the one on disk: a deferred flush moves its writes out
        // of the memtable before any persist names them.
        let snapshot = self.version_history.read().latest_version();
        let tables = snapshot
            .version
            .iter_tables()
            .map(Table::get_highest_seqno)
            .max();
        highest_memtable_seqno(&snapshot).max(tables)
    }

    fn get_highest_persisted_seqno(&self) -> Option<SeqNo> {
        // The version on disk, not the current one: a deferred flush is not
        // persisted until a persist writes it, and a caller trimming its log
        // by this seqno must keep what such a flush holds.
        self.version_history
            .read()
            .persisted_version()
            .iter_tables()
            .map(Table::get_highest_seqno)
            .max()
    }

    fn oldest_retained_seqno(&self) -> SeqNo {
        // The read boundary is the persisted floor, live and after a reopen.
        self.retention_floor()
    }

    fn retention_floor(&self) -> SeqNo {
        self.version_history
            .read()
            .latest_version_ref()
            .version
            .retention_floor()
    }

    fn lower_retention_floor(&self, floor: SeqNo) -> crate::Result<()> {
        let config = self.tree_config();
        let mut versions = self.get_version_history_lock();
        // Checked under the lock the install takes, so no install raising the
        // floor can land between the check and the edit.
        let current = versions.latest_version_ref().version.retention_floor();
        if floor > current {
            return Err(crate::Error::RetentionFloorRaise {
                current,
                requested: floor,
            });
        }
        if floor == current {
            return Ok(());
        }
        // A counter reset on reopen can stand below the current floor.
        let seqno = config.seqno.get();
        if floor > seqno {
            return Err(crate::Error::RetentionFloorAboveSeqno {
                seqno,
                requested: floor,
            });
        }
        versions.upgrade_version(
            &config.path,
            |v| {
                let mut copy = v.clone();
                copy.version = v.version.with_lowered_retention_floor(floor);
                Ok(copy)
            },
            &config.seqno,
            &config.visible_seqno,
            &*config.fs,
            self.0.runtime_config.load_full(),
            self.0.config.encryption.clone(),
            // The floor is the mutator's: `Keep` lets the install raise none.
            crate::version::RetentionEffect::Keep,
        )
    }

    fn compaction_rate_limiter(&self) -> Arc<crate::rate_limiter::RateLimiter> {
        Arc::clone(&self.compaction_rate_limiter)
    }

    fn write_rate_limiter(&self) -> Arc<crate::rate_limiter::RateLimiter> {
        Arc::clone(&self.write_rate_limiter)
    }

    fn get<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> crate::Result<Option<UserValue>> {
        let key = key.as_ref();

        let super_version = self.snapshot_for_read(seqno)?;
        // Counted here, not in the lookup: a columnar scan resolving merge
        // operands looks keys up too, as part of the scan it counts.
        super_version.version.read_mix().note_points(1);

        Self::resolve_or_passthrough(
            &super_version,
            key,
            seqno,
            self.config.merge_operator.as_ref(),
            self.config.comparator.as_ref(),
            || self.blob_source(),
        )
    }

    // Existence needs the newest visible version, not its value: a merge
    // chain always resolves to some value, so its operands are not merged and
    // a separated base is not read.
    fn contains_key<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> crate::Result<bool> {
        let super_version = self.snapshot_for_read(seqno)?;
        super_version.version.read_mix().note_points(1);
        Ok(Self::get_value(
            &super_version,
            key.as_ref(),
            seqno,
            self.config.comparator.as_ref(),
        )?
        .is_some())
    }

    // Key-only like `contains_key`: the scan runs without the merge operator,
    // which yields a chain's newest operand in place of its merged value, the
    // same key either way.
    fn contains_prefix<K: AsRef<[u8]>>(
        &self,
        prefix: K,
        seqno: SeqNo,
        index: Option<(Arc<Memtable>, SeqNo)>,
    ) -> crate::Result<bool> {
        Ok(self
            .create_internal_prefix(prefix.as_ref(), seqno, index, None, None)?
            .next()
            .transpose()?
            .is_some())
    }

    fn is_empty(&self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>) -> crate::Result<bool> {
        Ok(self
            .create_key_only_iter(seqno, index)?
            .next()
            .transpose()?
            .is_none())
    }

    fn len(&self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>) -> crate::Result<usize> {
        let mut count = 0;
        for item in self.create_key_only_iter(seqno, index)? {
            item?;
            count += 1;
        }
        Ok(count)
    }

    fn get_pinned<K: AsRef<[u8]>>(
        &self,
        key: K,
        seqno: SeqNo,
    ) -> crate::Result<Option<crate::PinnableSlice>> {
        let key = key.as_ref();

        let super_version = self.snapshot_for_read(seqno)?;
        super_version.version.read_mix().note_points(1);

        Self::resolve_or_passthrough_pinned(
            &super_version,
            key,
            seqno,
            self.config.merge_operator.as_ref(),
            self.config.comparator.as_ref(),
            || self.blob_source(),
        )
    }

    fn multi_get<K: AsRef<[u8]>>(
        &self,
        keys: impl IntoIterator<Item = K>,
        seqno: SeqNo,
    ) -> crate::Result<Vec<Option<UserValue>>> {
        let super_version = self.snapshot_for_read(seqno)?;
        let comparator = self.config.comparator.as_ref();
        let merge_operator = self.config.merge_operator.as_ref();

        let keys: Vec<_> = keys.into_iter().collect();
        let n = keys.len();
        if n == 0 {
            return Ok(Vec::new());
        }

        // For small batches, use the simple per-key path
        if n <= 2 {
            super_version
                .version
                .read_mix()
                .note_points(u64::try_from(n).unwrap_or(u64::MAX));
            // One blob source for every key of the batch, taken when a merge
            // first needs it, so both keys read under one fill policy.
            let blob_source = core::cell::OnceCell::new();
            return keys
                .iter()
                .map(|key| {
                    Self::resolve_or_passthrough(
                        &super_version,
                        key.as_ref(),
                        seqno,
                        merge_operator,
                        comparator,
                        || blob_source.get_or_init(|| self.blob_source()).clone(),
                    )
                })
                .collect();
        }

        Self::read_many(&read_job::ReadCtx {
            super_version,
            keys,
            seqno,
            comparator: Arc::clone(&self.config.comparator),
            merge_operator: self.config.merge_operator.clone(),
            merge_base: self.blob_source(),
            values: read_job::Values::Inline,
            metadata_budget: self.config.multi_get_metadata_budget,
        })
    }

    fn apply_batch(&self, batch: crate::WriteBatch, seqno: SeqNo) -> crate::Result<(u64, u64)> {
        if batch.is_empty() {
            return Ok((0, self.active_memtable().size()));
        }
        Ok(self.append_batch(batch.materialize(seqno)?))
    }

    fn insert<K: Into<UserKey>, V: Into<UserValue>>(
        &self,
        key: K,
        value: V,
        seqno: SeqNo,
    ) -> (u64, u64) {
        let value = InternalValue::from_components(key, value, seqno, ValueType::Value);
        self.append_entry(value)
    }

    fn merge<K: Into<UserKey>, V: Into<UserValue>>(
        &self,
        key: K,
        operand: V,
        seqno: SeqNo,
    ) -> (u64, u64) {
        let value = InternalValue::new_merge_operand(key, operand, seqno);
        self.append_entry(value)
    }

    fn remove<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u64, u64) {
        let value = InternalValue::new_tombstone(key, seqno);
        self.append_entry(value)
    }

    fn remove_weak<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u64, u64) {
        let value = InternalValue::new_weak_tombstone(key, seqno);
        self.append_entry(value)
    }

    fn remove_range<K: Into<UserKey>>(&self, start: K, end: K, seqno: SeqNo) -> u64 {
        let (start, end) = (start.into(), end.into());
        #[cfg(feature = "metrics")]
        self.0
            .metrics
            .accepted_range_deletion(start.len() + end.len());
        // The read guard is held through the insert, like `append_entry`: the
        // CDC scan's capture (write side of this lock) must exclude every
        // in-flight memtable write, or a backdated range deletion could land
        // after the capture yet below the returned watermark and be lost; the
        // guard also keeps a concurrent `rotate_memtable()` from sealing the
        // memtable mid-insert.
        let history = self.version_history.read();

        #[cfg(test)]
        inner::TestHooks::fire(&self.test_hooks.range_write);

        history
            .latest_version_ref()
            .active_memtable
            .insert_range_tombstone(start, end, seqno)
    }
}

impl Tree {
    /// The filter plan of new data written into tables under the policies of
    /// `level`, as a flush or an ingestion writes it: at most `count` keys and
    /// filter hashes (zero when unknown) under `bloom_policy`. `None` without
    /// an advisor.
    /// New data has no probe history of its own: its filters are sized by the
    /// load the live tables draw per key, and room is kept for every table the
    /// write fills. The plan is held until the tables are installed (see
    /// `WritePin`).
    ///
    /// `ecc_scheme` is the one the write's runtime snapshot frames its blocks
    /// under.
    pub(crate) fn new_data_filter_sizing(
        &self,
        level: usize,
        bloom_policy: crate::table::filter::BloomConstructionPolicy,
        count: crate::filter_budget::FilterCount,
        ecc_scheme: crate::runtime_config::EccScheme,
    ) -> Option<crate::filter_budget::FilterPlan> {
        let advisor = self.config.filter_advisor.as_ref()?;
        let version = self.current_version();
        crate::filter_budget::plan(
            advisor,
            &self.filter_budget,
            &crate::filter_budget::live(&version),
            crate::filter_budget::Rewrite {
                count,
                framing: crate::filter_budget::Framing {
                    encryption: self.config.encryption.clone(),
                    ecc: crate::table::writer::resolve_ecc(self.config.page_ecc, ecc_scheme),
                },
                ..crate::filter_budget::Rewrite::default()
            },
            bloom_policy,
            self.config
                .filter_block_partitioning_policy
                .get(level)
                .then(|| self.config.filter_block_partition_size_policy.get(level)),
        )
    }

    /// The encoded report of a repair the tree still owes, if any.
    #[cfg(feature = "std")]
    pub(crate) fn owed_repair_report(&self) -> Option<alloc::sync::Arc<[u8]>> {
        self.version_history
            .read()
            .latest_version_ref()
            .version
            .repair_report()
            .map(alloc::sync::Arc::from)
    }

    /// See [`AbstractTree::acknowledge_repair_report`].
    #[cfg(feature = "std")]
    pub(crate) fn acknowledge_repair_report(&self, id: u128) -> crate::Result<bool> {
        let mut version_lock = self.version_history.write();
        let owes_it = version_lock
            .latest_version_ref()
            .version
            .repair_report()
            .is_some_and(|owed| crate::repair::owed_report_id(owed) == id);
        if !owes_it {
            return Ok(false);
        }
        let installed = version_lock.upgrade_version(
            &self.config.path,
            |current| {
                let mut copy = current.clone();
                copy.version = copy.version.without_repair_report();
                Ok(copy)
            },
            &self.config.seqno,
            &self.config.visible_seqno,
            &*self.config.fs,
            self.0.runtime_config.load_full(),
            self.0.config.encryption.clone(),
            // Only the report goes: every snapshot reads as before.
            crate::version::RetentionEffect::Keep,
        );
        drop(version_lock);
        installed.map(|()| true)
    }

    /// Stores `dict` in the tree and records it in the current version, so it
    /// resolves after a reopen with no dictionary supplied in the config.
    ///
    /// Additive: tables already written keep resolving to the dictionary they
    /// were written against, which is what makes it safe to introduce a
    /// dictionary on a tree that already holds data, and to replace one (both
    /// are this same operation). Registering an id the tree already holds is a
    /// no-op, since the id is derived from the bytes.
    ///
    /// The file is written BEFORE the version edit that references it. The
    /// other order would publish an id whose bytes a crash could still lose,
    /// and the tables written against it would then fail to open; this order
    /// can only leave an unreferenced file, which the next collection removes.
    ///
    /// Both steps happen under the version lock, which is what serializes this
    /// against [`Self::collect_unreferenced_dictionaries`]. Taking the lock only
    /// for the edit would leave the file published in the window the collector
    /// scans, and it would be unlinked as an orphan before the edit that names
    /// it ever landed.
    ///
    /// # Errors
    ///
    /// Propagates the store's write failures and the version install's.
    #[cfg(zstd_any)]
    pub fn register_zstd_dictionary(
        &self,
        dict: alloc::sync::Arc<crate::compression::ZstdDictionary>,
    ) -> crate::Result<()> {
        let id = dict.id();
        let mut version_lock = self.version_history.write();

        let folder = self.config.path.join(crate::file::DICTS_FOLDER);
        crate::dicts::write(
            &*self.config.fs,
            &folder,
            &dict,
            self.config.encryption.as_deref(),
            self.config.sync_mode,
        )?;

        // Resolvable from this moment on rather than from the next open: the
        // tables this registration was made for are written right after it, and
        // reading them back needs the dictionary in the LIVE set.
        let dicts = self.config.current_zstd_dictionaries().with(dict);
        self.config
            .zstd_dictionaries
            .store(alloc::sync::Arc::new(dicts));

        if version_lock
            .latest_version_ref()
            .version
            .dicts()
            .contains(&id)
        {
            return Ok(());
        }
        version_lock.upgrade_version(
            &self.config.path,
            |current| {
                let mut copy = current.clone();
                copy.version = copy.version.with_dict(id);
                Ok(copy)
            },
            &self.config.seqno,
            &self.config.visible_seqno,
            &*self.config.fs,
            self.0.runtime_config.load_full(),
            self.0.config.encryption.clone(),
            // Registering a dictionary adds a file and drops nothing, so no
            // snapshot loses anything it could read before.
            crate::version::RetentionEffect::Keep,
        )
    }

    /// The dictionaries this tree can decompress against, as of this call.
    #[cfg(zstd_any)]
    #[must_use]
    pub fn zstd_dictionaries(&self) -> crate::compression::ZstdDictionaries {
        self.config.current_zstd_dictionaries()
    }

    /// The dictionary ids new files may still be written against: every one
    /// the live snapshot's policies name, and every one a replaced snapshot a
    /// writer still holds names (see `TreeInner::retired_write_snapshots`).
    #[cfg(zstd_any)]
    pub(crate) fn write_referenced_dict_ids(&self) -> Vec<crate::file::DictId> {
        let kv_separated = self.config.kv_separation_opts.is_some();
        let mut ids: Vec<crate::file::DictId> = self
            .0
            .runtime_config
            .load()
            .write_dict_ids(kv_separated)
            .collect();
        self.0.retired_write_snapshots.lock().retain(|snapshot| {
            let Some(held) = snapshot.upgrade() else {
                return false;
            };
            ids.extend(held.write_dict_ids(kv_separated));
            true
        });
        ids.sort_unstable();
        ids.dedup();
        ids
    }

    /// Drops every dictionary nothing references any more, returning how many
    /// files were removed.
    ///
    /// The current version first stops REGISTERING an id nothing references
    /// (a version edit, costing an install and nothing on disk), and the file
    /// goes in the same pass once the installed version no longer names it. A
    /// reader still holding an older version is unaffected: its tables and
    /// blob files pinned their dictionaries when they were opened.
    ///
    /// REFERENCED means both directions: the files that already exist (tables
    /// and blob files alike), and the ids the compression policies name for
    /// what is written next. Counting only the first would unregister a
    /// dictionary before its first table is written, and nothing puts the id
    /// back afterwards, so a later pass would unlink the file while live
    /// tables are compressed against it. What is written next includes the
    /// writers already running: a flush or compaction started under a policy
    /// [`Self::update_runtime_config`] has since replaced still writes against
    /// the dictionary that policy named, so it is spared until their files are
    /// installed and name it themselves.
    ///
    /// The whole pass holds the version lock. Registration takes the same lock
    /// before it writes anything, so the two cannot interleave: without that, a
    /// registration's file could land between this scan and its removals and be
    /// unlinked as an orphan while the edit naming it was still to come.
    ///
    /// # Errors
    ///
    /// Propagates the version install and the store's removal failures.
    #[cfg(zstd_any)]
    pub fn collect_unreferenced_dictionaries(&self) -> crate::Result<usize> {
        let mut version_lock = self.version_history.write();

        // Unregister what neither the current version's tables nor the write
        // policy needs.
        let latest = version_lock.latest_version_ref().version.clone();
        let mut referenced = latest.referenced_dicts();
        referenced.extend(self.write_referenced_dict_ids());
        let stale: Vec<crate::file::DictId> = latest
            .dicts()
            .iter()
            .copied()
            .filter(|id| !referenced.contains(id))
            .collect();

        if !stale.is_empty() {
            version_lock.upgrade_version(
                &self.config.path,
                |current| {
                    let mut copy = current.clone();
                    copy.version = copy.version.without_dicts(&stale);
                    Ok(copy)
                },
                &self.config.seqno,
                &self.config.visible_seqno,
                &*self.config.fs,
                self.0.runtime_config.load_full(),
                self.0.config.encryption.clone(),
                // Dropping a dictionary nothing reads takes away no row a
                // snapshot could observe: the current version no longer holds
                // a table that used it.
                crate::version::RetentionEffect::Keep,
            )?;
        }

        // Unlink the files the current version no longer names. Still under
        // the version lock, so no registration can publish a file into the
        // window between the listing and the removals.
        let still_owed = version_lock.registered_dicts();

        let folder = self.config.path.join(crate::file::DICTS_FOLDER);
        let mut removed = 0;
        for id in crate::dicts::list_ids(&*self.config.fs, &folder)? {
            if still_owed.contains(&id) || referenced.contains(&id) {
                continue;
            }
            // A held deletion pause SKIPS the dictionary entirely: it is not
            // queued for later. A checkpoint holds its captured version as a
            // LOCAL clone, so a concurrent install can replace that version
            // while the checkpoint is still going to link the dictionaries it
            // names; removing one now would fail
            // `link_dictionaries` on a missing file and abort a checkpoint that
            // was otherwise valid.
            //
            // Skipping rather than DEFERRING (which is what tables and blob
            // files do) because a queued removal fires unconditionally when the
            // pause drains, and by then the id may have been registered again:
            // registration finds the file already there, makes its write a
            // no-op, durably records the id, and the drain then deletes the
            // dictionary that registration just published. A table's removal
            // cannot be undone by re-creating the table, so deferring is right
            // for it; a dictionary collection is an explicit operation that can
            // simply be run again, so waiting for the next pass costs nothing
            // and leaves no queued action to fire against a re-registered file.
            if self.deletion_pause.is_active() {
                continue;
            }
            // A pin lists the dictionary for its copy: skipped the same way,
            // and the next pass after the pin drops removes it. Pins register
            // under the version lock held here, so none can slip in between.
            #[cfg(feature = "std")]
            if self
                .deletion_pause
                .is_pinned(&crate::dicts::path_of(&folder, id))
            {
                continue;
            }
            crate::dicts::remove(&*self.config.fs, &folder, id, self.config.sync_mode)?;

            // Out of the LIVE set too, not just off the disk. The registry holds
            // each dictionary's raw bytes and its prepared decoder state, so a
            // tree that rotates dictionaries over a long life would otherwise
            // accumulate every generation it ever held until it is dropped,
            // and `zstd_dictionaries()` would keep naming ids the tree no
            // longer owns.
            self.config.zstd_dictionaries.store(alloc::sync::Arc::new(
                self.config.current_zstd_dictionaries().without(id),
            ));
            removed += 1;
        }
        // Explicitly, and only here: the guard is what excludes a concurrent
        // registration from the removals above, so releasing it at its last READ
        // (which is what tightening the scope would do) is precisely the race.
        //
        // This drop is also what satisfies `clippy::significant_drop_tightening`
        // — it makes the guard's last use its own release, so the lint does not
        // fire and the function needs no expectation. Adding one anyway is a
        // BUILD FAILURE here, not dead weight: `unfulfilled_lint_expectations`
        // is an error under the crate's `-D warnings`.
        drop(version_lock);
        Ok(removed)
    }

    /// Maps a raw internal entry to its change-data-capture event, routing
    /// `Indirection` (KV-separated) values through `resolve_indirection`.
    ///
    /// A standard tree never stores `Indirection` and supplies a resolver that
    /// errors; the blob-tree scan path supplies one that reads the blob and
    /// returns an [`ScanSinceEvent::Insert`].
    fn map_event<F>(
        entry: InternalValue,
        version: &Version,
        resolve_indirection: &F,
    ) -> crate::Result<ScanSinceEvent>
    where
        F: Fn(&Version, InternalValue) -> crate::Result<ScanSinceEvent>,
    {
        // A cell row may reference blob objects, so it resolves where an
        // indirection does.
        if matches!(
            entry.key.value_type,
            ValueType::Indirection | ValueType::CellRow
        ) {
            return resolve_indirection(version, entry);
        }
        let seqno = entry.key.seqno;
        let key = entry.key.user_key;
        Ok(match entry.key.value_type {
            ValueType::Value => ScanSinceEvent::Insert {
                key,
                value: entry.value,
                seqno,
            },
            ValueType::MergeOperand => ScanSinceEvent::MergeOperand {
                key,
                operand: entry.value,
                seqno,
            },
            // Weak (single-delete) tombstones keep their own event kind: a
            // weak tombstone annihilates exactly its matching put during
            // compaction and can then expose an older value, while a regular
            // tombstone keeps hiding it — collapsing both into one event
            // would make a replica replay a weak delete as a full delete and
            // diverge from the source.
            ValueType::Tombstone => ScanSinceEvent::PointTombstone { key, seqno },
            ValueType::WeakTombstone => ScanSinceEvent::WeakTombstone { key, seqno },
            ValueType::Indirection | ValueType::CellRow => {
                unreachable!("Indirection and CellRow handled above")
            }
        })
    }

    /// Shared CDC aggregation behind [`Self::scan_since_seqno`] and the
    /// blob-tree scan path: gathers qualifying entries (`seqno >= target`) plus
    /// range tombstones from the active + sealed memtables and every SST (with
    /// block-skip), maps each entry to a [`ScanSinceEvent`] — routing
    /// `Indirection` values through `resolve_indirection` against the same
    /// version snapshot — and returns them in increasing seqno order.
    ///
    /// # Panics
    ///
    /// Panics if the internal version-history lock is poisoned.
    ///
    /// # Errors
    ///
    /// Returns `Err` if reading the index or a data block fails, or if
    /// `resolve_indirection` errors.
    pub(crate) fn scan_since_seqno_with<F>(
        &self,
        target_seqno: SeqNo,
        block_skip: bool,
        resolve_indirection: F,
    ) -> crate::Result<alloc::vec::IntoIter<ScanSinceEvent>>
    where
        F: Fn(&Version, InternalValue) -> crate::Result<ScanSinceEvent>,
    {
        self.scan_since_seqno_scoped(target_seqno, block_skip, resolve_indirection, None)
    }

    /// As [`Self::scan_since_seqno_with`], optionally scoped to a key range
    /// (in the tree comparator's order): point events are delivered only for
    /// keys INSIDE the bounds, range tombstones when their span OVERLAPS them
    /// (a tombstone reaching into the range affects replay within it), and
    /// SSTs whose key range cannot intersect the bounds are skipped without
    /// being read — which is what makes a post-repair reconciliation over
    /// [`RepairReport::lost_coverage`](crate::RepairReport) affordable.
    pub(crate) fn scan_since_seqno_scoped<F>(
        &self,
        target_seqno: SeqNo,
        block_skip: bool,
        resolve_indirection: F,
        key_range: Option<&(Bound<UserKey>, Bound<UserKey>)>,
    ) -> crate::Result<alloc::vec::IntoIter<ScanSinceEvent>>
    where
        F: Fn(&Version, InternalValue) -> crate::Result<ScanSinceEvent>,
    {
        use core::cmp::Ordering;

        let cmp = self.config.comparator.clone();
        let in_key_range = |key: &[u8]| -> bool {
            let Some((lo, hi)) = key_range else {
                return true;
            };
            (match lo {
                Bound::Included(b) => cmp.compare(key, b.as_ref()) != Ordering::Less,
                Bound::Excluded(b) => cmp.compare(key, b.as_ref()) == Ordering::Greater,
                Bound::Unbounded => true,
            }) && (match hi {
                Bound::Included(b) => cmp.compare(key, b.as_ref()) != Ordering::Greater,
                Bound::Excluded(b) => cmp.compare(key, b.as_ref()) == Ordering::Less,
                Bound::Unbounded => true,
            })
        };
        // A range tombstone covers `[start, end)`; it is delivered when that
        // span overlaps the scope, since a deletion reaching into the range
        // affects replay within it.
        let rt_in_range = |rt: &RangeTombstone| -> bool {
            let Some((lo, hi)) = key_range else {
                return true;
            };
            (match lo {
                // `rt.end` is EXCLUSIVE: the tombstone reaches keys strictly
                // below it, so it clears the lower bound only when its end is
                // ABOVE the bound key (for an excluded bound this over-includes
                // the touching case, which is harmless: replaying an extra
                // idempotent deletion event cannot corrupt a consumer).
                Bound::Included(b) | Bound::Excluded(b) => {
                    cmp.compare(rt.end.as_ref(), b.as_ref()) == Ordering::Greater
                }
                Bound::Unbounded => true,
            }) && (match hi {
                Bound::Included(b) => {
                    cmp.compare(rt.start.as_ref(), b.as_ref()) != Ordering::Greater
                }
                Bound::Excluded(b) => cmp.compare(rt.start.as_ref(), b.as_ref()) == Ordering::Less,
                Bound::Unbounded => true,
            })
        };
        // The active memtable is the one source a writer can still change, and
        // the seqno cap alone does not exclude that: a caller may commit with an
        // explicit seqno at or BELOW the cap (`apply_batch` takes the seqno from
        // the caller), and a live lock-free walk would then see that write or
        // miss it depending on where the node lands relative to the cursor —
        // even splitting one batch. A consumer that advanced past the returned
        // watermark would lose the change for good.
        //
        // So freeze it: a batch or range write holds the version-history READ
        // guard for its whole insert, and a single-entry insert holds its shard
        // of the insert gate instead, so taking the WRITE guard and closing the
        // gate excludes both, in the order a version change takes them. The cap
        // and the active memtable's raw entries are captured under them;
        // everything else (sealed memtables, tables) is immutable and needs
        // no coordination.
        //
        // Mapping runs AFTER the guard drops: it resolves blob indirections,
        // which reads a blob file, and no I/O may happen with writers blocked.
        // The memtables are walked over the scope only, as a range read walks
        // them.
        let memtable_keys = key_range.map_or(
            (Bound::Unbounded, Bound::Unbounded),
            crate::range::user_to_internal_bounds,
        );
        let (super_version, end_seqno, active_entries, active_range_tombstones) = {
            let guard = self.version_history.write();
            #[cfg(feature = "std")]
            let gate = self.insert_gate.close();
            let super_version = guard.latest_version();
            #[cfg(test)]
            inner::TestHooks::fire(&self.test_hooks.scan_freeze);
            let end_seqno = {
                let active = super_version.active_memtable.get_highest_seqno();
                let sealed = super_version
                    .sealed_memtables
                    .iter()
                    .map(|mt| mt.get_highest_seqno())
                    .max()
                    .flatten();
                let tables = super_version
                    .version
                    .iter_tables()
                    .map(Table::get_highest_seqno)
                    .max();
                active.max(sealed).max(tables)
            };
            let entries: Vec<InternalValue> = end_seqno.map_or_else(Vec::new, |cap| {
                super_version
                    .active_memtable
                    .range_internal(memtable_keys.clone())
                    .filter(|e| e.key.seqno >= target_seqno && e.key.seqno <= cap)
                    .collect()
            });
            let rts = super_version.active_memtable.range_tombstones_sorted();
            // Explicit: the gate and the guard must outlive the capture above,
            // and writers resume the moment they go.
            #[cfg(feature = "std")]
            drop(gate);
            drop(guard);
            (super_version, end_seqno, entries, rts)
        };
        let version = &super_version.version;
        // No entries anywhere ⇒ nothing qualifies, regardless of target.
        let Some(end_seqno) = end_seqno else {
            return Ok(Vec::new().into_iter());
        };

        // Events are gathered PER SOURCE, not into one flat list: copies of a
        // change across two sources are the same change and collapse, but a
        // single source may legitimately hold a byte-identical event more than
        // once (a write batch may carry the same merge operand for a key
        // twice; both are stored under the batch's shared seqno and both are
        // applied on read). See `merge_source_events`.
        let mut sources: Vec<Vec<ScanSinceEvent>> = Vec::new();

        let in_window = |seqno: SeqNo| seqno >= target_seqno && seqno <= end_seqno;
        let range_tombstone_event = |rt: &RangeTombstone| {
            in_window(rt.seqno).then(|| ScanSinceEvent::RangeTombstone {
                start_key: rt.start.clone(),
                end_key: rt.end.clone(),
                seqno: rt.seqno,
            })
        };

        // The scope bounds as borrowed slices, for SST key-range pruning.
        fn as_ref_bound(b: &Bound<UserKey>) -> Bound<&[u8]> {
            match b {
                Bound::Included(k) => Bound::Included(k.as_ref()),
                Bound::Excluded(k) => Bound::Excluded(k.as_ref()),
                Bound::Unbounded => Bound::Unbounded,
            }
        }
        let ref_bounds = key_range.map(|(lo, hi)| (as_ref_bound(lo), as_ref_bound(hi)));

        // Active memtable — mapped from the frozen capture above, not walked
        // again: a second walk would reintroduce exactly the race the freeze
        // closed.
        let mut source = Vec::new();
        for entry in active_entries {
            if !in_key_range(&entry.key.user_key) {
                continue;
            }
            source.push(Self::map_event(entry, version, &resolve_indirection)?);
        }
        for rt in active_range_tombstones {
            if rt_in_range(&rt) {
                source.extend(range_tombstone_event(&rt));
            }
        }
        sources.push(source);

        // Sealed memtables, NEWEST first: the list is kept in seal order, and
        // every source below must be older than the one before it, because the
        // merge derives replay precedence from that position.
        for memtable in super_version.sealed_memtables.iter().rev() {
            let mut source = Vec::new();
            // The walk is bounded by internal keys; the user bounds decide at
            // their own key, whatever version sits there.
            for entry in memtable.range_internal(memtable_keys.clone()) {
                if in_window(entry.key.seqno) && in_key_range(&entry.key.user_key) {
                    source.push(Self::map_event(entry, version, &resolve_indirection)?);
                }
            }
            for rt in memtable.range_tombstones_sorted() {
                if rt_in_range(&rt) {
                    source.extend(range_tombstone_event(&rt));
                }
            }
            sources.push(source);
        }

        // SSTs. A table whose key range cannot intersect the scope is not read
        // — the point of the scoped variant. Its tombstones still are: the key
        // range does not bound them, since a compaction cuts its outputs'
        // tombstones at the next output's first key without widening the
        // range up to it.
        for table in version.iter_tables() {
            let keys_in_scope = ref_bounds.as_ref().is_none_or(|bounds| {
                table
                    .metadata
                    .key_range
                    .overlaps_with_bounds_cmp(bounds, cmp.as_ref())
            });
            if !keys_in_scope {
                let mut source = Vec::new();
                for rt in table.visible_range_tombstones() {
                    if rt_in_range(&rt) {
                        source.extend(range_tombstone_event(&rt));
                    }
                }
                if !source.is_empty() {
                    sources.push(source);
                }
                continue;
            }
            // An RT-only table's synthetic weak-tombstone sentinel (the
            // writer's `finish`) is deliberately NOT filtered out here. It is
            // a real on-disk entry the READ path sees: at a seqno TIE between
            // the range deletion and an older source's write at the range's
            // start key, the sentinel is what makes the read converge to a
            // deletion — so the event stream must carry it too, or a consumer
            // replaying the stream keeps a value the tree itself does not
            // serve (this stream's one rule is mirroring the tree's reads,
            // see `merge_source_events`). It surfaces as the weak-tombstone
            // event it is on disk; away from that tie a replayed weak delete
            // at the range's start under the range deletion's own seqno is a
            // no-op.
            let mut source = Vec::new();
            let table_keys = ref_bounds.unwrap_or((Bound::Unbounded, Bound::Unbounded));
            for entry in table.scan_seqno_range(target_seqno, end_seqno, block_skip, table_keys)? {
                if !in_key_range(&entry.key.user_key) {
                    continue;
                }
                source.push(Self::map_event(entry, version, &resolve_indirection)?);
            }
            // Clamped to the view's tight-space restriction: the punched
            // prefix's deletions are re-emitted by the slice output that
            // superseded it, so the raw list would duplicate those events.
            for rt in table.visible_range_tombstones() {
                if rt_in_range(&rt) {
                    source.extend(range_tombstone_event(&rt));
                }
            }
            sources.push(source);
        }

        Ok(Self::merge_source_events(sources).into_iter())
    }

    /// Merge per-source event lists into one replay-ordered stream, `sources`
    /// ordered NEWEST first.
    ///
    /// Replay order is increasing seqno, then — for events sharing one seqno —
    /// increasing source AGE reversed, so the newest source's event is applied
    /// LAST. That matters because two sources can hold different values for one
    /// key at one seqno ([`AbstractTree::apply_batch`] takes a caller-chosen
    /// seqno and does not require it to be unique), the tree serves the newer
    /// one, and a consumer keeps whatever it applies last. Sorting such ties by
    /// payload instead would decide precedence by byte order.
    ///
    /// What happens to byte-identical copies follows ONE rule: the stream must
    /// mirror what a read of the same tree does, because a consumer replaying
    /// it has to reach the state the tree itself serves.
    ///
    /// - **Merge operands are all kept.** The read path collects every
    ///   physically stored operand for a key and applies them in order — it
    ///   never deduplicates by seqno — so two operands are two applications
    ///   whether they sit in one source or in two. Seqnos do not disambiguate
    ///   here: [`AbstractTree::apply_batch`] takes a caller-chosen seqno and
    ///   does not require it to be unique, and one batch may carry the same
    ///   operand for a key twice.
    /// - **Idempotent events collapse across sources.** A write, a deletion or
    ///   a range deletion replayed twice reaches the same state, and the read
    ///   path shadows the copies by seqno rather than compounding them. One
    ///   committed change can physically live in two published tables — a
    ///   manifest-loss repair publishes every surviving SST as its own L0 run,
    ///   including both the inputs and the outputs of a compaction that crashed
    ///   before deleting its inputs — and delivering it twice would be noise.
    ///   Repeats WITHIN one source are still kept: they are separate entries
    ///   the source genuinely holds.
    fn merge_source_events(sources: Vec<Vec<ScanSinceEvent>>) -> Vec<ScanSinceEvent> {
        // Per source, collapse equal neighbours into runs, each tagged with
        // its source's recency (0 = newest) and the position of EVERY copy it
        // carries.
        //
        // The POSITIONS are what keep an order-sensitive merge operator
        // correct: a source applies the operands of one batch in the order
        // they were added, all at one seqno, and grouping them by payload
        // would replay them in a different order — an append or a list push
        // then converges somewhere the tree never was. Grouping still SORTS
        // (equal events have to meet), so each run remembers where each of its
        // members sat: one shared position would fold a repeated operand's
        // copies onto its twin's slot and replay `B, A, B` as `A, B, B`.
        struct Run {
            event: ScanSinceEvent,
            recency: usize,
            /// Original scan position of every copy, ascending.
            positions: Vec<usize>,
        }
        let mut runs: Vec<Run> = Vec::new();
        for (recency, source) in sources.into_iter().enumerate() {
            let mut indexed: Vec<(usize, ScanSinceEvent)> =
                source.into_iter().enumerate().collect();
            indexed.sort_by(|(_, a), (_, b)| ScanSinceEvent::grouping_order(a, b));
            let mut iter = indexed.into_iter();
            let Some((position, mut current)) = iter.next() else {
                continue;
            };
            let mut positions = alloc::vec![position];
            for (index, event) in iter {
                if event == current {
                    positions.push(index);
                } else {
                    positions.sort_unstable();
                    runs.push(Run {
                        event: core::mem::replace(&mut current, event),
                        recency,
                        positions: core::mem::replace(&mut positions, alloc::vec![index]),
                    });
                }
            }
            positions.sort_unstable();
            runs.push(Run {
                event: current,
                recency,
                positions,
            });
        }

        // Merge the per-source runs. Operands are never collapsed — every copy
        // is an application the read path makes, so each keeps ITS source's
        // recency and ITS scan position, and the replay order below (oldest
        // source first, then position) applies them exactly as the tree does.
        // Idempotent events collapse across sources to the count a single
        // source holds; the collapsed event keeps the recency of the NEWEST
        // source holding it (and that source's positions), which is the slot
        // the tree's own precedence gives it.
        //
        // WEAK tombstones belong to the idempotent class even though a weak
        // delete annihilates one put at compaction: its documented contract
        // pairs it with a key written at most once, byte-identical copies
        // meeting in one compaction stream drain to a single survivor, and a
        // consumer cannot materialize multiplicity anyway — replaying the
        // same `remove_weak` twice at one seqno lands on ONE internal key in
        // its memtable, so a preserved duplicate would replay to the same
        // physical state the collapsed stream does.
        runs.sort_by(|a, b| ScanSinceEvent::grouping_order(&a.event, &b.event));
        let mut merged: Vec<(ScanSinceEvent, usize, usize)> = Vec::new();
        let mut iter = runs.into_iter().peekable();
        while let Some(run) = iter.next() {
            if matches!(run.event, ScanSinceEvent::MergeOperand { .. }) {
                // Equal operand runs from OTHER sources follow as their own
                // iterations and emit their own copies — no draining here.
                for &position in &run.positions {
                    merged.push((run.event.clone(), run.recency, position));
                }
                continue;
            }
            let Run {
                event,
                mut recency,
                mut positions,
            } = run;
            let mut count = positions.len();
            while let Some(other) = iter.next_if(|next| next.event == event) {
                debug_assert_eq!(other.event, event, "next_if matched the same event");
                count = count.max(other.positions.len());
                if other.recency < recency {
                    recency = other.recency;
                    positions = other.positions;
                }
            }
            // The winning source may hold fewer copies than the count another
            // source did; the extras repeat its last position (they are
            // byte-identical, so their relative order carries no information).
            while positions.len() < count {
                let last = positions.last().copied().unwrap_or_default();
                positions.push(last);
            }
            for &position in positions.iter().take(count) {
                merged.push((event.clone(), recency, position));
            }
        }

        // Finally, replay order: seqno, then range deletions, then oldest source
        // first, then the position that source gave the event — which is how an
        // order-sensitive merge operator converges to what the tree serves.
        //
        // The range-deletion step comes BEFORE source recency, not after: a tied
        // deletion does not suppress the writes it spans (suppression is
        // strictly `entry.seqno < tombstone.seqno`), so the tree keeps them, and
        // a replay that applied the deletion last would drop them. Ordering by
        // recency first would do exactly that whenever the deletion sits in the
        // newer source.
        merged.sort_by(|(a, a_recency, a_pos), (b, b_recency, b_pos)| {
            fn deletion_first(e: &ScanSinceEvent) -> u8 {
                u8::from(!matches!(e, ScanSinceEvent::RangeTombstone { .. }))
            }
            a.seqno()
                .cmp(&b.seqno())
                .then_with(|| deletion_first(a).cmp(&deletion_first(b)))
                .then_with(|| b_recency.cmp(a_recency))
                .then_with(|| {
                    // Within one source and one seqno, a scan yields a key's
                    // versions NEWEST first, and the read path reverses that run
                    // to apply them chronologically. Mirror it: same key ⇒ the
                    // later scan position replays FIRST. Distinct keys at one
                    // seqno touch different state, so their relative order is
                    // free — keep it deterministic by scan position.
                    //
                    // Identity is the engine's one relation (byte equality, see
                    // `same_user_key`), which is what the read path this mirrors
                    // uses to group a key's versions. Asking the comparator here
                    // would answer the same question — its contract makes
                    // `Equal` imply byte equality — while letting the two paths
                    // disagree the moment a comparator broke that.
                    if crate::comparator::same_user_key(a.key(), b.key()) {
                        b_pos.cmp(a_pos)
                    } else {
                        a_pos.cmp(b_pos)
                    }
                })
        });
        merged.into_iter().map(|(event, ..)| event).collect()
    }

    /// Iterate change events with `seqno >= target_seqno`.
    ///
    /// Returns every change committed at or after `target_seqno` as a stream
    /// of [`ScanSinceEvent`]s in increasing seqno order. This is the canonical
    /// change-data-capture primitive: a downstream consumer (replica, Kafka
    /// connector, Debezium-style pipeline) replays the events in order to
    /// reconstruct the source's history. Superseded versions are not collapsed
    /// (a key written three times after the target yields three events).
    ///
    /// # Concurrency
    ///
    /// The result is a snapshot of the tree as of the call: the active memtable
    /// is captured with writers excluded, so a batch committed concurrently is
    /// either wholly in the result or wholly absent, never split across it. This
    /// holds even for a caller-chosen sequence number at or below the reported
    /// watermark, which the seqno bound alone would not exclude. Writers are
    /// blocked only while that capture runs — the sealed memtables and SSTs the
    /// scan then reads are immutable.
    ///
    /// # History retention
    ///
    /// The stream carries what the tree still PHYSICALLY HOLDS. A compaction
    /// run with a GC watermark (the `gc_watermark` passed to
    /// [`compact`](crate::AbstractTree::compact) /
    /// [`major_compact`](crate::AbstractTree::major_compact)) drops shadowed
    /// versions and evicted tombstones below that watermark and may fold
    /// merge chains and zero bottommost seqnos — history a later scan cannot
    /// resurrect. The result is therefore complete only for a `target_seqno`
    /// at or above the highest GC watermark ever applied: a deployment
    /// replaying this stream (an external-WAL consumer, a CDC replica) must
    /// keep its compaction watermark at or below the lowest cursor it may
    /// still rewind to, exactly as `docs/external-wal.md` section 4's
    /// GC-coordination rules require. The watermark is caller-supplied and
    /// not persisted, so this method cannot detect a violation for you.
    ///
    /// # Block-skip
    ///
    /// On SSTs written with the `seqno_bounds` section (`seqno_in_index`), data
    /// blocks whose bounds cannot overlap the target window are skipped without
    /// being read; SSTs without the section are read and filtered per entry, so
    /// mixed trees are handled transparently.
    ///
    /// # KV-separation
    ///
    /// Standard trees never store blob-indirected values. On the inner tree of
    /// a KV-separated (blob) tree this returns an `Err` for indirected entries:
    /// blob resolution into [`ScanSinceEvent::Insert`] is provided by the
    /// blob-tree scan path, which owns the blob files.
    ///
    /// # Corruption resilience
    ///
    /// The per-block seqno-bounds used for skipping live in the optional
    /// `seqno_bounds` SST section, a Block covered by XXH3-128 (+ optional Page
    /// ECC) and verified when it is loaded at open, plus a decode that rejects
    /// non-ascending offsets and inverted bounds, so a corrupted bound is caught
    /// rather than trusted. Even in the impossible case of a fault bypassing
    /// those checks, a bad bound can only cause a *missed* record, never a wrong
    /// one. Callers who want defense against that hypothetical can use
    /// [`Self::scan_since_seqno_full_scan`], which reads every block (slower, no
    /// skip).
    ///
    /// # Panics
    ///
    /// Panics if the internal version-history lock is poisoned.
    ///
    /// # Errors
    ///
    /// Returns `Err` if reading the index or a data block fails, or if an entry
    /// is a KV-separated value (see above).
    pub fn scan_since_seqno(
        &self,
        target_seqno: SeqNo,
    ) -> crate::Result<impl Iterator<Item = ScanSinceEvent> + use<>> {
        // A standard tree never stores blob-indirected values; the resolver
        // errors so an indirected entry (only reachable via a blob tree's inner
        // index) surfaces as a clear error rather than a wrong event.
        self.scan_since_seqno_with(target_seqno, true, |_version, _entry| {
            Err(crate::Error::FeatureUnsupported(
                "scan_since_seqno on KV-separated values requires the blob-tree scan path",
            ))
        })
    }

    /// Paranoid variant of [`Self::scan_since_seqno`] that disables the
    /// per-block seqno-bounds skip: every data block is read and filtered per
    /// entry, even on seqno-indexed SSTs.
    ///
    /// # When to use
    ///
    /// The fast [`Self::scan_since_seqno`] trusts each block's recorded
    /// `[seqno_min, seqno_max]` to skip blocks that cannot hold a qualifying
    /// record. Those bounds live in the `seqno_bounds` SST section, a Block
    /// covered by XXH3-128 (and optional Page ECC) and verified at open, so
    /// on-disk corruption is caught, not silently trusted. This method exists
    /// for callers who
    /// want defense even against a fault that somehow bypassed those checks: a
    /// corrupted `seqno_max` can only ever cause a *missed* record (never a
    /// wrong one), and a full scan cannot miss. It is slower (no skip), so
    /// prefer [`Self::scan_since_seqno`] unless you specifically need this
    /// guarantee.
    ///
    /// # Panics
    ///
    /// Panics if the internal version-history lock is poisoned.
    ///
    /// # Errors
    ///
    /// Same as [`Self::scan_since_seqno`].
    pub fn scan_since_seqno_full_scan(
        &self,
        target_seqno: SeqNo,
    ) -> crate::Result<impl Iterator<Item = ScanSinceEvent> + use<>> {
        self.scan_since_seqno_with(target_seqno, false, |_version, _entry| {
            Err(crate::Error::FeatureUnsupported(
                "scan_since_seqno on KV-separated values requires the blob-tree scan path",
            ))
        })
    }

    /// Range-scoped variant of [`Self::scan_since_seqno`]: delivers only
    /// events whose key falls within `range` (in the tree comparator's
    /// order); range-deletion events are delivered when their span OVERLAPS
    /// it, since a tombstone reaching into the range affects replay within
    /// it. SSTs whose key range cannot intersect the bounds are skipped
    /// without a single block read.
    ///
    /// This is the presence-check primitive for reconciling an external
    /// write-ahead log after a repair: [`RepairReport::lost_coverage`] names
    /// the affected key ranges, and deciding which retained WAL records to
    /// re-apply (in particular, which merge operands SURVIVED and must not be
    /// folded twice) only needs the events inside those ranges. See
    /// `docs/external-wal.md` § Replay after repair.
    ///
    /// The history-retention caveat of [`Self::scan_since_seqno`] applies
    /// unchanged: the stream is complete only for a `target_seqno` at or
    /// above the highest compaction GC watermark ever applied.
    ///
    /// [`RepairReport::lost_coverage`]: crate::RepairReport::lost_coverage
    ///
    /// # Panics
    ///
    /// Panics if the internal version-history lock is poisoned.
    ///
    /// # Errors
    ///
    /// Same as [`Self::scan_since_seqno`].
    pub fn scan_since_seqno_in_range<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        target_seqno: SeqNo,
        range: R,
    ) -> crate::Result<impl Iterator<Item = ScanSinceEvent> + use<K, R>> {
        let bounds = range_to_user_bounds(&range);
        self.scan_since_seqno_scoped(
            target_seqno,
            true,
            |_version, _entry| {
                Err(crate::Error::FeatureUnsupported(
                    "scan_since_seqno on KV-separated values requires the blob-tree scan path",
                ))
            },
            Some(&bounds),
        )
    }

    /// Update the live [`crate::runtime_config::RuntimeConfig`].
    ///
    /// Mutator runs on a clone of the current snapshot; the new snapshot
    /// is then atomically swapped in. Subsequent calls to
    /// [`Self::runtime_config`] observe the new snapshot.
    ///
    /// ## Semantics
    ///
    /// - Write paths (flush, compaction, ingestion) take one snapshot when
    ///   they start and use it throughout, so a change applies to the next
    ///   one and never splits a single file between two configurations.
    /// - Existing on-disk data remains in its original format and reads
    ///   transparently: every block, manifest and blob file is
    ///   self-describing via its own header or descriptor. That includes
    ///   the compression policies, so changing one rewrites nothing.
    /// - Compaction acts as the live-migration mechanism: source blocks
    ///   are rewritten per the current snapshot over subsequent cycles,
    ///   so all data converges to the current settings without
    ///   stop-the-world coordination.
    ///
    /// ## Concurrency
    ///
    /// **Reader atomicity:** concurrent readers observe either the old
    /// or the new snapshot, never a torn intermediate state.
    ///
    /// **Writer semantics: last-writer-wins.** Two `update` calls racing
    /// from the same starting snapshot will have the second `store`
    /// overwrite the first — the first writer's mutation is lost. There
    /// is no CAS / RCU merge. Callers that need lost-update avoidance
    /// (e.g. two threads concurrently toggling different fields) MUST
    /// serialize their `update_runtime_config` calls, typically via a
    /// `Mutex` around the call site.
    /// # Errors
    ///
    /// Returns [`crate::Error::PageEccUnsupported`] when the mutator
    /// leaves `page_ecc = true` on a binary built without the
    /// `page_ecc` cargo feature, and
    /// [`crate::Error::ZstdDictMismatch`] when a compression policy names a
    /// dictionary the tree does not hold (register it first with
    /// `Self::register_zstd_dictionary`). The live snapshot stays at its
    /// pre-mutation value on error.
    pub fn update_runtime_config<F>(&self, mutator: F) -> crate::Result<()>
    where
        F: FnOnce(&mut crate::runtime_config::RuntimeConfig),
    {
        // The mutator is the caller's code and may read the tree, so it runs
        // before any lock is taken: under the version lock a read of the
        // version history would wait on this thread forever.
        let mut next = (*self.0.runtime_config.load_full()).clone();
        mutator(&mut next);

        // Under the version lock, which a dictionary collection holds for its
        // whole pass: checking a policy against the tree's dictionaries and
        // publishing it must not interleave with a collection that takes the
        // one it names.
        #[cfg(zstd_any)]
        let version_lock = self.version_history.write();
        #[cfg(zstd_any)]
        next.check_dictionaries(
            self.config.kv_separation_opts.is_some(),
            &self.config.current_zstd_dictionaries(),
        )?;
        // What the swap below replaces, read under the lock every update takes,
        // so it is the snapshot a writer may still hold, not the one the
        // mutator started from.
        #[cfg(zstd_any)]
        let replaced = self.0.runtime_config.load_full();
        // The heal gate below follows exactly the config THIS call commits,
        // rather than a separate `load_full()` that could observe a different
        // concurrent update's value. Concurrent `update_runtime_config` calls
        // must be serialized by the caller (see the last-writer-wins note
        // above); under that contract the gate and the committed config stay in
        // sync. On a validation error nothing is committed and `?` returns
        // before the gate is touched, so it keeps tracking the unchanged config.
        let auto_heal = next.auto_heal;
        // Route through the validating handle path so an invalid mutation
        // (e.g. `page_ecc = true` on a non-`page_ecc` build) is rejected at
        // update time, not silently swallowed at the next manifest write.
        self.0.runtime_config.try_update(|c| *c = next)?;

        // A writer that took `replaced` before this swap may still be about to
        // resolve the dictionary it names; see `retired_write_snapshots`.
        #[cfg(zstd_any)]
        {
            let kv_separated = self.config.kv_separation_opts.is_some();
            if replaced.write_dict_ids(kv_separated).next().is_some() {
                let mut retired = self.0.retired_write_snapshots.lock();
                retired.retain(|snapshot| snapshot.strong_count() > 0);
                retired.push(Arc::downgrade(&replaced));
            }
            drop(replaced);
            drop(version_lock);
        }
        self.0.heal_hints.set_enabled(auto_heal);
        // Mirror the insert-time digest gate for the write hot path (see
        // `TreeInner::kv_digest_at_insert`). Relaxed: a toggle taking effect
        // on the next inserts is the documented contract (mixed inserts are
        // supported), so no ordering against other memory is needed.
        let gate = inner::kv_digest_at_insert_gate(&self.0.runtime_config.load());
        self.0
            .kv_digest_at_insert
            .store(gate, core::sync::atomic::Ordering::Relaxed);
        // Drop the cached admission footprint so the next check re-probes
        // disk-free: an operator who just raised the budget (or freed disk)
        // should see it promptly, not at the next flush.
        *self.0.admission_used_cache.lock() = None;
        Ok(())
    }

    /// Snapshot of the current runtime config. Cheap atomic load —
    /// safe to call on hot paths.
    #[must_use]
    pub fn runtime_config(&self) -> Arc<crate::runtime_config::RuntimeConfig> {
        self.0.runtime_config.load_full()
    }

    /// Shared handle to this tree's ECC heal-hint queue.
    ///
    /// A read that recovers a block from Page-ECC parity records the owning SST
    /// here (when the on-disk fault is confirmed persistent). Pass the handle to
    /// [`compaction::EccHeal`](crate::compaction::EccHeal) and run that strategy
    /// via [`Tree::compact`](crate::AbstractTree::compact) — leader-only in a
    /// clustered deployment — to rewrite the flagged SSTs clean. Check
    /// [`HealHints::is_empty`](crate::heal_hints::HealHints::is_empty) to skip
    /// the pass when nothing is queued.
    ///
    /// # Examples
    ///
    /// ```no_run
    /// use lsm_tree::{AbstractTree, AnyTree, Config, SequenceNumberCounter, compaction::EccHeal};
    /// use std::sync::Arc;
    /// # fn main() -> lsm_tree::Result<()> {
    /// let AnyTree::Standard(tree) = Config::new(
    ///     "/tmp/db",
    ///     SequenceNumberCounter::default(),
    ///     SequenceNumberCounter::default(),
    /// )
    /// .open()?
    /// else {
    ///     return Ok(());
    /// };
    ///
    /// // Opt into rewrite scheduling; reads that recover a block from parity now
    /// // flag its SST for healing.
    /// tree.update_runtime_config(|c| c.auto_heal = true)?;
    ///
    /// // Drain the queue, rewriting each flagged SST clean (leader-only in a
    /// // clustered deployment).
    /// let hints = tree.heal_hints();
    /// while !hints.is_empty() {
    ///     tree.compact(Arc::new(EccHeal::new(tree.heal_hints(), u64::MAX)), 0)?;
    /// }
    /// # Ok(())
    /// # }
    /// ```
    #[must_use]
    pub fn heal_hints(&self) -> Arc<crate::heal_hints::HealHints> {
        Arc::clone(&self.0.heal_hints)
    }

    /// Starts a multi-get of `keys` at `seqno` that its caller drives: the
    /// read hands out its block reads and jobs instead of carrying them out,
    /// so the calling thread is never parked inside it. It answers what
    /// [`AbstractTree::multi_get`] answers at the moment it starts: what is
    /// written while it is suspended is not part of its answer, even at a
    /// ceiling such as [`SeqNo::MAX`](crate::SeqNo).
    ///
    /// # Errors
    ///
    /// Returns [`crate::Error::SnapshotBelowRetention`] when `seqno` is below
    /// what the tree retains.
    ///
    /// # Examples
    ///
    /// Driving the read on the calling thread:
    ///
    /// ```
    /// use lsm_tree::resumable::Step;
    /// use lsm_tree::{AbstractTree, Config, SequenceNumberCounter};
    ///
    /// # let folder = tempfile::tempdir()?;
    /// let tree = Config::new(&folder, SequenceNumberCounter::default(), SequenceNumberCounter::default()).open()?;
    /// tree.insert("a", "1", 0);
    /// tree.flush_active_memtable(0)?;
    ///
    /// let mut step = tree.start_multi_get(["a", "b"], 1)?;
    /// let values = loop {
    ///     let mut read = match step {
    ///         Step::Done(values) => break values?,
    ///         Step::Pending(read) => read,
    ///     };
    ///     for job in read.take_jobs() {
    ///         let outcome = job.run();
    ///         read.complete_job(outcome);
    ///     }
    ///     for mut block in read.take_reads() {
    ///         let result = block.file.read_at(&mut block.buf, block.offset).and_then(|n| {
    ///             if n == block.buf.len() { Ok(()) } else { Err(lsm_tree::io::ErrorKind::UnexpectedEof.into()) }
    ///         });
    ///         read.complete_read(block.tag, result, block.buf);
    ///     }
    ///     step = read.resume();
    /// };
    /// assert_eq!(values, [Some("1".as_bytes().into()), None]);
    /// # Ok::<(), lsm_tree::Error>(())
    /// ```
    pub fn start_multi_get<K: Into<UserKey>>(
        &self,
        keys: impl IntoIterator<Item = K>,
        seqno: SeqNo,
    ) -> crate::Result<resumable::Step> {
        let snapshot = self.snapshot_for_read(seqno)?;
        let seqno = Self::read_ceiling(&snapshot, seqno);
        let keys: Vec<UserKey> = keys.into_iter().map(Into::into).collect();
        // Each key a point lookup, counted once as the read starts, not on
        // every resume.
        snapshot
            .version
            .read_mix()
            .note_points(u64::try_from(keys.len()).unwrap_or(u64::MAX));
        Ok(resumable::ResumableMultiGet::start(read_job::ReadCtx {
            super_version: crate::version::SnapshotRef::Owned((*snapshot).clone()),
            keys,
            seqno,
            comparator: Arc::clone(&self.config.comparator),
            merge_operator: self.config.merge_operator.clone(),
            merge_base: self.blob_source(),
            values: read_job::Values::Inline,
            metadata_budget: self.config.multi_get_metadata_budget,
        }))
    }

    /// The seqno a read started at `seqno` on `snapshot` reads at for its whole
    /// life: at most one past the newest seqno the snapshot holds. The active
    /// memtable the snapshot shares keeps taking writes, and a read that is
    /// suspended still checks range deletions and merges against it after
    /// it started; what lands there at a higher seqno is then not part of its
    /// answer, which stays what the tree held when it started.
    pub(crate) fn read_ceiling(snapshot: &SuperVersion, seqno: SeqNo) -> SeqNo {
        // Past the newest seqno; nothing is newer than the largest one.
        let next = |newest: SeqNo| newest.checked_add(1).unwrap_or(SeqNo::MAX);
        let memtables = snapshot.active_memtable.get_highest_seqno().max(
            snapshot
                .sealed_memtables
                .iter()
                .map(|mt| mt.get_highest_seqno())
                .max()
                .flatten(),
        );
        // A ceiling the memtables already reach admits nothing newer: the
        // tables need not be looked at.
        if memtables.is_some_and(|newest| next(newest) >= seqno) {
            return seqno;
        }
        let tables = snapshot
            .version
            .iter_tables()
            .map(Table::get_highest_seqno)
            .max();
        // An empty snapshot holds nothing a read could see.
        memtables
            .max(tables)
            .map_or(0, |newest| seqno.min(next(newest)))
    }

    /// Shared point-read logic for `get()` and `multi_get()`: finds the newest
    /// entry, applies merge resolution or RT suppression, and returns the value.
    ///
    /// `blob_source` is asked for only by a merge, for a base kept in the
    /// value log.
    fn resolve_or_passthrough(
        super_version: &SuperVersion,
        key: &[u8],
        seqno: SeqNo,
        merge_operator: Option<&Arc<dyn crate::merge_operator::MergeOperator>>,
        comparator: &dyn crate::comparator::UserComparator,
        blob_source: impl FnOnce() -> Option<crate::blob_tree::BlobSource>,
    ) -> crate::Result<Option<UserValue>> {
        let entry = Self::get_value(super_version, key, seqno, comparator)?;

        match entry {
            Some((ValueType::MergeOperand, entry_seqno, value)) => {
                if let Some(merge_op) = merge_operator {
                    Self::resolve_point_merge(
                        super_version,
                        key,
                        seqno,
                        merge_op,
                        blob_source().as_ref(),
                    )
                } else if Self::is_suppressed_by_range_tombstones(
                    super_version,
                    key,
                    entry_seqno,
                    seqno,
                    comparator,
                ) {
                    Ok(None)
                } else {
                    Ok(Some(value))
                }
            }
            Some((_, _, value)) => Ok(Some(value)),
            None => Ok(None),
        }
    }

    /// Shared post-lookup resolution for `get_pinned` and `multi_get`:
    /// tombstone filter, range-tombstone suppression, merge operand resolution.
    /// Returns `None` if entry is tombstoned or suppressed.
    #[expect(
        clippy::too_many_arguments,
        reason = "each is a separate input of the one resolution"
    )]
    fn resolve_pinned_entry(
        super_version: &SuperVersion,
        key: &[u8],
        entry: InternalValue,
        seqno: SeqNo,
        merge_operator: Option<&Arc<dyn crate::merge_operator::MergeOperator>>,
        comparator: &dyn crate::comparator::UserComparator,
        wrap: impl FnOnce(UserValue) -> crate::PinnableSlice,
        blob_source: impl FnOnce() -> Option<crate::blob_tree::BlobSource>,
    ) -> crate::Result<Option<crate::PinnableSlice>> {
        use crate::PinnableSlice;

        let Some(entry) = ignore_tombstone_value(entry) else {
            return Ok(None);
        };
        if Self::is_suppressed_by_range_tombstones(
            super_version,
            key,
            entry.key.seqno,
            seqno,
            comparator,
        ) {
            return Ok(None);
        }
        if entry.key.value_type == ValueType::MergeOperand
            && let Some(merge_op) = merge_operator
        {
            // A merged value is built anew, so it is Owned.
            return Self::resolve_point_merge(
                super_version,
                key,
                seqno,
                merge_op,
                blob_source().as_ref(),
            )
            .map(|opt| opt.map(PinnableSlice::owned));
        }
        Ok(Some(wrap(entry.value)))
    }

    /// Like [`Tree::resolve_or_passthrough`], but returns a [`PinnableSlice`](crate::PinnableSlice)
    /// that may keep the decompressed block buffer alive.
    fn resolve_or_passthrough_pinned(
        super_version: &SuperVersion,
        key: &[u8],
        seqno: SeqNo,
        merge_operator: Option<&Arc<dyn crate::merge_operator::MergeOperator>>,
        comparator: &dyn crate::comparator::UserComparator,
        blob_source: impl FnOnce() -> Option<crate::blob_tree::BlobSource>,
    ) -> crate::Result<Option<crate::PinnableSlice>> {
        use crate::PinnableSlice;

        // Check memtables first — always Owned
        if let Some(entry) = super_version.active_memtable.get(key, seqno) {
            return Self::resolve_pinned_entry(
                super_version,
                key,
                entry,
                seqno,
                merge_operator,
                comparator,
                PinnableSlice::owned,
                blob_source,
            );
        }

        // Sealed memtables — always Owned
        if let Some(entry) =
            Self::get_internal_entry_from_sealed_memtables(super_version, key, seqno)
        {
            return Self::resolve_pinned_entry(
                super_version,
                key,
                entry,
                seqno,
                merge_operator,
                comparator,
                PinnableSlice::owned,
                blob_source,
            );
        }

        // Tables — Pinned (value shares decompressed block buffer)
        let key_hash = crate::hash::hash64(key);

        if let Some((entry, block)) = Self::get_internal_entry_with_block_from_tables(
            &super_version.version,
            key,
            seqno,
            key_hash,
            comparator,
        )? {
            return Self::resolve_pinned_entry(
                super_version,
                key,
                entry,
                seqno,
                merge_operator,
                comparator,
                |value| PinnableSlice::pinned(block, value),
                blob_source,
            );
        }

        Ok(None)
    }

    /// Like [`Tree::get_internal_entry_from_tables`], but returns the block
    /// along with the entry for pinned zero-copy access.
    fn get_internal_entry_with_block_from_tables(
        version: &Version,
        key: &[u8],
        seqno: SeqNo,
        key_hash: u64,
        comparator: &dyn crate::comparator::UserComparator,
    ) -> crate::Result<Option<(InternalValue, crate::table::Block)>> {
        Self::find_in_tables::<TableEntryWithBlock>(version, key, seqno, key_hash, comparator)
    }

    /// Where this tree's values kept in the value log are read from; only the
    /// index of a blob tree has any.
    pub(crate) fn blob_source(&self) -> Option<crate::blob_tree::BlobSource> {
        self.config
            .kv_separation_opts
            .is_some()
            .then(|| crate::blob_tree::BlobSource {
                tree_id: self.id,
                cache: Arc::clone(&self.config.cache),
                fill: self.runtime_config.load().blob_cache_fill,
                #[cfg(feature = "metrics")]
                metrics: Arc::clone(&self.0.metrics),
            })
    }

    /// Resolves the merge of `key` for a point read whose newest visible
    /// version is an operand: reads the sources newest first and stops at the
    /// first base, so a table below it is never opened.
    ///
    /// `blob_source` reads a base kept in the value log, which only a blob
    /// tree's index holds.
    pub(crate) fn resolve_point_merge(
        super_version: &SuperVersion,
        key: &[u8],
        seqno: SeqNo,
        merge_operator: &Arc<dyn crate::merge_operator::MergeOperator>,
        blob_source: Option<&crate::blob_tree::BlobSource>,
    ) -> crate::Result<Option<UserValue>> {
        Ok(crate::range::resolve_point_merge(
            super_version,
            key,
            seqno,
            merge_operator,
            blob_source,
        )?
        .map(|entry| entry.value))
    }

    #[doc(hidden)]
    pub fn create_internal_range<'a, K: AsRef<[u8]> + 'a, R: RangeBounds<K> + 'a>(
        version: SuperVersion,
        range: &'a R,
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
        merge_operator: Option<Arc<dyn crate::merge_operator::MergeOperator>>,
        comparator: crate::comparator::SharedComparator,
    ) -> impl DoubleEndedIterator<Item = crate::Result<InternalValue>> + 'static {
        Self::create_internal_range_with_prefix_hash(
            version,
            range,
            seqno,
            ephemeral,
            merge_operator,
            comparator,
            None,
            None,
        )
    }

    /// Like [`Tree::create_internal_range`], but with an optional prefix hash
    /// for prefix bloom filter skipping during prefix scans, and the
    /// `blob_source` a merge reads a base kept in the value log from.
    #[doc(hidden)]
    #[expect(
        clippy::too_many_arguments,
        reason = "each is a separate input of the iterator it builds"
    )]
    pub(crate) fn create_internal_range_with_prefix_hash<
        'a,
        K: AsRef<[u8]> + 'a,
        R: RangeBounds<K> + 'a,
    >(
        version: SuperVersion,
        range: &'a R,
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
        merge_operator: Option<Arc<dyn crate::merge_operator::MergeOperator>>,
        comparator: crate::comparator::SharedComparator,
        prefix_hash: Option<u64>,
        blob_source: Option<crate::blob_tree::BlobSource>,
    ) -> impl DoubleEndedIterator<Item = crate::Result<InternalValue>> + 'static {
        use crate::range::{IterState, TreeIter};
        use core::ops::Bound::{self, Excluded, Included, Unbounded};

        let lo: Bound<UserKey> = match range.start_bound() {
            Included(x) => Included(x.as_ref().into()),
            Excluded(x) => Excluded(x.as_ref().into()),
            Unbounded => Unbounded,
        };

        let hi: Bound<UserKey> = match range.end_bound() {
            Included(x) => Included(x.as_ref().into()),
            Excluded(x) => Excluded(x.as_ref().into()),
            Unbounded => Unbounded,
        };

        let bounds: (Bound<UserKey>, Bound<UserKey>) = (lo, hi);

        let iter_state = IterState {
            version,
            ephemeral,
            merge_operator,
            blob_source,
            comparator,
            prefix_hash,
            #[cfg(feature = "metrics")]
            metrics: None,
        };

        TreeIter::create_range(iter_state, bounds, seqno)
    }

    pub(crate) fn get_internal_entry_from_version(
        super_version: &SuperVersion,
        key: &[u8],
        seqno: SeqNo,
        comparator: &dyn crate::comparator::UserComparator,
    ) -> crate::Result<Option<InternalValue>> {
        // Search order: active → sealed → SST (newest first). A point
        // tombstone in a newer source is authoritative — no older source
        // can contain a newer value, so returning None is correct.
        if let Some(entry) = super_version.active_memtable.get(key, seqno) {
            let Some(entry) = ignore_tombstone_value(entry) else {
                return Ok(None);
            };

            // Check if any range tombstone suppresses this entry
            if Self::is_suppressed_by_range_tombstones(
                super_version,
                key,
                entry.key.seqno,
                seqno,
                comparator,
            ) {
                return Ok(None);
            }
            return Ok(Some(entry));
        }

        // Now look in sealed memtables
        if let Some(entry) =
            Self::get_internal_entry_from_sealed_memtables(super_version, key, seqno)
        {
            let Some(entry) = ignore_tombstone_value(entry) else {
                return Ok(None);
            };

            if Self::is_suppressed_by_range_tombstones(
                super_version,
                key,
                entry.key.seqno,
                seqno,
                comparator,
            ) {
                return Ok(None);
            }
            return Ok(Some(entry));
        }

        // Now look in tables... this may involve disk I/O
        let entry =
            Self::get_internal_entry_from_tables(&super_version.version, key, seqno, comparator)?;

        if let Some(entry) = entry {
            if Self::is_suppressed_by_range_tombstones(
                super_version,
                key,
                entry.key.seqno,
                seqno,
                comparator,
            ) {
                return Ok(None);
            }
            return Ok(Some(entry));
        }

        Ok(None)
    }

    /// Value-only mirror of [`Self::get_internal_entry_from_version`].
    ///
    /// Returns `(value_type, seqno, value)` for the newest visible entry without
    /// reconstructing the entry key. Same search order (active -> sealed -> SST,
    /// newest first), tombstone filtering, and range-tombstone suppression; only
    /// the SST path differs, using the value-only [`TableValue`] lookup that
    /// skips the delta-key fusion of the full `InternalValue` path. Used by the
    /// value-returning `get` path, which never reads the matched key.
    pub(crate) fn get_value(
        super_version: &SuperVersion,
        key: &[u8],
        seqno: SeqNo,
        comparator: &dyn crate::comparator::UserComparator,
    ) -> crate::Result<Option<(ValueType, SeqNo, crate::Slice)>> {
        if let Some(entry) = super_version.active_memtable.get(key, seqno) {
            let Some(entry) = ignore_tombstone_value(entry) else {
                return Ok(None);
            };
            if Self::is_suppressed_by_range_tombstones(
                super_version,
                key,
                entry.key.seqno,
                seqno,
                comparator,
            ) {
                return Ok(None);
            }
            return Ok(Some((entry.key.value_type, entry.key.seqno, entry.value)));
        }

        if let Some(entry) =
            Self::get_internal_entry_from_sealed_memtables(super_version, key, seqno)
        {
            let Some(entry) = ignore_tombstone_value(entry) else {
                return Ok(None);
            };
            if Self::is_suppressed_by_range_tombstones(
                super_version,
                key,
                entry.key.seqno,
                seqno,
                comparator,
            ) {
                return Ok(None);
            }
            return Ok(Some((entry.key.value_type, entry.key.seqno, entry.value)));
        }

        let key_hash = crate::hash::hash64(key);
        let entry = Self::find_in_tables::<TableValue>(
            &super_version.version,
            key,
            seqno,
            key_hash,
            comparator,
        )?;
        if let Some((value_type, entry_seqno, value)) = entry {
            if Self::is_suppressed_by_range_tombstones(
                super_version,
                key,
                entry_seqno,
                seqno,
                comparator,
            ) {
                return Ok(None);
            }
            return Ok(Some((value_type, entry_seqno, value)));
        }

        Ok(None)
    }

    /// Checks if a key at `key_seqno` is suppressed by any range tombstone
    /// in the active memtable, sealed memtables, or SST tables, visible at `read_seqno`.
    pub(crate) fn is_suppressed_by_range_tombstones(
        super_version: &SuperVersion,
        key: &[u8],
        key_seqno: SeqNo,
        read_seqno: SeqNo,
        comparator: &dyn crate::comparator::UserComparator,
    ) -> bool {
        // Check active memtable range tombstones.
        // Future optimization: skip lock when memtable has no RTs (atomic count).
        if super_version
            .active_memtable
            .is_key_suppressed_by_range_tombstone(key, key_seqno, read_seqno)
        {
            return true;
        }

        // Check sealed memtable range tombstones
        for mt in super_version.sealed_memtables.iter().rev() {
            if mt.is_key_suppressed_by_range_tombstone(key, key_seqno, read_seqno) {
                return true;
            }
        }

        // Check SST table range tombstones.
        //
        // Per-table RT lists are sorted by start key (using comparator) on load,
        // so binary search narrows candidates to RTs with start <= key. A
        // table's key range does not bound its tombstones (a compaction cuts
        // them at the next output's first key without widening the range up
        // to it), so the stretch they cover rejects a table instead: from the
        // first one's start to the greatest end, two compares.
        for table in super_version
            .version
            .iter_levels()
            .flat_map(|lvl| lvl.iter())
            .filter(|run| run.holds_range_tombstones())
            .flat_map(|run| run.iter())
        {
            let rts = table.range_tombstones();
            let (Some(first), Some(end)) = (rts.first(), table.range_tombstones_end()) else {
                continue;
            };
            if comparator.compare(&first.start, key) == core::cmp::Ordering::Greater
                || comparator.compare(key, end) != core::cmp::Ordering::Less
            {
                continue;
            }

            // Binary search: find the first RT whose start is > key (in comparator order).
            // All RTs before that index have start <= key and are candidates.
            let candidate_end = rts.partition_point(|rt| {
                comparator.compare(&rt.start, key) != core::cmp::Ordering::Greater
            });

            for rt in rts.iter().take(candidate_end) {
                // start <= key holds by the search; the seqno checks are
                // cheaper than the key compare, so they go first.
                if key_seqno < rt.seqno
                    && rt.visible_at(read_seqno)
                    && comparator.compare(key, &rt.end) == core::cmp::Ordering::Less
                {
                    return true;
                }
            }
        }

        false
    }

    /// De-duplicates equal query keys in a comparator-sorted `remaining` index
    /// list, returning the `(key_index, bloom_hash)` pairs for the batched
    /// on-disk resolver (which requires strictly-sorted-unique input) and a
    /// `(duplicate_index, representative_index)` map. Pair with
    /// [`Self::fan_out_duplicates`] after the batch resolves.
    ///
    /// Shared by [`Self::multi_get`] and the `BlobTree` multi-get so the two
    /// cannot silently diverge: forwarding duplicate miss keys into the
    /// strictly-sorted-unique resolver was exactly the regression class this
    /// guards against. `remaining` must already be sorted by `comparator`.
    #[expect(
        clippy::indexing_slicing,
        reason = "remaining/miss_keys carry batch-local key indices < keys.len()"
    )]
    pub(crate) fn dedup_sorted_miss_keys<K: AsRef<[u8]>>(
        remaining: &[usize],
        keys: &[K],
        comparator: &dyn crate::comparator::UserComparator,
    ) -> DedupedMissKeys {
        let mut miss_keys: Vec<(usize, u64)> = Vec::with_capacity(remaining.len());
        let mut duplicates: Vec<(usize, usize)> = Vec::new();
        for &idx in remaining {
            let key = keys[idx].as_ref();
            match miss_keys.last() {
                Some(&(rep_idx, _))
                    if comparator.compare(keys[rep_idx].as_ref(), key)
                        == core::cmp::Ordering::Equal =>
                {
                    duplicates.push((idx, rep_idx));
                }
                _ => miss_keys.push((idx, crate::hash::hash64(key))),
            }
        }
        (miss_keys, duplicates)
    }

    /// Fans each representative's answer out to its duplicate positions, so
    /// every input slot carries the same answer the per-key path would have
    /// produced. Counterpart to [`Self::dedup_sorted_miss_keys`]; call once the
    /// representatives' answers are in `answers`.
    #[expect(
        clippy::indexing_slicing,
        reason = "duplicate/representative indices are batch-local key indices < answers.len()"
    )]
    pub(crate) fn fan_out_duplicates<T: Clone>(
        duplicates: &[(usize, usize)],
        answers: &mut [Option<T>],
    ) {
        for &(dup_idx, rep_idx) in duplicates {
            let resolved = answers[rep_idx].clone();
            answers[dup_idx] = resolved;
        }
    }

    /// Resolves the keys of `remaining` (sorted under `comparator`) against
    /// `level` key by key, run by run, and returns the versions found by key
    /// index and the keys left for the levels below, still sorted.
    ///
    /// On level 0, and on a deeper level of several runs, every run is
    /// checked and the highest seqno per key kept; a key found at the read's
    /// ceiling skips the later runs, which cannot beat it. On a level of one
    /// run, the table covering a key answers it for the whole level.
    ///
    /// # Errors
    ///
    /// The first read of a table that fails.
    #[expect(
        clippy::indexing_slicing,
        reason = "remaining's indices are valid key indices, and `found` and `at_ceiling` are as long as `keys`"
    )]
    fn resolve_level_serially<K: AsRef<[u8]>>(
        level_zero: bool,
        level: &crate::version::Level,
        mut remaining: Vec<(usize, u64)>,
        keys: &[K],
        seqno: SeqNo,
        comparator: &dyn crate::comparator::UserComparator,
    ) -> crate::Result<tables_read::SerialLevel> {
        // A deeper level a tiered layout leaves overlapping runs in is read as
        // L0 is: a key's covering table in one run may miss it while an older
        // run holds it.
        if level_zero || level.run_count() > 1 {
            // L0: must check ALL runs, keep highest seqno per key. Track keys
            // at the seqno ceiling (seqno + 1 == read_seqno): no other L0 run
            // can beat them, so skip them in subsequent runs. Both are dense
            // over 0..keys.len().
            let mut found: Vec<Option<InternalValue>> = vec![None; keys.len()];
            let mut at_ceiling = vec![false; keys.len()];

            for run in level.iter() {
                // `at_ceiling` is read as this run's skip set (a key is visited
                // once per run, so the updates below only affect later runs)
                // and mutated from the returned outcomes: never both at once.
                let resolved =
                    Self::resolve_run_batched(run, &remaining, keys, seqno, comparator, |idx| {
                        at_ceiling[idx]
                    })?;
                for (idx, _hash, item) in resolved.covered {
                    let Some(item) = item else { continue };
                    match &found[idx] {
                        Some(current) if current.key.seqno >= item.key.seqno => {}
                        _ => {
                            if item.key.seqno.checked_add(1) == Some(seqno) {
                                at_ceiling[idx] = true;
                            }
                            found[idx] = Some(item);
                        }
                    }
                }
                // Uncovered keys stay in `remaining`; the retain below prunes
                // the ones any run resolved.
            }

            // Remove found keys (both values and tombstones)
            remaining.retain(|&(idx, _)| found[idx].is_none());
            let found = found
                .into_iter()
                .enumerate()
                .filter_map(|(idx, item)| Some((idx, item?)))
                .collect();
            return Ok((found, remaining));
        }

        // L1+ runs have non-overlapping key ranges within a level. A covering
        // run resolves a key definitively: a hit is found, a covering miss
        // drops it to lower levels (`covered_miss`), and an uncovered key
        // tries the next run in this level (`not_covered`).
        let mut found: Vec<(usize, InternalValue)> = Vec::new();
        let mut covered_miss: Vec<(usize, u64)> = Vec::new();

        for run in level.iter() {
            let resolved =
                Self::resolve_run_batched(run, &remaining, keys, seqno, comparator, |_| false)?;
            for (idx, hash, item) in resolved.covered {
                if let Some(item) = item {
                    found.push((idx, item));
                } else {
                    // Covering run found, key absent: no other run in this
                    // level can have it. Keep for lower levels.
                    covered_miss.push((idx, hash));
                }
            }
            remaining = resolved.not_covered;
        }

        // Merge back: keys without a covering run + keys with a covering miss
        // both proceed to lower levels. Re-sort to preserve comparator order
        // for the next level's sequential scan.
        let needs_sort = !covered_miss.is_empty();
        remaining.extend(covered_miss);
        if needs_sort {
            remaining
                .sort_by(|&(a, _), &(b, _)| comparator.compare(keys[a].as_ref(), keys[b].as_ref()));
        }
        Ok((found, remaining))
    }

    /// Resolves `remaining` (sorted ascending under `comparator`) against a
    /// single run with per-table batched gets instead of a per-key `table.get`:
    /// consecutive keys covered by the same table within the run share one
    /// [`Table::batch_get`], so co-located keys decode their data block once.
    /// Byte-identical to per-key resolution (the same point reads, the same
    /// values). `skip(idx)` omits a key (e.g. one already pinned at the L0 seqno
    /// ceiling, where no later run can beat it).
    ///
    /// Returns, per covered non-skipped key, `(idx, hash, resolved item)` in
    /// input order, plus the keys this run does not cover (also in input order)
    /// for the caller to pass to the next run or level.
    #[expect(
        clippy::indexing_slicing,
        reason = "i < remaining.len() is loop-checked; idx values are valid key indices (caller's keys/results are aligned, same as batch_get_from_tables)"
    )]
    fn resolve_run_batched<K: AsRef<[u8]>>(
        run: &crate::version::Run<crate::Table>,
        remaining: &[(usize, u64)],
        keys: &[K],
        seqno: SeqNo,
        comparator: &dyn crate::comparator::UserComparator,
        skip: impl Fn(usize) -> bool,
    ) -> crate::Result<RunResolve> {
        let mut covered: Vec<CoveredKey> = Vec::new();
        let mut not_covered: Vec<(usize, u64)> = Vec::new();

        // One pair of buffers reused across the run's tables, cleared per
        // table. Each is consumed before the next table fills it, so a fresh
        // Vec per table would only re-allocate the capacity the previous one
        // just released — once per table on a batched read path.
        let mut batch: Vec<(&[u8], u64)> = Vec::new();
        let mut batch_keys: Vec<(usize, u64)> = Vec::new();

        let mut i = 0;
        while i < remaining.len() {
            let (idx, hash) = remaining[i];
            if skip(idx) {
                i += 1;
                continue;
            }
            let key = keys[idx].as_ref();
            let Some(table) = run.get_for_key_cmp(key, comparator) else {
                not_covered.push((idx, hash));
                i += 1;
                continue;
            };

            // Gather the contiguous, non-skipped keys covered by THIS table. The
            // input is sorted and a run's tables partition the key space, so the
            // keys for one table form a contiguous slice; one `batch_get` drains
            // them with a single block decode for co-located keys.
            let table_id = table.id();
            batch.clear();
            batch_keys.clear();
            while i < remaining.len() {
                let (jdx, jhash) = remaining[i];
                if skip(jdx) {
                    i += 1;
                    continue;
                }
                let jkey = keys[jdx].as_ref();
                match run.get_for_key_cmp(jkey, comparator) {
                    Some(t) if t.id() == table_id => {
                        batch.push((jkey, jhash));
                        batch_keys.push((jdx, jhash));
                        i += 1;
                    }
                    _ => break,
                }
            }

            // `drain`, not `into_iter`: the buffer is reused by the next table,
            // so its capacity has to survive the walk. The lint assumes the
            // vector is dead afterwards, which is exactly what this is not.
            #[expect(
                clippy::iter_with_drain,
                reason = "buffer is reused across tables; into_iter would consume it"
            )]
            for ((kidx, khash), item) in batch_keys.drain(..).zip(table.batch_get(&batch, seqno)?) {
                covered.push((kidx, khash, item));
            }
        }

        Ok(RunResolve {
            covered,
            not_covered,
        })
    }

    /// The most of these `tables` whose files a level read holds open at
    /// once: what the smallest descriptor cache among them keeps, unbounded
    /// when their descriptors are pinned and open anyway.
    fn open_cap<'t>(tables: impl Iterator<Item = &'t Table>) -> usize {
        tables
            .filter_map(Table::descriptor_capacity)
            .min()
            .map_or(usize::MAX, |cap| {
                usize::try_from(cap).unwrap_or(usize::MAX).max(1)
            })
    }

    /// Reads the keys of `ctx` on the calling thread, through the memtables
    /// and the levels of its version, and turns each key's newest version
    /// into its value as its value source says: the multi-get of a standard
    /// tree and of a blob tree alike.
    ///
    /// # Errors
    ///
    /// The first failure of a level resolved key by key, or of the lowest
    /// key whose merge or blob read failed.
    pub(crate) fn read_many<K: AsRef<[u8]>>(
        ctx: &read_job::ReadCtx<K>,
    ) -> crate::Result<Vec<Option<UserValue>>> {
        // Each key of the batch is a point lookup of the read mix.
        ctx.super_version
            .version
            .read_mix()
            .note_points(u64::try_from(ctx.keys.len()).unwrap_or(u64::MAX));
        let mut read = multi_get_read::MultiGetRead::new(ctx);
        Self::drive(&mut read, ctx)
    }

    /// Drives a read of `ctx` to its end on the calling thread, and returns
    /// its answer. A block read goes to the read queue of the backend its
    /// table was opened through as it is asked for, and the queues hold the
    /// reads of a pass until the driver waits on them, so they go out
    /// together; jobs are run after the pass that asked for them, and the read
    /// moves on again before any wait. A read is handed back the moment it is
    /// in, while others may still be in flight: no table waits on the slowest
    /// file of the level.
    fn drive<'a, K: AsRef<[u8]>, M: read_job::ReadMachine<'a>>(
        level: &mut M,
        ctx: &read_job::ReadCtx<K>,
    ) -> M::Output {
        let mut sink = DriveSink {
            queues: Vec::new(),
            #[cfg(feature = "std")]
            wake: Arc::new(LevelWake {
                generation: core::sync::atomic::AtomicU64::new(0),
                sleeping: core::sync::atomic::AtomicBool::new(false),
                thread: std::thread::current(),
            }),
            jobs: Vec::new(),
            cache: None,
        };
        // The jobs being run; those their results ask for collect in the
        // sink meanwhile.
        let mut running: Vec<read_job::Job> = Vec::new();

        loop {
            if let Some(answer) = level.pump(&mut sink) {
                return answer;
            }
            if !sink.jobs.is_empty() {
                core::mem::swap(&mut running, &mut sink.jobs);
                #[expect(
                    clippy::iter_with_drain,
                    reason = "the two job lists trade places on every pass and keep their allocations; into_iter would consume one"
                )]
                for job in running.drain(..) {
                    level.job_done(job.run(ctx), &mut sink);
                }
                continue;
            }

            // A block is handed to its read the moment it is back.
            let mut on_done = |done: crate::fs::ReadDone| level.read_done(done);
            let cache = sink.cache;
            let queues = &mut sink.queues;
            #[cfg(feature = "std")]
            let wake = &sink.wake;
            // What has finished on any backend, without waiting. The wake's
            // generation is taken first, so a read back after this look is
            // seen by the sleep below.
            #[cfg(feature = "std")]
            let seen = wake.generation.load(core::sync::atomic::Ordering::SeqCst);
            let mut handed = 0usize;
            for q in queues.iter_mut() {
                q.queue.wait(0, &mut |done| {
                    handed += 1;
                    on_done(done);
                });
            }
            if handed > 0 {
                continue;
            }
            // Nothing is back. One backend still reading is waited on itself.
            // A level whose tables sit on several (after a route change, until
            // compaction moves them) sleeps until any of them has a read back,
            // so a fast backend's tables move on while a slow one is still
            // reading. A queue that cannot wake the level, or holds reads only
            // a wait carries out, is waited on itself.
            let must_wait = |q: &LevelQueue<'_>| !q.wakes || q.queue.held() > 0;
            let mut reading = queues.iter_mut().filter(|q| q.queue.outstanding() > 0);
            let Some(first) = reading.next() else {
                // Nothing in flight: the level moves on from what is back.
                continue;
            };
            let second = reading.next();
            if second.is_none() || must_wait(first) {
                Self::timed_wait(first.queue.as_mut(), cache, &mut on_done);
                continue;
            }
            if let Some(q) = second.into_iter().chain(reading).find(|q| must_wait(q)) {
                Self::timed_wait(q.queue.as_mut(), cache, &mut on_done);
                continue;
            }
            // Every queue still reading wakes the level, which only a queue
            // given the wake under `std` does.
            #[cfg(feature = "std")]
            {
                wake.sleeping
                    .store(true, core::sync::atomic::Ordering::SeqCst);
                while wake.generation.load(core::sync::atomic::Ordering::SeqCst) == seen {
                    std::thread::park();
                }
                wake.sleeping
                    .store(false, core::sync::atomic::Ordering::SeqCst);
            }
        }
    }

    /// Waits on `queue` for at least one read, handing each to `on_done`,
    /// and folds a sample of such waits into `cache`'s load-time estimate as
    /// the wait's length shared among the reads it handed back: what each
    /// read cost the storage, whether the queue reads them one after another
    /// or overlaps them in flight.
    fn timed_wait(
        queue: &mut dyn crate::fs::ReadQueue,
        cache: Option<&crate::cache::Cache>,
        on_done: &mut dyn FnMut(crate::fs::ReadDone),
    ) {
        let timer = crate::cache::Cache::time_load();
        let mut reads = 0usize;
        queue.wait(1, &mut |done| {
            reads += 1;
            on_done(done);
        });
        if let Some(cache) = cache {
            cache.record_batch_wait(timer, reads);
        }
    }

    /// Resolves the current version's level `level_idx` from its staged plan
    /// for `keys` on the calling thread, with the default comparator and
    /// metadata budget: `true` when it answered the level (results updated,
    /// found keys dropped from `still_remaining`), `false` when it hands the
    /// level to the serial resolve.
    #[cfg(test)]
    fn resolve_level_staged<K: AsRef<[u8]>>(
        &self,
        level_idx: usize,
        still_remaining: &mut Vec<(usize, u64)>,
        keys: Vec<K>,
        results: &mut [Option<InternalValue>],
    ) -> crate::Result<bool> {
        /// One level's resolve, answering into the caller's `results`.
        struct OneLevel<'a, 'r, K> {
            level: level_resolve::LevelResolve<'a, K>,
            results: &'r mut [Option<InternalValue>],
        }

        impl<'a, K: AsRef<[u8]>> read_job::ReadMachine<'a> for OneLevel<'a, '_, K> {
            type Output = bool;

            fn pump<S: read_job::ReadSink<'a>>(&mut self, out: &mut S) -> Option<bool> {
                match self.level.pump(self.results, out) {
                    level_resolve::LevelStep::Pending => None,
                    level_resolve::LevelStep::Resolved => Some(true),
                    level_resolve::LevelStep::Serial => Some(false),
                }
            }

            fn job_done<S: read_job::ReadSink<'a>>(
                &mut self,
                done: read_job::JobDone,
                out: &mut S,
            ) {
                self.level.job_done(done, out);
            }

            fn read_done(&mut self, done: crate::fs::ReadDone) {
                self.level.read_done(done);
            }
        }

        let ctx = read_job::ReadCtx {
            super_version: self.snapshot_for_read(SeqNo::MAX)?,
            keys,
            seqno: SeqNo::MAX,
            comparator: crate::comparator::default_comparator(),
            merge_operator: None,
            merge_base: None,
            values: read_job::Values::Inline,
            metadata_budget: crate::config::DEFAULT_MULTI_GET_METADATA_BUDGET,
        };
        let Some(level) = ctx.version().level(level_idx) else {
            return Ok(true);
        };
        let mut one = OneLevel {
            level: level_resolve::LevelResolve::new(
                level,
                level_idx,
                core::mem::take(still_remaining),
                &ctx.keys,
                ctx.comparator.as_ref(),
                ctx.seqno,
                ctx.metadata_budget,
            ),
            results,
        };
        let resolved = Self::drive(&mut one, &ctx);
        *still_remaining = one.level.into_remaining();
        Ok(resolved)
    }

    /// Counts, once per (table, key), the keys a table's filter let through
    /// that no read of that table found: a filter query and, where the read
    /// saw every version, a false positive, as a point read counts them.
    #[expect(
        clippy::indexing_slicing,
        reason = "task indices come from enumerating `tasks`"
    )]
    fn count_chunked_false_positives(
        tasks: &[BlockTask<'_>],
        mut found: Vec<(crate::TableId, usize)>,
    ) {
        found.sort_unstable();
        found.dedup();
        let mut missed: Vec<(crate::TableId, usize, usize)> = tasks
            .iter()
            .enumerate()
            .filter(|(_, task)| task.table.counts_filter_misses())
            .flat_map(|(at, task)| {
                task.keys
                    .iter()
                    .map(move |&(key, _)| (task.table.id(), key, at))
            })
            .filter(|&(table, key, _)| found.binary_search(&(table, key)).is_err())
            .collect();
        missed.sort_unstable_by_key(|&(table, key, _)| (table, key));
        missed.dedup_by_key(|&mut (table, key, _)| (table, key));
        for (_, _, at) in missed {
            let task = &tasks[at];
            task.table.count_filter_miss(task.table_seqno);
        }
    }

    /// Decodes the block of task `index` from `bytes`, keeping it in the cache
    /// when it fits in `keep_room` and handing it to the reads waiting on
    /// `lead`, and point-reads its keys, adding each hit to `hits` as
    /// `(task index, key index, entry)`.
    fn resolve_block_task<K: AsRef<[u8]>>(
        task: &BlockTask<'_>,
        index: usize,
        bytes: &[u8],
        keep_room: &mut u64,
        lead: Option<crate::cache::BlockLead>,
        keys: &[K],
        hits: &mut Vec<(usize, usize, InternalValue)>,
    ) -> crate::Result<()> {
        let block = task
            .table
            .decode_data_block_keeping(bytes, &task.handle, keep_room, lead)?;
        Self::read_task_keys(task, index, &block, keys, hits)
    }

    /// Point-reads the keys of task `index` in its data `block`, adding each
    /// hit to `hits` as `(task index, key index, entry)`.
    #[expect(
        clippy::indexing_slicing,
        reason = "the task's key indices are valid (caller's keys aligned)"
    )]
    fn read_task_keys<K: AsRef<[u8]>>(
        task: &BlockTask<'_>,
        index: usize,
        block: &crate::table::DataBlock,
        keys: &[K],
        hits: &mut Vec<(usize, usize, InternalValue)>,
    ) -> crate::Result<()> {
        for &(kidx, key_hash) in &task.keys {
            if let Some(item) = task.table.point_read_translated(
                block,
                keys[kidx].as_ref(),
                key_hash,
                task.table_seqno,
            )? {
                hits.push((index, kidx, item));
            }
        }
        Ok(())
    }

    /// Keeps the higher-seqno of an existing result and a new candidate (the L0
    /// newest-version-wins merge; correct for L1+ too, where each key has one
    /// candidate).
    #[expect(
        clippy::indexing_slicing,
        reason = "idx is a valid key index aligned with results"
    )]
    fn keep_highest(results: &mut [Option<InternalValue>], idx: usize, item: InternalValue) {
        match &results[idx] {
            Some(current) if current.key.seqno >= item.key.seqno => {}
            _ => results[idx] = Some(item),
        }
    }

    fn get_internal_entry_from_tables(
        version: &Version,
        key: &[u8],
        seqno: SeqNo,
        comparator: &dyn crate::comparator::UserComparator,
    ) -> crate::Result<Option<InternalValue>> {
        let key_hash = crate::hash::hash64(key);
        Self::find_in_tables::<TableEntry>(version, key, seqno, key_hash, comparator)
    }

    /// Generic level-walk for point reads, monomorphized over the lookup result type.
    ///
    /// A level of several runs (always L0, and a deeper level a tiered
    /// layout leaves overlapping runs in): check ALL runs, keep highest seqno.
    /// A level of one run: at most one table covers the key.
    /// Once a level yields a match, lower levels cannot have newer data.
    fn find_in_tables<T: TablePointLookup>(
        version: &Version,
        key: &[u8],
        seqno: SeqNo,
        key_hash: u64,
        comparator: &dyn crate::comparator::UserComparator,
    ) -> crate::Result<Option<T>> {
        for (level_idx, level) in version.iter_levels().enumerate() {
            if level_idx == 0 || level.run_count() > 1 {
                let mut best: Option<T> = None;

                for run in level.iter() {
                    if let Some(table) = run.get_for_key_cmp(key, comparator)
                        && let Some(item) = T::lookup(table, key, seqno, key_hash)?
                    {
                        match &best {
                            Some(current) if current.entry_seqno() >= item.entry_seqno() => {}
                            _ => {
                                // Short-circuit: point reads use exclusive upper bound,
                                // so the highest visible seqno is read_seqno - 1.
                                // If matched, no other L0 run can have a higher one.
                                if item.entry_seqno().checked_add(1) == Some(seqno) {
                                    return Ok(item.filter_tombstone());
                                }
                                best = Some(item);
                            }
                        }
                    }
                }

                if let Some(entry) = best {
                    return Ok(entry.filter_tombstone());
                }
            } else if let Some(table) = level
                .iter()
                .next()
                .and_then(|run| run.get_for_key_cmp(key, comparator))
                && let Some(item) = T::lookup(table, key, seqno, key_hash)?
            {
                // One run: the table covering the key answers for the level.
                return Ok(item.filter_tombstone());
            }
        }

        Ok(None)
    }

    pub(crate) fn get_internal_entry_from_sealed_memtables(
        super_version: &SuperVersion,
        key: &[u8],
        seqno: SeqNo,
    ) -> Option<InternalValue> {
        for mt in super_version.sealed_memtables.iter().rev() {
            if let Some(entry) = mt.get(key, seqno) {
                return Some(entry);
            }
        }

        None
    }

    /// Resolves the super-version serving snapshot `seqno`, as an owned clone
    /// a caller can keep for as long as it reads (an iterator, a scan).
    ///
    /// Every snapshot above the retention floor is served by the current
    /// version (see
    /// [`SuperVersions::get_version_for_snapshot`](crate::version::SuperVersions::get_version_for_snapshot)),
    /// so under `std` it is cloned from the lock-free mirror rather than out of
    /// the locked history. The clone is the reader's hold: it keeps the
    /// version's tables on disk until the reader drops it, however many
    /// installs happen in the meantime.
    ///
    /// # Errors
    ///
    /// [`Error::SnapshotBelowRetention`](crate::Error::SnapshotBelowRetention)
    /// when `0 < seqno <= floor`.
    #[cfg(feature = "std")]
    pub(crate) fn get_version_for_snapshot(&self, seqno: SeqNo) -> crate::Result<SuperVersion> {
        let current = self.latest_super_version.load();
        current.check_serves(seqno)?;
        Ok(SuperVersion::clone(&current))
    }

    /// Resolves the super-version serving snapshot `seqno`; see the `std`
    /// build's twin. Without the mirror it clones out of the locked history.
    ///
    /// # Errors
    ///
    /// [`Error::SnapshotBelowRetention`](crate::Error::SnapshotBelowRetention)
    /// when `0 < seqno <= floor`.
    #[cfg(not(feature = "std"))]
    pub(crate) fn get_version_for_snapshot(&self, seqno: SeqNo) -> crate::Result<SuperVersion> {
        self.version_history.read().get_version_for_snapshot(seqno)
    }

    /// Unflushed memtable bytes the memtable backpressure axis compares: the
    /// total of the shared write-buffer budget when the tree joined one, else
    /// the tree's own active and sealed memtables.
    #[cfg(feature = "std")]
    pub(crate) fn unflushed_memtable_bytes(&self) -> u64 {
        match &self.config.write_buffer_budget {
            Some(budget) => budget.unflushed_bytes(),
            None => self.latest_super_version.load().unflushed_bytes(),
        }
    }

    /// The tree's own unflushed memtable bytes; see the `std` build's twin.
    #[cfg(not(feature = "std"))]
    pub(crate) fn unflushed_memtable_bytes(&self) -> u64 {
        self.version_history
            .read()
            .latest_version_ref()
            .unflushed_bytes()
    }

    /// The snapshot for one point read, without a clone.
    ///
    /// Every snapshot above the retention floor is served by the current
    /// version, so under `std` a point read never takes the history `RwLock`:
    /// it loads the mirrored current [`SuperVersion`], checks the floor it
    /// carries, and reads under the load guard. Recent inserts stay visible
    /// because they mutate the shared `active_memtable` behind a stable Arc;
    /// the current version only changes on rotation, flush and compaction,
    /// which refresh the mirror under the write lock.
    ///
    /// What a caller gets, and may assume: the memtables and tables of ONE
    /// version, the current one. Nothing here hides a compaction from a read
    /// the floor admits: a snapshot below an install is answered from the
    /// install's output, which holds every key version that snapshot reads.
    ///
    /// Point reads only: a guard held across a long scan would delay the
    /// mirror's writers, so iterators keep their own clones (see
    /// [`get_version_for_snapshot`](Self::get_version_for_snapshot)). no-std has
    /// no mirror (`arc-swap` is std-only) and clones out of the locked history.
    ///
    /// # Errors
    ///
    /// [`Error::SnapshotBelowRetention`](crate::Error::SnapshotBelowRetention)
    /// when `0 < seqno <= floor`.
    #[inline]
    pub(crate) fn snapshot_for_read(
        &self,
        seqno: SeqNo,
    ) -> crate::Result<crate::version::SnapshotRef> {
        #[cfg(feature = "std")]
        {
            let current = self.latest_super_version.load();
            current.check_serves(seqno)?;
            Ok(crate::version::SnapshotRef::Latest(current))
        }
        #[cfg(not(feature = "std"))]
        {
            self.version_history
                .read()
                .get_version_for_snapshot(seqno)
                .map(crate::version::SnapshotRef::Owned)
        }
    }

    /// Opens an LSM-tree in the given directory.
    ///
    /// Will recover previous state if the folder was previously
    /// occupied by an LSM-tree, including the previous configuration.
    /// If not, a new tree will be initialized with the given config.
    ///
    /// After recovering a previous state, use `Tree::set_active_memtable`
    /// to fill the memtable with data from a write-ahead log for full durability.
    ///
    /// # Errors
    ///
    /// Returns error, if an IO error occurred.
    ///
    /// `lock` says how the open comes by the directory lock: a caller that
    /// wrote the tree's files under it passes it in, so no other opener gets
    /// in between.
    ///
    /// `names` says who syncs the folders that gain an entry when the open
    /// makes the tree's folder.
    ///
    /// Returns the tree, and when this open made it rather than recovering
    /// one, what takes it back.
    pub(crate) fn open(
        config: Config,
        #[cfg(feature = "std")] lock: crate::config::DirectoryLock,
        names: NewFolderNames,
    ) -> crate::Result<(Self, Option<Creation>)> {
        log::debug!("Opening LSM-tree at {}", config.path.display());

        // Resolve the per-tree compaction compression pool once, at open: if the
        // caller supplied no shared pool but asked for >1 thread, build the
        // default rayon-backed pool now so every compaction reuses it (building
        // a pool per compaction would spawn threads on each run). A caller-
        // supplied pool is left untouched. Shadowed under `parallel` only, so
        // non-parallel builds don't carry an unused `mut`.
        // `mut` under `zstd_any` too: installing the dictionaries ASSIGNS the
        // config a registry of its own rather than storing through the one it
        // arrived with, which is what keeps two trees opened from clones of one
        // config from sharing a set.
        #[cfg_attr(
            not(any(feature = "parallel", zstd_any)),
            expect(unused_mut, reason = "assigned only by the parallel / zstd builds")
        )]
        let mut config = config;

        #[cfg(feature = "parallel")]
        if config.compaction_pool.is_none() && config.compaction_threads > 1 {
            config.compaction_pool = Some(Arc::new(
                crate::table::writer::RayonSpawner::with_threads(config.compaction_threads)?,
            ));
        }

        // Gate on the `page_ecc` cargo feature: caller asked for ECC
        // but the build does not link the Reed-Solomon codec. We have
        // no way to verify or recover RS parity without the codec, so
        // refuse to open rather than silently downgrade integrity.
        // Two surfaces to check:
        //   - `Config::page_ecc(true)`  → SST data-block ECC
        //   - `Config::with_runtime_config(RuntimeConfig { page_ecc: true, .. })`
        //     → manifest-Block ECC (consumed by manifest_blocks::writer)
        // Both silently no-op without the feature; refusing here is
        // the only place callers see a typed error.
        if (config.page_ecc || config.initial_runtime_config.page_ecc)
            && !cfg!(feature = "page_ecc")
        {
            return Err(crate::Error::PageEccUnsupported);
        }

        // Acquire the cross-process directory lock BEFORE any manifest access
        // (the installed-snapshot probe + `has_existing_version_state` check below, and
        // the recover / create paths). Acquiring it here makes `open()`
        // exclusive end-to-end: a concurrent opener fails fast with
        // `Error::Locked` instead of racing through the probe and observing a
        // peer's half-created directory (which would surface as the InvalidData
        // "half-written checkpoint" path rather than `Locked`). The `LOCK` file
        // needs its directory to exist, so create the root directory first
        // (idempotent; `create_new` re-creates the `tables/` subtree). The lock
        // is threaded into the constructor so it lives for the tree's lifetime.
        #[cfg(feature = "std")]
        let restoring = matches!(lock, crate::config::DirectoryLock::Held(_));
        // The folders that gain an entry when the open makes the tree folder:
        // a tree created here syncs each of them, though by then they exist.
        let made_by_open = new_entry_holders(&*config.fs, &config.path)?;
        let open_holders: Vec<(crate::path::PathBuf, Arc<dyn Fs>)> = made_by_open
            .iter()
            .map(|holder| (holder.clone(), Arc::clone(&config.fs)))
            .collect();
        // What the tree folder holds before this open, when it exists: a tree
        // the open makes there and then takes back takes back only what it
        // added.
        let found = if made_by_open.is_empty() {
            Some(folder_entries(&*config.fs, &config.path)?)
        } else {
            None
        };
        #[cfg(feature = "std")]
        let directory_lock = match lock {
            crate::config::DirectoryLock::Held(held) => held,
            crate::config::DirectoryLock::Acquire => {
                config.fs.create_dir_all(&config.path)?;
                match crate::config::acquire_directory_lock(
                    &*config.fs,
                    &config.path,
                    config.directory_lock,
                ) {
                    Ok(held) => held,
                    Err(e) => {
                        // Without the lock the folder may be another opener's
                        // as much as this one's: nothing is removed, and the
                        // names this open made are made durable instead, so
                        // a retry that finds them needs no sync for them.
                        sync_made_names(&open_holders);
                        return Err(e);
                    }
                }
            }
        };

        // From here to the creation, a failure takes back the folders this
        // open made, as a failed creation does: a retry finds them existing
        // and would give the folders holding their names no sync.
        let prelude = (|| -> crate::Result<bool> {
            // A restore that published the manifest but never made the restored
            // memtable contents durable left a tree that lacks them: serving it
            // would answer from a partial snapshot. Only the restore that finishes
            // the job opens it.
            #[cfg(feature = "std")]
            if !restoring
                && config
                    .fs
                    .exists(&config.path.join(crate::file::RESTORE_MARKER_FILE))?
            {
                return Err(crate::Error::from(crate::io::Error::new(
                    crate::io::ErrorKind::InvalidData,
                    format!(
                        "{} holds an interrupted restore; run restore_pinned again to finish it",
                        config.path.display(),
                    ),
                )));
            }

            // Check for old version
            if config.fs.exists(&config.path.join("version"))? {
                log::error!(
                    "refusing to open: this directory has a `version` marker file, which only the \
                 retired V1 layout wrote. V6 is the only on-disk format THIS engine decodes, and \
                 it ships no conversion tooling for V1. If the directory is a V1 database the data is \
                 not lost: open it with the engine that wrote it, or convert it there. If the \
                 file is unrelated to this store, move it aside and retry"
                );
                // The marker's contents are deliberately not read: no legacy
                // decode path exists to act on them, so parsing it could only
                // change the wording of this error. That makes the presence of
                // the file evidence, not proof, hence "has a marker" rather than
                // "is a V1 database", and the second escape hatch for a directory
                // that merely happens to carry the name.
                //
                // Scoped to this engine on purpose. The operator reads this line
                // while deciding what to do with the directory, and "no conversion
                // path" full stop would read as "unrecoverable" — which is wrong,
                // and the opposite of what the repair gate documents (an
                // unsupported version needs offline conversion or a matching
                // binary; see `is_repairable_open_error`).
                //
                // Literal discriminant: V1 is a retired format and FormatVersion
                // carries no legacy variants (single-format contract).
                return Err(crate::Error::InvalidVersion(1));
            }

            // Recover when the tree holds an installed snapshot, create one
            // otherwise. The installed snapshot is verified here, before the
            // dictionaries below are read or their registrations swept: its
            // footer under the configured provider, its format, and that it is
            // the version its name says.
            let installed =
                crate::version::recovery::installed_snapshot(&config.path, &*config.fs)?;
            if let Some(id) = installed {
                crate::version::recovery::verify_snapshot(
                    &config.path,
                    id,
                    &*config.fs,
                    config.encryption.clone(),
                )?;
            }
            let recovering = installed.is_some();

            // Load the tree's own dictionaries before anything opens a table: a
            // table resolves the dictionary id it recorded against this set, so an
            // empty one fails every dictionary-compressed table in the tree. Before
            // the recover / create split, because a freshly created tree writes
            // dictionary-compressed tables too.
            //
            // AFTER the probe above, which verified the manifest under the
            // configured provider. A dictionary file carries no header saying it is
            // sealed, so without the key an encrypted one reads as bytes that fail
            // their hash, which is how a damaged one reads, and a damaged one is
            // what `open_or_repair` repairs. The probe fails a wrong or missing key
            // first, as the configuration error it is.
            //
            // A dictionary supplied through the config joins them, which is what
            // keeps `Config::dict` working: on the first open it is the only one
            // there, and it is registered at the end of this function so later
            // opens need no config at all.
            //
            // Under the directory lock, since it reads the tree's own folder and
            // SWEEPS unpublished `.tmp` registrations: doing that before the lock
            // lets an opener that is about to fail with `Locked` delete a live
            // owner's in-flight registration between its write and its rename.
            #[cfg(zstd_any)]
            config.install_own_zstd_dictionaries()?;

            // Only now can the compression policies be checked: they name
            // dictionaries by id, and the tree may hold one without the caller
            // supplying the bytes again. Validating before the load would refuse
            // exactly the reopen the tree owning its dictionaries exists to allow.
            #[cfg(zstd_any)]
            config.initial_runtime_config.check_dictionaries(
                config.kv_separation_opts.is_some(),
                &config.current_zstd_dictionaries(),
            )?;

            // No installed snapshot MUST coincide with a directory whose
            // tables and blob folders hold nothing; otherwise we are looking
            // at a half-written checkpoint (or other interrupted sealing),
            // and calling `create_new` would overwrite the partial state with
            // an empty tree, turning a recoverable failure into data loss.
            // What a creation that never completed leaves (its empty folders,
            // a temporary snapshot never renamed into place, the empty log
            // made before that rename) holds no data and is created over. A
            // snapshot under its own name is installed, with or without its
            // log, and is recovered instead.
            if !recovering && has_existing_version_state(&config)? {
                // Return Error::Io(InvalidData, ...) rather than
                // Error::Unrecoverable so callers that don't read
                // logs still get a programmatic surface with the
                // path and remediation hint embedded. `log::error!`
                // stays for human ops who DO watch logs and want
                // the full context at the moment of failure (the
                // structured error is what propagates up the call
                // chain; the log line records the diagnosis next
                // to the timestamp).
                let msg = format!(
                    "Tree::open: refusing to recover {} — it holds no installed manifest \
                     snapshot (a v<N>) but its tables/ or blobs/ folder holds files, \
                     or an edits-N holds edits. This is the on-disk signature of a \
                     half-written \
                     checkpoint or interrupted sealing. Remove the partial directory and \
                     retry the checkpoint, or restore the snapshot from a backup before \
                     reopening.",
                    config.path.display(),
                );
                log::error!("{msg}");
                return Err(crate::Error::from(crate::io::Error::new(
                    crate::io::ErrorKind::InvalidData,
                    msg,
                )));
            }
            Ok(recovering)
        })();
        let recovering = match prelude {
            Ok(recovering) => recovering,
            Err(e) => {
                if !made_by_open.is_empty() {
                    // Another opener may have filled the folder between the
                    // probe that found it missing and this open's lock: only
                    // what is empty is taken back. The lock file goes while
                    // the lock is held, so no opener is left holding the lock
                    // of a file another one can make anew; where an open
                    // file cannot be removed it stays, and so does the folder.
                    #[cfg(feature = "std")]
                    {
                        let lock_file = config.path.join(crate::config::DIRECTORY_LOCK_FILE);
                        if let Err(e) = config.fs.remove_file(&lock_file)
                            && e.kind() != crate::io::ErrorKind::NotFound
                        {
                            log::warn!(
                                "Tree::open: could not remove {} after a failed open ({e})",
                                lock_file.display()
                            );
                        }
                        drop(directory_lock);
                    }
                    let made = made_folders(&config.path, &made_by_open)
                        .into_iter()
                        .map(|folder| (folder, Arc::clone(&config.fs)))
                        .collect();
                    undo_creation(None, made, &open_holders);
                }
                return Err(e);
            }
        };

        let creation = (!recovering).then(|| Creation {
            path: config.path.clone(),
            fs: Arc::clone(&config.fs),
            holders: made_by_open.clone(),
            found,
            names,
            sync_mode: config.sync_mode,
        });
        let tree = if recovering {
            Self::recover(
                config,
                #[cfg(feature = "std")]
                directory_lock,
            )
        } else {
            Self::create_new(
                config,
                &made_by_open,
                names,
                #[cfg(feature = "std")]
                directory_lock,
            )
        }?;

        // A dictionary supplied through the config becomes the tree's, so the
        // caller supplies it once rather than on every open forever. Idempotent
        // by id, so re-opening with the same one writes nothing.
        //
        // BOTH write slots, not just the table one: a KV-separated tree
        // compresses its blob files against a dictionary of their own, and a
        // blob file whose dictionary the tree never stored cannot be read back
        // from a checkpoint or after the caller stops supplying it — the same
        // failure the table side had, one file class over.
        //
        // After the recover / create above, because registering installs a
        // version edit and there is no history to install into before that.
        #[cfg(zstd_any)]
        let registered = [
            tree.config.zstd_dictionary.clone(),
            tree.config
                .kv_separation_opts
                .as_ref()
                .and_then(|o| o.zstd_dictionary.clone()),
        ]
        .into_iter()
        .flatten()
        .try_for_each(|dict| tree.register_zstd_dictionary(dict));
        // A tree this open made, whose open then fails, is taken back: the
        // caller is told it was not opened, and a retry makes it anew.
        #[cfg(zstd_any)]
        if let Err(e) = registered {
            if let Some(creation) = creation {
                creation.take_back(tree);
            }
            return Err(e);
        }

        Ok((tree, creation))
    }

    /// Returns `true` if there are some tables that are being compacted.
    #[doc(hidden)]
    #[must_use]
    pub fn is_compacting(&self) -> bool {
        !self.compaction_state.lock().hidden_set().is_empty()
    }

    /// Computed storage admission predicate backing
    /// [`AbstractTree::write_admission`].
    ///
    /// Cheap: reads in-memory size accounting only (no syscall). Returns
    /// `Ok(())` unless admission control is enabled AND a budget is set AND the
    /// live footprint plus reserved headroom exceeds it.
    /// Best-effort minimum free space across every filesystem this tree writes
    /// to: the primary data path AND each per-level route (`Config::level_routes`
    /// can place cold-level SSTs on separate volumes). The admission gate must
    /// reflect the tightest volume, since a full routed disk fails compaction /
    /// flush targeting it even while the primary still has room.
    ///
    /// A backend that cannot report free space (or an I/O hiccup) yields
    /// `u64::MAX` = "no disk pressure", so a probe failure never falsely drives
    /// the tree read-only.
    fn probe_disk_free(&self) -> u64 {
        self.0.config.min_available_space()
    }

    /// Disk-aware capacity figures for [`AbstractTree::storage_stats`], given the
    /// live footprint `used`: `(capacity, available, compaction_possible)`.
    ///
    /// `capacity` is the tighter of the configured quota and the physical disk
    /// headroom (`free + used`) — the same effective limit
    /// [`Self::compute_write_admission`] gates against — reported regardless of
    /// whether the admission gate is enabled (introspection is always available).
    /// `None` capacity/available means unbounded (no quota AND the backend
    /// cannot report free space). `compaction_possible` is `true` when unbounded
    /// or when at least [`MIN_RESERVED_HEADROOM`] of working room remains.
    pub(crate) fn admission_capacity(&self, used: u64) -> (Option<u64>, Option<u64>, bool) {
        let quota = self
            .0
            .runtime_config
            .load()
            .storage_limit_bytes
            .unwrap_or(u64::MAX);
        let free = self.probe_disk_free();
        // `free == u64::MAX` is the "backend can't report free space" sentinel:
        // adding `used` would overflow, so treat capacity as quota-only (the
        // explicit branch avoids the overflow without masking it with saturation).
        // Otherwise `free + used` ≤ ~2× disk capacity and cannot overflow u64.
        let capacity = if free == u64::MAX {
            quota
        } else {
            quota.min(free + used)
        };
        if capacity == u64::MAX {
            return (None, None, true);
        }
        // `available = max(0, capacity - used)`: an operator quota set below the
        // live footprint makes `capacity < used`, and available space cannot be
        // negative. The clamp-to-zero IS the intended semantics here.
        let available = capacity.saturating_sub(used);
        (
            Some(capacity),
            Some(available),
            available >= MIN_RESERVED_HEADROOM,
        )
    }

    /// The logical partition-quota headroom for the two-layer space model:
    /// `max(0, storage_limit_bytes - used)`, or `u64::MAX` when no quota is set.
    ///
    /// The quota half of [`crate::compaction::worker::merge_would_fit`]; the
    /// free space of each volume is the other. An operator quota set below the
    /// live footprint leaves zero headroom — the clamp-to-zero is the intended
    /// min-semantics, not masking.
    pub(crate) fn quota_headroom(&self, used: u64) -> u64 {
        self.0
            .runtime_config
            .load()
            .storage_limit_bytes
            .map_or(u64::MAX, |limit| limit.saturating_sub(used))
    }

    /// Whether the opt-in storage admission gate is active (a near-full disk or
    /// configured quota can drive the tree read-only and gate compaction space).
    /// Capacity introspection figures are reported regardless; this only governs
    /// whether the gate actually enforces.
    pub(crate) fn storage_admission_enabled(&self) -> bool {
        self.0.runtime_config.load().storage_admission_check
    }

    #[expect(
        clippy::significant_drop_tightening,
        reason = "the admission cache lock intentionally spans the recompute \
                  (stat + disk-free probe) so concurrent admission checks \
                  coalesce on a single probe rather than each issuing a syscall"
    )]
    fn compute_write_admission(&self) -> crate::Result<()> {
        let rc = self.0.runtime_config.load();
        if !rc.storage_admission_check {
            return Ok(());
        }

        // Take ONE coherent snapshot of the latest super-version and derive
        // BOTH the on-disk footprint and the pending-memtable bytes from it.
        // Reading them from two separate `latest_version()` loads would be a
        // TOCTOU bug: a flush installing a new version between the two reads
        // could pair an old (larger) disk usage with new (smaller) pending
        // bytes — or vice versa — and open the gate incorrectly.
        let super_version = self.version_history.read().latest_version();
        let vid = super_version.version.id();

        // True physical footprint, including blob files — the SAME basis
        // `storage_stats()` reports, so the gate and the reported usage agree.
        // NOT `disk_space()` (metadata Level::size, which omits blob files and
        // undercounts the physical file by the meta block / footer).
        //
        // Cached so gated writes don't re-stat every live file or re-probe disk
        // on every call. `used_bytes` only changes when a new version is
        // installed (flush / compaction), so it is recomputed on a version
        // change. `disk_free` can change under us (another process writing the
        // same filesystem), so it is ALSO re-probed once its sample is older
        // than `ADMISSION_DISK_FREE_TTL` — bounding staleness without a syscall
        // per write. `update_runtime_config` resets the entry for an immediate
        // re-probe. The values live behind one mutex as a coherent unit (see
        // `TreeInner::admission_used_cache`).
        //
        // The TTL fast-path is std-only: under `no_std` there is no monotonic
        // clock (`crate::time::Instant::elapsed` is a zero stub), so an
        // elapsed-time window cannot bound staleness — a same-version sample
        // would otherwise look fresh forever and a filling disk would never be
        // re-probed. Under `no_std` the fast-path is skipped, so `disk_free` is
        // re-probed on every gated write (the `used` footprint stays cached by
        // version either way), keeping admission safe without a monotonic clock.
        let now = crate::time::Instant::now();
        let (used, disk_free) = {
            let mut cache = self.0.admission_used_cache.lock();
            match *cache {
                // Fresh: same version AND disk sample within the TTL. std-only —
                // `cfg!(feature = "std")` is `false` under `no_std`, so the guard
                // short-circuits there and the next arm re-probes every call.
                Some((cvid, used, free, at))
                    if cvid == vid
                        && cfg!(feature = "std")
                        && at.elapsed() < ADMISSION_DISK_FREE_TTL =>
                {
                    (used, free)
                }
                // Same version, stale disk sample: keep `used`, re-probe disk.
                Some((cvid, used, _, _)) if cvid == vid => {
                    let free = self.probe_disk_free();
                    *cache = Some((vid, used, free, now));
                    (used, free)
                }
                // New version (or unset): recompute footprint and re-probe disk.
                _ => {
                    let used = crate::storage_stats::compute_used_bytes(&super_version.version)?;
                    let free = self.probe_disk_free();
                    *cache = Some((vid, used, free, now));
                    (used, free)
                }
            }
        };

        // Effective limit is the tighter of the configured quota and the
        // physical disk headroom (free + what we already occupy): the disk can
        // fill from other processes even below a generous quota, and a tree with
        // no quota at all must still stop before ENOSPC. `None` quota = unbounded
        // by configuration; disk-free then alone bounds it.
        //
        // `disk_free` is the MINIMUM free across every volume the tree writes to
        // (`probe_disk_free` mins the primary path and all `level_routes`). The
        // `+ used` here is NOT an accounting of one volume's usage against
        // another's free space — it cancels out of the disk branch of the gate:
        // passing requires `used + reserved <= disk_free + used`, i.e.
        // `reserved <= disk_free`. So a passing gate guarantees the TIGHTEST
        // volume alone has at least `reserved` free — a conservative per-volume
        // headroom, never the sum of an empty routed volume's slack plus an
        // unrelated full volume's occupancy. A route that drops below `reserved`
        // free drives the whole tree read-only, exactly so a later flush /
        // compaction targeting that route cannot hit ENOSPC.
        let quota = rc.storage_limit_bytes.unwrap_or(u64::MAX);
        // `disk_free == u64::MAX` is the "backend can't report" sentinel; adding
        // `used` would overflow, so treat the limit as quota-only (explicit
        // branch, no saturation masking). Otherwise `disk_free + used` ≤ ~2× disk
        // capacity and cannot overflow u64.
        let limit = if disk_free == u64::MAX {
            quota
        } else {
            quota.min(disk_free + used)
        };
        // Both sources unbounded → nothing to gate.
        if limit == u64::MAX {
            return Ok(());
        }

        // Reserved headroom keeps the soft budget from becoming a hard wall:
        // enough to flush every pending memtable (plus a margin for the
        // index/filter/footer overhead a flush adds) so a queued flush always
        // fits at the limit, with a floor for compaction working space.
        // Internal flush / compaction are never gated, so this band is the
        // engine's room to reclaim.
        //
        // Count ALL pending memtable bytes in this snapshot — the active one AND
        // any sealed (rotated) memtables awaiting flush — not just the active
        // one: after a rotation the active memtable is empty but the sealed
        // memtable's queued flush will still consume disk, so it must be
        // reserved for. Memtable sizes are bounded by RAM, so the sum (and the
        // +1/8 overhead margin below) cannot overflow u64 → plain arithmetic.
        let pending_memtable_bytes: u64 = super_version.active_memtable.size()
            + super_version
                .sealed_memtables
                .iter()
                .map(|m| m.size())
                .sum::<u64>();

        let reserved =
            (pending_memtable_bytes + pending_memtable_bytes / 8).max(MIN_RESERVED_HEADROOM);
        // `used` (disk) + `reserved` (RAM-bounded) cannot realistically overflow,
        // but keep the comparison fail-closed with checked arithmetic: any
        // overflow means "definitely over budget", so deny.
        match used.checked_add(reserved) {
            Some(total) if total <= limit => Ok(()),
            _ => Err(crate::Error::StorageFull { used, limit }),
        }
    }

    fn inner_compact(
        &self,
        strategy: Arc<dyn CompactionStrategy>,
        gc_watermark: SeqNo,
    ) -> crate::Result<crate::compaction::CompactionResult> {
        use crate::compaction::worker::{Options, do_compaction};

        let mut opts = Options::from_tree(self, strategy);
        opts.gc_watermark = gc_watermark;

        let result = do_compaction(&opts)?;

        log::debug!("Compaction run over");

        Ok(result)
    }

    /// Iterator over the whole tree at snapshot `seqno`.
    ///
    /// # Errors
    ///
    /// [`Error::SnapshotBelowRetention`](crate::Error::SnapshotBelowRetention)
    /// when `seqno` is at or below the retention floor; the error is
    /// raised here, before any I/O, rather than as an iterator item.
    #[doc(hidden)]
    pub fn create_iter(
        &self,
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
    ) -> crate::Result<impl DoubleEndedIterator<Item = crate::Result<KvPair>> + 'static> {
        self.create_range::<UserKey, _>(&.., seqno, ephemeral)
    }

    /// Iterator over `range` at snapshot `seqno`.
    ///
    /// # Errors
    ///
    /// [`Error::SnapshotBelowRetention`](crate::Error::SnapshotBelowRetention)
    /// when `seqno` is at or below the retention floor; the error is
    /// raised here, before any I/O, rather than as an iterator item.
    ///
    /// The version is resolved ONCE here and moved into the iterator, so the
    /// whole traversal reads one file set: a compaction installing mid-scan
    /// neither adds its output nor removes the inputs this iterator holds, and
    /// those inputs stay on disk until the iterator drops.
    #[doc(hidden)]
    pub fn create_range<'a, K: AsRef<[u8]> + 'a, R: RangeBounds<K> + 'a>(
        &self,
        range: &'a R,
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
    ) -> crate::Result<impl DoubleEndedIterator<Item = crate::Result<KvPair>> + 'static> {
        let super_version = self.get_version_for_snapshot(seqno)?;

        Ok(Self::create_internal_range_with_prefix_hash(
            super_version,
            range,
            seqno,
            ephemeral,
            self.config.merge_operator.clone(),
            self.config.comparator.clone(),
            None,
            self.blob_source(),
        )
        .map(|item| match item {
            Ok(kv) => Ok((kv.key.user_key, kv.value)),
            Err(e) => Err(e),
        }))
    }

    /// Build a [`SeekableTreeIter`](crate::range::SeekableTreeIter) over
    /// `[lo, hi)`. Source collection (Phase 1) runs once; repositions reuse it.
    ///
    /// Because the sources are collected once and reused, every reposition
    /// resolves against the file set of the version taken here, however long
    /// the iterator lives. That is the same one-version rule the plain range
    /// iterator states, and it binds for longer.
    ///
    /// # Errors
    ///
    /// [`Error::SnapshotBelowRetention`](crate::Error::SnapshotBelowRetention)
    /// when `seqno` is at or below the retention floor.
    #[doc(hidden)]
    pub fn create_seekable_range_bounds(
        &self,
        lo: Bound<UserKey>,
        hi: Bound<UserKey>,
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
    ) -> crate::Result<crate::range::SeekableTreeIter> {
        self.create_seekable_range_bounds_with(lo, hi, seqno, ephemeral, self.blob_source())
    }

    /// [`Self::create_seekable_range_bounds`], reading values kept in the
    /// value log through `blob_source`, the one its caller took as the read
    /// began.
    pub(crate) fn create_seekable_range_bounds_with(
        &self,
        lo: Bound<UserKey>,
        hi: Bound<UserKey>,
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
        blob_source: Option<crate::blob_tree::BlobSource>,
    ) -> crate::Result<crate::range::SeekableTreeIter> {
        use crate::range::{IterState, SeekableTreeIter};

        let super_version = self.get_version_for_snapshot(seqno)?;

        let iter_state = IterState {
            version: super_version,
            ephemeral,
            merge_operator: self.config.merge_operator.clone(),
            blob_source,
            comparator: self.config.comparator.clone(),
            prefix_hash: None,
            #[cfg(feature = "metrics")]
            metrics: Some(self.0.metrics.clone()),
        };

        Ok(SeekableTreeIter::create(iter_state, lo, hi, seqno))
    }

    /// Iterator over the keys starting with `prefix` at snapshot `seqno`.
    ///
    /// # Errors
    ///
    /// [`Error::SnapshotBelowRetention`](crate::Error::SnapshotBelowRetention)
    /// when `seqno` is at or below the retention floor; the error is
    /// raised here, before any I/O, rather than as an iterator item.
    ///
    /// One version for the whole traversal, as for the range iterator. The
    /// prefix filter narrows which of ITS tables are consulted; it never
    /// reaches a table outside the version resolved here.
    #[doc(hidden)]
    pub fn create_prefix<'a, K: AsRef<[u8]> + 'a>(
        &self,
        prefix: K,
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
    ) -> crate::Result<impl DoubleEndedIterator<Item = crate::Result<KvPair>> + 'static> {
        Ok(self
            .create_internal_prefix(
                prefix.as_ref(),
                seqno,
                ephemeral,
                self.config.merge_operator.clone(),
                self.blob_source(),
            )?
            .map(|item| match item {
                Ok(kv) => Ok((kv.key.user_key, kv.value)),
                Err(e) => Err(e),
            }))
    }

    /// Versions visible at `seqno` under `prefix`, a merge chain resolved by
    /// `merge_operator` (reading a separated base from `blob_source`) or, with
    /// none, yielded as its newest operand.
    fn create_internal_prefix(
        &self,
        prefix: &[u8],
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
        merge_operator: Option<Arc<dyn crate::merge_operator::MergeOperator>>,
        blob_source: Option<crate::blob_tree::BlobSource>,
    ) -> crate::Result<
        impl DoubleEndedIterator<Item = crate::Result<InternalValue>> + 'static + use<>,
    > {
        use crate::prefix::compute_prefix_hash;
        use crate::range::{IterState, TreeIter, prefix_to_range};

        let prefix_hash = compute_prefix_hash(self.config.prefix_extractor.as_ref(), prefix);

        let range = prefix_to_range(prefix);

        let super_version = self.get_version_for_snapshot(seqno)?;

        let iter_state = IterState {
            version: super_version,
            ephemeral,
            merge_operator,
            blob_source,
            comparator: self.config.comparator.clone(),
            prefix_hash,
            #[cfg(feature = "metrics")]
            metrics: Some(self.0.metrics.clone()),
        };

        Ok(TreeIter::create_range(iter_state, range, seqno))
    }

    /// The keys visible at `seqno`, each as its newest version with a merge
    /// chain left unmerged: what the key-only reads walk.
    fn create_key_only_iter(
        &self,
        seqno: SeqNo,
        ephemeral: Option<(Arc<Memtable>, SeqNo)>,
    ) -> crate::Result<
        impl DoubleEndedIterator<Item = crate::Result<InternalValue>> + 'static + use<>,
    > {
        let super_version = self.get_version_for_snapshot(seqno)?;
        Ok(Self::create_internal_range_with_prefix_hash::<UserKey, _>(
            super_version,
            &..,
            seqno,
            ephemeral,
            None,
            self.config.comparator.clone(),
            None,
            None,
        ))
    }

    /// Seals the active memtable under the held version lock, returning it,
    /// or `None` when it is empty.
    pub(crate) fn rotate_memtable_locked(
        &self,
        history: &mut crate::version::SuperVersions,
    ) -> Option<Arc<Memtable>> {
        let super_version = history.latest_version_ref();

        if super_version.active_memtable.is_empty() {
            return None;
        }

        let yanked_memtable = Arc::clone(&super_version.active_memtable);

        let mut copy = super_version.clone();
        copy.active_memtable = Arc::new(Memtable::new(
            self.memtable_id_counter.next(),
            self.config.comparator.clone(),
        ));
        copy.sealed_memtables =
            Arc::new(super_version.sealed_memtables.add(yanked_memtable.clone()));

        // Rotate does not modify the memtable so it cannot break snapshots
        copy.seqno = super_version.seqno;

        history.replace_latest_version(copy);

        log::trace!(
            "rotate: added memtable id={} to sealed memtables",
            yanked_memtable.id,
        );

        Some(yanked_memtable)
    }

    /// Adds an item to the active memtable.
    ///
    /// Returns the added item's size and new size of the memtable.
    #[doc(hidden)]
    #[must_use]
    pub fn append_entry(&self, value: InternalValue) -> (u64, u64) {
        #[cfg(feature = "metrics")]
        self.accept(&value);
        let kv_digest = self.insert_digest(&value);

        // The insert holds its thread's shard of the insert gate, which a
        // version replacing the active memtable closes before it publishes:
        // `value` and its digest land in the active memtable the gate hands
        // out, and no rotation seals it mid-insert. Unlike the history read
        // lock, the shard is a line no other writer thread touches.
        #[cfg(feature = "std")]
        {
            self.insert_gate
                .enter()
                .memtable()
                .insert_with_kv_digest(value, kv_digest)
        }
        // no-std: the history read lock, with the same guarantee.
        #[cfg(not(feature = "std"))]
        {
            self.version_history
                .read()
                .latest_version_ref()
                .active_memtable
                .insert_with_kv_digest(value, kv_digest)
        }
    }

    /// Adds a cell row whose references are `refs` to the active memtable,
    /// once each reference is shown to name a frame the current version still
    /// holds.
    ///
    /// The check and the insert run under the version-history read lock, the
    /// lock a version install takes for writing: an install that removes or
    /// punches a blob file sees this row's registration in the memtable, or
    /// this check sees the file gone.
    ///
    /// # Errors
    ///
    /// [`crate::Error::BlobRef`] when a reference names a blob file the current
    /// version no longer holds, or a frame before that file's live start: a
    /// relocation has moved it, and the key's latest version names the copy.
    /// Also when its object was released after the version it was read from
    /// (each reference comes with that version's id).
    pub(crate) fn append_cell_row(
        &self,
        value: InternalValue,
        refs: &[(crate::blob_tree::handle::BlobIndirection, u64)],
    ) -> crate::Result<(u64, u64)> {
        let kv_digest = self.insert_digest(&value);
        let history = self.version_history.read();
        let latest = history.latest_version_ref();
        for (reference, source) in refs {
            let held = latest
                .version
                .blob_files
                .get(reference.vhandle.blob_file_id)
                .is_some_and(|file| reference.vhandle.offset >= file.live_data_start());
            if !held {
                return Err(crate::Error::BlobRef(
                    "stale reference: the object has moved, read the key again",
                ));
            }
            // An object let go of since the read: writing it back would make
            // this row hold what the accounting already charged as garbage.
            if history
                .released()
                .released_since(*source, &reference.vhandle)
            {
                return Err(crate::Error::BlobRef(
                    "stale reference: the object was released, read the key again",
                ));
            }
        }
        let inserted = latest
            .active_memtable
            .insert_with_kv_digest(value, kv_digest);
        // Held through the insert: the check above is only as good as the
        // version it read staying the latest until the row is in.
        drop(history);
        Ok(inserted)
    }

    /// Charges `value`, taken in from the caller, to the payload the tree's
    /// writes are measured against: a deletion its key, anything else its key
    /// and value.
    #[cfg(feature = "metrics")]
    fn accept(&self, value: &InternalValue) {
        let key = value.key.user_key.len();
        if value.key.value_type.is_tombstone() {
            self.0.metrics.accepted_deletion(key);
        } else {
            self.0.metrics.accepted_value(key + value.value.len());
        }
    }

    /// The insert-time per-KV digest of `value`, when the runtime config asks
    /// for one.
    fn insert_digest(
        &self,
        value: &InternalValue,
    ) -> Option<(u32, crate::runtime_config::ChecksumAlgorithm)> {
        // Per-KV residence digest (KvChecksumComputePoint::AtInsert): compute
        // the entry's 4-byte logical-content digest now, so a RAM bit-flip
        // while it sits in the memtable is caught at flush. The digest covers
        // the OWNED `value` and is independent of which active memtable
        // receives it, so computing it before taking the version-history guard
        // is correct (a concurrent rotation just routes the same value+digest
        // into the new active memtable) AND keeps the hash out of the read-lock
        // critical section. The gate is one relaxed byte mirrored from the
        // runtime config (`TreeInner::kv_digest_at_insert`); under the default
        // `AtBlockCompile` (or `Off`) it is `0` and no digest is computed.
        let gate = self
            .0
            .kv_digest_at_insert
            .load(core::sync::atomic::Ordering::Relaxed);
        inner::kv_digest_algo_from_gate(gate).and_then(|algo| {
            crate::table::block::kv_checksum::kv_digest(value, algo).map(|d| {
                #[expect(
                    clippy::cast_possible_truncation,
                    reason = "AtInsert is config-validated to a 4-byte algorithm; the digest fits u32"
                )]
                let lo = d as u32;
                (lo, algo)
            })
        })
    }

    /// Adds multiple items to the active memtable in bulk.
    ///
    /// Acquires the version-history lock once and delegates to
    /// [`Memtable::insert_batch`] for batch size accounting.
    ///
    /// Returns the total bytes added and new size of the memtable.
    #[doc(hidden)]
    #[must_use]
    pub(crate) fn append_batch(&self, items: Vec<InternalValue>) -> (u64, u64) {
        // Per-KV residence digest under AtInsert (see `append_entry`): pass the
        // algorithm so the bulk path fixes each entry's digest at insert. The
        // default path passes `None` and is unchanged.
        let kv_algo = inner::kv_digest_algo_from_gate(
            self.0
                .kv_digest_at_insert
                .load(core::sync::atomic::Ordering::Relaxed),
        );
        #[cfg(feature = "metrics")]
        for item in &items {
            self.accept(item);
        }

        // Hold the read guard for the entire insert to prevent rotate_memtable()
        // from sealing this memtable mid-batch (which could cause data loss if
        // a concurrent flush persists only a prefix of the batch).
        self.version_history
            .read()
            .latest_version_ref()
            .active_memtable
            .insert_batch_with_kv_algo(items, kv_algo)
    }

    /// Recovers previous state, by loading the level manifest, tables and blob files.
    ///
    /// # Errors
    ///
    /// Returns error, if an IO error occurred.
    #[expect(
        clippy::too_many_lines,
        reason = "Tree::recover threads the whole open sequence (snapshot validation, \
                  Manifest decode, encryption + runtime plumbing, version recovery, \
                  TreeInner assembly) — splitting it would create helper functions whose \
                  only caller is this one site"
    )]
    fn recover(
        mut config: Config,
        // The cross-process directory lock acquired by `Tree::open` before the
        // manifest probe; held for the tree's lifetime via
        // `TreeInner::directory_lock`.
        #[cfg(feature = "std")] directory_lock: Option<Box<dyn crate::fs::FsFile>>,
    ) -> crate::Result<Self> {
        use crate::stop_signal::StopSignal;
        use inner::get_next_tree_id;

        log::info!("Recovering LSM-tree at {}", config.path.display());

        // Validate manifest metadata (format version, comparator name)
        // BEFORE recover_levels, so a rejected open is side-effect free
        // — recover_levels loads tables and cleans up orphans.
        // Tree type is checked after recovery (needs the Version object).
        // NOTE: the version file is read twice (here for metadata, then inside
        // recover_levels for table/blob data). This is intentional — metadata
        // validation must complete before any disk-mutating recovery work.
        // Version id of the installed on-disk snapshot. This is the base the
        // edit log replays on top of; the live version id can be higher (it
        // has no `v{id}` file of its own). Threaded into the version history
        // so the next persist appends to / rotates the right snapshot's log.
        let snapshot_id = crate::version::recovery::installed_snapshot(&config.path, &*config.fs)?
            .ok_or(crate::Error::ManifestFooterInvalid(
                "the tree holds no installed manifest snapshot",
            ))?;
        {
            let version_id = snapshot_id;
            let manifest_path = config.path.join(format!("v{version_id}"));
            // Open the manifest with a default runtime snapshot: ECC
            // awareness is captured per-Block via the header
            // (`ECC_PARITY` flag), so the reader does not need to know
            // which ECC mode the writer used and nothing on this path
            // reads the runtime.
            let mut archive_reader = crate::manifest_blocks::reader::ManifestArchiveReader::open(
                &manifest_path,
                &*config.fs,
                alloc::sync::Arc::new(crate::runtime_config::RuntimeConfig::default()),
                config.encryption.clone(),
            )?;
            let manifest = Manifest::decode_from(&mut archive_reader)?;

            // V6 is the only variant `FormatVersion` can decode to (the
            // engine reads exactly one on-disk format, no legacy paths), so
            // anything else already failed above: on its framing if the
            // manifest is not shaped like the current one, on the version
            // field if it is. This match stays as the explicit gate the
            // format contract documents — and as the compile-time hook that
            // forces a review of the open path when a new variant is added.
            match manifest.version {
                FormatVersion::V6 => {}
            }

            let supplied_name = config.comparator.name();
            if manifest.comparator_name != supplied_name {
                log::warn!(
                    "Comparator mismatch: tree was created with {:?} but opened with {:?}",
                    manifest.comparator_name,
                    supplied_name,
                );
                return Err(crate::Error::ComparatorMismatch {
                    stored: manifest.comparator_name,
                    supplied: supplied_name,
                });
            }

            // IMPORTANT: Restore persisted config
            config.level_count = manifest.level_count;
        }

        let tree_id = get_next_tree_id();

        #[cfg(feature = "metrics")]
        let metrics = Arc::new(Metrics::default());

        let (version, pooled) = Self::recover_levels(
            &config.path,
            tree_id,
            &config,
            #[cfg(feature = "metrics")]
            &metrics,
        )?;

        {
            let requested_tree_type = match config.kv_separation_opts {
                Some(_) => crate::TreeType::Blob,
                None => crate::TreeType::Standard,
            };

            if version.tree_type() != requested_tree_type {
                log::error!(
                    "Tried to open a {requested_tree_type:?}Tree, but the existing tree is of type {:?}Tree. This indicates a misconfiguration or corruption.",
                    version.tree_type(),
                );
                // A dedicated error, NOT `Unrecoverable`: the auto-repair path
                // answers `Unrecoverable` with a manifest rebuild, and a
                // rebuild under the mismatched type commits the wrong tree
                // shape (a Standard rebuild of a blob tree strands its blob
                // files for the orphan sweep). A configuration error must
                // propagate to the caller instead.
                return Err(crate::Error::TreeTypeMismatch {
                    requested: requested_tree_type,
                    actual: version.tree_type(),
                });
            }
        }

        // Table ids and L0 recency keys share one counter, and a flushed or
        // ingested table's recency is an id taken that no table carries: the
        // next id has to be above both, or a flush after the reopen would lay
        // out behind one it is newer than. The pooled files hold ids of their
        // own, which no later table may take.
        let highest_table_id = version
            .iter_tables()
            .map(|table| table.id().max(table.l0_recency()))
            .chain(pooled.iter().flat_map(|(_, _, ids)| ids.iter().copied()))
            .max()
            .unwrap_or_default();
        let table_id_counter = SequenceNumberCounter::new(highest_table_id + 1);
        let life = crate::close::Life::new();
        let table_files = Arc::new(crate::table::file_pool::TableFilePools::for_tree(
            table_id_counter.clone(),
            config.table_file_pool,
            config.sync_mode,
            config.table_file_refill,
            Arc::clone(&life),
        ));
        for (folder, folder_fs, ids) in pooled {
            table_files.adopt(&folder, &folder_fs, ids);
        }

        let comparator = config.comparator.clone();

        let deletion_pause = crate::deletion_pause::DeletionPause::for_tree(Arc::clone(&life));
        #[cfg(feature = "std")]
        let background_deleter =
            Arc::new(crate::BackgroundDeleter::for_tree(None, Arc::clone(&life)));
        let heal_hints =
            crate::heal_hints::HealHints::new_shared(config.initial_runtime_config.auto_heal);

        // Clone the seed snapshot BEFORE moving config into the Arc
        // below — the runtime handle initializer needs it after the
        // move.
        let initial_runtime = config.initial_runtime_config.clone();
        let sync_mode = config.sync_mode;
        // Same reason: built before the move.
        let compaction_rate_limiter = config.tree_compaction_rate_limiter();
        // A strategy reads the compaction budget from the config: given the
        // live limiter, it sees a rate changed after open.
        config.live_compaction_rate_limiter = Some(Arc::clone(&compaction_rate_limiter));
        let compaction_capacity = config.tree_compaction_capacity();
        let write_rate_limiter = config.tree_write_rate_limiter();
        // A compaction throttled by the limiter sleeps until its deadline;
        // dropping the tree has to wake it.
        let stop_signal = StopSignal::default();
        #[cfg(feature = "std")]
        stop_signal.wake_on_stop(&compaction_rate_limiter);
        let filter_budget = Arc::<crate::filter_budget::FilterBudget>::default();
        // The open installed the recovered state as its own snapshot.
        let snapshot_id = version.id();
        let mut super_versions = SuperVersions::new(
            version,
            &comparator,
            sync_mode,
            snapshot_id,
            config.manifest_log_rotate_bytes,
        );
        if config.filter_advisor.is_some() {
            super_versions = super_versions.with_filter_budget(Arc::clone(&filter_budget));
        }
        #[cfg(feature = "std")]
        let latest_super_version = super_versions.latest_handle();
        #[cfg(feature = "std")]
        let insert_gate = super_versions.insert_gate_handle();
        #[cfg(feature = "std")]
        if let Some(budget) = &config.write_buffer_budget {
            budget.register(Arc::downgrade(&latest_super_version));
        }
        let inner = TreeInner {
            id: tree_id,
            life,
            closing: core::sync::atomic::AtomicBool::new(false),
            memtable_id_counter: SequenceNumberCounter::new(1),
            table_id_counter,
            table_files,
            blob_file_id_counter: SequenceNumberCounter::default(),
            version_history: Arc::new(RwLock::new(super_versions)),
            #[cfg(feature = "std")]
            latest_super_version,
            #[cfg(feature = "std")]
            insert_gate,
            stop_signal,
            config: Arc::new(config),
            major_compaction_lock: RwLock::default(),
            flush_lock: Mutex::default(),
            #[cfg(feature = "std")]
            directory_lock: directory_lock.map(Arc::from),
            compaction_state: Arc::new(Mutex::new(CompactionState::default())),
            deletion_pause: Arc::clone(&deletion_pause),
            #[cfg(feature = "std")]
            background_deleter: Arc::clone(&background_deleter),
            heal_hints: Arc::clone(&heal_hints),
            filter_budget,
            compaction_rate_limiter,
            compaction_capacity,
            write_rate_limiter,
            kv_digest_at_insert: portable_atomic::AtomicU8::new(inner::kv_digest_at_insert_gate(
                &initial_runtime,
            )),
            runtime_config: Arc::new(crate::runtime_config::handle::RuntimeConfigHandle::new(
                initial_runtime,
            )),
            admission_used_cache: Mutex::new(None),
            #[cfg(zstd_any)]
            retired_write_snapshots: Mutex::new(Vec::new()),

            #[cfg(feature = "metrics")]
            metrics,

            #[cfg(test)]
            test_hooks: inner::TestHooks::default(),
        };

        // Install the pause on every recovered table / blob file so their
        // Drop impls consult it when a checkpoint is in flight. Snapshot
        // the Arc handles into owned collections so the read lock is
        // released before iterating (avoids `significant_drop_tightening`).
        // Snapshot the version under the read lock, then drop the lock before
        // collecting so the version_history lock isn't held across the clones.
        let version = inner.version_history.read().latest_version().version;
        let recovered_tables: Vec<Table> = version.iter_tables().cloned().collect();
        let recovered_blobs: Vec<BlobFile> = version.blob_files.iter().cloned().collect();

        let sinks = crate::table::TableSinks {
            deletion_pause: &deletion_pause,
            heal_hints: &heal_hints,
            read_budget: inner.config.columnar_read_budget,
            #[cfg(feature = "std")]
            background_deleter: &background_deleter,
            track_filter_probes: inner.config.filter_advisor.is_some(),
        };
        for table in &recovered_tables {
            table.bind_to_tree(&sinks);
        }
        for blob_file in &recovered_blobs {
            blob_file.bind_to_tree(&sinks);
        }

        // Re-arm the tight-space reclaims a previous session could not finish.
        // A reclaim deferred because a checkpoint still hard-linked the file
        // lived only in that session's queue, and the unrestricted view that
        // could re-arm it is gone once the process restarts, so the consumed
        // prefix would stay allocated for the table's lifetime. Nothing is
        // persisted for this: the intent is DERIVABLE, and the extent is
        // exactly the prefix the committed bound cuts away. A prefix already
        // punched re-punches as a no-op, so a completed reclaim costs one
        // call, and only on a restricted table.
        #[cfg(feature = "std")]
        {
            for table in &recovered_tables {
                let Some(bound) = table.restrict_lower_bound() else {
                    continue;
                };
                // Reclaiming frees space; it never decides what the tree
                // serves. A table that opened cleanly must not be denied to
                // readers because its punch offset cannot be re-derived, so a
                // failure here is reported and skipped. An ENVIRONMENTAL fault
                // still propagates: it says nothing about this table, and a
                // retry can re-read it.
                let offset = match table.punch_offset_for(bound) {
                    Ok(offset) => offset,
                    Err(e) if e.is_environmental() => return Err(e),
                    Err(e) => {
                        log::warn!(
                            "table {} carries a committed restriction whose punch offset \
                             could not be re-derived ({e}); its consumed prefix stays \
                             allocated until the next tight-space compaction",
                            table.id(),
                        );
                        continue;
                    }
                };
                if offset > 0 {
                    deletion_pause.retain_reclaim(
                        Arc::clone(&table.fs),
                        (*table.path).clone(),
                        alloc::vec![(0, offset)],
                    );
                }
            }
            // Blob files carry the same deferred intent, in their committed
            // frontier rather than a restriction bound.
            for blob in &recovered_blobs {
                let extent = match blob.committed_reclaimable_prefix() {
                    Ok(Some(extent)) => extent,
                    Ok(None) => continue,
                    Err(e) if e.is_environmental() => return Err(e),
                    Err(e) => {
                        log::warn!(
                            "blob file {:?} carries a committed frontier whose reclaimable \
                             extent could not be re-derived ({e}); its consumed prefix stays \
                             allocated until the next relocation",
                            blob.id(),
                        );
                        continue;
                    }
                };
                deletion_pause.retain_reclaim(
                    Arc::clone(&blob.0.fs),
                    blob.0.path.clone(),
                    alloc::vec![extent],
                );
            }
            deletion_pause.retry_pending_reclaims();
        }

        Ok(Self(Arc::new(inner)))
    }

    /// Creates a new LSM-tree in a directory.
    fn create_new(
        config: Config,
        // The folders that gained an entry when `Tree::open` made the tree
        // folder, to lock it.
        made_by_open: &[crate::path::PathBuf],
        // Whether this creation syncs those folders, or its caller does.
        names: NewFolderNames,
        // The cross-process directory lock acquired by `Tree::open`, held for
        // the tree's lifetime.
        #[cfg(feature = "std")] directory_lock: Option<Box<dyn crate::fs::FsFile>>,
    ) -> crate::Result<Self> {
        use crate::file::{BLOBS_FOLDER, fsync_directory};
        use crate::fs::SyncMode;
        use crate::path::PathBuf;

        /// Adds `folder` on `fs` to `folders` unless it is there already.
        fn once(folders: &mut Vec<(PathBuf, Arc<dyn Fs>)>, folder: &Path, fs: &Arc<dyn Fs>) {
            if !folders
                .iter()
                .any(|(at, on)| at == folder && Arc::ptr_eq(on, fs))
            {
                folders.push((folder.to_path_buf(), Arc::clone(fs)));
            }
        }

        let path = config.path.clone();
        log::trace!("Creating LSM-tree at {}", path.display());

        let sync_mode = config.sync_mode;

        // Every folder that gains a new entry is synced once, before the first
        // snapshot is written, so a sync that fails fails the creation before
        // there is a tree for a retry to open instead. The tree folder on the
        // tree's own backend is the one exception: the directory sync that
        // makes the snapshot's name durable makes every name made in it
        // durable too. A route on another backend holds its own names, even
        // one whose path lies inside the tree folder. The folders above the
        // tree folder are left to the caller under `NewFolderNames::Deferred`,
        // which syncs them once for a batch of trees after all of them.
        let mut holders: Vec<(PathBuf, Arc<dyn Fs>)> = Vec::new();
        // Every folder a chain made, on its backend: what a failed creation
        // removes, so a retry makes the chain anew and syncs it, rather than
        // finding folders whose names were never made durable.
        let mut made: Vec<(PathBuf, Arc<dyn Fs>)> = Vec::new();
        // The open made the tree folder already, to lock it, and every folder
        // above it that did not exist: their names are new all the same.
        for folder in made_folders(&path, made_by_open) {
            once(&mut made, &folder, &config.fs);
        }
        if names == NewFolderNames::Synced {
            for holder in made_by_open {
                once(&mut holders, holder, &config.fs);
            }
        }

        let built = (|| -> crate::Result<()> {
            // A tree folder that a restore made and locked before this open:
            // probed under the cleanup, so a probe that fails takes back the
            // folders found missing before it rather than leave them unsynced.
            let tree_holders = new_entry_holders(&*config.fs, &path)?;
            for folder in made_folders(&path, &tree_holders) {
                once(&mut made, &folder, &config.fs);
            }
            for holder in &tree_holders {
                once(&mut holders, holder, &config.fs);
            }
            (*config.fs).create_dir_all(&path)?;
            for (tables_folder, folder_fs) in config.all_tables_folders() {
                let covered = Arc::ptr_eq(&folder_fs, &config.fs);
                let folder_holders = new_entry_holders(&*folder_fs, &tables_folder)?;
                for folder in made_folders(&tables_folder, &folder_holders) {
                    once(&mut made, &folder, &folder_fs);
                }
                for holder in folder_holders {
                    if !(covered && holder == path) {
                        once(&mut holders, &holder, &folder_fs);
                    }
                }
                folder_fs.create_dir_all(&tables_folder)?;
            }
            if config.kv_separation_opts.is_some() {
                let blobs = path.join(BLOBS_FOLDER);
                if !(*config.fs).exists(&blobs)? {
                    once(&mut made, &blobs, &config.fs);
                }
                (*config.fs).create_dir_all(&blobs)?;
            }
            // A barrier orders syncs on its own device only: the last sync of
            // the creation on each other device than the tree's is a full one,
            // and the ones before it there are ordered ahead of it.
            let tree_volume = config.fs.volume_id(&path);
            let volumes: Vec<Option<u64>> = holders
                .iter()
                .map(|(folder, folder_fs)| folder_fs.volume_id(folder))
                .collect();
            for (at, (folder, folder_fs)) in holders.iter().enumerate() {
                let volume = volumes.get(at).copied().flatten();
                let foreign = volume.is_none() || volume != tree_volume;
                let last_there =
                    volume.is_none() || !volumes.iter().skip(at + 1).any(|later| *later == volume);
                let mode = if sync_mode == SyncMode::Barrier && foreign && last_there {
                    SyncMode::Full
                } else {
                    sync_mode
                };
                fsync_directory(folder, &**folder_fs, mode)?;
            }
            Ok(())
        })();

        let config_fs = Arc::clone(&config.fs);
        let created = built.and_then(|()| {
            TreeInner::create_new(
                config,
                #[cfg(feature = "std")]
                directory_lock,
            )
        });
        match created {
            Ok(inner) => Ok(Self(Arc::new(inner))),
            Err(e) => {
                undo_creation(Some((&path, &config_fs)), made, &holders);
                Err(e)
            }
        }
    }

    /// Recovers the level manifest, loading all tables from disk.
    ///
    /// When [`level_routes`](Config::level_routes) is configured, all
    /// configured table folders are scanned so tables on different storage
    /// tiers are discovered correctly.
    #[expect(
        clippy::too_many_lines,
        reason = "recovery logic is inherently complex"
    )]
    fn recover_levels<P: AsRef<Path>>(
        tree_path: P,
        tree_id: TreeId,
        config: &Config,
        #[cfg(feature = "metrics")] metrics: &Arc<Metrics>,
    ) -> crate::Result<(Version, PooledFiles)> {
        use crate::{TableId, file::fsync_directory};

        let tree_path = tree_path.as_ref();

        let recovery = recover(
            tree_path,
            &*config.fs,
            config.manifest_recovery_mode,
            config.encryption.clone(),
        )?;

        // The installed on-disk snapshot: the generation orphan cleanup
        // must preserve. Intermediate versions live only in the edit log, so the
        // latest version id (`version.id()`) has no `v{id}` file of its own.
        let snapshot_id = recovery.snapshot_id;
        let mut sweep = OpenSweep::default();

        let mut table_map = {
            let mut result: crate::HashMap<
                TableId,
                (
                    u8, /* Level index */
                    Checksum,
                    SeqNo,
                    TableId, /* L0 recency */
                ),
            > = crate::HashMap::default();

            for (level_idx, table_ids) in recovery.table_ids.iter().enumerate() {
                for run in table_ids {
                    for table in run {
                        #[expect(
                            clippy::expect_used,
                            reason = "there are always less than 256 levels"
                        )]
                        result.insert(
                            table.id,
                            (
                                level_idx
                                    .try_into()
                                    .expect("there are less than 256 levels"),
                                table.checksum,
                                table.global_seqno,
                                table.recency,
                            ),
                        );
                    }
                }
            }

            result
        };

        let cnt = table_map.len();

        // Immutable snapshot of every table id the manifest knows. `table_map`
        // is drained as tables are recovered below, so it cannot answer "is this
        // id live?" order-independently; this set can. Used to sweep an orphaned
        // `.heal-attest` sidecar whose SST was retired.
        let manifest_ids: crate::HashSet<TableId> = table_map.keys().copied().collect();

        log::debug!("Recovering {cnt} tables from {}", tree_path.display());

        let progress_mod = match cnt {
            _ if cnt <= 20 => 1,
            _ if cnt <= 100 => 10,
            _ => 100,
        };

        let mut tables = vec![];
        // Track recovered table IDs so duplicate sightings (via symlinks,
        // junctions, or case-insensitive aliases of the same directory) are
        // skipped rather than orphan-deleted.
        let mut recovered_table_ids: crate::HashSet<TableId> = crate::HashSet::default();
        let mut orphaned_tables: Vec<(crate::path::PathBuf, Arc<dyn crate::fs::Fs>)> = vec![];
        // Copies the digest PROVED stale. Left on disk they are worse than
        // clutter: once the winning route is removed or temporarily unmounted,
        // such a file is the only sighting of its id, arbitration is skipped
        // for want of a duplicate, and the stale generation is served instead
        // of the missing route being reported. They are swept only after a
        // winner for that id is established, so a scan that never finds one
        // keeps every copy it has.
        let mut rejected_copies: Vec<(TableId, crate::path::PathBuf, Arc<dyn crate::fs::Fs>)> =
            Vec::new();
        // Where an ambiguous id was accepted from, so a LATER sighting of it can
        // be judged against the winner rather than merely skipped.
        let mut accepted_copies: crate::HashMap<
            TableId,
            (crate::path::PathBuf, Arc<dyn crate::fs::Fs>),
        > = crate::HashMap::default();
        // First recovery failure per manifest id, kept until a later routed
        // folder yields a copy that opens. Whatever is left once every folder
        // is scanned is a table the manifest names and no copy delivers, so
        // its error is the open's.
        let mut unrecovered_sightings: crate::HashMap<TableId, crate::Error> =
            crate::HashMap::default();
        // Repair replacements whose authority could not be settled against the
        // damaged original beside them. Held until every folder is scanned: a
        // later routed copy that opens against the manifest settles it (the temp
        // is then provably NOT what the manifest names, so it is swept there and
        // then), and only an id no copy delivers surfaces its ambiguity.
        // A LIST, not a per-id map: routing can put a temp for the same id in
        // more than one folder, and each one is a file that has to be settled.
        let mut deferred_temps: Vec<(
            TableId,
            crate::path::PathBuf,
            Arc<dyn crate::fs::Fs>,
            crate::Error,
        )> = Vec::new();

        // Scan all configured table folders (primary + level routes).
        let all_folders = config.all_tables_folders();

        // One listing per folder, taken up front. The recovery loop has to know
        // whether an id is sighted in MORE THAN ONE routed folder BEFORE it
        // accepts the first sighting, and answering that later would mean
        // listing every folder a second time.
        let mut folder_scans: Vec<(
            &crate::path::PathBuf,
            &Arc<dyn crate::fs::Fs>,
            Vec<crate::fs::FsDirEntry>,
        )> = Vec::with_capacity(all_folders.len());
        // Ids present in more than one folder. Only these are digest-arbitrated
        // at open: a post-commit sweep that failed leaves an INTACT stale twin,
        // and `Table::recover` parses structure without re-deriving the
        // manifest's digest, so it opens the stale generation just as happily.
        // Ids sighted once cannot be ambiguous, and hashing them would turn
        // every open into a full read of the tree.
        let mut folder_sightings: crate::HashMap<TableId, usize> = crate::HashMap::default();
        for (table_base_folder, folder_fs) in &all_folders {
            if !folder_fs.exists(table_base_folder)? {
                folder_fs.create_dir_all(table_base_folder)?;
                fsync_directory(table_base_folder, &**folder_fs, config.sync_mode)?;
                if let Some(parent) = table_base_folder.parent() {
                    fsync_directory(parent, &**folder_fs, config.sync_mode)?;
                    if let Some(grandparent) = parent.parent() {
                        fsync_directory(grandparent, &**folder_fs, config.sync_mode)?;
                    }
                }
            }

            // Pending repair swaps resolve FIRST: a committed swap's `{id}` file
            // is the superseded source until the rename lands, so adopting it
            // before the temp entry is processed would hand this session a
            // handle onto bytes the finished swap then replaces on disk.
            let mut dirents = folder_fs.read_dir(table_base_folder)?;
            dirents.sort_by_key(|e| {
                !matches!(
                    crate::file::TableDirEntry::classify(&e.file_name),
                    crate::file::TableDirEntry::RepairTmp(_)
                )
            });
            for dirent in &dirents {
                if let crate::file::TableDirEntry::Table(id) =
                    crate::file::TableDirEntry::classify(&dirent.file_name)
                {
                    *folder_sightings.entry(id).or_insert(0) += 1;
                }
            }
            folder_scans.push((table_base_folder, folder_fs, dirents));
        }
        let ambiguous_ids: crate::HashSet<TableId> = folder_sightings
            .into_iter()
            .filter(|(_, count)| *count > 1)
            .map(|(id, _)| id)
            .collect();

        // The empty table files no version names, per folder: the pool each
        // folder kept, adopted by the tree.
        let mut pooled: PooledFiles = Vec::new();
        let mut pooled_ids: Vec<TableId> = Vec::new();
        for (table_base_folder, folder_fs, dirents) in folder_scans {
            for dirent in dirents {
                let crate::fs::FsDirEntry {
                    path: table_file_path,
                    file_name,
                    is_dir,
                } = dirent;

                let table_file_name = &file_name;
                if is_dir {
                    log::warn!(
                        "Skipping unexpected directory in tables folder: {}",
                        table_file_path.display()
                    );
                    continue;
                }

                // One grammar decides what each name IS (`TableDirEntry`, shared
                // with the repair scan so the two can never disagree on
                // ownership); this match is the open's POLICY for each kind.
                let table_id = match crate::file::TableDirEntry::classify(table_file_name) {
                    // An in-place heal's detach copy, renamed over the live path
                    // on success: a survivor is a crash leftover no manifest ever
                    // references. Sweep it.
                    crate::file::TableDirEntry::HealTmp(_) => {
                        log::warn!(
                            "Removing abandoned heal copy: {}",
                            table_file_path.display()
                        );
                        sweep.remove(folder_fs, &table_file_path);
                        continue;
                    }
                    // A crashed attestation publish: either the live sidecar it
                    // would have replaced still bridges the crash window, or the
                    // heal is re-run. Disposable.
                    crate::file::TableDirEntry::HealAttestTmp(_) => {
                        log::warn!(
                            "Removing abandoned heal-attest temp: {}",
                            table_file_path.display()
                        );
                        sweep.remove(folder_fs, &table_file_path);
                        continue;
                    }
                    // A LIVE table's pending attestation is preserved (the next
                    // scrub reconciles a crashed digest refresh through it). One
                    // whose SST left the manifest is unreconcilable forever:
                    // sweep the orphan rather than re-process it on every open.
                    crate::file::TableDirEntry::HealAttest(attest_id) => {
                        if !manifest_ids.contains(&attest_id) {
                            log::warn!(
                                "Removing orphaned heal attestation (its table is gone): {}",
                                table_file_path.display()
                            );
                            sweep.remove(folder_fs, &table_file_path);
                        }
                        continue;
                    }
                    // A crashed bound publish. Disposable.
                    crate::file::TableDirEntry::RestrictBoundTmp(_) => {
                        log::warn!(
                            "Removing abandoned restrict-bound temp: {}",
                            table_file_path.display()
                        );
                        sweep.remove(folder_fs, &table_file_path);
                        continue;
                    }
                    // A LIVE table's restriction bound is preserved (manifest
                    // repair reads it); an ORPHAN one is swept so a reused id
                    // cannot later pick up a stale restriction.
                    crate::file::TableDirEntry::RestrictBound(bound_id) => {
                        if !manifest_ids.contains(&bound_id) {
                            log::warn!(
                                "Removing orphaned restrict-bound sidecar (its table is gone): {}",
                                table_file_path.display()
                            );
                            sweep.remove(folder_fs, &table_file_path);
                        }
                        continue;
                    }
                    // A repair's replacement still at its temp name. The manifest
                    // is the authority on what it is — but it names the id in
                    // BOTH crash cases (before the commit its entry still
                    // describes the SOURCE beside the temp), so the entry's
                    // checksum decides: only a committed repair recorded the
                    // temp's digest, and it died before the swap — this file is
                    // what the manifest describes, so the swap is finished.
                    // Any other temp is an abandoned build (possibly truncated
                    // mid-write), and swapping it in would destroy the source
                    // the manifest names: it is garbage. An open resolves this
                    // exactly as a re-run of the repair would, from the durable
                    // manifest alone.
                    crate::file::TableDirEntry::RepairTmp(tmp_id) => {
                        #[cfg(feature = "std")]
                        {
                            let published = match table_map.get(&tmp_id) {
                                Some(&(_, manifest_checksum, _, _)) => {
                                    match crate::repair::repair_tmp_is_published(
                                        config,
                                        folder_fs,
                                        &table_file_path,
                                        tmp_id,
                                        manifest_checksum,
                                        recovery.restrictions.get(&tmp_id),
                                    ) {
                                        Ok(published) => published,
                                        // A refused mount / missing key says
                                        // nothing about which copy the manifest
                                        // names: surface it.
                                        Err(e) if e.is_environmental() => return Err(e),
                                        // Neither this temp nor the damaged
                                        // original beside it can prove it is the
                                        // manifest's copy. A LATER routed folder
                                        // may still hold that copy, and deciding
                                        // here would end the open on a leftover a
                                        // failed post-commit sweep left behind.
                                        // Defer: leave the temp untouched, keep
                                        // the ambiguity, and let the end of the
                                        // scan decide (see `deferred_temps`).
                                        Err(e) => {
                                            log::warn!(
                                                "repair replacement {} is ambiguous ({e}); \
                                                 deferring until every routed folder is scanned",
                                                table_file_path.display(),
                                            );
                                            deferred_temps.push((
                                                tmp_id,
                                                table_file_path,
                                                Arc::clone(folder_fs),
                                                e,
                                            ));
                                            continue;
                                        }
                                    }
                                }
                                None => false,
                            };
                            if published {
                                log::warn!(
                                    "Finishing a repair's pending swap of table {tmp_id}: {}",
                                    table_file_path.display()
                                );
                                crate::repair::commit_repair_tmp(
                                    folder_fs.as_ref(),
                                    &table_file_path,
                                    &table_base_folder.join(tmp_id.to_string()),
                                    config.sync_mode,
                                    recovery.restrictions.contains_key(&tmp_id),
                                )?;
                            } else {
                                log::warn!(
                                    "Removing abandoned repair replacement: {}",
                                    table_file_path.display()
                                );
                                // A RESTRICTED salvage also wrote
                                // `{temp}.restrict-bound`; that companion must
                                // go with the temp — its name classifies as
                                // Foreign and would fail this very open.
                                let companion =
                                    crate::restrict_bound::sidecar_path(&table_file_path);
                                if folder_fs.exists(&companion)? {
                                    sweep.remove(folder_fs, &companion);
                                }
                                sweep.remove(folder_fs, &table_file_path);
                            }
                        }
                        // Without the repair module nothing here can verify or
                        // finish a swap the manifest may describe, and sweeping
                        // the temp could destroy the only copy of what the
                        // manifest names.
                        #[cfg(not(feature = "std"))]
                        {
                            if manifest_ids.contains(&tmp_id) {
                                log::error!(
                                    "Table {tmp_id} exists only as an unpublished repair \
                                     replacement; run a repair to finish it: {}",
                                    table_file_path.display()
                                );
                                return Err(crate::Error::Unrecoverable);
                            }
                            log::warn!(
                                "Removing abandoned repair replacement: {}",
                                table_file_path.display()
                            );
                            // Same companion rule as the std arm above (the
                            // `restrict_bound` helper is std-gated, so the
                            // name is spelled out).
                            let companion = table_base_folder.join(alloc::format!(
                                "{tmp_id}{}.restrict-bound",
                                crate::file::REPAIR_TMP_SUFFIX
                            ));
                            if folder_fs.exists(&companion)? {
                                sweep.remove(folder_fs, &companion);
                            }
                            sweep.remove(folder_fs, &table_file_path);
                        }
                        continue;
                    }
                    // The companion's fate followed its temp when that entry
                    // resolved (first, by sort order): a finished swap renamed
                    // it into place, an abandoned build's sweep removed it. A
                    // survivor here is an orphan (its temp is gone) — remove
                    // it rather than reject the whole open over it.
                    crate::file::TableDirEntry::RepairTmpCompanion(_) => {
                        if folder_fs.exists(&table_file_path)? {
                            log::warn!(
                                "Removing orphaned repair-replacement sidecar: {}",
                                table_file_path.display()
                            );
                            sweep.remove(folder_fs, &table_file_path);
                        }
                        continue;
                    }
                    // Not a shape the engine names, so not engine state: passed
                    // over untouched. Refusing the store here would let any
                    // stray file (an operator's note, a backup, a desktop
                    // environment's directory metadata) make it unopenable,
                    // which is why scanners used to carry a list of foreign
                    // names to tolerate. The grammar answers it instead.
                    crate::file::TableDirEntry::Foreign => {
                        log::debug!(
                            "Ignoring {table_file_name:?} in the tables folder: not an engine file"
                        );
                        continue;
                    }
                    crate::file::TableDirEntry::Table(id) => id,
                };

                // Remove from map to prevent duplicate recovery if the same
                // table file exists in multiple scanned folders.
                if let Some(entry) = table_map.remove(&table_id) {
                    let (level_idx, checksum, global_seqno, recency) = entry;
                    let pin_filter = config.filter_block_pinning_policy.get(level_idx.into());
                    let pin_index = config.index_block_pinning_policy.get(level_idx.into());

                    let table = {
                        let mut params = crate::table::RecoverParams::new(
                            table_file_path.clone(),
                            checksum,
                            table_id,
                            folder_fs.clone(),
                            config.comparator.clone(),
                            config.cache.clone(),
                        );
                        params.global_seqno = global_seqno;
                        params.recency = Some(recency);
                        params.tree_id = tree_id;
                        params.descriptor_table.clone_from(&config.descriptor_table);
                        params.pin_filter = pin_filter;
                        params.pin_index = pin_index;
                        params.encryption.clone_from(&config.encryption);
                        params.prefix_extractor.clone_from(&config.prefix_extractor);
                        #[cfg(zstd_any)]
                        {
                            params.zstd_dictionaries = config.current_zstd_dictionaries();
                        }
                        #[cfg(feature = "metrics")]
                        {
                            params.metrics = metrics.clone();
                        }
                        match Table::recover(params) {
                            Ok(table) => table,
                            Err(e) => {
                                // A routed tree can hold this id in more than
                                // one folder, and repair's post-commit sweep of
                                // the copy it displaced can fail after the
                                // manifest is already durable. Ending the search
                                // on the first sighting would then shut the tree
                                // on a table that is present and intact one
                                // folder over. Put the id back, remember the
                                // failure, and keep scanning; if no folder
                                // yields the manifest's copy, this error is what
                                // the open reports.
                                log::warn!(
                                    "table {table_id} at {} did not recover ({e}); \
                                     looking for another routed copy",
                                    table_file_path.display(),
                                );
                                table_map.insert(table_id, entry);
                                unrecovered_sightings.entry(table_id).or_insert(e);
                                continue;
                            }
                        }
                    };

                    // Opening proves the file is STRUCTURALLY sound, never that
                    // it is the generation the manifest committed: recover parses
                    // metadata and loads data blocks lazily. Where two folders
                    // hold this id, take the digest as the arbiter, exactly as
                    // repair does, so a stale twin an interrupted sweep left
                    // behind cannot win on scan order.
                    if ambiguous_ids.contains(&table_id) {
                        // The candidate is UNRESTRICTED here: the manifest's
                        // restrictions are attached when the version is built,
                        // which is after this scan. Digesting it whole would
                        // compare against a live-suffix digest and reject every
                        // copy of a restricted id, so the bound is supplied
                        // explicitly.
                        let live =
                            match table.suffix_checksum_for(recovery.restrictions.get(&table_id)) {
                                Ok(live) => live,
                                // A fault in the ENVIRONMENT says nothing about
                                // these bytes, so it propagates and a retry can
                                // re-read them.
                                Err(e) if e.is_environmental() => return Err(e),
                                // Anything else is damage to THIS copy: metadata
                                // can parse while a data extent is unreadable, and
                                // ending the scan on it would let a damaged
                                // displaced copy permanently block the intact one a
                                // folder over. Same treatment as a failed recover.
                                Err(e) => {
                                    log::warn!(
                                        "table {table_id} at {} could not be digested ({e}); \
                                     looking for another routed copy",
                                        table_file_path.display(),
                                    );
                                    table_map.insert(table_id, entry);
                                    unrecovered_sightings.entry(table_id).or_insert(e);
                                    continue;
                                }
                            };
                        if live != checksum {
                            log::warn!(
                                "table {table_id} at {} is not the generation the manifest \
                                 committed; looking for another routed copy",
                                table_file_path.display(),
                            );
                            table_map.insert(table_id, entry);
                            unrecovered_sightings.entry(table_id).or_insert(
                                crate::Error::ChecksumMismatch {
                                    got: live,
                                    expected: checksum,
                                },
                            );
                            rejected_copies.push((
                                table_id,
                                table_file_path,
                                Arc::clone(folder_fs),
                            ));
                            continue;
                        }
                        accepted_copies
                            .insert(table_id, (table_file_path.clone(), Arc::clone(folder_fs)));
                    }

                    tables.push(table);
                    recovered_table_ids.insert(table_id);
                    unrecovered_sightings.remove(&table_id);

                    if tables.len() % progress_mod == 0 {
                        log::debug!("Recovered {}/{cnt} tables", tables.len());
                    }
                } else if recovered_table_ids.contains(&table_id) {
                    // Duplicate sighting of an already-recovered manifest table
                    // (e.g., via symlink or case-insensitive alias). Never an
                    // orphan: that would delete the live SST. But an id the
                    // digest arbitrated has a KNOWN answer, so a later sighting
                    // is judged rather than merely skipped, or a stale twin
                    // scanned after the winner would outlive the open.
                    let stale = match accepted_copies.get(&table_id) {
                        Some((winner, winner_fs)) if *winner != table_file_path => {
                            differs_byte_for_byte(
                                &**winner_fs,
                                winner,
                                folder_fs.as_ref(),
                                &table_file_path,
                            )?
                        }
                        _ => false,
                    };
                    if stale {
                        rejected_copies.push((
                            table_id,
                            table_file_path.clone(),
                            Arc::clone(folder_fs),
                        ));
                    }
                    log::warn!(
                        "Skipping duplicate sighting of manifest table {table_id} in {}",
                        table_file_path.display(),
                    );
                } else if config.table_file_pool > 0
                    // The counter starts above every pooled id, so one at its
                    // top would leave it no id to hand out.
                    && table_id < crate::seqno::MAX_SEQNO
                    && folder_fs
                        .metadata(&table_file_path)
                        .is_ok_and(|meta| meta.is_file && meta.len == 0)
                    // A table is written into a pooled file where it lies: a
                    // symlink would take it to a file the tree never made.
                    && folder_fs
                        .read_link(&table_file_path)
                        .is_ok_and(|target| target.is_none())
                {
                    // No version names it and no table is empty: a pooled
                    // file, used again rather than made anew. Anything else
                    // unnamed, or whose kind cannot be read, is an orphan like
                    // any other.
                    pooled_ids.push(table_id);
                } else {
                    orphaned_tables.push((table_file_path, folder_fs.clone()));
                }
            }
            if !pooled_ids.is_empty() {
                pooled.push((
                    table_base_folder.clone(),
                    Arc::clone(folder_fs),
                    core::mem::take(&mut pooled_ids),
                ));
            }
        }

        // Every folder is scanned, so an id that never recovered has no copy
        // left to try. Report the failure that stopped it — a missing-table
        // diagnostic would hide the reason the file on disk could not be read.
        if let Some((_, e)) = unrecovered_sightings
            .into_iter()
            .find(|(id, _)| table_map.contains_key(id))
        {
            return Err(e);
        }

        // A deferred replacement whose id RECOVERED from some folder is settled:
        // that copy matched the manifest, so this temp is provably NOT what the
        // manifest names — an abandoned build, removed here exactly as the
        // in-scan branch removes one. One whose id never arrived is still
        // ambiguous: the temp may be the only copy of what the manifest
        // describes, so the ambiguity is what the open reports.
        #[cfg(feature = "std")]
        for (tmp_id, temp_path, temp_fs, ambiguity) in deferred_temps {
            if !recovered_table_ids.contains(&tmp_id) {
                return Err(ambiguity);
            }
            log::warn!(
                "Removing abandoned repair replacement for table {tmp_id} (the copy this open \
                 recovered is what the manifest names): {}",
                temp_path.display(),
            );
            // The restricted-salvage companion classifies as Foreign and would
            // fail the next open, so it goes with the temp.
            let companion = crate::restrict_bound::sidecar_path(&temp_path);
            if temp_fs.exists(&companion)? {
                sweep.remove(&temp_fs, &companion);
            }
            sweep.remove(&temp_fs, &temp_path);
        }

        if tables.len() < cnt {
            // Route configuration is NOT persisted.  This is a best-effort
            // heuristic: it checks each missing table's level against the
            // current routes, but cannot detect same-level path changes
            // (e.g., L0 routed to /hot_old → /hot_new).  Persisting route
            // provenance per-table in the manifest would enable exact
            // detection but requires a format change.
            //
            // - Level IS covered by a current route → its directory was scanned
            //   and the file was not found → data corruption / deletion.
            // - Level is NOT covered → falls back to primary (always scanned).
            //   If the table isn't there, it was likely in a route that has
            //   since been removed from the config.
            //
            // Return RouteMismatch only when ALL missing tables are on levels
            // not covered by any current route.  If ANY missing table is on a
            // covered level, at least one SST was genuinely lost.
            if let Some(routes) = &config.level_routes {
                let all_missing_uncovered = table_map
                    .values()
                    .all(|(level, ..)| !routes.iter().any(|r| r.levels.contains(level)));

                if all_missing_uncovered {
                    let found = tables.len();
                    let missing_ids: Vec<_> = table_map.keys().collect();

                    log::error!(
                        "Route mismatch: expected {cnt} tables but found {found} — \
                         level_routes do not cover all previously used levels. \
                         Missing table IDs: {missing_ids:?}",
                    );
                    return Err(crate::Error::RouteMismatch {
                        expected: cnt,
                        found,
                    });
                }
            }

            log::error!(
                "Recovered less tables than expected: {:?}",
                table_map.keys(),
            );
            return Err(crate::Error::Unrecoverable);
        }

        log::debug!("Successfully recovered {} tables", tables.len());

        // Pair each blob file with its live-data frontier: a file whose consumed
        // prefix was reclaimed in place records a checksum over the suffix only,
        // so the recovered view must carry the offset that digest starts at.
        let blob_ids_with_frontier: Vec<(crate::vlog::BlobFileId, crate::Checksum, u64)> = recovery
            .blob_file_ids
            .iter()
            .map(|&(id, checksum)| {
                (
                    id,
                    checksum,
                    recovery.blob_restrictions.get(&id).copied().unwrap_or(0),
                )
            })
            .collect();
        let (blob_files, orphaned_blob_files) = crate::vlog::recover_blob_files(
            &tree_path.join(crate::file::BLOBS_FOLDER),
            &blob_ids_with_frontier,
            tree_id,
            config.descriptor_table.as_ref(),
            &config.fs,
            #[cfg(zstd_any)]
            &config.current_zstd_dictionaries(),
        )?;

        let version =
            Version::from_recovery(recovery, &tables, &blob_files, config.comparator.as_ref())?;

        // Registered ids the tree no longer holds are dropped. One a recovered
        // file names cannot be among them, since that file would have refused
        // to open; the rest owe a reader nothing once the file is gone, while
        // every checkpoint copies what the version registers and would fail on
        // the missing file.
        #[cfg(zstd_any)]
        let version = {
            let held = config.current_zstd_dictionaries();
            if version.dicts().iter().all(|id| held.get(*id).is_some()) {
                version
            } else {
                let dicts = version
                    .dicts()
                    .iter()
                    .copied()
                    .filter(|id| held.get(*id).is_some())
                    .collect();
                version.with_dicts(dicts)
            }
        };

        // The state this open recovered becomes durable before the tree is
        // served: a caller takes the persisted seqno of the tree it opened as
        // the point up to which its own log may be trimmed, and what was read
        // may be an edit or a snapshot name whose sync failed, which a power
        // loss can still take back. Syncing the files read is no proof (a
        // sync after a failed one may report success for pages the kernel
        // already dropped), so the recovered state is written as a fresh
        // snapshot under the next id, installed as a rotation installs one:
        // its bytes synced, renamed into place, the folder synced. A repair
        // report the tree still owes rides in the version, so the snapshot
        // carries it on.
        //
        // A tree whose id reached the top half of the range goes back to id
        // 0 instead. Recovery takes the snapshot with the highest id, so no
        // other may be left above the new one: every manifest file but the
        // snapshot read goes, durably, before the install, and that snapshot
        // goes, durably, right after it. A power loss in between leaves the
        // snapshot read as the highest, which a reopen installs again.
        let renumbered = version.is_renumbered_on_open();
        if renumbered {
            log::warn!(
                "version {} is in the top half of the id range; reinstalling the tree as \
                 version 0",
                version.id()
            );
            Self::remove_manifests_but(tree_path, snapshot_id, &config.fs, config.sync_mode)?;
        }
        let version = version.reinstalled();
        crate::version::persist_version(
            tree_path,
            &version,
            config.comparator.name(),
            &*config.fs,
            Arc::new(config.initial_runtime_config.clone()),
            config.encryption.clone(),
            config.sync_mode,
        )?;
        if renumbered {
            Self::remove_manifests_but(tree_path, version.id(), &config.fs, config.sync_mode)?;
        }

        // Republish any restriction sidecar that never landed. The sidecar is
        // written AFTER its slice commits, so a failure (or a crash) in that
        // window leaves a committed restriction with no `.restrict-bound` file.
        // The manifest still describes it, so a normal open is unaffected — but
        // a later manifest-loss repair would find an unrestricted input beside
        // the slice output and publish BOTH histories, applying every merge
        // operand of the consumed prefix twice (operands are deliberately never
        // deduplicated across sources). The manifest is the authority for the
        // bound, so the missing sidecar is derived from it here, once the
        // install above made that manifest durable: derived from a manifest
        // still in an unsynced log, it would outlive that manifest when a
        // power loss takes it back, and drop an input prefix whose
        // replacement went with it.
        #[cfg(feature = "std")]
        Self::republish_missing_restriction_sidecars(&version, config)?;

        // Everything of the generation read goes, now that it is superseded:
        // its snapshot and its log.
        Self::cleanup_orphaned_version(tree_path, version.id(), &config.fs, &mut sweep)?;

        // A copy the digest rejected goes only once its id has a winner: with
        // one it is provably superseded, without one it may be all that is
        // left. Its `.restrict-bound` companion goes with it, or the next scan
        // classifies that name as foreign and fails the open.
        for (table_id, path, copy_fs) in rejected_copies {
            if !recovered_table_ids.contains(&table_id) {
                continue;
            }
            log::warn!(
                "Removing superseded copy of table {table_id}: {}",
                path.display()
            );
            #[cfg(feature = "std")]
            {
                let companion = crate::restrict_bound::sidecar_path(&path);
                if copy_fs.exists(&companion)? {
                    sweep.remove(&copy_fs, &companion);
                }
            }
            sweep.remove(&copy_fs, &path);
        }

        for (table_path, orphan_fs) in orphaned_tables {
            log::debug!("Deleting orphaned table {}", table_path.display());
            sweep.remove(&orphan_fs, &table_path);
        }

        for blob_file_path in orphaned_blob_files {
            log::debug!("Deleting orphaned blob file {}", blob_file_path.display());
            sweep.remove(&config.fs, &blob_file_path);
        }

        sweep.finish()?;
        Ok((version, pooled))
    }

    /// Writes the `.restrict-bound` sidecar of every restricted table in
    /// `version` that has none, so the bound the manifest holds is recoverable
    /// without it. An existing sidecar is REREAD rather than assumed good: its
    /// mere presence proves nothing, and a repair that later trusts a corrupt
    /// one derives a conservative bound (dropping up to one live block), while
    /// a valid-but-STALE one — the shape a second slice leaves when its own
    /// write fails — restricts LESS than reality and resurrects consumed rows.
    /// A sidecar that already records this table and this bound is left alone,
    /// so a healthy tree does not churn the file on every open. Failures
    /// propagate — an unrecoverable restriction is exactly what this closes, so
    /// silently skipping it would keep the window open.
    ///
    /// The sidecar is a filesystem artifact of the tight-space reclaim path, so
    /// this is a no-op without `std` — a build without it never writes one.
    #[cfg(feature = "std")]
    fn republish_missing_restriction_sidecars(
        version: &Version,
        config: &Config,
    ) -> crate::Result<()> {
        for table in version.iter_tables() {
            let Some(bound) = table.restrict_lower_bound() else {
                continue;
            };
            let recorded =
                crate::restrict_bound::read(&*table.fs, &table.path, config.encryption.as_deref())?;
            let state = match &recorded {
                crate::restrict_bound::SidecarRead::Present(id, recorded_bound)
                    if *id == table.metadata.id && recorded_bound.as_slice() == bound.as_ref() =>
                {
                    continue;
                }
                crate::restrict_bound::SidecarRead::Present(..) => {
                    "disagrees with the manifest (stale bound or another table)"
                }
                crate::restrict_bound::SidecarRead::Corrupt => "unreadable",
                crate::restrict_bound::SidecarRead::Missing => "absent",
            };
            log::warn!(
                "table {} carries a committed restriction whose sidecar is {state}; \
                 republishing it from the manifest",
                table.id(),
            );
            table.write_restrict_sidecar(bound, config.sync_mode)?;
        }
        Ok(())
    }

    /// Removes stale manifest files left by older generations: every `v{id}`
    /// snapshot except the live one (`v{snapshot_id}`) and every `edits-{id}`
    /// log except the live snapshot's (`edits-{snapshot_id}`). A crashed
    /// rotation can leak an old snapshot or its log; this sweeps them on open.
    /// The live snapshot and log are the installed generation.
    ///
    /// # Behavior change vs pre-Fs-trait code
    ///
    /// The previous implementation used `std::fs::read_dir` + `to_string_lossy()`,
    /// which silently skipped non-UTF-8 filenames. `Fs::read_dir` returns
    /// `InvalidData` for such entries instead (see [`FsDirEntry`](crate::fs::FsDirEntry) docs), so this
    /// function now fails fast on non-UTF-8 names. This is intentional: version
    /// files are always `v{u64}` — any non-UTF-8 entry indicates filesystem
    /// corruption and should surface as an error rather than be silently ignored.
    fn cleanup_orphaned_version(
        path: &Path,
        snapshot_id: crate::version::VersionId,
        fs: &Arc<dyn crate::fs::Fs>,
        sweep: &mut OpenSweep,
    ) -> crate::Result<()> {
        use crate::version::recovery::{ManifestFile, manifest_file_of};
        for dirent in fs.read_dir(path)? {
            if dirent.is_dir {
                continue;
            }
            let orphan = match manifest_file_of(&dirent.file_name) {
                Some(ManifestFile::Snapshot(id) | ManifestFile::Log(id)) => id != snapshot_id,
                Some(ManifestFile::Temporary(_)) => true,
                None => false,
            };
            if orphan {
                log::trace!("Cleanup orphaned manifest file {}", dirent.file_name);
                sweep.remove(fs, &dirent.path);
            }
        }

        Ok(())
    }

    /// Removes every manifest file [`Self::cleanup_orphaned_version`] finds
    /// stale beside snapshot `keep`, at once rather than after the install,
    /// and makes the removals durable.
    ///
    /// The snapshots go first, durably, and only then their logs: a snapshot
    /// that outlives its log would be recovered without the edits in it.
    fn remove_manifests_but(
        path: &Path,
        keep: crate::version::VersionId,
        fs: &Arc<dyn crate::fs::Fs>,
        sync_mode: crate::fs::SyncMode,
    ) -> crate::Result<()> {
        use crate::version::recovery::{ManifestFile, manifest_file_of};
        let mut snapshots = OpenSweep::default();
        for dirent in fs.read_dir(path)? {
            let other = match manifest_file_of(&dirent.file_name) {
                Some(ManifestFile::Snapshot(id)) => id != keep,
                Some(ManifestFile::Temporary(_)) => true,
                Some(ManifestFile::Log(_)) | None => false,
            };
            if !dirent.is_dir && other {
                snapshots.remove(fs, &dirent.path);
            }
        }
        snapshots.finish()?;
        crate::file::fsync_directory(path, &**fs, sync_mode)?;
        let mut rest = OpenSweep::default();
        Self::cleanup_orphaned_version(path, keep, fs, &mut rest)?;
        rest.finish()?;
        crate::file::fsync_directory(path, &**fs, sync_mode)?;
        Ok(())
    }
}

/// Who syncs the folders that gain an entry when an open makes a tree's
/// folder.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum NewFolderNames {
    /// The open, before the tree's first snapshot.
    Synced,
    /// The open's caller, once for a batch of trees after every one of them
    /// is made.
    Deferred,
}

/// A tree an open made, and what takes it back: its folder on its backend,
/// the folders that gained an entry making that folder, what the folder held
/// before the open when it existed, and who syncs those folders.
pub(crate) struct Creation {
    path: crate::path::PathBuf,
    fs: Arc<dyn Fs>,
    /// Nearest first; none when the tree folder existed already.
    holders: Vec<crate::path::PathBuf>,
    /// The names in the tree folder before the open; `None` when the open
    /// made the folder.
    found: Option<Vec<alloc::string::String>>,
    names: NewFolderNames,
    sync_mode: crate::fs::SyncMode,
}

impl Creation {
    /// Takes back `tree`, which this open made: what it put in its folder goes
    /// while its lock is still held, then the folders the open made, once
    /// empty, and the folders that held their names are synced where the open
    /// synced them, so the tree does not come back after a power loss.
    pub(crate) fn take_back(self, tree: Tree) {
        #[cfg(feature = "std")]
        let lock = tree.0.directory_lock.clone();
        drop(tree);
        self.empty();
        #[cfg(feature = "std")]
        drop(lock);
        undo_creation(None, self.made_folders(), &[]);
        if self.names == NewFolderNames::Synced {
            sync_made_names(&self.holders_on_backend());
        }
    }

    /// Removes what the tree put in its folder.
    fn empty(&self) {
        empty_tree_folder(&self.path, &self.fs, self.found.as_deref());
    }

    /// The folders the open made, on the tree's backend.
    fn made_folders(&self) -> Vec<(crate::path::PathBuf, Arc<dyn Fs>)> {
        made_folders(&self.path, &self.holders)
            .into_iter()
            .map(|folder| (folder, Arc::clone(&self.fs)))
            .collect()
    }

    /// The folders that gained an entry for the tree folder, on its backend.
    fn holders_on_backend(&self) -> Vec<(crate::path::PathBuf, Arc<dyn Fs>)> {
        self.holders
            .iter()
            .map(|holder| (holder.clone(), Arc::clone(&self.fs)))
            .collect()
    }
}

/// The names in the folder `path`.
fn folder_entries(fs: &dyn Fs, path: &Path) -> crate::Result<Vec<alloc::string::String>> {
    Ok(fs
        .read_dir(path)?
        .into_iter()
        .map(|entry| entry.file_name)
        .collect())
}

/// A tree a batch made, and while the batch runs, the tree's directory lock.
struct BatchMade {
    creation: Creation,
    #[cfg(feature = "std")]
    lock: Option<Arc<dyn crate::fs::FsFile>>,
}

/// Opens a tree for each config, making the missing ones, and syncs each
/// folder that gained a new tree's name once, after all of them: see
/// [`Config::open_many`].
pub(crate) fn open_batch(
    configs: impl IntoIterator<Item = Config>,
) -> crate::Result<Vec<crate::AnyTree>> {
    let mut trees = Vec::new();
    let mut made: Vec<BatchMade> = Vec::new();
    for config in configs {
        let fs = Arc::clone(&config.fs);
        let path = config.path.clone();
        let sync_mode = config.sync_mode;
        let holders = match new_entry_holders(&*fs, &path) {
            Ok(holders) => holders,
            Err(e) => {
                undo_batch(trees, made, None);
                return Err(e);
            }
        };
        match config.open_with(
            #[cfg(feature = "std")]
            crate::config::DirectoryLock::Acquire,
            NewFolderNames::Deferred,
        ) {
            Ok((tree, creation)) => {
                // A tree made in a folder that existed already is the batch's
                // as much as one whose folder it made: it is taken back too,
                // though the folder stays.
                if let Some(creation) = creation {
                    made.push(BatchMade {
                        #[cfg(feature = "std")]
                        lock: batch_tree(&tree).0.directory_lock.clone(),
                        creation,
                    });
                }
                trees.push(tree);
            }
            Err(e) => {
                // The failed open took back what it made; the folders that
                // gained an entry for it are synced with the batch's.
                let failed = Creation {
                    path,
                    fs,
                    holders,
                    found: None,
                    names: NewFolderNames::Deferred,
                    sync_mode,
                };
                undo_batch(trees, made, Some(&failed));
                return Err(e);
            }
        }
    }
    let holders = batch_holders(made.iter().map(|tree| &tree.creation));
    for (folder, fs, mode) in holders {
        if let Err(e) = crate::file::fsync_directory(&folder, &*fs, mode) {
            undo_batch(trees, made, None);
            return Err(e.into());
        }
    }
    Ok(trees)
}

/// The tree behind `tree`, whose folder holds the manifest and the lock.
#[cfg(feature = "std")]
fn batch_tree(tree: &crate::AnyTree) -> &Tree {
    match tree {
        crate::AnyTree::Standard(tree) => tree,
        crate::AnyTree::Blob(tree) => &tree.index,
    }
}

/// Whether `a` and `b` name one namespace of paths: one handle, or two
/// handles of one backend, as configs made one by one each hold their own
/// handle of the real file system.
fn same_backend(a: &Arc<dyn Fs>, b: &Arc<dyn Fs>) -> bool {
    Arc::ptr_eq(a, b) || a.backend_id().is_some_and(|id| b.backend_id() == Some(id))
}

/// The folders that hold the names of the trees `made`, each once, on its
/// backend, with the sync that makes them durable: each tree's own mode where
/// they agree and a full sync where they do not, and a full one under barrier
/// syncs for a folder on another device than a tree it holds, whose own syncs
/// a barrier there does not order.
fn batch_holders<'a>(
    made: impl Iterator<Item = &'a Creation>,
) -> Vec<(crate::path::PathBuf, Arc<dyn Fs>, crate::fs::SyncMode)> {
    use crate::fs::SyncMode;
    let mut holders: Vec<(crate::path::PathBuf, Arc<dyn Fs>, SyncMode)> = Vec::new();
    for tree in made {
        let tree_volume = tree.fs.volume_id(&tree.path);
        for folder in &tree.holders {
            let volume = tree.fs.volume_id(folder);
            let mode = if tree.sync_mode == SyncMode::Barrier
                && (volume.is_none() || volume != tree_volume)
            {
                SyncMode::Full
            } else {
                tree.sync_mode
            };
            match holders
                .iter_mut()
                .find(|(at, on, _)| at == folder && same_backend(on, &tree.fs))
            {
                Some((_, _, held)) if *held != mode => *held = SyncMode::Full,
                Some(_) => {}
                None => holders.push((folder.clone(), Arc::clone(&tree.fs), mode)),
            }
        }
    }
    holders
}

/// Takes back a failed batch: closes the trees it opened, removes what each
/// tree it made put in its folder while still holding that tree's lock, then
/// the folders it made once they are empty, and makes the removals durable by
/// syncing every folder that held a name the batch made, `failed`'s included,
/// so no tree of the batch comes back after a power loss.
fn undo_batch(trees: Vec<crate::AnyTree>, made: Vec<BatchMade>, failed: Option<&Creation>) {
    let holders: Vec<(crate::path::PathBuf, Arc<dyn Fs>)> =
        batch_holders(made.iter().map(|tree| &tree.creation).chain(failed))
            .into_iter()
            .map(|(folder, fs, _)| (folder, fs))
            .collect();
    // The trees close their files; each made one's lock stays held by `made`.
    drop(trees);
    // Another opener taking a lock now would have its tree taken back from
    // under it: what each tree holds goes while its lock is held.
    let mut folders = Vec::new();
    for tree in &made {
        tree.creation.empty();
        folders.extend(tree.creation.made_folders());
    }
    // Then the locks go, and only folders left empty with them, deepest
    // first: one the batch made for several of its trees goes after all of
    // them, and one a lock no longer keeps another opener out of may hold
    // that opener's tree by now.
    #[cfg(feature = "std")]
    for tree in made {
        drop(tree.lock);
    }
    undo_creation(None, folders, &[]);
    sync_made_names(&holders);
}

/// Removes what a tree made in the tree folder `path`, the lock file last:
/// everything in a folder the open made (`found` is `None`), and in one that
/// existed, holding `found`, only what was not there before. A tables or
/// blob folder that was there was empty, as a creation requires, so what it
/// holds now is the tree's. The lock file goes while the lock is still held,
/// so no opener is left holding the lock of a file another one can make
/// anew. What cannot be removed stays, and keeps the folder. A folder that
/// existed is synced, so its emptying is durable and no snapshot of the tree
/// comes back after a power loss.
fn empty_tree_folder(path: &Path, fs: &Arc<dyn Fs>, found: Option<&[alloc::string::String]>) {
    let entries = match fs.read_dir(path) {
        Ok(entries) => entries,
        Err(e) => {
            log::warn!(
                "could not list {} to take back the tree made there ({e})",
                path.display()
            );
            return;
        }
    };
    let (lock, rest): (Vec<_>, Vec<_>) = entries
        .into_iter()
        .partition(|entry| entry.file_name == crate::config::DIRECTORY_LOCK_FILE);
    let remove = |at: &Path, is_dir: bool| {
        let removed = if is_dir {
            fs.remove_dir_all(at)
        } else {
            fs.remove_file(at)
        };
        match removed {
            Ok(()) => {}
            Err(gone) if gone.kind() == crate::io::ErrorKind::NotFound => {}
            Err(kept) => log::warn!(
                "could not remove {} taking back the tree made there ({kept})",
                at.display()
            ),
        }
    };
    for entry in rest.into_iter().chain(lock) {
        let was_there = found.is_some_and(|found| found.contains(&entry.file_name));
        if !was_there {
            remove(&entry.path, entry.is_dir);
        } else if entry.is_dir
            && (entry.file_name == crate::file::TABLES_FOLDER
                || entry.file_name == crate::file::BLOBS_FOLDER)
        {
            match fs.read_dir(&entry.path) {
                Ok(inner) => {
                    for inner in inner {
                        remove(&inner.path, inner.is_dir);
                    }
                    // Files a power loss brought back here would read as a
                    // half-written tree to the next open.
                    if let Err(e) =
                        crate::file::fsync_directory(&entry.path, &**fs, crate::fs::SyncMode::Full)
                    {
                        log::warn!(
                            "could not sync {} after taking back the tree made there ({e})",
                            entry.path.display()
                        );
                    }
                }
                Err(e) => log::warn!(
                    "could not list {} to take back the tree made there ({e})",
                    entry.path.display()
                ),
            }
        }
    }
    if found.is_some()
        && let Err(e) = crate::file::fsync_directory(path, &**fs, crate::fs::SyncMode::Full)
    {
        log::warn!(
            "could not sync {} after taking back the tree made there ({e}); a power loss \
             may bring the tree back",
            path.display()
        );
    }
}

/// Takes back what a failed creation made: the folders in `made`, so a retry
/// makes them anew and syncs the folders `holders` that gained their names;
/// or, where one cannot be removed, those syncs now, since a retry finds it
/// existing and syncs nothing for it. `tree` names the tree folder (on its
/// backend) when everything in it is the creation's own.
fn undo_creation(
    tree: Option<(&Path, &Arc<dyn Fs>)>,
    mut made: Vec<(crate::path::PathBuf, Arc<dyn Fs>)>,
    holders: &[(crate::path::PathBuf, Arc<dyn Fs>)],
) {
    // Deepest first, so a folder is empty when its turn comes. The tree folder
    // goes with what the creation put in it; any other folder is shared with
    // whatever else may have been put there since it was found missing, which
    // no lock kept out: it is removed only while empty.
    made.sort_by_key(|(folder, _)| core::cmp::Reverse(folder.components().count()));
    let mut left = false;
    for (folder, folder_fs) in &made {
        let own =
            tree.is_some_and(|(tree, tree_fs)| folder == tree && Arc::ptr_eq(folder_fs, tree_fs));
        let removed = if own {
            folder_fs.remove_dir_all(folder)
        } else {
            folder_fs.remove_dir(folder)
        };
        match removed {
            Ok(()) => {}
            Err(gone) if gone.kind() == crate::io::ErrorKind::NotFound => {}
            Err(kept) => {
                log::warn!(
                    "Tree::open: could not remove {} after a failed creation ({kept}); \
                     syncing the folders it made instead",
                    folder.display()
                );
                left = true;
            }
        }
    }
    if left {
        sync_made_names(holders);
    }
}

/// Makes durable the names a failed creation leaves behind, by syncing the
/// folders `holders` that gained them, each with a device flush: a retry
/// finds those folders existing and syncs nothing for them.
fn sync_made_names(holders: &[(crate::path::PathBuf, Arc<dyn Fs>)]) {
    use crate::file::fsync_directory;
    use crate::fs::SyncMode;
    for (folder, folder_fs) in holders {
        if let Err(sync) = fsync_directory(folder, &**folder_fs, SyncMode::Full) {
            log::warn!(
                "Tree::open: could not sync {} after a failed creation ({sync}); a power \
                 loss may take back the folder it made",
                folder.display()
            );
        }
    }
}

/// Every folder made on the way to `folder`, deepest first, given the folders
/// that gained an entry making it ([`new_entry_holders`], nearest first):
/// `folder` and each one above it up to, not including, the farthest of them.
/// Empty when nothing was made.
fn made_folders(folder: &Path, holders: &[crate::path::PathBuf]) -> Vec<crate::path::PathBuf> {
    let Some(farthest) = holders.last() else {
        return Vec::new();
    };
    let mut made = Vec::new();
    let mut at = folder;
    while at != farthest.as_path() {
        made.push(at.to_path_buf());
        match at.parent() {
            Some(parent) => at = parent,
            None => break,
        }
    }
    made
}

/// The empty table files an open found that no version names, per tables
/// folder and its backend.
type PooledFiles = Vec<(
    crate::path::PathBuf,
    Arc<dyn crate::fs::Fs>,
    Vec<crate::TableId>,
)>;

/// What an open finds no version names, removed only once the state it judged
/// that by is installed as a fresh snapshot.
///
/// What an open reads may be what a failed sync left: an edit in the log that
/// was never synced, or a snapshot name whose install or withdrawal was never
/// made durable. Syncing those files again proves nothing (a sync after a
/// failed one may report success for pages the kernel already dropped), so the
/// open writes the state it recovered as a new snapshot instead, and a removal
/// judged by that state runs after it is durable.
#[derive(Default)]
struct OpenSweep {
    pending: Vec<(Arc<dyn Fs>, crate::path::PathBuf)>,
}

impl OpenSweep {
    /// Queues `path` on `fs` for removal.
    fn remove(&mut self, fs: &Arc<dyn Fs>, path: &Path) {
        self.pending.push((Arc::clone(fs), path.to_path_buf()));
    }

    /// Removes every queued file, a file already gone included, and fails
    /// with the first removal that failed. Each removal is tried: one file
    /// that cannot go must not keep the others, the generation an open
    /// superseded among them, from going.
    fn finish(self) -> crate::Result<()> {
        let mut first = None;
        for (fs, path) in self.pending {
            match fs.remove_file(&path) {
                Ok(()) => {}
                Err(e) if e.kind() == crate::io::ErrorKind::NotFound => {}
                Err(e) => {
                    first.get_or_insert(e);
                }
            }
        }
        first.map_or(Ok(()), |e| Err(e.into()))
    }
}

/// The folders that gain a new entry when `folder` is made on `fs`: each one
/// above it up to the first that exists already, which holds the first new
/// one. A folder that exists makes nothing new.
fn new_entry_holders(fs: &dyn Fs, folder: &Path) -> crate::Result<Vec<crate::path::PathBuf>> {
    let mut holders = Vec::new();
    if fs.exists(folder)? {
        return Ok(holders);
    }
    let mut made = folder;
    while let Some(holder) = made.parent() {
        holders.push(holder.to_path_buf());
        if fs.exists(holder)? {
            break;
        }
        made = holder;
    }
    Ok(holders)
}

/// Returns `true` if any tables folder of the tree (the primary one and every
/// [`level_routes`](crate::Config::level_routes) one) or its `blobs/` folder
/// holds a file, or the tree folder holds an edit log holding an edit.
///
/// Used by [`Tree::open`], for a directory with no installed snapshot, to
/// distinguish a fresh directory or a creation that never completed (empty
/// folders, a snapshot never renamed into place: nothing of value, safe to
/// `create_new` over) from a lost manifest, a half-written checkpoint or
/// another interrupted sealing (files already placed: must error rather than
/// silently overwrite, and leave the files to orphan cleanup).
///
/// A missing folder is treated as "no state": `create_new` is what creates
/// the directories in the first place, so callers may invoke `Tree::open`
/// against a path that does not exist yet.
fn has_existing_version_state(config: &Config) -> crate::Result<bool> {
    let blobs = (
        config.path.join(crate::file::BLOBS_FOLDER),
        Arc::clone(&config.fs),
    );
    // Files only: a folder there holds no table itself. A level route inside
    // the primary tables folder is one, empty after a creation cut short or
    // when made in advance, and is listed here as a tables folder of its own.
    for (folder, fs) in config.all_tables_folders().into_iter().chain([blobs]) {
        match fs.read_dir(&folder) {
            Ok(entries) if entries.iter().any(|entry| !entry.is_dir) => return Ok(true),
            Ok(_) => {}
            Err(e) if e.kind() == crate::io::ErrorKind::NotFound => {}
            Err(e) => return Err(e.into()),
        }
    }
    // A tree's history (a clear, the retention floor it raised) outlives its
    // tables, and a lost snapshot leaves its log behind: an edit in any log,
    // or the log of any generation past the first, which only a rotation
    // makes, is a tree that lived. A creation cut short leaves only the
    // first generation's empty log.
    let entries = match config.fs.read_dir(&config.path) {
        Ok(entries) => entries,
        Err(e) if e.kind() == crate::io::ErrorKind::NotFound => return Ok(false),
        Err(e) => return Err(e.into()),
    };
    // A name is judged by its shape, digits after the prefix, not by whether
    // the digits parse: a snapshot whose id is past the counter's range is
    // no installed one, yet no creation wrote it either, and it is refused
    // rather than created over.
    let digits = |rest: Option<&str>| {
        rest.is_some_and(|id| !id.is_empty() && id.bytes().all(|b| b.is_ascii_digit()))
    };
    for entry in &entries {
        let name = entry.file_name.as_str();
        if digits(name.strip_prefix('v')) {
            return Ok(true);
        }
        if digits(name.strip_prefix("edits-"))
            && (name != "edits-0" || config.fs.metadata(&entry.path)?.len > 0)
        {
            return Ok(true);
        }
    }
    Ok(false)
}

/// Whether two sightings of one table id PROVABLY hold different bytes.
///
/// Used to judge a duplicate scanned after its id was already accepted: the
/// winner matched the manifest, so a copy whose bytes differ from it cannot
/// also be the committed generation and is safe to sweep. Identical bytes mean
/// an alias or an exact copy, which is kept.
///
/// Only a completed comparison is proof. A read that fails on the BYTES proves
/// nothing about which generation this is, so it answers `false` and the file
/// stays; an ENVIRONMENTAL fault propagates, since a retry can re-read it.
///
/// # Errors
///
/// Propagates an environmental read failure of either file.
fn differs_byte_for_byte(
    winner_fs: &dyn crate::fs::Fs,
    winner: &Path,
    candidate_fs: &dyn crate::fs::Fs,
    candidate: &Path,
) -> crate::Result<bool> {
    let digest = |fs: &dyn crate::fs::Fs, path: &Path| -> crate::Result<Option<u128>> {
        match crate::file::checksum_from_with_overrides(fs, path, 0, &[]) {
            Ok(d) => Ok(Some(d)),
            Err(e) if e.is_environmental() => Err(e),
            Err(_) => Ok(None),
        }
    };
    let (Some(a), Some(b)) = (digest(winner_fs, winner)?, digest(candidate_fs, candidate)?) else {
        return Ok(false);
    };
    Ok(a != b)
}

/// Raises a query's lower bound to a table's tight-space restriction, if any.
///
/// Keys below `restriction` are the punched-out prefix served by the
/// replacement table, so a range estimate must not charge them to the
/// restricted view. Returns `lo` unchanged when the table is unrestricted or
/// the restriction is at or below `lo`.
fn effective_lower_bound<'a>(
    lo: core::ops::Bound<&'a [u8]>,
    restriction: Option<&'a [u8]>,
    cmp: &dyn crate::comparator::UserComparator,
) -> core::ops::Bound<&'a [u8]> {
    use core::cmp::Ordering;
    use core::ops::Bound;
    match (lo, restriction) {
        (Bound::Unbounded, Some(rb)) => Bound::Included(rb),
        (Bound::Included(k) | Bound::Excluded(k), Some(rb))
            if cmp.compare(rb, k) == Ordering::Greater =>
        {
            Bound::Included(rb)
        }
        _ => lo,
    }
}

#[cfg(test)]
mod cardinality_tests;

#[cfg(test)]
#[expect(clippy::expect_used, reason = "test code")]
mod scan_since_freeze_tests;

#[cfg(test)]
#[expect(clippy::expect_used, clippy::panic, reason = "test code")]
mod scan_since_scope_tests;

#[cfg(all(test, feature = "metrics"))]
mod cache_stats_tests;

#[cfg(all(test, feature = "std"))]
#[expect(clippy::expect_used, reason = "test code")]
mod restricted_reclaim_tests;

#[cfg(all(test, feature = "std", zstd_any))]
mod dict_collect_tests;

#[cfg(all(test, feature = "std", zstd_any))]
#[expect(clippy::expect_used, reason = "test code")]
mod live_compression_tests;

#[cfg(test)]
#[expect(clippy::expect_used, reason = "test code")]
mod partition_size_tests;

#[cfg(all(test, feature = "std"))]
mod chunk_order_tests;

#[cfg(all(test, feature = "std"))]
mod chunk_file_tests;

#[cfg(all(test, feature = "std"))]
#[expect(clippy::expect_used, reason = "test code")]
mod merge_read_tests;

#[cfg(all(test, feature = "std"))]
mod probe_stats_tests;

#[cfg(all(test, feature = "std"))]
mod filter_advisor_tests;

#[cfg(all(test, feature = "std"))]
mod open_batch_tests;

#[cfg(all(test, feature = "std"))]
#[expect(clippy::expect_used, reason = "test code")]
mod clear_race_tests;

#[cfg(all(test, feature = "std"))]
#[expect(clippy::expect_used, reason = "test code")]
mod insert_rotation_tests;

#[cfg(all(test, feature = "std"))]
#[expect(clippy::expect_used, reason = "test code")]
mod overlapping_runs_tests;