Provided by: manpages-ro-dev_4.27.0-1_all 
NUME
btree - metoda de acces la baza de date btree
BIBLIOTECA
Biblioteca C standard (libc, -lc)
SINOPSIS
#include <sys/types.h> #include <db.h>
DESCRIERE
Notează bine: Această pagină documentează interfețele furnizate până la glibc 2.1. Începând cu glibc 2.2,
glibc nu mai furnizează aceste interfețe. Probabil că, în schimb, căutați API-urile furnizate de
biblioteca libdbb.
Rutina dbopen(3) este interfața bibliotecii cu fișierele de baze de date. Unul dintre formatele de
fișiere acceptate este cel al fișierelor btree. Descrierea generală a metodelor de acces la baza de date
se găsește în dbopen(3), iar această pagină de manual descrie doar informațiile specifice btree.
Structura de date btree este o structură arborescentă sortată, echilibrată, care stochează perechi
cheie/date asociate.
Structura de date specifică metodei de acces btree furnizată lui dbopen(3) este definită în fișierul de
includere <db.h> după cum urmează:
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;
Elementele acestei structuri sunt următoarele:
flags Valoarea fanionului este specificată prin combinarea prin OR a oricăreia dintre următoarele
valori:
R_DUP Permite cheile duplicate în arbore, adică permite inserarea în cazul în care cheia care
urmează să fie inserată există deja în arbore. Comportamentul implicit, așa cum este
descris în dbopen(3), este de a suprascrie o cheie corespunzătoare atunci când se inserează
o nouă cheie sau de a eșua dacă se specifică fanionul R_NOOVERWRITE. Fanionul R_DUP este
anulat de fanionul R_NOOVERWRITE, iar în cazul în care este specificat fanionul
R_NOOVERWRITE, încercările de a introduce chei duplicate în arbore vor eșua.
În cazul în care baza de date conține chei duplicate, ordinea de recuperare a perechilor
cheie/date este nedefinită dacă se utilizează rutina get; cu toate acestea, apelurile de
rutină seq cu fanionul R_CURSOR activat vor returna întotdeauna „prima” logică din orice
grup de chei duplicate.
cachesize
O dimensiune maximă sugerată (în octeți) a memoriei cache. Această valoare este doar consultativă,
iar metoda de acces va aloca mai multă memorie în loc să eșueze. Deoarece fiecare căutare
examinează pagina rădăcină a arborelui, punerea în cache a celor mai recent utilizate pagini
îmbunătățește substanțial timpul de acces. În plus, scrierile fizice sunt întârziate cât mai mult
posibil, astfel încât o memorie cache moderată poate reduce semnificativ numărul de operații de
In/Ieș. Evident, utilizarea unei memorii cache crește (dar numai crește) probabilitatea de
corupție sau de pierdere a datelor în cazul în care sistemul se blochează în timp ce un arbore
este modificat. Dacă cachesize este 0 (nu este specificată nicio dimensiune), se utilizează o
memorie cache implicită.
maxkeypage
Numărul maxim de chei care vor fi stocate pe o singură pagină. Nu este implementat în prezent.
minkeypage
Numărul minim de chei care vor fi stocate pe o singură pagină. Această valoare este utilizată
pentru a determina ce chei vor fi stocate pe paginile de depășire, adică, dacă o cheie sau un
element de date este mai lung decât dimensiunea paginii împărțită la valoarea „minkeypage”, acesta
va fi stocat pe paginile de depășire în loc să fie stocat în pagina propriu-zisă. Dacă minkeypage
este 0 (nu este specificat un număr minim de chei), se utilizează o valoare de 2.
psize Dimensiunea paginii este dimensiunea (în octeți) a paginilor utilizate pentru nodurile din arbore.
Dimensiunea minimă a paginii este de 512 octeți, iar dimensiunea maximă a paginii este de 64Kio.
Dacă psize este 0 (nu se specifică dimensiunea paginii), dimensiunea paginii este aleasă pe baza
dimensiunii blocului de intrare/ieșire a sistemului de fișiere subiacent.
compare
compare este funcția cheie de comparare. Aceasta trebuie să returneze un număr întreg mai mic,
egal sau mai mare decât zero dacă primul argument cheie este considerat a fi mai mic, egal sau mai
mare decât al doilea argument cheie. Aceeași funcție de comparare trebuie să fie utilizată pentru
un anumit arbore de fiecare dată când acesta este deschis. În cazul în care compare este NULL (nu
este specificată nicio funcție de comparație), cheile sunt comparate lexical, cheile mai scurte
fiind considerate mai mici decât cele mai lungi.
prefix prefix este funcția de comparare a prefixelor. Dacă este specificată, această rutină trebuie să
returneze numărul de octeți ai celui de-al doilea argument cheie care sunt necesari pentru a
determina că acesta este mai mare decât primul argument cheie. În cazul în care cheile sunt egale,
trebuie returnată lungimea cheii. Rețineți că utilitatea acestei rutine depinde în mare măsură de
date, dar, în unele seturi de date, poate produce o reducere semnificativă a dimensiunii arborelui
și a timpului de căutare. Dacă prefix este NULL (nu este specificată nicio funcție de prefix), și
nu este specificată nicio funcție de comparație, se utilizează o rutină de comparație lexicală
implicită. Dacă prefix este NULL și este specificată o rutină de comparare, nu se face nicio
comparație de prefix.
lorder Ordinea octeților pentru numerele întregi din metadatele stocate în baza de date. Numărul ar
trebui să reprezinte ordinea ca număr întreg; de exemplu, ordinea big endian ar fi numărul 4,321.
Dacă lorder este 0 (nu se specifică nicio ordine), se utilizează ordinea curentă a gazdei.
În cazul în care fișierul există deja (și nu este specificat fanionul O_TRUNC), valorile specificate
pentru argumentele flags, lorder și psize sunt ignorate în favoarea valorilor utilizate la crearea
arborelui.
Scanările secvențiale înainte ale unui arbore se fac de la cheia cea mai mică la cea mai mare.
Spațiul eliberat prin ștergerea perechilor cheie/date din arbore nu este niciodată recuperat, deși în mod
normal este disponibil pentru reutilizare. Aceasta înseamnă că structura de stocare btree este de tip
„grow-only” (doar-creștere). Singurele soluții sunt evitarea ștergerilor excesive sau crearea periodică a
unui nou arbore din scanarea unuia existent.
Căutările, inserările și ștergerile într-un arbore btree se vor finaliza în O lg bază N, unde baza este
factorul mediu de umplere. Adesea, inserarea de date ordonate în btrees are ca rezultat un factor de
umplere scăzut. Această implementare a fost modificată pentru a face ca inserarea ordonată să fie cel mai
bun caz, ceea ce duce la un factor de umplere a paginii mult mai bun decât cel normal.
ERORI-IEȘIRE
Rutinele metodei de acces btree pot eșua și pot configura errno pentru oricare dintre erorile specificate
pentru rutina de bibliotecă dbopen(3).
ERORI
Se acceptă numai ordinea big și little endian a octeților.
CONSULTAȚI ȘI
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.
TRADUCERE
Traducerea în limba română a acestui manual a fost făcută de Remus-Gabriel Chelu
<remusgabriel.chelu@disroot.org>
Această traducere este documentație gratuită; citiți Licența publică generală GNU Versiunea 3 sau o
versiune ulterioară cu privire la condiții privind drepturile de autor. NU se asumă NICIO
RESPONSABILITATE.
Dacă găsiți erori în traducerea acestui manual, vă rugăm să trimiteți un e-mail la translation-team-
ro@lists.sourceforge.net.
Pagini de manual de Linux 6.9.1 2 mai 2024 btree(3)