Module btree 

Available on crate feature btree only.

B+Tree Map - A in memory cache-optimized B+Tree for single-threaded use.

Feature outlines

• Designed for CPU cache efficiency and memory efficiency
• Optimised for numeric key type
  • Typical scenario: range-tree-rs
• A B+tree. Data stores only at leaf level, with links at leaf level.
  • Provides efficient iteration of data
  • Linear search within nodes, respecting cacheline boundaries
• Nodes are filled up in 4 cache lines (256 bytes on x86_64)
  • keys stored in first 128B (with header)
  • Values/pointers stored in last 128B
  • the capacity is calculated according to the size of K, V, with limitations:
    • K & V should <= CACHE_LINE_SIZE - 16 (If K & V is larger should put into Box)
• Specially Cursor & Entry API which allow to modify after moving the cursor to adjacent data.
• The detail design notes are with the source in mod.rs and node.rs

Special APIs

Batch removal:

• BTreeMap::remove_range()
• BTreeMap::remove_range_with()

Adjacent entry:

• Entry::peek_forward()
• Entry::peek_backward()
• Entry::move_forward()
• Entry::move_backward()
• VacantEntry::peek_forward()
• VacantEntry::peek_backward()
• VacantEntry::move_forward()
• VacantEntry::move_backward()
• OccupiedEntry::peek_forward()
• OccupiedEntry::peek_backward()
• OccupiedEntry::move_forward()
• OccupiedEntry::move_backward()
• OccupiedEntry::alter_key()

Readonly Cursor:

• BTreeMap::cursor()
• BTreeMap::first_cursor()
• BTreeMap::last_cursor()

Structs

BTreeMap

B+Tree Map for single-threaded usage, optimized for numeric type.

Cursor

A read-only cursor for navigating through entries in a BTreeMap.

IntoIter

An owning iterator over the entries of a BTreeMap Uses PathCache to manage tree traversal and safe deallocation

Iter

An iterator over the entries of a BTreeMap

IterMut

A mutable iterator over the entries of a BTreeMap

Keys

An iterator over the keys of a BTreeMap

OccupiedEntry

Entry for an existing key-value pair in the tree

Range

An iterator over a sub-range of entries in a BTreeMap RangeBase is wrapped in Option - when exhausted, it becomes None

RangeMut

A mutable iterator over a sub-range of entries in a BTreeMap RangeBase is wrapped in Option - when exhausted, it becomes None

VacantEntry

Entry for a vacant key position in the tree

Values

An iterator over the values of a BTreeMap

ValuesMut

A mutable iterator over the values of a BTreeMap

Enums

Entry

Entry into a BTreeMap for in-place manipulation