Enregistrer des Btrees dans un fichier disque et le lire

Question

Je veux enregistrer un Btree (pas un binaire) dans un fichier disque. puis le lire dans la mémoire. Un parcours de niveau peut être un bon moyen pour un Btree binaire. mais si ce n'est pas un binaire. Je construis le Btree du leafnode au rootnode en mémoire. Je crois que je dois définir certaines structures dans le fichier disque et sortir les nœuds de l'arbre. en utilisant une balise supplémentaire pour identifier un nœud dans le fichier? comment traverser peut être le problème clé ici. Je n'arrive pas à trouver un bon moyen de sauvegarder les nœuds et les pointeurs. puis lisez-le. reconstruire l'arbre en mémoire. de bonnes idées? merci beaucoup.

Answer 1

Si vous voulez vraiment faire quelque chose de similaire, vous pouvez simplement attribuer à chaque noeud d'un identifiant et d'enregistrer les noeuds dans ce format:

[valeur noeud-id gauche-node-id droit noeud-id]

puis de visiter l'arbre avec une recherche en largeur d'abord. Lorsque vous voulez reconstruire l'arborescence, créez une carte id-> node puis lisez en arrière le fichier: ainsi, lorsque vous lisez un enregistrement, créez le nœud, enregistrez-le sur la carte et affectez-lui la gauche et nœud droit récupérant les nœuds de la carte.

Answer 2

Pour chaque noeud, définissez une structure de données qui conservera pour vous les mêmes informations que le noeud et ajoutera à cette structure un champ supplémentaire qui marquera pour vous le décalage dans le fichier pour les fils suivants. Et faire le champ supérieur de cette structure c'est la taille réelle, puisque vous ne savez pas quel type d'arbre vous cherchez maintenant. Maintenant, en sautant par-dessus le fichier, vous pourrez reconstruire votre arbre. Je suis sûr que ma solution n'est pas définitive, mais j'espère que cela pourrait être le bon point de départ pour vous.

Answer 3

Vous voudrez peut-être vérifier Protocol Buffers. Ils sont compacts, binaires, extensibles, faciles à lire et à écrire, et disponibles en C++, Java et Python (ainsi que des implémentations tierces dans d'autres langages).

Vous pouvez définir un message de tampon de protocole pour un nœud BTree, avec des décalages de fichiers pour les nœuds enfants, et simplement le sérialiser sur le disque de manière évidente.

Answer 4

La technique habituelle pour les arbres B est de s'assurer que la taille d'un nœud est égale à la taille de bloc du disque, et mmap le fichier du disque. Vous ne spécifiez pas le langage de programmation dans lequel vous travaillez, donc cela peut être aussi simple qu'un cast en C, ou quelque chose de plus compliqué comme la création d'objets flyweight pour envelopper un java.nio.IntBuffer. D'une manière ou d'une autre, l'avantage de l'arbre B est que vous n'avez pas à le charger en une seule fois, mais vous pouvez le contourner assez efficacement.