NOM
btree - Méthodes d’accès à une base de données en arbre binaire
SYNOPSIS
#include <sys/types.h>
#include <db.h>
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 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 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.23 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
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