Module sanakirja::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.

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.
del	If value is None, delete the first entry for key from the database, if present. Else, delete the entry for (key, value), if present.
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()).
iter
put	Insert an entry into a database, returning false if and only if the exact same entry (key and value) was already in the database.
rev_iter

Type Definitions

Db	A database of sized values.
UDb	A database of unsized values.