BTREE(3) Manuel du programmeur Linux BTREE(3)
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 com
portement par défaut, comme décrit dans
dbopen(3), est d'écraser la clé existante ou
d'échouer si la valeur d'attribut R_NOOVER
WRITE est indiquée. L'attribut R_NOOVER
WRITE 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
Linux 06 Mai 1999 1
BTREE(3) Manuel du programmeur Linux BTREE(3)
utilise la routine get. Toutefois la rou
tine 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 indica
tive, 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 possi
ble, 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 proba
bilité (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
Linux 06 Mai 1999 2
BTREE(3) Manuel du programmeur Linux BTREE(3)
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éces
saires pour déterminer s'il est supérieur au pre
mier 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 lexi
cographique 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.
Linux 06 Mai 1999 3
BTREE(3) Manuel du programmeur Linux BTREE(3)
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.
BUGS
Seuls les ordres d'octets big-endian et little-endian
fonctionnent.
TRADUCTION
Christophe Blaess, 1999
Linux 06 Mai 1999 4