B-stromy: cache-efektivita a optimalizace datových struktur

B-stromy a optimalizace cache: Jak zvýšit výkon datových struktur

Moderní aplikace se neustále potýkají s potřebou zpracovávat obrovské objemy dat a výkon datových struktur je v takových podmínkách kriticky důležitý. Tradiční binární vyhledávací stromy, jako jsou červeno-černé stromy, vykazují značné nedostatky při práci s velkými datovými sadami, zejména pokud jde o interakci s cache procesoru. V tomto článku se podíváme na to, jak B-stromy řeší problém cache missů a proč jsou preferovanou volbou pro vysoce výkonné systémy pro ukládání a vyhledávání dat, i když jsou všechna data v operační paměti.

Problém výkonu tradičních stromů

Při práci s databázemi obsahujícími miliony záznamů mohou operace vyhledávání v binárních vyhledávacích stromech zabrat tisíce taktů procesoru. Hlavní příčinou této neefektivnosti je nízká lokalita dat a s ní spojené časté cache missy. Každý uzel v binárním stromu může být umístěn v libovolné oblasti paměti, což vede k nutnosti načtení nové cache linky při přechodu z jednoho uzlu na druhý. Pro strom s výškou 20 úrovní (což je typické pro milion prvků) může každá vyhledávací operace iniciovat až 20 cache missů. To mnohonásobně zpomaluje přístup k datům, protože doba přístupu k hlavní paměti řádově převyšuje dobu přístupu k cache.

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

Tento příklad ukazuje, že červeno-černý strom při zpracování dotazů generuje 18,5 milionu cache missů a spotřebuje 120 milionů taktů, což je pro systémy reálného času nepřijatelné.

Základy B-stromů: vícesměrný přístup

B-strom představuje samo-balancující vyhledávací strom, ve kterém každý uzel může mít mnoho potomků, nikoli pouze dva, jako v binárních stromech. Klíčovou vlastností B-stromů je výrazné snížení výšky stromu díky zvýšení počtu klíčů uložených v každém uzlu. Například B-strom řádu M může mít až M-1 klíčů a M potomků v každém uzlu. Pro jeden milion prvků bude mít B-strom řádu 64 výšku pouze asi 3 úrovně, zatímco binární strom by vyžadoval asi 20 úrovní.

Hlavní vlastnosti B-stromu:

• Každý uzel obsahuje až M-1 klíčů.
• Každý vnitřní uzel má až M potomků.
• Všechny listy jsou na stejné hloubce, což zajišťuje vyváženost.
• Klíče v každém uzlu jsou seřazeny.

Tato struktura umožňuje provádět binární vyhledávání uvnitř každého uzlu, což je extrémně efektivní, protože všechny klíče uzlu jsou uloženy sekvenčně v paměti. To minimalizuje cache missy, jelikož po načtení uzlu do cache jsou všechny jeho klíče dostupné bez dalších přístupů k hlavní paměti.

typedef struct btree_node {
    int num_keys;                    // 4 bajty
    int keys[BTREE_ORDER - 1];       // 252 bajtů (63 klíčů pro BTREE_ORDER=64)
    void *values[BTREE_ORDER - 1];   // 504 bajtů
    struct btree_node *children[BTREE_ORDER];  // 512 bajtů
    // Celkem: ~1272 bajtů (vejde se do ~20 cache linek)
} btree_node_t;

int find_key(btree_node_t *node, int key) {
    // Binární vyhledávání v seřazeném poli (cache-friendly!)
    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;  // Nenalezeno
}

Mechanismy cache-efektivity a benchmarky

Klíčovou výhodou B-stromů je jejich cache-efektivita. Při přístupu k uzlu dojde pouze k jednomu cache missu, který načte celý uzel do cache procesoru. Poté se binární vyhledávání klíčů uvnitř uzlu provádí prakticky bez dalších zpoždění. Počet cache missů při hledání prvku v B-stromu je tedy roven jeho výšce. Pro B-strom s výškou 3 to znamená pouze 3 cache missy na vyhledávací operaci, což je výrazně méně než u binárních stromů.

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;  // Nenalezeno
        }
        
        node = node->children[i]; // Zde cache miss při přechodu k potomkovému uzlu
    }
    
    return NULL;
}

