Provided by:
manpages-fr-dev_3.27fr1.4-1_all 
NOM
btree - Methodes d'acces a une base de donnees en arbre binaire
SYNOPSIS
#include <sys/types.h>
#include <db.h>
DESCRIPTION
La routine dbopen(3) est l'interface de bibliotheque pour les fichiers
de base de donnees. L'un des formats de fichier supportes 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 <db.h> 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 utilise.
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 ko. 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 retournee. 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. Ceci 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. Ceci 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.
COLOPHON
Cette page fait partie de la publication 3.27 du projet man-pages
Linux. Une description du projet et des instructions pour signaler des
anomalies peuvent etre trouvees a l'adresse
<URL:http://www.kernel.org/doc/man-pages/>.
TRADUCTION
Depuis 2010, cette traduction est maintenue a l'aide de l'outil po4a
<URL:http://po4a.alioth.debian.org/> par l'equipe de traduction
francophone au sein du projet perkamon
<URL:http://perkamon.alioth.debian.org/>.
Christophe Blaess <URL:http://www.blaess.fr/christophe/> (1996-2003),
Alain Portal <URL:http://manpagesfr.free.fr/> (2003-2006). Florentin
Duneau et l'equipe francophone de traduction de Debian (2006-2009).
Veuillez signaler toute erreur de traduction en ecrivant a
<debian-l10n-french@lists.debian.org> ou par un rapport de bogue sur le
paquet manpages-fr.
Vous pouvez toujours avoir acces a la version anglaise de ce document
en utilisant la commande << man -L C <section> <page_de_man> >>.
18 aout 1994 BTREE(3)