| btree(3) | Library Functions Manual | btree(3) |
btree - Méthodes d'accès à une base de données en arbre binaire
Bibliothèque C standard (libc, -lc)
#include <sys/types.h> #include <db.h>
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 :
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.
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).
Seuls les ordres d'octets gros boutiste (big-endian) et petit boutiste (little-endian) fonctionnent.
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.
La traduction française de cette page de manuel a été créée par Christophe Blaess <https://www.blaess.fr/christophe/>, Stéphan Rafin <stephan.rafin@laposte.net>, Thierry Vignaud <tvignaud@mandriva.com>, François Micaux, Alain Portal <aportal@univ-montp2.fr>, Jean-Philippe Guérard <fevrier@tigreraye.org>, Jean-Luc Coulon (f5ibh) <jean-luc.coulon@wanadoo.fr>, Julien Cristau <jcristau@debian.org>, Thomas Huriaux <thomas.huriaux@gmail.com>, Nicolas François <nicolas.francois@centraliens.net>, Florentin Duneau <fduneau@gmail.com>, Simon Paillard <simon.paillard@resel.enst-bretagne.fr>, Denis Barbier <barbier@debian.org> et David Prévot <david@tilapin.org>
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 à debian-l10n-french@lists.debian.org.
| 4 décembre 2022 | Pages du manuel de Linux 6.03 |