Drzewa B: efektywność cache i optymalizacja struktur danych

Drzewa B i optymalizacja pamięci podręcznej: jak zwiększyć wydajność struktur danych

Współczesne aplikacje nieustannie mierzą się z koniecznością przetwarzania ogromnych ilości danych, a wydajność struktur danych w takich warunkach staje się kluczowa. Tradycyjne binarne drzewa poszukiwań, takie jak drzewa czerwono-czarne, wykazują znaczące niedociągnięcia podczas pracy z dużymi zbiorami danych, zwłaszcza w kontekście interakcji z pamięcią podręczną procesora. W tym artykule przyjrzymy się, w jaki sposób drzewa B rozwiązują problem błędów pamięci podręcznej (cache misses) i dlaczego są preferowanym wyborem dla wysokowydajnych systemów przechowywania i wyszukiwania danych, nawet jeśli wszystkie dane znajdują się w pamięci operacyjnej.

Problem wydajności tradycyjnych drzew

W przypadku baz danych zawierających miliony rekordów, operacje wyszukiwania w binarnych drzewach poszukiwań mogą pochłaniać tysiące cykli procesora. Główną przyczyną tej nieefektywności jest niska lokalność danych, a co za tym idzie, częste błędy pamięci podręcznej (cache misses). Każdy węzeł w drzewie binarnym może być umieszczony w dowolnym obszarze pamięci, co prowadzi do konieczności ładowania nowej linii pamięci podręcznej przy przechodzeniu z jednego węzła do drugiego. Dla drzewa o wysokości 20 poziomów (co jest typowe dla miliona elementów) każda operacja wyszukiwania może zainicjować do 20 błędów pamięci podręcznej. To wielokrotnie spowalnia dostęp do danych, ponieważ czas dostępu do pamięci głównej jest o rzędy wielkości dłuższy niż czas dostępu do pamięci podręcznej.

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

Ten przykład pokazuje, że drzewo czerwono-czarne podczas przetwarzania zapytań generuje 18,5 miliona błędów pamięci podręcznej i zużywa 120 milionów cykli, co jest nieakceptowalne dla systemów czasu rzeczywistego.

Podstawy drzew B: podejście wielościeżkowe

Drzewo B to samobalansujące się drzewo poszukiwań, w którym każdy węzeł może mieć wiele elementów potomnych, a nie tylko dwa, jak w drzewach binarnych. Kluczową cechą drzew B jest znaczne zmniejszenie wysokości drzewa poprzez zwiększenie liczby kluczy przechowywanych w każdym węźle. Na przykład, drzewo B rzędu M może mieć do M-1 kluczy i M elementów potomnych w każdym węźle. Dla miliona elementów drzewo B rzędu 64 będzie miało wysokość zaledwie około 3 poziomów, podczas gdy drzewo binarne wymagałoby około 20 poziomów.

Główne właściwości drzewa B:

• Każdy węzeł zawiera do M-1 kluczy.
• Każdy węzeł wewnętrzny ma do M elementów potomnych.
• Wszystkie liście znajdują się na tej samej głębokości, zapewniając zrównoważenie.
• Klucze w każdym węźle są posortowane.

Taka struktura umożliwia wykonywanie wyszukiwania binarnego wewnątrz każdego węzła, co jest niezwykle efektywne, ponieważ wszystkie klucze węzła są przechowywane sekwencyjnie w pamięci. Minimalizuje to błędy pamięci podręcznej, gdyż po załadowaniu węzła do pamięci podręcznej wszystkie jego klucze stają się dostępne bez dodatkowych odwołań do pamięci głównej.

typedef struct btree_node {
    int num_keys;                    // 4 bajty
    int keys[BTREE_ORDER - 1];       // 252 bajty (63 klucze dla BTREE_ORDER=64)
    void *values[BTREE_ORDER - 1];   // 504 bajty
    struct btree_node *children[BTREE_ORDER];  // 512 bajtów
    // I łącznie: ~1272 bajty (mieści się w ~20 liniach pamięci podręcznej)
} btree_node_t;

int find_key(btree_node_t *node, int key) {
    // Wyszukiwanie binarne w posortowanej tablicy (przyjazne dla pamięci podręcznej!)
    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;  // Nie znaleziono
}

Mechanizmy efektywności pamięci podręcznej i benchmarki

Kluczową zaletą drzew B jest ich efektywność pamięci podręcznej. Podczas dostępu do węzła następuje tylko jeden błąd pamięci podręcznej, który ładuje cały węzeł do pamięci podręcznej procesora. Następnie wyszukiwanie binarne kluczy wewnątrz węzła odbywa się praktycznie bez dodatkowych opóźnień. W ten sposób liczba błędów pamięci podręcznej podczas wyszukiwania elementu w drzewie B jest równa jego wysokości. Dla drzewa B o wysokości 3 oznacza to zaledwie 3 błędy pamięci podręcznej na operację wyszukiwania, co jest znacznie mniej niż w przypadku drzew binarnych.

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;  // Nie znaleziono
        }
        
        node = node->children[i]; // Tutaj błąd pamięci podręcznej przy przejściu do węzła potomnego
    }
    
    return NULL;
}

