btree(3) Library Functions Manual btree(3) NOM btree - Methodes d'acces a une base de donnees en arbre binaire BIBLIOTHEQUE Bibliotheque C standard (libc, -lc) SYNOPSIS #include #include DESCRIPTION NOTE : cette page decrit des interfaces fournies jusqu'a la glibc 2.1. Depuis la glibc 2.2, la glibc ne fournit plus ces interfaces. Veuillez consulter les API fournies par la bibliotheque libdb. La routine dbopen(3) est l'interface de bibliotheque pour les fichiers de base de donnees. L'un des formats de fichier pris en charge est l'arbre binaire de fichiers. La description generale des methodes d'acces a une base de donnees est fournie dans la page de manuel dbopen(3). La presente page ne decrit que les informations specifiques aux arbres binaires. Une telle structure de donnees est un arbre equilibre, trie, memorisant les paires << cles-donnees >> associees. La structure de donnees specifique aux methodes d'acces aux arbres binaires que l'on fournit a dbopen(3) est definie dans le fichier d'en-tete comme suit : typedef struct { unsigned long flags; unsigned int cachesize; int maxkeypage; int minkeypage; unsigned int psize; int (*compare)(const DBT *key1, const DBT *key2); size_t (*prefix)(const DBT *key1, const DBT *key2); int lorder; } BTREEINFO; Les elements de cette structure sont les suivants : flags La valeur de ce champ est calculee avec un OU binaire sur certaines des constantes suivantes : R_DUP Autoriser les cles dupliquees dans l'arbre, c'est-a-dire, permettre l'insertion meme si la cle existe deja dans l'arbre. Le comportement par defaut, comme decrit dans dbopen(3), est d'ecraser une cle correspondante lors de l'insertion d'une nouvelle cle, ou d'echouer si le drapeau R_NOOVERWRITE est indique. Le drapeau R_NOOVERWRITE a priorite sur le drapeau R_DUP, et si R_NOOVERWRITE est specifie, une tentative d'insertion d'une cle deja existante echouera. Si la base de donnees contient des cles dupliquees, l'ordre de recuperation des paires << cle-valeur >> est indefini si l'on utilise la routine get. Toutefois la routine seq avec le drapeau R_CURSOR positionne renvoie la cle << logiquement premiere >> de chaque groupe de cles dupliquees. cachesize Une suggestion de taille maximale (en octets) du cache memoire. Cette valeur est seulement indicative, et les methodes d'acces alloueront plus de memoire plutot que d'echouer. Comme chaque recherche examine la page racine de l'arbre, le cache des pages les plus recemment consultees ameliore les temps d'acces. De plus, les ecritures physiques sont retardees aussi longtemps que possible, ainsi un cache, meme modeste, peut reduire sensiblement le nombre d'operations d'entree-sortie. Bien sur, l'utilisation d'un cache augmente (et seulement augmente) la probabilite de corruption ou de perte de donnees si le systeme plante alors qu'un arbre est en cours de modification. Si cachesize vaut 0 (pas de taille indiquee) un cache est utilise par defaut. maxkeypage Le nombre maximal de cles qui seront stockees sur une seule page. Pas encore implemente. minkeypage Le nombre minimal de cles qui seront stockees sur la meme page. Cette valeur est utilisee pour determiner quelles cles seront stockees sur des pages de debordement. Par exemple, lorsqu'une cle ou une donnee est plus grande que la taille de page divisee par le nombre minimal de cles, elle est stockee sur des pages de debordement plutot que sur la page elle-meme. Si minkeypage est nulle (aucun nombre minimal de cles indique), une valeur de 2 est utilisee. psize Taille (en octets) des pages utilisees pour les noeuds de l'arbre. La taille minimale est de 512 octets, et la taille maximale de 64 kio. Si psize vaut 0, (aucune taille indiquee), la taille de la page est choisie en fonction de la taille des blocs d'entree-sortie du systeme de fichiers sous-jacent. compare Fonction de comparaison de cle. Elle doit renvoyer un entier inferieur, egal ou superieur a zero lorsque le premier argument est respectivement inferieur, egal ou superieur au second. La meme fonction de comparaison doit toujours etre utilisee pour un arbre donne pendant son ouverture. Si compare vaut NULL (aucune fonction indiquee), les cles sont comparees de maniere lexicographique ; les cles les plus courtes sont considerees comme inferieures aux cles les plus longues. prefix Fonction de comparaison avec prefixe. Si elle est specifiee, cette routine doit renvoyer le nombre d'octets du second argument (une cle) qui sont necessaires pour determiner s'il est superieur au premier argument (une cle). Si les cles sont egales, la longueur de la cle devrait etre renvoyee. Remarquez que l'utilite de cette routine depend dans une tres large mesure du type de donnees manipulees, mais il arrive que cette routine fournisse des reductions significatives de taille d'arbre et de temps de recherche. Si prefix vaut NULL (aucune fonction indiquee), et si aucune fonction de comparaison n'est mentionnee, une routine de comparaison lexicographique est employee. Si prefix est NULL et si une routine de comparaison est specifiee, aucune comparaison de prefixe n'est effectuee. lorder L'ordre des octets des entiers stockes dans la base de donnees. Ce nombre doit representer l'ordre sous forme d'entier. Par exemple, l'ordre poids faible poids fort (gros boutiste) est represente par le nombre 4321. Si lorder vaut 0 (aucun ordre indique), on utilise l'ordre des octets du systeme hote. Si le fichier existe deja (et si le drapeau O_TRUNC n'est pas specifie), les valeurs indiquees par les parametres flags, lorder, et psize sont ignorees, et remplacees par les valeurs utilisees lors de la creation de l'arbre. Le balayage sequentiel de l'arbre vers l'avant se deroule de la plus petite cle vers la plus grande. L'espace libere par la destruction des paires << cles-donnees >> n'est jamais recupere, bien qu'il soit theoriquement disponible pour etre reutilise. Cela signifie qu'une base de donnees en arbre binaire ne fait que grandir. Il faut donc eviter les suppressions exagerees, ou reconstruire regulierement un nouvel arbre depuis un balayage de l'ancien. Les recherches, les insertions et les suppressions dans un arbre binaire s'effectuent en O log base N, ou base represente le facteur de remplissage moyen. Souvent, l'insertion de donnees deja ordonnees dans un arbre binaire resulte en un facteur d'insertion faible. Cette implementation a ete modifiee pour rendre l'insertion d'elements ordonnes encore plus profitable. Cela donne un facteur de remplissage de pages encore meilleur. ERREURS Les routines d'acces btree peuvent echouer et definir errno avec le code de toutes les erreurs indiquees pour les routines de la bibliotheque dbopen(3). BOGUES Seuls les ordres d'octets gros boutiste (big-endian) et petit boutiste (little-endian) fonctionnent. VOIR AUSSI dbopen(3), hash(3), mpool(3), recno(3) The Ubiquitous B-tree, Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138. Prefix B-trees, Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1 (March 1977), 11-26. The Art of Computer Programming Vol. 3: Sorting and Searching, D.E. Knuth, 1968, pp 471-480. TRADUCTION La traduction francaise de cette page de manuel a ete creee par Christophe Blaess , Stephan Rafin , Thierry Vignaud , Francois Micaux, Alain Portal , Jean-Philippe Guerard , Jean-Luc Coulon (f5ibh) , Julien Cristau , Thomas Huriaux , Nicolas Francois , Florentin Duneau , Simon Paillard , Denis Barbier et David Prevot Cette traduction est une documentation libre ; veuillez vous reporter a la GNU General Public License version 3 concernant les conditions de copie et de distribution. Il n'y a aucune RESPONSABILITE LEGALE. Si vous decouvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un message a . Pages du manuel de Linux 6.06 31 octobre 2023 btree(3)