Il me semble qu'un seul moyen de stocker des données dans un arbre B en tant que fichier peut être effectué efficacement avec C à l'aide d'un fichier binaire avec une séquence (réseau) de structures, avec chaque structure représentant un nœud. On peut donc connecter les nœuds individuels avec une approche similaire à la création de listes liées à l'aide de tableaux. Mais ensuite, le problème que les accessoires constitueraient une suppression d'un nœud, car il n'existe que quelques octets au centre dans un énorme fichier n'est pas possible.
Un moyen de supprimer pourrait être de garder une trace des nœuds «vides» jusqu'à atteindre un seuil de coupure, puis effectuez un autre fichier qui jettera les nœuds vides. Mais c'est fastidieux.
Y a-t-il une meilleure approche du point de vue de simplicité / efficacité pour la suppression, voire représentant un arbre B dans un fichier?
tia, -Sviya
3 Réponses :
J'ai fait une recherche très rapide et creusé ceci: http: //people.csail. mit.edu/jaffer/wb C Source: http: / /cvs.savannah.gnu.org/viewvc/wb/wb/c/ - Il semble proposer des bases de données de style B-Tree basées sur disque - bien que de jeter un coup d'œil à "delete.c" il semblait impliquer si Vous supprimez un nœud de tout le bas de celui-ci serait retiré - si c'est le comportement correct, il ressemble à quelque chose qui pourrait aider?
Aussi - Les arbres B sont souvent utilisés dans les systèmes de fichiers - pourriez-vous ne pas regarder un code de système de fichiers?
Ma propre inclination est celle d'un système de fichiers - si vous avez un arbre B de taille fixe, chaque fois que vous "supprimez" un nœud plutôt que de tenter de supprimer la référence, il suffit de définir la valeur sur tout ce qui ne veut rien dire votre code. Ensuite, demandez à un thread de nettoyage qui vérifie si quelqu'un dispose du fichier ouvert pour la lecture et si tout le calme bloque le fichier et les rangements.
Merci pour la référence, neuffoingers. :) devra certainement le lire. Parce que la suppression peut être fréquente, il faut en tenir compte d'être efficaces. Je m'attendrais à ce que certaines de ces opérations puissent peut-être être retardées, mais j'aurais besoin de lire le code pour voir s'il y a une meilleure option. J'ai également l'intention de l'utiliser pour un système de fichiers plus tard, mais la mise en œuvre serait différente car la taille serait constante. La conception devra donc en tenir compte.
Hmm je suis d'accord. Ce code prétend faire ce dont vous avez besoin et un coup d'œil curseur chez ViewCVS suggère qu'il pourrait - sans s'asseoir et reconstruire votre problème, bien qu'il soit difficile de dire ... Je pense que les systèmes de fichiers ne font que "zéro" éléments qu'ils souhaitent supprimer et assigner à tout Élément zéro mais je pourrais avoir ce problème. De toute façon, si cela ne répond pas, veuillez ouvrir la question à nouveau!
Les questions répondent à ce que je cherchais, et j'ai déjà découvert que le fichier tronquable et que le problème de la suppression des données du milieu est contourné. Merci. :)
Vous pouvez également utiliser Berkley DB aussi. Cela fonctionne bien avec les programmes C et implémente B + Tree.
Oui, mais je veux écrire mon propre code pour obtenir la vraie sensation. :)
Se mettre d'accord. L'écriture seul va bien pour obtenir la vraie sensation. BBD est une base de données très sophistiquée et offre de nombreuses fonctionnalités que le code normal ne serait pas. En cas de déploiement réel du produit, je choisirais BDB. La roue de réinventer serait difficile ici.
Pour implémenter des arbres B dans un fichier, vous pouvez utiliser le décalage de fichier au lieu des pointeurs. En outre, vous pouvez implémenter un "gestionnaire de mémoire de fichiers", de sorte que vous puissiez réutiliser des éléments supprimés dans le fichier.
Pour récupérer complètement les blocs supprimés dans un fichier B-Tree, vous devrez recréer l'arborescence B dans un nouveau fichier. Rappelez-vous également que la plupart des OSE n'ont aucune méthode pour tronquer des fichiers. Une méthode portable pour tronquer un fichier consiste à écrire un nouveau fichier et à détruire l'ancien.
Une autre suggestion est de partitionner le fichier dans la partition de partition et de données (article) B-Tree. Une partition B-Tree contiendra les pages. Les pages de feuilles contiendront des compensations vers les é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 plus d'une de chaque partition et les partitions peuvent être entrelacées.
J'ai passé beaucoup de temps à jouer avec un arbre B basé sur un fichier, jusqu'à ce que j'ai abandonné et j'ai décidé de laisser un programme de base de données (ou serveur) gérer les données pour moi.
Ça a l'air intéressant. Cet exercice de mine est d'obtenir une certaine exposition au codage de faible niveau. Je suis principalement intéressé par les systèmes basés sur Linux et il prend en charge la troncature du fichier. :)
La plupart des systèmes d'exploitation font ont des fonctions pour tronquer des fichiers. Dans Linux, BSDS, Windows, vous pouvez définir la longueur de fichier sur ce que vous voulez.
Juste pour être clair, demandez-vous des arbres B ou des arbres binaires.
B-arbres. Mais je suppose que dans le but de stocker comme fichiers que le problème serait le même?
BTW, C et C ++ sont deux langues différentes. Si vous écrivez un code qui fonctionne sur les deux, puis ajoutez la balise C ++.