Module btree 

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

Feature outlines

• 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
  • Reduce memory fragmentation by alignment.
• Optimised for numeric key type
  • Typical scenario: range-tree-rs
  • Respecting numeric space for sequential insertion.
  • Reduce latency for sequential insertion.
• Support string keys, but optimization is non-goal
  • You may look for other structures with prefix compression: Art, Masstree.
• 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
• Limitation:
  • K should have clone (for propagate into the InterNode during split)
  • K & V should <= CACHE_LINE_SIZE - 16
    • It make sure InterNode can hold at least two children.
    • If K & V is large you should put into Box, for room saving, and for the speed to move value
• The detail design notes are with the source in mod.rs and node.rs

Special APIs

We have special Cursor & Entry API, which allow to modify after moving the cursor to adjacent data.

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