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> ».