B-træ

Træ

Et selvbalancerende 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-træet er fundamentalt forskelligt fra binære træer fordi hver node kan have mange nøgler og børn, ikke kun to. Et B-træ af orden m kan have op til m børn per node og m-1 nøgler. B-træer blev specifikt designet til at arbejde effektivt med diskbaserede lagringssystemer hvor læsning af en hel blok fra disken er relativt dyrt. Ved at pakke mange nøgler ind i hver node (som matcher diskblokstørrelse), minimeres antallet af diskoperationer. B-træer holder sig balanceret ved at alle blade altid er på samme niveau, og når en node bliver fuld, splittes den i to noder og medianen forfremmes til forældernoden. Alle indsættelser og sletninger sker på bladniveau. B-træer bruges massivt i databasestyringssystemer (MySQL, PostgreSQL, Oracle) og filsystemer (NTFS, HFS+, ext4) fordi de håndterer store datasæt ekstremt effektivt. En variant, B+-træet, gemmer alle data i bladene og bruges endnu mere i databaser fordi den understøtter effektiv intervalscanning.

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);

    // Flyt halvdelen af nøglerne til ny node
    newChild.keys = fullChild.keys.splice(mid + 1);
    const midKey = fullChild.keys.pop();

    // Hvis ikke blad, flyt også halvdelen af børnene
    if (!fullChild.isLeaf) {
      newChild.children = fullChild.children.splice(mid + 1);
    }

    // Indsæt midternøgle i forælder
    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) {
      // Indsæt nøgle på sorteret 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 barn at indsætte i
      while (i >= 0 && node.keys[i] > key) {
        i--;
      }
      i++;

      // Hvis barn er fuldt, split det
      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;

    // Hvis rod er fuld, split den
    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) + 'Nøgler:', node.keys.join(', '));
    if (!node.isLeaf) {
      node.children.forEach(child => this.traverse(child, level + 1));
    }
  }
}

// Brug
const tree = new BTree(3); // Orden 3 (maks 2 nøgler 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('Søg 6:', tree.find(6)); // true
console.log('Søg 15:', tree.find(15)); // false
tree.traverse();

Anvendelsesområder

•Databaseindekser (MySQL, PostgreSQL)
•Filsystemer (NTFS, ext4, HFS+)
•Store datasæt der ikke passer i RAM
•Intervalforespørgsler og sorterede scanninger
•Systemer med mange samtidige læse/skrive-operationer

Fordele

✓Minimerer disk I/O-operationer
✓Alle blade på samme niveau (perfekt balanceret)
✓Fremragende til store datasæt på disk
✓Høj fanout reducerer træets højde
✓God til både sekventiel og tilfældig adgang

Ulemper

✗Mere kompleks end binære træer
✗Højere hukommelsesforbrug per node
✗Split- og merge-operationer er dyre
✗Ikke optimal for data i hukommelsen
✗Sværere at implementere korrekt

Eksempler fra den virkelige verden

•MySQL InnoDB storage engine indekser
•PostgreSQL GiST og B-træ indekser
•MongoDB WiredTiger storage engine
•NTFS Master File Table
•Oracle Database B-træ indekser

Relaterede strukturer

B+ TreeRed-Black TreeAVL TreeHash Table