C / C ++: Comment stocker les données dans un fichier dans l'arborescence B

Question

Il nous semble que un moyen de stockage de données dans un arbre B en tant que fichier peut être réalisé efficacement avec C en utilisant le fichier binaire avec une séquence (array) de structs, chaque structure représentant un noeud. On peut ainsi relier les nœuds individuels avec l'approche qui sera similaire à la création de listes liées à l'aide de tableaux. Mais le problème que les accessoires en serait la suppression d'un nœud, comme l'effacement seulement quelques octets au milieu dans un énorme fichier n'est pas possible.

Une façon de supprimer pourrait être de garder une trace des nœuds « vides » jusqu'à ce qu'une coupure de seuil est atteint, puis faire un autre fichier qui annule les nœuds vides. Mais cela est fastidieux.

Y at-il une meilleure approche du point de vue simplicité / efficacité pour la suppression, ou même représentant un B-tree dans un fichier?

TIA, -Sviiya

Answer 1

Je l'ai fait une recherche très rapide et déterré ceci: http: //people.csail. mit.edu/jaffer/WB de la source de C: http: / /cvs.savannah.gnu.org/viewvc/wb/wb/c/ - il semble offrir des bases de données de type B-tree sur disque - bien que jeter un oeil à « delete.c » semblait impliquer si vous supprimez un tout nœud vers le bas de celui-ci serait retiré - si c'est le comportement correct, alors il ressemble à quelque chose qui pourrait aider

De plus - B-arbres sont souvent utilisés dans les systèmes de fichiers - pourriez-vous pas jeter un oeil à un code du système de fichiers?

Mon inclination est celle d'un système de fichiers - si vous avez un B-arbre de taille fixe, chaque fois que vous « supprimer » un noeud plutôt que de tenter de supprimer la référence, vient de mettre la valeur à tout ce qui ne signifie rien dans votre code. Ensuite, une course de fil de nettoyage qui vérifie si quelqu'un a ouvert le fichier pour la lecture et si tout est calme le fichier blocs et range.

Answer 2

Pour la mise en œuvre B-arbres dans un fichier, vous pouvez utiliser le fichier de décalage au lieu des pointeurs. En outre, vous pouvez mettre en œuvre un « gestionnaire de mémoire de fichier », de sorte que vous pouvez réutiliser les éléments supprimés dans le fichier.

Afin de récupérer complètement les blocs supprimés dans un fichier B-Tree, vous devrez recréer le B-Tree dans un nouveau fichier. Rappelez-vous aussi le plus OSes ont aucune méthode pour les fichiers tronquer. Méthode portable pour tronquer un fichier est d'écrire un nouveau fichier et détruire l'ancien.

Une autre suggestion est de partitionner le fichier dans la partition de la partition B-Tree et des données (point). Une partition B-Tree contiendra les pages. Les pages de feuilles contiennent des compensations aux éléments de données. La partition de données sera une section dans le fichier contenant des éléments de données. Vous pouvez finir par créer plusieurs de chaque partition et les partitions peuvent être intercalés.

J'ai passé beaucoup de temps à jouer avec un fichier basé B-Tree, jusqu'à ce que j'ai abandonné et décidé de laisser un programme de base de données (ou serveur) gèrent les données pour moi.

Answer 3

Vous pouvez utiliser Berkley DB ainsi. Il fonctionne bien avec les programmes C et met en œuvre B + arbre.