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(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