ordered-btree

A pure-Python, typed, generic ordered collection of unique keys, with a B-tree storage engine. Python 3.12+, including Python 3.14. No runtime dependencies. Licensed under MIT.

The distribution is ordered-btree; the import is ordered_btree. Version 0.1.0 is prepared as the initial public release. This is a pre-1.0 API: pin a tested version and review the changelog before upgrading. Check GitHub releases for completed releases and their PyPI links; a source checkout is not proof of publication. See releasing for the TestPyPI verification and production-approval gates.

Highlights

• Private mutable nodes; read-only degree; detached frozen diagnostic snapshots.
• Only < is required. Unhashable keys and keys without usable == work.
• A single comparison-only search precedes comparator-free updates. Raising comparisons leave contents, structure, size, and iterator validity unchanged.
• Iterative traversal and bisected range seeking, with fail-fast iterators.
• One-pass structural validation, including cycles, shared nodes, bounds and size.
• Tests, fault injection, exhaustive/randomized stress, deterministic benchmarks, wheel/sdist packaging, py.typed, and CI configuration.

Validation: see the validation record for exact executed runtimes, commands, results and limitations. Configured CI is not evidence that a remote run has completed. See contributing for development and security for the security policy.

Installation

After the version is published and verified on PyPI, applications can install it with:

python -m pip install ordered-btree==0.1.0

Until then, install from source or the verified local wheel below. For development, use uv 0.12.15 or newer. The following commands work from the project directory on Windows, Linux and macOS; no shell activation is needed:

uv sync --locked                   # Development environment, Python 3.14 by default
uv run --locked python examples/basic.py

To install just the library into a separate application environment:

uv venv --python 3.14
uv pip install /path/to/ordered-btree
# Or install a locally built wheel without runtime dependencies:
uv pip install --no-deps /path/to/ordered_btree-0.1.0-py3-none-any.whl

Ordinary python -m pip install /path/to/ordered-btree also works: uv is a contributor tool, not a requirement for applications using the library. Python 3.12 and 3.13 remain supported. The project's Python pin selects a development default; it does not raise the minimum version.

Basic usage

from ordered_btree import BTree

numbers = BTree[int](t=32, keys=[10, 20, 5, 6, 12, 30, 7, 17])

assert list(numbers) == [5, 6, 7, 10, 12, 17, 20, 30]
assert list(numbers.range(6, 18)) == [6, 7, 10, 12, 17]  # [start, stop)
assert list(numbers.range(None, 7)) == [5, 6]
assert list(numbers.range(20, None)) == [20, 30]

assert numbers.search(6) == 6       # Stored representative, not a node.
assert numbers.search(999) is None
assert 12 in numbers
assert numbers.insert(6) is False  # Equivalent key already present.
assert numbers.delete(12) is True
assert numbers.delete(999) is False

assert numbers.min() == 5
assert numbers.max() == 30
assert numbers.pop_min() == 5
assert numbers.pop_max() == 30
numbers.validate()

t is the minimum degree, not the maximum number of keys. A node holds at most 2*t-1 keys. The default remains t=2 for compatibility. t=32 in these examples is an explicit starting point to benchmark, not a universally optimal default. Floats (including 2.0), booleans, strings, NaN, and infinity are rejected as degrees. Invalid integer degrees below two raise ValueError.

Custom immutable records

from __future__ import annotations
from dataclasses import dataclass
from ordered_btree import BTree

@dataclass(frozen=True, slots=True)
class Job:
    priority: int
    job_id: int
    description: str = ""

    def __lt__(self, other: Job) -> bool:
        return (self.priority, self.job_id) < (other.priority, other.job_id)

first = Job(1, 42, "Original payload")
jobs = BTree[Job](keys=[first, Job(3, 12, "Later")])
probe = Job(1, 42, "Different payload")

assert probe != first                 # Dataclass equality sees the payload.
assert jobs.insert(probe) is False    # BTree ordering does not.
assert jobs.search(probe) is first     # First equivalent representative wins.
assert jobs.pop_min() is first

Ordering must be a stable strict weak ordering across all stored keys and probes. Keys are equivalent when neither is less than the other. No ==, <=, >, >=, or hashing is used internally. None is reserved for missing results and open range bounds and cannot be stored. NaN keys, partial orders, and inconsistent comparators are unsupported; arbitrary comparator laws are not validated automatically. In particular, this implementation does not promise to recognize and reject every invalid key before insertion into an empty tree.

Frozen dataclasses help, but Python does not enforce Rust-style ownership. Nested values may remain mutable, and the tree retains the exact objects passed in. Never change ordering-relevant state while a key is stored. Use an immutable replacement and an explicit delete/insert operation instead. Mutable payloads are acceptable only when they cannot affect ordering. Range-bound objects must also remain stable until iteration ends.

Mutation and iteration

from ordered_btree import BTree, ConcurrentModificationError

tree = BTree[int](keys=[1, 2, 3])
iterator = iter(tree)           # Version captured immediately.
assert next(iterator) == 1

tree.insert(4)
try:
    next(iterator)
except ConcurrentModificationError:
    print("Create a new iterator, or iterate over a snapshot.")

Successful insertion, deletion, clearing, and extreme removal invalidate active iterators. Duplicate insertion, missing-key deletion, and clearing an empty tree are genuine no-ops and do not invalidate them. Deleting and reinserting the same key still invalidates an iterator even if the size is unchanged.

