Decrypt

Un article de saison pour clore cette année : un peu d’algorithmique et notamment le B-tree (de Noël ;ob). Le B-tree (ou arbre équilibré) est un algorithme très utilisé et notamment dans la gestion des bases de données et des systèmes de fichiers. Il permet d’effectuer des opérations sur les données triées qui le composent suivant un temps amorti logarithmique. Ce sujet n’est pas tant pour vous expliquer le fonctionnement d’un B-tree, même si le fonctionnement est intéressant au demeurant, mais pour vous sensibiliser à la connaissance des algorithmes (les grands classiques et leurs dérivés) qu’il est très pratique de comprendre pour optimiser les performances de nos architectures et effectuer les bons choix.

Nordmann ou Epicéa ?
Le B-tree est un algorithme connu, un grand classique, que je vais vous résumer. Prenons l’exemple de l’insertion d’éléments dans un B-tree, la cinématique est la suivante : on insère la clé de l’élément dans le noeud dans lequel il devrait être positionné (le B-tree contient des clés ordonnées). Ensuite 2 possibilités : soit le noeud modifié contient un nombre de clés inférieur ou égal au nombre de clés autorisées, auquel cas on ne fait rien de plus, soit le noeud possède plus de clés que la limite, auquel cas on scinde le noeud en 2 et on fait remonter la « clé du milieu » dans le noeud père. Le noeud père est alors soumis au même traitement si son nombre d’éléments dépasse le maximum autorisé et ainsi de suite. C’est comme cela que l’arbre s’équilibre.

B-Tree exemple insertion

Dans l’exemple ci-dessus, le nombre maximum d’éléments par noeud est 2. On voit bien que lors de l’insertion de la clé de valeur 3, la racine se scinde en 2 et la « clé du milieu » (2) devient la racine. De même, sur l’insertion de la clé de valeur 5, le noeud <3-4-5> se scinde en 2 et la « clé du milieu » (4) rejoint la racine qui n’est pas en surpopulation. Sur l’ajout de la clé de valeur 7, le noeud <5-6-7> est en surpopulation : il en découle 2 noeuds contenant respectivement 5 et 7, et 6 remonte. La racine est alors la suivante <2-4-6>. Elle est en surnombre et va elle-même se scinder en 2 noeuds contenant respectivement 2 et 6 (qui ont chacun 2 noeuds fils) et une nouvelle racine est créée : 4. L’arbre s’équilibre donc automatiquement.

J’avais parlé lors du précédent article Tokyo Tyrant / Tokyo Cabinet, un key-value store à la Japonaise des différentes APIs de stockage et de la notion de complexité des mécanismes de stockage Hash et B+tree.

Sur la notion de complexité des mécanismes de stockage Hash et B+tree (On memory ou File), les fonctions O(1) et O(log N) représentent la complexité d’accès à la donnée en fonction du nombre d’occurences stockées dans le système. On comprend bien que le comportement O(1) correspond bien à celui d’une hashtable, puisque le temps d’accès à la donnée ne dépend pas du nombre d’occurrences. En effet, la donnée est accédée directement à partir du hash de sa clé. Eventuellement, cette complexité peut varier si des collisions sur le hash apparaissent (2 clés différentes peuvent donner le même hash, à ce hash correspond alors une liste chainée de valeurs possibles).

J’avais davantage détaillé celui du Hash, mais voilà c’est réparé ! On comprend à présent pourquoi la complexité sur l’API de type B-tree correspond à O(log N) (amorti logarithmique) : plus il y aura d’éléments insérés, moins vite va augmenter la « hauteur » de l’arbre puisqu’il y aura de plus en plus de noeuds distribués sur un niveau donné de l’arbre en allant « vers le bas ». Cette complexité s’applique autant à l’insertion, qu’à la suppression ou à la recherche.

