btree - metoda de acces la baza de date btree
Biblioteca C standard (libc, -lc)
#include <sys/types.h> #include <db.h>
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).
Se acceptă numai ordinea big și little endian a
octeților.
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.
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.