Mutation before the first next() is detected. Once an iterator has raised StopIteration, it stays exhausted. After a modification error it is also exhausted. Iterator creation/lower-bound comparisons happen eagerly; comparisons against the upper bound happen as results are consumed. An upper-bound comparison exception leaves its candidate unconsumed, so it can be retried after the comparator is repaired. A StopIteration raised by that comparison is wrapped in RuntimeError with the original exception as its cause: comparator failure must not look like normal iterator exhaustion. Other comparison errors propagate.

stable_values = tree.snapshot()  # tuple of keys, detached from future updates
shape = tree.inspect()           # frozen NodeSnapshot; tuples of child snapshots
clone = tree.copy()              # independent mutable nodes, same key objects

for key in tree.snapshot():
    tree.delete(key)             # Safe: iterating over the detached tuple.

Snapshots are structurally immutable, not deep copies. search, min, max, iteration, snapshots, and copy all share key references. There is no public live root, and there is no public mutable node class. Underscore attributes are implementation details, not a security boundary against deliberate tampering.

API at a glance

This is not a collections.abc.MutableSet subclass: unordered set equality and hash-based equivalence would suggest semantics this library does not implement. There are no set operators, map values, multiset counts, rank/select operations, key-projection callback, persistence layer, or bulk-transaction API.

Exception and concurrency contracts

For ordinary exceptions raised by comparisons, single-key insert and delete have a strong no-change guarantee: all comparisons finish before mutation. No-op updates are equally non-mutating. Replacement extraction, borrowing, merging, and root contraction do not compare keys. Invalid-type comparison errors propagate.

This is not a transaction against allocation failure, KeyboardInterrupt, process termination, or malicious callbacks changing private state. Commit-time allocation failure/interruption can leave the tree unusable; rebuild it from a trusted external source. Construction is incremental, not a bulk transaction. validate() detects structure errors but cannot prove comparator laws; exceptions from its comparisons propagate rather than being relabeled as corruption.

Public content operations reject same-tree re-entrancy with ReentrantOperationError, including callbacks trying to read the tree during an active comparison. Constant-time metadata (len, degree and occupancy limits) can be read in callbacks. Callbacks may operate on a different tree.

There is no thread-safety guarantee, with or without the GIL. The re-entrancy flag and iterator version are not locks. All callers sharing a mutable instance must use an external lock, including around reads and the entire consumption of an iterator. See the synchronization example.

Complexity and performance

Let h be height, t minimum degree, n stored keys, and k returned keys. Comparison costs are assumed constant; expensive comparators add their own cost.

Splits also use O(t) temporary list storage. The range bound includes amortized successor traversal, not a promise that every individual next() is O(1). Clearing may perform O(n) reference releases, subject to outstanding references and garbage collection. Keys and their callbacks may have additional costs.

Faster asymptotics do not guarantee faster wall-clock performance for every workload. Fail-fast checks and Python iterator dispatch have a cost, particularly for full scans with large nodes. Performance measurements record deterministic inputs, actual runtimes and limitations. Degree should be selected using your own comparator, key sizes, and operation mix.

Development and tests

uv sync --locked
uv run --locked pytest -q -m "not stress"
uv run --locked pytest -q -m stress
uv run --locked python tools/stress.py
uv run --locked python benchmarks/benchmark.py
uv run --locked coverage run -m pytest -q -m "not stress"
uv run --locked coverage report --fail-under=99
uv run --locked mypy
uv run --locked ruff check src examples tests tools benchmarks
uv run --locked ruff format --check src examples tests tools benchmarks
uv run --locked python examples/basic.py
uv run --locked python examples/records.py
uv run --locked python examples/synchronized.py

tools/stress.py --quick is a shorter deterministic run. Hypothesis is installed by the development dependency group and is required for the property tests. Verification tools reject optimized Python (-O / PYTHONOPTIMIZE), use fresh report destinations and record failures rather than reusing stale success data. Raw reports and local agent files are intentionally not committed.

Build into a new directory and independently exercise the artifacts:

uv build --no-create-gitignore --out-dir dist/candidate
uv run --locked twine check --strict dist/candidate/*
uv run --locked python tools/verify_dist.py dist/candidate

The artifact verifier checks metadata, archive contents, py.typed and hashes, installs the wheel in an external temporary uv environment, and independently rebuilds and exercises a wheel from the extracted sdist. Publication is a separate, intentional step; follow the release checklist.

Project map

src/ordered_btree/    Runtime implementation, public exports, py.typed
examples/            Executable basics, immutable records, external locking
tests/               API, mutation, exception safety, independent model checks,
                     property tests, and verification-tool regressions
tools/               Stress, isolated artifact checks and publication preflight
benchmarks/          Deterministic workload measurements with raw samples
docs/                Design, compatibility, validation, performance and releases
.github/             CI, dependency updates and contribution templates

Scope and release status

The library deliberately uses private mutable nodes, shallow immutable snapshots, first-wins ordering equivalence, fail-fast iteration, explicit external locking, None reserved, and Python 3.12+ compatibility. See design and compatibility before depending on pre-1.0 API stability.

The project is MIT licensed. Publication uses the verified wheel/sdist pair from CI, first on TestPyPI and then on PyPI after the owner's production approval. Only completed remote runs and index checks establish publication; local checks do not claim that those steps have happened.