BTREE
Section : Manuel du programmeur Linux (
3)
Mise à jour de la version anglaise : 18 août 1994
Index
Menu principal
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(3)
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 que l'on transmet à
dbopen(3)
est définie dans le fichier d'entê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 par 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 l'attribut
R_NOOVERWRITE
est indiqué.
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'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é),
on utilise la valeur 2.
- 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 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é, même lors de la réouverture ultérieure
de la base de données.
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 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 (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 mais si une routine de comparaison est fournie, 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 (aucun ordre indiqué),
on utilise l'ordre des octets du système hôte.
Si le fichier existe déjà (et si l'attribut
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 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 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).
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.
TRADUCTION
Ce document est une traduction réalisée par Christophe Blaess
<http://www.blaess.fr/christophe/> le 6 mai 1999
et révisée le 17 juillet 2008.
L'équipe de traduction a fait le maximum pour réaliser une adaptation
française de qualité. La version anglaise la plus à jour de ce document est
toujours consultable via la commande : « LANG=C man 3 btree ».
N'hésitez pas à signaler à l'auteur ou au traducteur, selon le cas, toute
erreur dans cette page de manuel.
Index
- NOM
-
- SYNOPSIS
-
- DESCRIPTION
-
- ERREURS
-
- BOGUES
-
- VOIR AUSSI
-
- TRADUCTION
-
Dernière mise à jour : 17 juillet 2008