Provided by: manpages-fr-dev_3.65d1p1-1_all 
NOM
btree - Méthodes d'accès à une base de données en arbre binaire
SYNOPSIS
#include <sys/types.h>
#include <db.h>
DESCRIPTION
NOTE: cette page décrit des interfaces fournies par la glibc jusque dans sa version 2.1.
Depuis la version 2.2, la glibc ne fournit plus ces interfaces. Veuillez consulter les API
fournies par la bibliothèque libdb.
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 {
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 éléments de cette structure sont les suivants :
flags La valeur de ce champ est calculée avec un OU binaire sur certaines des constantes
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 maximal de clés qui seront stockées sur une seule page. Pas encore
implémenté.
minkeypage
Le nombre minimal 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 minimal 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
minimal de clés indiqué), une valeur de 2 est utilisé.
psize Taille (en octets) des pages utilisées pour les nœuds 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é. Cela 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. Cela 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 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.65 du projet man-pages Linux. Une description
du projet et des instructions pour signaler des anomalies peuvent être trouvées à
l'adresse http://www.kernel.org/doc/man-pages/.
TRADUCTION
Depuis 2010, cette traduction est maintenue à l'aide de l'outil po4a
<http://po4a.alioth.debian.org/> par l'équipe de traduction francophone au sein du projet
perkamon <http://perkamon.alioth.debian.org/>.
Christophe Blaess <http://www.blaess.fr/christophe/> (1996-2003), Alain Portal
<http://manpagesfr.free.fr/> (2003-2006). Florentin Duneau et l'équipe francophone de
traduction de Debian (2006-2009).
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> ».
23 avril 2012 BTREE(3)