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:

fanioane

Valoarea fanionului este specificată prin combinarea prin OR a oricăreia dintre următoarele valori:

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.