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