Index de type B-Arbre en C

Citation:

Envoyé par greegthegeek

Bonjour à tous,

Je dois réaliser un programme qui va représenter un index de type B-arbre pour un fichier plat. Cet index devra être écrit en C, et en plus de gérer tout ce que doit gérer un index, il faudra qu'il se sauvegarde dans un fichier, et qu'il puisse se restaurer...

Le problème c'est que je ne suis aucunement compétent en BD ou en C !! Y'aurait-il une âme charitable pour m'aider, me guider?

J'ai trouver ceci:http://www.cc.gatech.edu/classes/AY2...spring/btree.c

Est-ce ce que je cherche (je suis tellement une bille que je ne saurais même pas voir la réponse si elle était sous mes yeux...)?

Je demande de l'aide pas la réponse évidemment

Merci de m'avoir lu,
GreeG

Déjà ton lien ne fonctionne pas. Il semble incomplet car je peux arriver jusqu'ici http://www.cc.gatech.edu/classes mais ensuite, pour trouver la tienne...

Bon, c'est quoi un fichier ? Des lignes qui contiennent des infos comme nom, prénom, age. Comme ici
Bob:Tibère:18
Arthur:Romero:22
Grudu:Nicolas:55

C'est quoi un index ? C'est un truc qui permet d'accéder rapidement à l'info cherchée. Donc ça contient
- la valeur nécessaire (par exemple le nom)
- l'endroit où se trouve ce nom dans le fichier (par exemple la position à partir du départ
Exemple
Bob:0
Arthur:14
Grudu:33

La phase de recherche s'effectue en 2 étapes
1) je balaye mon index pour trouver le nom demandé et je récupère la position
2) grace à la position je me déplace dans le fichier et je lis la ligne à cet endroit là => je récupère toute la ligne contenant mon nom

Pour la phase n° 1, il est intéressant que l'index soit trié ce qui accélère la recherche. Et pour trier tes infos, on te propose de les regrouper en arbre binaire gauche/droite. Comment ça marche => tu as une info à stocker
1) si le noeud sur lequel tu te trouves est libre tu stockes l'info sur ce noeud
2) sinon si l'info est plus petite que celle présente sur ce noeud tu te déplaces sur le noeud de gauche et tu retournes en 1)
3) sinon c'est que l'info est plus grande donc tu te déplaces sur le noeud de droite et tu retournes en 1)

Une fois l'arbre construit, chaque info située à gauche d'un noeud est toujours plus petite que celle située sur le noeud qui est elle-même toujours plus petite que celle située sur la droite. A partir de là, faire une recherche est plus rapide puisqu'à chaque étape de recherche tu élimines la moitié des éléments qui ne correspondent pas (à condition que l'arbre soit bien équilibré)