B-trees: Cache-Effizienz und Datenstruktur-Optimierung

B-Bäume und Cache-Optimierung: Leistungssteigerung von Datenstrukturen

Moderne Anwendungen stehen ständig vor der Herausforderung, riesige Datenmengen zu verarbeiten, wodurch die Leistung von Datenstrukturen von entscheidender Bedeutung ist. Traditionelle binäre Suchbäume, wie Rot-Schwarz-Bäume, weisen erhebliche Nachteile auf, wenn es um große Datensätze geht, insbesondere im Hinblick auf die Interaktion mit dem CPU-Cache. Dieser Artikel untersucht, wie B-Bäume das Problem der Cache-Fehlzugriffe lösen und warum sie die bevorzugte Wahl für Hochleistungs-Datenspeicher- und -abrufsysteme sind, selbst wenn alle Daten im Hauptspeicher liegen.

Das Leistungsproblem traditioneller Bäume

Beim Arbeiten mit Datenbanken, die Millionen von Datensätzen enthalten, können Suchoperationen in binären Suchbäumen Tausende von CPU-Zyklen verbrauchen. Der Hauptgrund für diese Ineffizienz ist eine schlechte Datenlokalität, die zu häufigen Cache-Fehlzugriffen führt. Jeder Knoten in einem Binärbaum kann sich in einem beliebigen Speicherbereich befinden, was das Laden einer neuen Cache-Zeile beim Übergang von einem Knoten zum nächsten erforderlich macht. Bei einem Baum mit einer Höhe von 20 Ebenen (typisch für eine Million Elemente) kann jede Suchoperation bis zu 20 Cache-Fehlzugriffe auslösen. Dies verlangsamt den Datenzugriff erheblich, da Hauptspeicherzugriffszeiten um Größenordnungen langsamer sind als Cache-Zugriffszeiten.

$ perf stat -e cache-misses,cycles ./db_query_rbtree
  Performance counter stats:
    18,500,000 cache-misses
   120,000,000 cycles

Dieses Beispiel zeigt, dass ein Rot-Schwarz-Baum bei der Verarbeitung von Abfragen 18,5 Millionen Cache-Fehlzugriffe erzeugt und 120 Millionen Zyklen verbraucht, was für Echtzeitsysteme inakzeptabel ist.

B-Baum-Grundlagen: Der Multi-Way-Ansatz

Ein B-Baum ist ein selbstbalancierender Suchbaum, bei dem jeder Knoten mehrere Kinder haben kann, nicht nur zwei, wie bei Binärbäumen. Das Hauptmerkmal von B-Bäumen ist eine erhebliche Reduzierung der Baumhöhe durch Erhöhung der Anzahl der in jedem Knoten gespeicherten Schlüssel. Zum Beispiel kann ein B-Baum der Ordnung M bis zu M-1 Schlüssel und M Kinder pro Knoten haben. Für eine Million Elemente hätte ein B-Baum der Ordnung 64 eine Höhe von nur etwa 3 Ebenen, während ein Binärbaum ungefähr 20 Ebenen benötigen würde.

Wichtige Eigenschaften eines B-Baums:

• Jeder Knoten enthält bis zu M-1 Schlüssel.
• Jeder interne Knoten hat bis zu M Kinder.
• Alle Blätter befinden sich auf derselben Tiefe, was die Balance gewährleistet.
• Schlüssel innerhalb jedes Knotens sind sortiert.

Diese Struktur ermöglicht eine binäre Suche innerhalb jedes Knotens, was äußerst effizient ist, da alle Schlüssel eines Knotens zusammenhängend im Speicher gespeichert sind. Dies minimiert Cache-Fehlzugriffe, da das Laden eines Knotens in den Cache alle seine Schlüssel ohne zusätzliche Hauptspeicherzugriffe zugänglich macht.

typedef struct btree_node {
    int num_keys;                    // 4 Bytes
    int keys[BTREE_ORDER - 1];       // 252 Bytes (63 Schlüssel für BTREE_ORDER=64)
    void *values[BTREE_ORDER - 1];   // 504 Bytes
    struct btree_node *children[BTREE_ORDER];  // 512 Bytes
    // Gesamt: ~1272 Bytes (passt in ~20 Cache-Zeilen)
} btree_node_t;

int find_key(btree_node_t *node, int key) {
    // Binäre Suche in einem sortierten Array (Cache-freundlich!)
    int left = 0, right = node->num_keys - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (node->keys[mid] == key) return mid;
        if (key < node->keys[mid]) right = mid - 1;
        else left = mid + 1;
    }
    return -1;  // Nicht gefunden
}

Cache-Effizienz-Mechanismen und Benchmarks

Der entscheidende Vorteil von B-Bäumen ist ihre Cache-Effizienz. Wenn auf einen Knoten zugegriffen wird, tritt nur ein Cache-Fehlzugriff auf, der den gesamten Knoten in den CPU-Cache lädt. Danach erfolgt die binäre Suche nach Schlüsseln innerhalb des Knotens praktisch ohne zusätzliche Latenz. Somit entspricht die Anzahl der Cache-Fehlzugriffe während einer Elementsuche in einem B-Baum seiner Höhe. Für einen B-Baum mit einer Höhe von 3 bedeutet dies nur 3 Cache-Fehlzugriffe pro Suchoperation, deutlich weniger als bei Binärbäumen.

void* btree_search(btree_node_t *root, int key) {
    btree_node_t *node = root;
    
    while (node) {
        int i = 0;
        while (i < node->num_keys && key > node->keys[i]) {
            i++;
        }
        
        if (i < node->num_keys && key == node->keys[i]) {
            return node->values[i];
        }
        
        if (!node->children[0]) {
            return NULL;  // Nicht gefunden
        }
        
        node = node->children[i]; // Cache-Fehlzugriff hier beim Traversieren zu einem Kindknoten
    }
    
    return NULL;
}

