The type of keys used for indexing the entries. This might be an element of TEntry, or TEntry itself.
The type of entries stored in the B-tree.
OptionalkeyFromEntry: (entry: TEntry) => TKey = ...a function to extract the key from an entry. The default assumes the key is the entry itself.
Optionalcompare: (a: TKey, b: TKey) => number = ...a comparison function for keys. The default uses < and > operators.
OptionalbaseOrOptions: BTree<TKey, TEntry> | BTreeOptionseither a base tree to derive from (copy-on-write inheritance), or a BTreeOptions object. When a base tree is given, the derived tree initially shares all of the base's nodes and clones them lazily as it is mutated, and options may be passed as the fourth argument.
Optionaloptions: BTreeOptionsoptional per-tree tuning of the freeze / comparator-check safety costs. See BTreeOptions. Used when the third argument is a base tree; ignored otherwise (pass the options as the third argument when there is no base).
BASE-IMMUTABILITY CONTRACT: a base must be treated as immutable for the lifetime of its derived children. The child reads any un-modified node directly from the base (see root), so mutating the base (insert/update/delete) while a derived child is still in use can corrupt that child's view of every node it still shares with the base. The fix is structural, not incidental: derive your children first and then leave the base frozen, or, if you need to keep mutating the original, mutate a derived child instead and treat the original base as the frozen snapshot. This contract is enforced at runtime by a detect-on-next-use version guard (MutatedBaseError): the child snapshots its base chain's version at construction and, on its next operation after the base was mutated, throws instead of returning a corrupted view. The guard cannot cover a detached child: after clearBase there is no base version left to compare, so the shared-node hazard from that point on is unguardable — use flatten up front if you need true isolation. See also clearBase, whose "frozen" obligation outlives the base pointer.
ReadonlyownerThis tree's identity token, stamped onto every node it creates or clones (see nodes owner).
A node belongs to this tree iff node.owner === this.owner. A bare Symbol rather than a this
back-reference is deliberate: it answers the O(1) ownership question without letting a shared node pin
the whole owning tree — and transitively its entire base chain — alive past clearBase/clear.
A class-field initializer, so it is set before the constructor body runs and is available at every
node-creation site (including the lazy root getter).
The total number of entries in the tree (an alias for the no-arg getCount). O(1) - reads the stored count, maintained per mutation.
Iterates forward over live cursors, starting from the given path (inclusive) to the end. With no argument, starts from first (the whole tree, ascending).
WARNING: this yields the SAME cursor object every step, mutated in place - so it is a cursor-level tool,
not a collection. Spreading it ([...tree.ascending()]) or .mapping it gives N references to one path
parked off the end, and reading them afterwards is all-undefined; read tree.at(path) INSIDE the loop,
and path.clone() any cursor you need to retain. For the common "give me the entries" case prefer
entries/keys, which yield distinct values and sidestep this entirely.
WARNING: mutation during iteration invalidates the cursor and the next step will throw.
Empties the tree, invalidating every outstanding path (a subsequent use throws InvalidPathError). The tree stays usable afterward: getCount is 0 and insert works again. This is the intended way to empty a tree in place, rather than deleting every entry or discarding the instance. On a copy-on-write child this also detaches the base: an empty tree shares nothing, so there is nothing left to inherit (the base itself is untouched, as always).
Detaches this tree from its base, flattening it into a standalone tree. After this call the tree no
longer depends on the base object: a child that has already written keeps its cloned _root; an
unwritten child pins the base's current root as its own.
IMPORTANT — this is a cheap pointer drop, NOT a deep copy. Copy-on-write only clones the nodes a
child actually mutated, so a flattened child can still SHARE every untouched subtree with its former
base by identity (an unwritten child shares the entire tree). Once the base pointer is gone neither
tree copies-on-write anymore, so a structural write to a shared node mutates it in place for BOTH.
The base-immutability contract therefore outlives this call: after clearBase(), treat the former
base as frozen — in practice, discard it. If you genuinely need two independently-mutable trees,
build a fresh tree and re-insert, rather than relying on clearBase to isolate shared structure.
The base-immutability guard runs here too: if the base was already mutated before this call, clearBase
throws MutatedBaseError rather than laundering an already-corrupt base into a detached tree.
After this call base === undefined, so the guard becomes a permanent no-op — a detached child is,
by construction, past the reach of the version guard (use flatten up front for true isolation).
ProtectedcompareInvokes user-provided comperator to compare two keys. Inner-loop code, so this doesn't do backflips to iron out ES's idiosyncrasies (undefined quirks, infinity, nulls, etc.), but does ensure deterministic comparison.
The antisymmetry check (a second, reversed compare) runs on every comparison when the tree was
constructed with { checkComparator: true }; otherwise it runs only for the first
BTree.SampleCheckCount comparisons (a cheap sample), then drops off the hot path entirely.
A subtly-inconsistent comparator that only misbehaves deep in a large tree can therefore slip past
the default sample — use { checkComparator: true } for the exhaustive (historical) check.
If you want to eak out more performance at the risk of corruption, you can override this method and omit the consistency check.
Iterates backward over live cursors, starting from the given path (inclusive) to the start. With no argument, starts from last (the whole tree, descending).
WARNING: same aliasing caveat as ascending - one reused, mutated cursor per step. Read inside the
loop, clone() to retain, and prefer entries/keys when you just want the values.
WARNING: mutation during iteration invalidates the cursor and the next step will throw.
Yields each entry in the tree (or in range if given) directly - the safe, aliasing-free default for
reading. No argument iterates the whole tree ascending; a KeyRange delegates to range
(honoring direction and inclusive/exclusive bounds identically). Each yielded value is a distinct entry,
so [...tree.entries()] and .map work as expected.
WARNING: mutation during iteration invalidates the underlying cursor and the next step will throw.
Produces a genuinely independent copy of this tree in one O(n) pass - the safe alternative to
clearBase when true isolation from a former base is required. Where clearBase merely drops
the base pointer (so untouched nodes can still be shared by identity with the former base - see its
docs), flatten walks this tree's entries once and rebuilds them into a fresh, standalone tree via
BTree.buildFrom, sharing no node with this tree or its base. The freeze and checkComparator
options are carried over so the result behaves identically to this tree. Works the same whether or
not this tree has a base, and on an empty tree (returns a valid, independent empty tree).
Number of entries in the tree. With no argument, O(1): returns the stored count.
Optionalfrom: { ascending?: boolean; path: Path<TKey, TEntry> }if provided, the count is a partial count that walks from the given path (inclusive) - O(n/af) where af is average fill. If ascending is false, the count starts from the end of the tree. Ascending is true by default. This overload cannot be answered from the stored count and always walks.
Inserts or updates depending on the existence of the given key, using callbacks to generate the new value.
path to new entry and whether an update or insert attempted. If getUpdated callback returns a row that is already present, the resulting path will not be on.
Updates the entry at the given path to the given value. Deletes and inserts if the key changes.
path to resulting entry and whether it was an update (as opposed to an insert). * on = true if update/insert succeeded. * wasUpdate = true if updated; false if inserted. * Returned path is on entry * on = false if the insert failed: newEntry's new key already present; returned path is "near" the existing entry (wasUpdate = false)
Inserts the entry if it doesn't exist, or updates it if it does. The entry is frozen to ensure immutability.
path to the affected row. on = true if an existing entry was updated (path sits ON the
updated row); on = false if the entry was newly inserted (path sits on the crack BEFORE the new
row, not on it). This is the inverse of insert's on-flag and the opposite of merge, which sets
on = true on insert too.
WARNING: on a fresh insert, tree.at(tree.upsert(x)) returns undefined - the returned path is not
on the new entry. To read the freshly-inserted row, step off the crack first:
tree.at(tree.next(path)) (or use tree.get(key)).
StaticbuildBuilds a tree in a single bottom-up pass from already-sorted, duplicate-free input. O(n) - versus the O(n log n) of repeated insert - and packs nodes near capacity rather than the roughly half-full nodes that natural splits leave behind. The result is indistinguishable from a tree built by inserting the same entries (same structural invariants, same query answers) and is returned fresh at version 0.
The input must be strictly ascending by compare. It is validated - and, unless disabled, frozen - in
one linear pass; the first out-of-order or duplicate pair throws UnsortedInputError and nothing is
returned (the partially-built work is discarded). Note the shared pass means that on the throw path the
entries before the offending pair have already been frozen in place; the discarded tree is unreachable but
those caller-owned objects stay frozen. Pass { freeze: false } if that side-effect matters.
Parameter order and defaults mirror the constructor (keyFromEntry, then compare, then options), so a
trusted load can pass { freeze: false } to skip freezing. A bulk-loaded tree is always standalone (no
base); derive children from it afterward if copy-on-write inheritance is wanted.
Represents a lightweight B+(ish)Tree (data at leaves, but no linked list of leaves). Provides copy-on-write capabilities