Tree

Binary Tree

B-Tree

B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, insertions, and deletions in logarithmic time. It’s particularly useful for systems that read and write large blocks of data, like databases and file systems.

Nodes can have more than two children (non-binary) and each node contains multiple keys, which divide its children into ranges. All leaves are at the same level, ensuring balanced height. A B-tree of order m can have at most m children and at least ⌈m/2⌉ children (except the root).

Fewer levels compared to binary trees → faster disk access. Great for minimizing I/O operations, which makes it the backbone of database indexing (e.g., MySQL, PostgreSQL use B+ trees, a variant).

use std::collections::BTreeMap;
fn main() {
    let mut btree = BTreeMap::new();
    btree.insert(1, "one");
    btree.insert(2, "two");
    btree.insert(3, "three");
    // Efficiently retrieve values
    if let Some(value) = btree.get(&2) {
        println!("The value for key 2 is: {}", value);
    }
}