adjonction dans un Arbres-b
Bonjour à tous,
Je travaille actuellement sur les index en base de données et j'ai lu que les index utilisent la structure de donnée arbres-b.
J'essaye donc de comprendre le fonctionnement de cette structure de donnée.
J'écris de manière général l'algo en pseudo français pour le cas d'adjonctions de clé d'index.
Je prends l'exemple d'un arbre-B d'ordre 3
donc m=3 et k=2*m+1 où k-1 est la taille maximum d'un nœud.
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
On cherche la feuille dans laquelle il faut insérer la clé (parcours de l'arbre à partir de la racine)
Procedure inserer_recursif
Debut
Si la longueur du nœud est inférieur à k alors
On insère dans le noeud/feuille
Sinon
On éclate le noeud/feuille en deux
On remonte au noeud parent la médiane (la médiane devient l'élément à insérer)
inserer_recursif
Fin si
Fin |
J'ai souligné les fonctions/procedures.
Mon algo est-il correct ?
Merci de votre aide.