B-Tree

Træ

Et self-balancing træ optimeret til systemer der læser og skriver store datablokke som databaser og filsystemer.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(log n)`
Search	`O(log n)`
Insertion	`O(log n)`
Deletion	`O(log n)`

Beskrivelse

B-Tree er fundamentalt forskellig fra binære træer fordi hver node kan have mange keys og børn, ikke kun to. En B-Tree af orden m kan have op til m børn per node og m-1 keys. B-Trees blev specifikt designet til at arbejde effektivt med disk-baserede storage systems hvor læsning af en hel blok fra disk er relativt dyrt. Ved at pakke mange keys ind i hver node (som matcher disk block størrelse), minimeres antallet af disk accesses. B-Trees holder sig balanceret ved at alle blade altid er på samme niveau, og når en node bliver fuld, splittes den i to nodes og medianen promoveres til parent node. Alle insertions og deletions sker på leaf niveau. B-Trees bruges massivt i database management systems (MySQL, PostgreSQL, Oracle) og filsystemer (NTFS, HFS+, ext4) fordi de håndterer store datasets ekstremt effektivt. En variant, B+ Tree, gemmer alle data i leaves og bruges endnu mere i databaser fordi den understøtter effektiv range scanning.

Kode Eksempel

// JavaScript B-Tree Implementation (simplified, order 3)
class BTreeNode {
  constructor(isLeaf = true) {
    this.keys = [];
    this.children = [];
    this.isLeaf = isLeaf;
  }
}

class BTree {
  constructor(order = 3) {
    this.root = new BTreeNode();
    this.order = order;
    this.minKeys = Math.ceil(order / 2) - 1;
    this.maxKeys = order - 1;
  }

  search(node, key) {
    let i = 0;
    while (i < node.keys.length && key > node.keys[i]) {
      i++;
    }

    if (i < node.keys.length && key === node.keys[i]) {
      return true;
    }

    if (node.isLeaf) {
      return false;
    }

    return this.search(node.children[i], key);
  }

  find(key) {
    return this.search(this.root, key);
  }

  splitChild(parent, index) {
    const fullChild = parent.children[index];
    const newChild = new BTreeNode(fullChild.isLeaf);
    const mid = Math.floor(this.maxKeys / 2);

    // Move half of keys to new node
    newChild.keys = fullChild.keys.splice(mid + 1);
    const midKey = fullChild.keys.pop();

    // If not leaf, move half of children too
    if (!fullChild.isLeaf) {
      newChild.children = fullChild.children.splice(mid + 1);
    }

    // Insert mid key into parent
    parent.keys.splice(index, 0, midKey);
    parent.children.splice(index + 1, 0, newChild);
  }

  insertNonFull(node, key) {
    let i = node.keys.length - 1;

    if (node.isLeaf) {
      // Insert key in sorted position
      node.keys.push(key);
      while (i >= 0 && node.keys[i] > key) {
        node.keys[i + 1] = node.keys[i];
        i--;
      }
      node.keys[i + 1] = key;
    } else {
      // Find child to insert into
      while (i >= 0 && node.keys[i] > key) {
        i--;
      }
      i++;

      // If child is full, split it
      if (node.children[i].keys.length === this.maxKeys) {
        this.splitChild(node, i);
        if (key > node.keys[i]) {
          i++;
        }
      }
      this.insertNonFull(node.children[i], key);
    }
  }

  insert(key) {
    const root = this.root;

    // If root is full, split it
    if (root.keys.length === this.maxKeys) {
      const newRoot = new BTreeNode(false);
      newRoot.children.push(this.root);
      this.splitChild(newRoot, 0);
      this.root = newRoot;
    }

    this.insertNonFull(this.root, key);
  }

  traverse(node = this.root, level = 0) {
    console.log('  '.repeat(level) + 'Keys:', node.keys.join(', '));
    if (!node.isLeaf) {
      node.children.forEach(child => this.traverse(child, level + 1));
    }
  }
}

// Brug
const tree = new BTree(3); // Order 3 (max 2 keys per node)
tree.insert(10);
tree.insert(20);
tree.insert(5);
tree.insert(6);
tree.insert(12);
tree.insert(30);
tree.insert(7);
tree.insert(17);

console.log('Search 6:', tree.find(6)); // true
console.log('Search 15:', tree.find(15)); // false
tree.traverse();

Anvendelsesområder

•Database indexes (MySQL, PostgreSQL)
•Filsystemer (NTFS, ext4, HFS+)
•Large datasets der ikke passer i RAM
•Range queries og sorted scans
•Systems med mange concurrent reads/writes

Fordele

✓Minimerer disk I/O operations
✓Alle leaves på samme niveau (perfekt balanceret)
✓Excellent til store datasets på disk
✓Høj fanout reducerer træets højde
✓God til sequential og random access

Ulemper

✗Mere kompleks end binære træer
✗Højere memory overhead per node
✗Split og merge operations er dyre
✗Ikke optimal for in-memory data
✗Sværere at implementere korrekt

Eksempler fra den virkelige verden

•MySQL InnoDB storage engine indexes
•PostgreSQL GiST og B-tree indexes
•MongoDB WiredTiger storage engine
•NTFS Master File Table
•Oracle Database B-Tree indexes

Relaterede strukturer

B+ TreeRed-Black TreeAVL TreeHash Table