Wyniki benchmarków to potwierdzają. Dla miliona elementów i 10 000 losowych operacji wyszukiwania, drzewo B rzędu 64 wykazało 6,7-krotne przyspieszenie w porównaniu z drzewem czerwono-czarnym, redukując liczbę błędów pamięci podręcznej z 18,5 miliona do 2,8 miliona.

| Drzewo | Wysokość | Cykle/operacja wyszukiwania | Błędy pamięci podręcznej | Przyspieszenie |

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

| Czerwono-czarne | 20 | 12 000 | 18,5 mln | 1× |

| Drzewo B (rząd 16) | 5 | 3 200 | 4,8 mln | 3,75× |

| Drzewo B (rząd 64) | 3 | 1 800 | 2,8 mln | 6,7× |

| Drzewo B (rząd 256) | 2 | 1 200 | 1,9 mln | 10× |

Wybór optymalnego rzędu drzewa B

Wybór rzędu M dla drzewa B to kompromis między wysokością drzewa a liczbą porównań wewnątrz węzła. Idealny rząd jest określany przez rozmiar linii pamięci podręcznej procesora (zazwyczaj 64 bajty). Węzeł drzewa B powinien w miarę możliwości w całości mieścić się w jednej lub kilku liniach pamięci podręcznej. Minimalizuje to liczbę błędów podczas ładowania węzła. Na przykład, dla drzewa B przechowywanego w pamięci RAM, optymalny rząd zazwyczaj mieści się w zakresie 16-64. Dla dyskowych baz danych, gdzie koszt operacji wejścia-wyjścia na dysku jest znacznie wyższy, rząd może być znacznie większy (128-512), aby zminimalizować liczbę operacji dyskowych.

Wstawianie, drzewa B+ i struktury niezależne od pamięci podręcznej

Wstawianie do drzewa B wymaga utrzymania jego zrównoważenia, co osiąga się poprzez dzielenie przepełnionych węzłów. Gdy węzeł osiągnie maksymalną liczbę kluczy, jest dzielony na dwa, a klucz medianowy przenoszony jest do węzła rodzica. Ta operacja ma zamortyzowaną złożoność O(1), ponieważ zdarza się stosunkowo rzadko.

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]) {  // Węzeł-liść
        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 {  // Węzeł wewnętrzny
        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);
    }
}

Drzewa B+ dla efektywnych zapytań zakresowych

Drzewa B+ są modyfikacją drzew B, zoptymalizowaną pod kątem baz danych. W drzewach B+ wszystkie dane (wartości) są przechowywane wyłącznie w węzłach-liściach, które dodatkowo są ze sobą połączone w listę jednokierunkową. Węzły wewnętrzne zawierają jedynie klucze, które kierują wyszukiwaniem. Pozwala to znacznie przyspieszyć zapytania zakresowe, ponieważ po znalezieniu początkowego punktu zakresu można po prostu sekwencyjnie przeglądać liście, nie przechodząc przez całe drzewo. Taka struktura jest wykorzystywana w większości nowoczesnych relacyjnych baz danych, takich jak MySQL InnoDB, PostgreSQL i SQLite.

Drzewa B niezależne od pamięci podręcznej

Optymalny rząd drzewa B zależy od rozmiaru linii pamięci podręcznej, który może się różnić w zależności od architektury. Drzewa B niezależne od pamięci podręcznej, oparte na schematach rekurencyjnych (np. schemat van Emde Boasa), adaptują się do dowolnego rozmiaru pamięci podręcznej bez konieczności ręcznej konfiguracji. Chociaż ich implementacja jest bardziej złożona, zapewniają wysoką wydajność na szerokim spektrum platform sprzętowych.

Co jest ważne

• Drzewa B znacząco redukują błędy pamięci podręcznej w porównaniu z binarnymi drzewami poszukiwań, co jest kluczowe dla wydajności przy pracy z dużymi wolumenami danych.
• Mniejsza wysokość drzewa i sekwencyjne przechowywanie kluczy w węzłach drzewa B to kluczowe czynniki jego efektywności pamięci podręcznej.
• Wybór optymalnego rzędu drzewa B powinien uwzględniać rozmiar linii pamięci podręcznej procesora dla maksymalnej wydajności.
• Drzewa B+ są idealne dla baz danych dzięki efektywnemu przetwarzaniu zapytań zakresowych i przechowywaniu wszystkich wartości w liściach.
• Zrozumienie hierarchii pamięci i zachowania pamięci podręcznej jest niezbędne do projektowania wysokowydajnych struktur danych i systemów.

— Editorial Team