btree

NOM

btree - Méthodes d'accès à une base de données en arbre binaire

BIBLIOTHÈQUE

Bibliothèque C standard ( libc, -lc)

SYNOPSIS

#include <sys/types.h> #include <db.h>

DESCRIPTION

NOTE : cette page décrit des interfaces fournies jusqu'à la glibc 2.1. Depuis la glibc 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 pris en charge 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 :

drapeaux

La valeur de ce champ est calculée avec un OU binaire sur certaines des constantes suivantes :

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ée.

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 kio. 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 renvoyé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.

TRADUCTION

La traduction française de cette page de manuel a été créée par Christophe Blaess <https://www.blaess.fr/christophe/>, Stéphan Rafin <[email protected]>, Thierry Vignaud <[email protected]>, François Micaux, Alain Portal <[email protected]>, Jean-Philippe Guérard <[email protected]>, Jean-Luc Coulon (f5ibh) <[email protected]>, Julien Cristau <[email protected]>, Thomas Huriaux <[email protected]>, Nicolas François <[email protected]>, Florentin Duneau <[email protected]>, Simon Paillard <[email protected]>, Denis Barbier <[email protected]> et David Prévot <[email protected]> Cette traduction est une documentation libre ; veuillez vous reporter à la GNU General Public License version 3 concernant les conditions de copie et de distribution. Il n'y a aucune RESPONSABILITÉ LÉGALE. Si vous découvrez un bogue dans la traduction de cette page de manuel, veuillez envoyer un message à [email protected]