Discussion :

[smyley]

Je vous expose la situation : il semblerai que les B+Tree soient les plus utilisés quand il s'agit de représenter une hiérarchie dans un système de fichier afin de stocker la liste des éléments enfants d'un dossier donné. En effet, avoir du O(log(n)) pour presque toues les opérations semble plutôt bien (moi je suis pour l'instant en O(n) avec la méthode la plus basique qui soit pour enregistrer ma liste ... ).

Je voudrais donc implémenter mon propre B+Tree pour mon "système de fichier" (plus une base de donnée) afin d'améliorer les temps d'accès et de modifications des nodes. Cependant en cherchant sur le net soit j'ai trouvé des exemples trop spécialisés pour être utilisés (j'y comprends rien ) soit il manquait certaines opérations (dont la suppression d'une node, j'en ai besoin). Existe-t-il des descriptions complètes de l'algo sous une forme "simple" (pseudocode) sur le net ?

Petite précision, je fonctionne avec des blocks de 64 octets, en comptant que chaque "pointeur" fait 8 octets je peut donc en mettre 8 par node. Donc à priori 7 de données et le 8ième qui pointe vers la node suivante. Les nodes doivent cependant êtres comparées par le nom, qui peut être obtenu en le lisant à partir du pointeur de la node (mais qui se trouve dans un autre bloc, avec ~32760 caractères maxi). Par contre, la lecture d'un bloc n'est pas très rapide donc une économie de n vers log(n) pourrait être intéressante. Le B+Tree est-il adapté à mon problème ?

Merci d'avance

[PRomu@ld]

Existe-t-il des descriptions complètes de l'algo sous une forme "simple" (pseudocode) sur le net ?

SUr le net je ne sais pas trop, tu peux trouver des infos dans le Cormen (introduction à l'algorithmique - chapitre 18 pour la deuxième édition)

Tu pourras également trouver des infos dans le Handbook of Data structures and applications (Chapman - chapitre 15)

[smyley]

Le truc c'est qu'il n'y a pas de libraires vendant ce genre de choses à coté de chez moi (je suis loin, même pas en France Métro) donc bon ... j'avais donc espéré qu'il existe des ressources (pdf, doc, html, etc...) montrant une implémentation simple du B+Tree (ou même, d'un B-Tree d'ordre 6 ou 7 si j'ai bien compris ce que ça veux dire) en pseudocode ou en pascal (facile à comprendre, avec le C/C++ les pointeurs commencent à noircir l'algo)... ça n'existe pas ?

[millie]

Sur :
http://en.wikipedia.org/wiki/B%2B_tree
et http://en.wikipedia.org/wiki/B-tree

Il y a un max de lien en dans la partie Ressources. Tu n'as rien trouvé de bien ?


Il y a des sources Java et C++ d'ailleurs.

[smyley]

Ben en fait chacune des sources présentées proposent une implémentation spécialisée de l'algo et finalement l'idée même du principe est un peut masqué (d'ailleurs les exemples que j'ai trouvé en C# ne sont pas vraiment documentés). Pour le C++ ... je suis nase en C++.
C'est pour celà que je voulais d'une source en "pseudocode" afin de n'avoir que l'algo devant moi car je ne sais pas trop comment je vais l'implémenter (j'ai finalement trouvé quelques problèmes dont des possibles collisions avec des clefs différents qui auraient le même id.) donc voilà, les details de chaque langage alourdissent l'algo ... Mais je pense que je vais essayer de me lancer dans un BTree perso mais beaucoup de détails sont encore bizarres pour moi :

Pour éviter d'accéder à un bloc trop souvent, je peut enregistrer un hashcode fait à partir du nom de la clef -> problème des collisions
Mes "pointeurs" dans la BdD font aussi 8 octets, donc pour les feuilles j'aurai 7 clefs et pour les nodes internes 4 séparés par 3 hashcode -> what ?
Et aussi savoir où stocker les hashcode.
En fait j'ai de plus en plus l'impression que je vais m'orienter vers un arbre binnaire, mais la perte question espace risque d'être grande vis à vis d'une simple liste des clefs ...

[millie]

On va faire autrement. Quel type de données veux tu exactement enregistrer ?

Et qu'elles sont les opérations que tu souhaites ?

[Jean-Marc.Bourguet]

Le truc c'est qu'il n'y a pas de libraires vendant ce genre de choses à coté de chez moi (je suis loin, même pas en France Métro) donc bon ... j'avais donc espéré qu'il existe des ressources (pdf, doc, html, etc...) montrant une implémentation simple du B+Tree (ou même, d'un B-Tree d'ordre 6 ou 7 si j'ai bien compris ce que ça veux dire) en pseudocode ou en pascal (facile à comprendre, avec le C/C++ les pointeurs commencent à noircir l'algo)... ça n'existe pas ?

http://www.jcolibri.com/livres/livre...el_indexe.html

[smyley]

Tient j'avais oublié ce message
Bon ben entre temps j'ai réussit à faire mon petit BTree et j'ai investit sur un AVL Tree (dont je n'ai rien compris) qui permet de rendre tout ça plus amusant.
Merci à tous ceux qui m'ont inspiré