Výsledky benchmarků to potvrzují. Pro milion prvků a 10 000 náhodných vyhledávacích operací vykázal B-strom řádu 64 zrychlení 6,7krát ve srovnání s červeno-černým stromem, čímž snížil počet cache missů z 18,5 milionu na 2,8 milionu.

| Strom | Výška | Takty/operace vyhledávání | Cache missů | Zrychlení |

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

| Červeno-černý | 20 | 12 000 | 18,5 mil. | 1× |

| B-strom (řád 16) | 5 | 3 200 | 4,8 mil. | 3,75× |

| B-strom (řád 64) | 3 | 1 800 | 2,8 mil. | 6,7× |

| B-strom (řád 256) | 2 | 1 200 | 1,9 mil. | 10× |

Volba optimálního řádu B-stromu

Volba řádu M pro B-strom je kompromisem mezi výškou stromu a počtem porovnání uvnitř uzlu. Ideální řád je určen velikostí cache linky procesoru (obvykle 64 bajtů). Uzel B-stromu by se měl pokud možno celý vejít do jedné nebo několika cache linek. Tím se minimalizuje počet missů při načítání uzlu. Například pro B-strom uložený v paměti se optimální řád obvykle pohybuje v rozmezí 16-64. Pro diskové databáze, kde jsou náklady na diskové I/O mnohem vyšší, může být řád výrazně větší (128-512), aby se minimalizoval počet diskových operací.

Vkládání, B+ stromy a cache-nezávislé struktury

Vkládání do B-stromu vyžaduje udržení jeho vyváženosti, čehož se dosahuje rozdělením přeplněných uzlů. Když uzel dosáhne maximálního počtu klíčů, rozdělí se na dva a mediánový klíč se přesune do rodičovského uzlu. Tato operace má amortizovanou složitost O(1), protože k ní dochází relativně zřídka.

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]) {  // Listový uzel
        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 {  // Vnitřní uzel
        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+ stromy pro efektivní dotazy na rozsahy

B+ stromy jsou modifikací B-stromů, optimalizovanou pro databáze. V B+ stromech jsou všechna data (hodnoty) uložena pouze v listových uzlech, které jsou navíc propojeny do spojového seznamu. Vnitřní uzly obsahují pouze klíče, které řídí vyhledávání. To umožňuje výrazně urychlit dotazy na rozsahy, protože po nalezení počátečního bodu rozsahu lze jednoduše sekvenčně procházet listy, aniž by bylo nutné procházet celý strom. Tato struktura se používá ve většině moderních relačních databází, jako jsou MySQL InnoDB, PostgreSQL a SQLite.

Cache-nezávislé B-stromy

Optimální řád B-stromu závisí na velikosti cache linky, která se může lišit na různých architekturách. Cache-nezávislé B-stromy, založené na rekurzivních schématech (například schéma van Emde Boase), se přizpůsobují jakékoli velikosti cache bez nutnosti ručního nastavení. Ačkoli je jejich implementace složitější, poskytují vysoký výkon na široké škále hardwarových platforem.

Co je důležité:

• B-stromy výrazně snižují cache missy ve srovnání s binárními vyhledávacími stromy, což je kriticky důležité pro výkon při práci s velkými objemy dat.
• Menší výška stromu a sekvenční ukládání klíčů v uzlech B-stromu jsou klíčovými faktory jeho cache-efektivity.
• Volba optimálního řádu B-stromu by měla brát v úvahu velikost cache linky procesoru pro maximální výkon.
• B+ stromy jsou ideální pro databáze díky efektivnímu zpracování dotazů na rozsahy a ukládání všech hodnot v listech.
• Pochopení hierarchie paměti a chování cache je nezbytné pro vývoj vysoce výkonných datových struktur a systémů.

— Editorial Team