Module btree

An implementation of B trees. The core operations on B trees (lookup, iterate, put and del) are generic in the actual implementation of nodes, via the BTreePage and BTreeMutPage. This allows for a simpler code for the high-level functions, as well as specialised, high-performance implementations for the nodes.

Two different implementations are supplied: one in page for types with a size known at compile-time, which yields denser leaves, and hence shallower trees (if the values are really using the space). The other one, in page_unsized, is for dynamic-sized types, or types whose representation is dynamic, for example enums that are Sized in Rust, but whose cases vary widely in size.

Re-exports

pub use del::del;

pub use del::del_no_decr;

pub use put::put;

Modules

del

Deletions from a B tree.

page

Implementation of B tree pages for Sized types, i.e. types whose representation has a size known at compile time (and the same as core::mem::size_of()).

page_unsized

Implementation of B tree pages for Unsized types, or types with an dynamically-sized representation (for example enums with widely different sizes).

put

Insertions into a B tree.

Structs

Cursor

A position in a B tree.

Db_

A database, which is essentially just a page offset along with markers.

Iter

PageIterator

RevIter

Traits

BTreeMutPage

BTreePage

Functions

create_db^⚠

Create a database for sized keys and values.

create_db_^⚠

Create a database with an arbitrary page implementation.

drop^⚠

Drop a database recursively, dropping all referenced keys and values that aren’t shared with other databases.

fork_db

Fork a database.

get

Get the first entry of a database greater than or equal to k (or to (k, v) if v.is_some()), and return true if this entry is shared with another structure (i.e. the RC of at least one page along a path to the entry is at least 2).

get_shared

Get the first entry of a database greater than or equal to k (or to (k, v) if v.is_some()), and return true if this entry is shared with another structure (i.e. the RC of at least one page along a path to the entry is at least 2).

iter

rev_iter

Type Aliases

Db

A database of sized values.

UDb

A database of unsized values.