Benchmark-Ergebnisse bestätigen dies. Für eine Million Elemente und 10.000 zufällige Suchoperationen zeigte ein B-Baum der Ordnung 64 eine 6,7-fache Beschleunigung im Vergleich zu einem Rot-Schwarz-Baum, wodurch die Anzahl der Cache-Fehlzugriffe von 18,5 Millionen auf 2,8 Millionen reduziert wurde.

| Baum | Höhe | Zyklen/Suchoperation | Cache-Fehlzugriffe | Beschleunigung |

| :----------------- | :----- | :-------------------- | :----------- | :-------- |

| Rot-Schwarz | 20 | 12.000 | 18,5 Millionen | 1× |

| B-Baum (Ordnung 16) | 5 | 3.200 | 4,8 Millionen | 3,75× |

| B-Baum (Ordnung 64) | 3 | 1.800 | 2,8 Millionen | 6,7× |

| B-Baum (Ordnung 256) | 2 | 1.200 | 1,9 Millionen | 10× |

Die Wahl der optimalen B-Baum-Ordnung

Die Wahl der Ordnung M für einen B-Baum beinhaltet einen Kompromiss zwischen Baumhöhe und der Anzahl der Vergleiche innerhalb eines Knotens. Die ideale Ordnung wird durch die Cache-Zeilengröße des Prozessors (typischerweise 64 Bytes) bestimmt. Ein B-Baum-Knoten sollte idealerweise vollständig in eine oder mehrere Cache-Zeilen passen. Dies minimiert Cache-Fehlzugriffe beim Laden eines Knotens. Zum Beispiel liegt die optimale Ordnung für einen In-Memory-B-Baum typischerweise zwischen 16 und 64. Für plattenbasierte Datenbanken, bei denen die Kosten für Disk-I/O viel höher sind, kann die Ordnung deutlich größer sein (128-512), um Festplattenoperationen zu minimieren.

Einfügen, B+ Bäume und Cache-oblivious Strukturen

Das Einfügen in einen B-Baum erfordert die Aufrechterhaltung seiner Balance, was durch das Aufteilen überlaufender Knoten erreicht wird. Wenn ein Knoten seine maximale Schlüsselanzahl erreicht, teilt er sich in zwei auf, und der mittlere Schlüssel wird zum Elternknoten hochgestuft. Diese Operation hat eine amortisierte Komplexität von O(1), da sie relativ selten auftritt.

void btree_insert(btree_node_t **root, int key, void *value) {
    btree_node_t *node = *root;

    if (node->num_keys == BTREE_ORDER - 1) {
        btree_node_t *new_root = create_node();
        new_root->children[0] = node;
        split_child(new_root, 0);
        *root = new_root;
    }

    insert_non_full(*root, key, value);
}

void insert_non_full(btree_node_t *node, int key, void *value) {
    int i = node->num_keys - 1;

    if (!node->children[0]) {  // Blattknoten
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            node->values[i + 1] = node->values[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->values[i + 1] = value;
        node->num_keys++;
    } else {  // Interner Knoten
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        if (node->children[i]->num_keys == BTREE_ORDER - 1) {
            split_child(node, i);
            if (key > node->keys[i]) i++;
        }

        insert_non_full(node->children[i], key, value);
    }
}

B+ Bäume für effiziente Bereichsabfragen

B+ Bäume sind eine Modifikation von B-Bäumen, optimiert für Datenbanken. In B+ Bäumen werden alle Daten (Werte) ausschließlich in Blattknoten gespeichert, die auch in einer sequenziellen Liste miteinander verbunden sind. Interne Knoten enthalten nur Schlüssel, die die Suche leiten. Dies beschleunigt Bereichsabfragen erheblich, da man, sobald der Startpunkt eines Bereichs gefunden ist, einfach die Blattknoten sequenziell durchlaufen kann, ohne den gesamten Baum zu durchqueren. Diese Struktur wird in den meisten modernen relationalen Datenbanken eingesetzt, einschließlich MySQL InnoDB, PostgreSQL und SQLite.

Cache-oblivious B-Bäume

Die optimale Ordnung eines B-Baums hängt von der Cache-Zeilengröße ab, die über verschiedene Architekturen hinweg variieren kann. Cache-oblivious B-Bäume, basierend auf rekursiven Layouts (wie dem van Emde Boas Layout), passen sich jeder Cache-Größe an, ohne manuelle Abstimmung zu erfordern. Obwohl ihre Implementierung komplexer ist, liefern sie hohe Leistung über eine breite Palette von Hardware-Plattformen.

Wichtige Erkenntnisse

• B-Bäume reduzieren Cache-Fehlzugriffe erheblich im Vergleich zu binären Suchbäumen, was für die Leistung bei großen Datensätzen entscheidend ist.
• Geringere Baumhöhe und zusammenhängende Schlüsselspeicherung innerhalb von B-Baum-Knoten sind Schlüsselfaktoren für ihre Cache-Effizienz.
• Die Wahl der optimalen B-Baum-Ordnung sollte die Cache-Zeilengröße des Prozessors für maximale Leistung berücksichtigen.
• B+ Bäume sind ideal für Datenbanken aufgrund ihrer effizienten Handhabung von Bereichsabfragen und der Speicherung aller Werte in Blattknoten.
• Das Verständnis der Speicherhierarchie und des Cache-Verhaltens ist unerlässlich für die Entwicklung von Hochleistungs-Datenstrukturen und -systemen.

— Editorial Team