B-trees : efficacité du cache et optimisation des structures de données

Arbres B et Optimisation du Cache : Améliorer la Performance des Structures de Données

Les applications modernes sont constamment confrontées au défi de traiter de vastes quantités de données, ce qui rend la performance des structures de données d'une importance capitale. Les arbres binaires de recherche traditionnels, tels que les arbres rouge-noir, présentent des inconvénients majeurs lorsqu'il s'agit de grands ensembles de données, en particulier en ce qui concerne l'interaction avec le cache du CPU. Cet article explore comment les arbres B abordent le problème des défauts de cache et pourquoi ils sont le choix privilégié pour les systèmes de stockage et de récupération de données à haute performance, même lorsque toutes les données résident en mémoire principale.

Le Problème de Performance des Arbres Traditionnels

Lorsque l'on travaille avec des bases de données contenant des millions d'enregistrements, les opérations de recherche dans les arbres binaires de recherche peuvent consommer des milliers de cycles CPU. La raison principale de cette inefficacité est une faible localité des données, entraînant de fréquents défauts de cache. Chaque nœud d'un arbre binaire peut être situé dans une région mémoire arbitraire, nécessitant le chargement d'une nouvelle ligne de cache lors de la traversée d'un nœud à l'autre. Pour un arbre d'une hauteur de 20 niveaux (typique pour un million d'éléments), chaque opération de recherche peut déclencher jusqu'à 20 défauts de cache. Cela ralentit considérablement l'accès aux données, car les temps d'accès à la mémoire principale sont des ordres de grandeur plus lents que les temps d'accès au cache.

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

Cet exemple démontre qu'un arbre rouge-noir, lors du traitement des requêtes, génère 18,5 millions de défauts de cache et consomme 120 millions de cycles, ce qui est inacceptable pour les systèmes en temps réel.

Fondamentaux des Arbres B : L'Approche Multi-Voies

Un arbre B est un arbre de recherche auto-équilibré où chaque nœud peut avoir plusieurs enfants, et non pas seulement deux, comme dans les arbres binaires. La caractéristique clé des arbres B est une réduction significative de la hauteur de l'arbre en augmentant le nombre de clés stockées dans chaque nœud. Par exemple, un arbre B d'ordre M peut avoir jusqu'à M-1 clés et M enfants par nœud. Pour un million d'éléments, un arbre B d'ordre 64 aurait une hauteur d'environ 3 niveaux seulement, tandis qu'un arbre binaire nécessiterait environ 20 niveaux.

Propriétés Clés d'un Arbre B :

• Chaque nœud contient jusqu'à M-1 clés.
• Chaque nœud interne a jusqu'à M enfants.
• Toutes les feuilles sont à la même profondeur, assurant l'équilibre.
• Les clés de chaque nœud sont triées.

Cette structure permet une recherche binaire au sein de chaque nœud, ce qui est très efficace car toutes les clés d'un nœud sont stockées de manière contiguë en mémoire. Cela minimise les défauts de cache, car le chargement d'un nœud dans le cache rend toutes ses clés accessibles sans accès supplémentaires à la mémoire principale.

typedef struct btree_node {
    int num_keys;                    // 4 bytes
    int keys[BTREE_ORDER - 1];       // 252 bytes (63 keys for BTREE_ORDER=64)
    void *values[BTREE_ORDER - 1];   // 504 bytes
    struct btree_node *children[BTREE_ORDER];  // 512 bytes
    // Total: ~1272 bytes (fits into ~20 cache lines)
} btree_node_t;

int find_key(btree_node_t *node, int key) {
    // Recherche binaire dans un tableau trié (optimisé pour le cache !)
    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;  // Non trouvé
}

Mécanismes d'Efficacité du Cache et Benchmarks

L'avantage clé des arbres B est leur efficacité en matière de cache. Lorsqu'un nœud est accédé, un seul défaut de cache se produit, ce qui charge l'intégralité du nœud dans le cache du CPU. Après cela, la recherche binaire des clés au sein du nœud se déroule avec pratiquement aucune latence supplémentaire. Ainsi, le nombre de défauts de cache lors de la recherche d'un élément dans un arbre B est égal à sa hauteur. Pour un arbre B d'une hauteur de 3, cela signifie seulement 3 défauts de cache par opération de recherche, nettement moins que pour les arbres binaires.

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;  // Not found
        }
        
        node = node->children[i]; // Défaut de cache ici lors de la traversée vers un nœud enfant
    }
    
    return NULL;
}