Il ne faut pas non plus s’arrêter là, lors du choix d’un algorithme : il faut ensuite le paramétrer. Par exemple, dans le cadre du B-tree, on peut définir le nombre maximum d’éléments sur un noeud donné. Il faut faire un compromis entre la hauteur de l’arbre (le nombre de niveaux à parcourir pour accéder à un noeud en terminaison de l’arbre, une feuille donc ;ob) et la taille de chaque noeud (donc le nombre d’éléments à parcourir linéairement). On peut également définir si la scission d’un noeud est à effectuer lors du dépassement de la taille maximale du noeud sur insertion d’une clé ou bien de manière anticipée, sur tous les noeuds « complets » (ayant atteints le nombre limite de clés) rencontrés lors de la recherche d’un noeud (pour une insertion par exemple). On évite ainsi une « remontée » potentielle dans l’arbre, puisque l’on assure que le père d’un nœud à scinder peut accueillir une clé supplémentaire. La contrepartie est une légère augmentation de la hauteur moyenne de l’arbre. Ceci est un exemple pour vous montrer qu’une fois le choix de l’algorithme convenant à votre cas d’utilisation effectué, vous pouvez encore le paramétrer.

Il y a ensuite pour chaque algorithme des variantes. Par exemple, l’arbre binaire de recherche, mais aussi (je l’ai appris en même temps que la rédaction de l’article :o)) des variantes pour ce-dit arbre binaire de recherche comme l’arbre AVL, l’arbre bicolore ou rouge et noir (rien à voir avec une ex-chanteuse ;ob), ou bien encore le Splay tree. Chaque variante apporte une optimisation pour un cas donné d’utilisation.

Les algorithmes d’éviction des lignes en cache
Dans le remplacement des lignes en cache, là aussi, les algorithmes sont présents (comme dans beaucoup d’autres sujets). Je cite cet exemple car il est intéressant. Il est vrai que si l’on pense à un Memcached avec ses Go de données montées en mémoire, la question du remplacement des lignes en cache se pose moins, puisque l’objectif est d’avoir un cache applicatif distribué qui peut accueillir un pool de données nécessaires à son besoin. Si trop d’informations dans le cache induisent de l’éviction automatique et du remplacement, c’est peut-être qu’il faut ajouter un serveur… ou mieux organiser ses données ! ;ob Mais il y a également des caches mémoires plus « modestes » et intégrés dans nos systèmes ou logiciels et qui sont bâtis sur des algorithmes tels que « LRU » (Least Recently Used), « FIFO » (First In First Out), LFU (Least Frequently Used), PLRU (Pseudo LRU, approximation de l’algorithme LRU basé sur l’hypothèse qu’en bas de la liste des accès, on peut sélectionner arbitrairement un élément à remplacer) de type t (arbre de décision binaire) ou m, …

Cet exemple est là, encore, pour montrer que les algorithmes constituent la base de l’informatique et ne sont pas compliqués quand on prend le temps de les regarder et d’en comprendre le principe (pas besoin de les modifier non plus ! :o)). Il est important de comprendre leur fonctionnement afin de savoir si ils sont adaptés ou non à nos besoin et il ne faut pas hésiter à s’informer sur le sujet, c’est abordable et très utile. De même, chaque algorithme (ou tout du moins certains) peut être affiné par paramétrage et il est également possible d’envisager d’utiliser des algorithmes dérivés tels que des approximations.

Un très bon condensé d’algorithmes de remplacement de lignes en cache est accessible ici.

Conclusion
Le but de cet article n’était pas de faire un cours d’algorithmique (quoique vaste sujet passionnant), mais de vous sensibiliser au fait que ces dits algorithmes sont présents dans toutes nos architectures et que leur connaissance permet de mieux aborder les différents sujets, notamment de performances, qui se posent à nous. Les algorithmes utilisés dans nos systèmes ne sont pas très difficiles à comprendre (en tout cas les grands standards), et il ne faut pas hésiter à regarder et comprendre les grandes lignes qui sont suffisantes pour aborder un peu plus profondément et avec un peu plus de justesse certains problèmes.

Frédéric FAURE