Provided by:
manpages-fr_1.67.0-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
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.