Provided by: manpages-fr-dev_3.27fr1.4-1_all bug

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)