Les résultats des benchmarks le confirment. Pour un million d'éléments et 10 000 opérations de recherche aléatoires, un arbre B d'ordre 64 a montré une accélération de 6,7 fois par rapport à un arbre rouge-noir, réduisant le nombre de défauts de cache de 18,5 millions à 2,8 millions.

| Arbre | Hauteur | Cycles/Opération de recherche | Défauts de cache | Accélération |

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

| Rouge-Noir | 20 | 12 000 | 18,5 millions | 1× |

| Arbre B (ordre 16) | 5 | 3 200 | 4,8 millions | 3,75× |

| Arbre B (ordre 64) | 3 | 1 800 | 2,8 millions | 6,7× |

| Arbre B (ordre 256) | 2 | 1 200 | 1,9 million | 10× |

Choisir l'Ordre Optimal d'un Arbre B

Le choix de l'ordre M pour un arbre B implique un compromis entre la hauteur de l'arbre et le nombre de comparaisons au sein d'un nœud. L'ordre idéal est déterminé par la taille de la ligne de cache du processeur (généralement 64 octets). Un nœud d'arbre B devrait idéalement tenir entièrement dans une ou plusieurs lignes de cache. Cela minimise les défauts de cache lors du chargement d'un nœud. Par exemple, pour un arbre B en mémoire, l'ordre optimal se situe généralement entre 16 et 64. Pour les bases de données basées sur disque, où le coût des E/S disque est beaucoup plus élevé, l'ordre peut être significativement plus grand (128-512) afin de minimiser les opérations disque.

Insertion, Arbres B+ et Structures Cache-Oblivious

L'insertion dans un arbre B nécessite de maintenir son équilibre, ce qui est réalisé en divisant les nœuds débordants. Lorsqu'un nœud atteint son nombre maximal de clés, il se divise en deux, et la clé médiane est promue au nœud parent. Cette opération a une complexité amortie de O(1) car elle se produit relativement rarement.

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]) {  // Nœud feuille
        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 {  // Nœud interne
        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);
    }
}

Arbres B+ pour des Requêtes de Plage Efficaces

Les arbres B+ sont une modification des arbres B optimisée pour les bases de données. Dans les arbres B+, toutes les données (valeurs) sont stockées exclusivement dans les nœuds feuilles, qui sont également liés entre eux dans une liste séquentielle. Les nœuds internes ne contiennent que des clés qui guident la recherche. Cela accélère considérablement les requêtes de plage, car une fois le point de départ d'une plage trouvé, on peut simplement parcourir les nœuds feuilles séquentiellement sans traverser l'arbre entier. Cette structure est utilisée dans la plupart des bases de données relationnelles modernes, y compris MySQL InnoDB, PostgreSQL et SQLite.

Arbres B Cache-Oblivious

L'ordre optimal d'un arbre B dépend de la taille de la ligne de cache, qui peut varier selon les architectures. Les arbres B cache-oblivious, basés sur des agencements récursifs (tels que l'agencement de van Emde Boas), s'adaptent à n'importe quelle taille de cache sans nécessiter de réglage manuel. Bien que leur implémentation soit plus complexe, ils offrent des performances élevées sur un large éventail de plateformes matérielles.

Points Clés à Retenir

• Les arbres B réduisent considérablement les défauts de cache par rapport aux arbres binaires de recherche, ce qui est critique pour la performance lors du traitement de grands ensembles de données.
• Une hauteur d'arbre réduite et un stockage contigu des clés au sein des nœuds d'arbre B sont des facteurs clés de leur efficacité de cache.
• Le choix de l'ordre optimal de l'arbre B doit tenir compte de la taille de la ligne de cache du processeur pour des performances maximales.
• Les arbres B+ sont idéaux pour les bases de données grâce à leur gestion efficace des requêtes de plage et au stockage de toutes les valeurs dans les nœuds feuilles.
• Comprendre la hiérarchie de la mémoire et le comportement du cache est essentiel pour développer des structures de données et des systèmes à haute performance.

— Editorial Team