Provided by: manpages-fr_1.67.0-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 est l’interface de bibliothèque pour les fichiers de
       base de données.  L’un des formats de fichier supportés est le type des
       arbres  binaires.   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  page
       présente   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, et que l’on transmet à dbopen est  définie  dans  le  fichier
       d’en-tête <db.h> ainsi :

       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  Cet  attribut  est  rempli  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 la clé existante ou d’échouer si
                     la  valeur   d’attribut   R_NOOVERWRITE   est   indiquée.
                     L’attribut  R_NOOVERWRITE  a  priorité  sur R_DUP, et une
                     tentative d’insertion  de  clé  déjà  existante  échouera
                     s’ils sont tous les deux mentionnés.

                     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 l’attribut 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   améliorer
              sensiblement    les   opérations   d’entrée/sortie.   Bien   sûr
              l’utilisation d’un cache augmente la probabilité  (jamais  nulle
              toutefois) de corruption ou de perte de données si le système se
              plante alors qu’un arbre  est  en  cours  de  modification.   Si
              cachesize  vaut  0  (pas de taille indiquée) on utilise un cache
              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 sert à déterminer quelles clés seront stockées  sur
              des  pages de débordement.  Lorsqu’un 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 (pas  de  nombre
              minimum de clés indiqué), on utilise la valeur 2.

       psize  Taille  (en  octets)  des  pages  utilisées  pour  les noeuds de
              l’arbre. La  taille  minimale  est  512  octets,  et  la  taille
              maximale  64  K.   Si psize vaut 0, (pas de taille indiquée), la
              taille de 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é pour  un
              arbre  donné,  même lors de la réouverture ultérieure de la base
              de données.  Si compare vaut NULL (pas  de  fonction  indiquée),
              les clés sont comparées de manière lexicographique, les clés les
              plus courtes considérées comme inférieures  aux  clés  les  plus
              longues.

       prefix Fonction  de  comparaison  avec  préfixe.   Si elle est fournie,
              cette  routine  doit  renvoyer  le  nombre  d’octets  du  second
              argument  clé  qui  sont  nécessaires  pour  déterminer s’il est
              supérieur au premier argument. Si les clés sont égales, on  doit
              renvoyer  la  longueur  de la clé. Remarquez que l’utilité d’une
              telle 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 (pas de 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
              mais si un routine de comparaison est founie, aucune comparaison
              de préfixe n’est effectuée.

       lorder L’ordre  des  octets  pour  les  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 (big
              endian) est représenté par le nombre 4321.   Si  lorder  vaut  0
              (pas  d’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 fournies 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 destructions exagérées, ou
       reconstruire régulièrement un nouvel arbre en balayant systématiquement
       l’ancien.

       Les  recherches,  les  insertions  et  les  suppressions  dans un arbre
       binaire s’effectuent en O lg 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  aux arbres binaires peuvent échouer et renvoyer
       dans errno le code de toutes les erreurs indiquées pour les routines de
       la bibliothèque dbopen(3).

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.

BOGUES

       Seuls les ordres d’octets big-endian et little-endian fonctionnent.

TRADUCTION

       Christophe Blaess, 1999-2003.