Provided by: manpages-fr-dev_2.64.1-1_all bug

NOM

       btree - Méthodes d’accès à une base de données en arbre binaire

SYNOPSIS

       #include <sys/types.h>
       #include <db.h>

DESCRIPTION

       La  routine dbopen(3) est l’interface de bibliothèque pour les fichiers
       de base de données. L’un des formats de fichier supportés  est  l’arbre
       binaire de fichiers. La description générale des méthodes d’accès à une
       base de données est fournie  dans  la  page  de  manuel  dbopen(3).  La
       présente  page  ne  décrit  que les informations spécifiques aux arbres
       binaires.

       Une telle structure de données est un arbre équilibré, trié, mémorisant
       les paires « clés-données » associées.

       La  structure  de  données  spécifique  aux méthodes d’accès aux arbres
       binaires que l’on fournit à  dbopen(3)  est  définie  dans  le  fichier
       d’en-tête <db.h> comme suit :
            typedef struct {
                u_long   flags;
                u_int    cachesize;
                int      maxkeypage;
                int      minkeypage;
                u_int    psize;
                int    (*compare)(const DBT *key1, const DBT *key2);
                size_t (*prefix)(const DBT *key1, const DBT *key2);
            int lorder;
            } BTREEINFO;

       Les éléments de cette structures sont les suivants :

       flags  Cette  valeur  est  définie avec un OU binaire entre les valeurs
              suivantes :

              R_DUP  Autoriser les clés dupliquées dans l’arbre, c’est-à-dire,
                     permettre  l’insertion  même  si  la clé existe déjà dans
                     l’arbre. Le comportement par défaut,  comme  décrit  dans
                     dbopen(3),  est  d’écraser une clé correspondante lors de
                     l’insertion  d’une  nouvelle  clé,  ou  d’échouer  si  le
                     drapeau    R_NOOVERWRITE    est   indiqué.   Le   drapeau
                     R_NOOVERWRITE a priorité sur  le  drapeau  R_DUP,  et  si
                     R_NOOVERWRITE  est  spécifié,  une  tentative d’insertion
                     d’une clé déjà existante échouera.

                     Si la base  de  données  contient  des  clés  dupliquées,
                     l’ordre  de  récupération  des  paires « clé-valeur » est
                     indéfini si l’on utilise la  routine  get.  Toutefois  la
                     routine  seq  avec le drapeau R_CURSOR positionné renvoie
                     la clé « logiquement première » de chaque groupe de  clés
                     dupliquées.

       cachesize
              Une  suggestion de taille maximale (en octets) du cache mémoire.
              Cette valeur est seulement indicative, et les  méthodes  d’accès
              alloueront  plus  de  mémoire plutôt que d’échouer. Comme chaque
              recherche examine la page racine de l’arbre, le cache des  pages
              les  plus  récemment  consultées  améliore les temps d’accès. De
              plus, les écritures physiques sont retardées aussi longtemps que
              possible,   ainsi   un   cache,   même   modeste,  peut  réduire
              sensiblement le nombre d’opérations d’entrée-sortie.  Bien  sûr,
              l’utilisation  d’un  cache  augmente  (et seulement augmente) la
              probabilité de corruption ou de perte de données si  le  système
              plante  alors  qu’un  arbre  est  en  cours  de modification. Si
              cachesize vaut 0 (pas de taille indiquée) un cache  est  utilisé
              par défaut.

       maxkeypage
              Le  nombre  maximum  de  clés  qui seront stockées sur une seule
              page. Pas encore implémenté.

       minkeypage
              Le nombre minimum de clés qui seront stockées sur la même  page.
              Cette  valeur  est  utilisée pour déterminer quelles clés seront
              stockées sur des pages de débordement. Par  exemple,  lorsqu’une
              clé  ou une donnée est plus grande que la taille de page divisée
              par le nombre minimum de clés, elle est stockée sur des pages de
              débordement  plutôt que sur la page elle-même. Si minkeypage est
              nulle (aucun nombre minimum de clés indiqué), une  valeur  de  2
              est utilisé.

       psize  Taille  (en  octets)  des  pages  utilisées  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 indiquée), la
              taille de la page est choisie en fonction de la taille des blocs
              d’entrée-sortie du système de fichiers sous-jacent.

       compare
              Fonction  de  comparaison  de  clé. Elle doit renvoyer un entier
              inférieur, égal ou supérieur à zéro lorsque le premier  argument
              est  respectivement  inférieur,  égal ou supérieur au second. La
              même fonction de comparaison doit toujours être utilisée pour un
              arbre  donné pendant son ouverture. Si compare vaut NULL (aucune
              fonction  indiquée),  les  clés  sont   comparées   de   manière
              lexicographique ;  les  clés  les  plus courtes sont considérées
              comme inférieures aux clés les plus longues.

       prefix Fonction de comparaison avec préfixe.  Si  elle  est  spécifiée,
              cette  routine  doit  renvoyer  le  nombre  d’octets  du  second
              argument (une clé) qui sont nécessaires pour déterminer s’il est
              supérieur  au  premier  argument  (une  clé).  Si  les clés sont
              égales, la longueur de la clé devrait être retournée.  Remarquez
              que l’utilité de cette routine dépend dans une très large mesure
              du type de données manipulées, mais il arrive que cette  routine
              fournisse  des réductions significatives de taille d’arbre et de
              temps  de  recherche.  Si  prefix  vaut  NULL  (aucune  fonction
              indiquée),   et   si   aucune   fonction  de  comparaison  n’est
              mentionnée,  une  routine  de  comparaison  lexicographique  est
              employée.  Si  prefix  est NULL et si une routine de comparaison
              est spécifiée, aucune comparaison de préfixe n’est effectuée.

       lorder L’ordre des octets des entiers stockés dans la base de  données.
              Ce  nombre  doit  représenter  l’ordre  sous forme d’entier. Par
              exemple, l’ordre poids faible poids  fort  (gros  boutiste)  est
              représenté  par  le  nombre  4321. Si lorder vaut 0 (aucun ordre
              indiqué), on utilise l’ordre des octets du système hôte.

       Si le  fichier  existe  déjà  (et  si  le  drapeau  O_TRUNC  n’est  pas
       spécifié),  les  valeurs indiquées par les paramètres flags, lorder, et
       psize sont ignorées, et remplacées par les valeurs utilisées lors de la
       création de l’arbre.

       Le  balayage  séquentiel  de l’arbre vers l’avant se déroule de la plus
       petite clé vers la plus grande.

       L’espace libéré par la destruction des  paires  « clés-données »  n’est
       jamais  récupéré,  bien  qu’il  soit théoriquement disponible pour être
       réutilisé. Ceci signifie qu’une base de données  en  arbre  binaire  ne
       fait  que  grandir.  Il faut donc éviter les suppressions exagérées, ou
       reconstruire régulièrement  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, où base représente le facteur  de
       remplissage  moyen. Souvent, l’insertion de données déjà ordonnées dans
       un arbre binaire  résulte  en  un  facteur  d’insertion  faible.  Cette
       implémentation  a  été  modifiée  pour  rendre  l’insertion  d’éléments
       ordonnés encore plus profitable. Ceci donne un facteur  de  remplissage
       de pages encore meilleur.

ERREURS

       Les  routines  d’accès  btree  peuvent échouer et définir errno avec le
       code  de  toutes  les  erreurs  indiquées  pour  les  routines  de   la
       bibliothèque dbopen(3).

BOGUES

       Seuls les ordres d’octets petit et gros boutiste sont gérés.

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

       Cette page de manuel a été traduite  et  mise  à  jour  par  Christophe
       Blaess  <http://www.blaess.fr/christophe/> entre 1996 et 2003, puis par
       Alain Portal <aportal AT univ-montp2 DOT fr> jusqu’en 2006, et  mise  à
       disposition sur http://manpagesfr.free.fr/.

       Les mises à jour et corrections de la version présente dans Debian sont
       directement gérées par Florentin Duneau <fduneau@gmail.com> et l’équipe
       francophone de traduction de Debian.

       Veuillez   signaler   toute   erreur   de   traduction  en  écrivant  à
       <debian-l10n-french@lists.debian.org> ou par un rapport de bogue sur le
       paquet manpages-fr.

       Vous  pouvez  toujours avoir accès à la version anglaise de ce document
       en utilisant la commande « man -L C <section> <page_de_man> ».

                                 18 août 1994                         BTREE(3)