CHAPITRE 1 : POURQUOI LE DISQUE CHANGE TOUT
On peut connaître les arbres binaires de recherche par cœur et ne rien comprendre aux B-arbres. Parce qu'un B-arbre ne répond pas à la question « comment chercher vite ? » mais à une autre, beaucoup plus concrète : comment déranger le disque le moins souvent possible ?
Deux mémoires qui n'ont rien à voir
Un ordinateur range ses données à deux endroits très différents.
- La mémoire vive, rapide, chère, volatile. Un accès coûte quelques dizaines de nanosecondes.
- Le disque, lent, bon marché, persistant. Un accès coûte de l'ordre de la milliseconde sur un disque à plateaux.
Mettons ces deux nombres côte à côte :
| Durée d'un accès | Rapport | |
|---|---|---|
| Mémoire vive | ≈ 10 nanosecondes | 1 |
| Disque à plateaux | ≈ 10 millisecondes | 1 000 000 |
Un accès disque coûte environ un million de fois un accès mémoire. Tout le reste du cours découle de ce seul chiffre.
Pour se le représenter : si lire en mémoire prenait une seconde, lire sur le disque prendrait onze jours et demi.
Ce que cela fait au calcul de complexité
Quand les données tiennent en mémoire, on compte les comparaisons. Dès qu'elles vivent sur le disque, cette façon de compter devient trompeuse : mille comparaisons en mémoire ne pèsent rien à côté d'un seul accès disque.
On change donc d'unité de mesure. La question n'est plus « combien d'opérations ? » mais « combien de fois va-t-on toucher le disque ? »
Deux opérations, et deux seulement. Pour raisonner proprement, on se donne deux opérations que l'on considère comme indivisibles :
LIRE-DISQUE(x): amener en mémoire le nœudx;ÉCRIRE-DISQUE(x): réécrire sur le disque le nœudxmodifié.
Tout ce qui se passe entre les deux, en mémoire, est considéré comme gratuit, ou presque. C'est une approximation, mais elle est du bon côté : elle surestime à peine le coût réel.
La page : l'unité de transfert
Le disque ne se lit pas octet par octet. Il se lit par blocs de taille fixe, appelés pages : typiquement 4 ko, parfois 8 ou 16 ko. Demander un seul octet ou demander la page entière coûte exactement la même chose.
Voilà l'idée décisive :
Puisqu'une page arrive de toute façon en entier, autant la remplir de données utiles.
C'est précisément ce que fait un B-arbre : un nœud = une page. Là où un arbre binaire range une seule clé par nœud et gaspille le reste de la page, un B-arbre en range des centaines.
Le prix de l'arbre binaire
Prenons un arbre binaire de recherche équilibré contenant un milliard de clés. Sa hauteur vaut environ log₂(10⁹) ≈ 30. Chaque descente d'un niveau peut provoquer un accès disque, car rien ne garantit que deux nœuds voisins dans l'arbre soient voisins sur le disque.
30 accès × 10 ms = 0,3 seconde pour une seule recherche
Pour un site qui traite mille requêtes par seconde, c'est éliminatoire.
Le pari du B-arbre : des nœuds énormes
Si un nœud contient non pas une clé mais, disons, 199 clés et 200 fils, l'arbre devient très large et très plat. Sa hauteur ne vaut plus log₂ n mais log₁₀₀ n environ.
Sur le même milliard de clés :
| Structure | Hauteur | Accès disque | Durée |
|---|---|---|---|
| ABR équilibré | ≈ 30 | 30 | 0,30 s |
| B-arbre, t = 100 | ≈ 5 | 5 | 0,05 s |
Six fois moins d'allers-retours. Et comme la racine reste en permanence en mémoire, on descend en réalité à quatre accès.
Et avec un SSD ? Un disque à mémoire flash ramène l'accès autour de 100 microsecondes : le rapport tombe de 1 000 000 à environ 10 000. Il reste énorme. Le raisonnement ne change pas, seules les durées sont divisées par cent. C'est pourquoi les bases de données modernes utilisent toujours des B-arbres.
D'où ils viennent
Les B-arbres ont été introduits en 1970 par Rudolf Bayer et Edward M. McCreight, chez Boeing, pour indexer de gros fichiers. Plus de cinquante ans plus tard, ils sont partout : dans les index de PostgreSQL, MySQL et Oracle, et dans les systèmes de fichiers NTFS (1993), ext4 (2006) ou APFS (2017).
Quant à savoir ce que le « B » désigne : Bayer, balanced, Boeing, broad ? : les auteurs ne l'ont jamais tranché. McCreight s'en amusait encore en 2013 : plus on y réfléchit, disait-il en substance, mieux on comprend la structure.
À retenir
- Un accès disque coûte environ un million de fois un accès mémoire.
- On ne compte donc plus les comparaisons, mais les accès disque.
- Le disque se lit par pages entières : autant remplir chaque page.
- Un nœud de B-arbre occupe exactement une page, d'où des nœuds à des centaines de clés et un arbre très plat.
Exercices d'application
Voir le corrigeMasquer le corrige
Un nœud à n clés contient n clés et n+1 pointeurs :
8n + 8(n+1) <= 4096
16n + 8 <= 4096
16n <= 4088
n <= 255Un nœud contient donc jusqu'à 255 clés. Comme le maximum vaut 2t − 1, on a 2t − 1 = 255, soit t = 128.
Avec un tel degré, un arbre de hauteur 3 contient déjà au moins 2 × 128³ − 1 ≈ 4 millions de clés, et un arbre de hauteur 4 au moins 537 millions. Quatre accès disque suffisent donc : trois, en gardant la racine en mémoire.
En pratique on réserve quelques octets pour l'en-tête du nœud (nombre de clés, drapeau de feuille), ce qui fait descendre un peu ce 255 sans rien changer à l'ordre de grandeur.
Voir le corrigeMasquer le corrige
Parce que O(log n) compte les comparaisons, pas les accès disque, et que ces derniers sont les seuls qui coûtent.
Un ABR équilibré sur un milliard de clés a une hauteur de 30. Chaque nœud visité est à un endroit arbitraire du disque : la descente provoque jusqu'à 30 accès, soit environ 0,3 seconde.
Plus grave encore, un nœud d'ABR occupe quelques dizaines d'octets. Comme le disque livre des pages de 4 ko, on transfère 4 096 octets pour n'en exploiter que 24. Plus de 99 % de chaque transfert est jeté.
Le B-arbre corrige exactement ces deux défauts : il remplit la page, et il réduit la hauteur dans la même proportion.
Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.
Questions / Réponses
Ajouter un commentaire