btree(3)                   Library Functions Manual                   btree(3)

NUME
       btree - metoda de acces la baza de date btree

BIBLIOTECA
       Biblioteca C standard (libc, -lc)

REZUMAT
       #include <sys/types.h> #include <db.h>

DESCRIERE
       Noteaza bine: Aceasta pagina documenteaza interfe<?>ele furnizate pana
       la glibc 2.1. Incepand cu glibc 2.2, glibc nu mai furnizeaza aceste
       interfe<?>e. Probabil ca, in schimb, cauta<?>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 generala a metodelor de acces la baza
       de date se gase<?>te in dbopen(3), iar aceasta pagina de manual descrie
       doar informa<?>iile specifice btree.

       Structura de date btree este o structura arborescenta sortata,
       echilibrata, care stocheaza perechi cheie/date asociate.

       Structura de date specifica metodei de acces btree furnizata lui
       dbopen(3) este definita in fi<?>ierul de includere <db.h> dupa cum
       urmeaza:

           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 urmatoarele:

       fanioane
              Valoarea fanionului este specificata prin combinarea prin OR a
              oricareia dintre urmatoarele valori:

              R_DUP  Permite cheile duplicate in arbore, adica permite
                     inserarea in cazul in care cheia care urmeaza sa fie
                     inserata exista deja in arbore. Comportamentul implicit,
                     a<?>a cum este descris in dbopen(3), este de a suprascrie
                     o cheie corespunzatoare atunci cand se insereaza o noua
                     cheie sau de a e<?>ua daca se specifica fanionul
                     R_NOOVERWRITE. Fanionul R_DUP este anulat de fanionul
                     R_NOOVERWRITE, iar in cazul in care este specificat
                     fanionul R_NOOVERWRITE, incercarile de a introduce chei
                     duplicate in arbore vor e<?>ua.

                     In cazul in care baza de date con<?>ine chei duplicate,
                     ordinea de recuperare a perechilor cheie/date este
                     nedefinita daca se utilizeaza rutina get; cu toate
                     acestea, apelurile de rutina seq cu fanionul R_CURSOR
                     activat vor returna intotdeauna ,,prima" logica din orice
                     grup de chei duplicate.

       cachesize
              O dimensiune maxima sugerata (in octe<?>i) a memoriei cache.
              Aceasta valoare este doar consultativa, iar metoda de acces va
              aloca mai multa memorie in loc sa e<?>ueze. Deoarece fiecare
              cautare examineaza pagina radacina a arborelui, punerea in cache
              a celor mai recent utilizate pagini imbunata<?>e<?>te
              substan<?>ial timpul de acces. In plus, scrierile fizice sunt
              intarziate cat mai mult posibil, astfel incat o memorie cache
              moderata poate reduce semnificativ numarul 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 in cazul in care sistemul se blocheaza in timp ce un
              arbore este modificat. Daca cachesize este 0 (nu este
              specificata nicio dimensiune), se utilizeaza o memorie cache
              implicita.

       maxkeypage
              Numarul maxim de chei care vor fi stocate pe o singura pagina.
              Nu este implementat in prezent.

       minkeypage
              Numarul minim de chei care vor fi stocate pe o singura pagina.
              Aceasta valoare este utilizata pentru a determina ce chei vor fi
              stocate pe paginile de depa<?>ire, adica, daca o cheie sau un
              element de date este mai lung decat dimensiunea paginii
              impar<?>ita la valoarea ,,minkeypage", acesta va fi stocat pe
              paginile de depa<?>ire in loc sa fie stocat in pagina
              propriu-zisa. Daca minkeypage este 0 (nu este specificat un
              numar minim de chei), se utilizeaza o valoare de 2.

       psize  Dimensiunea paginii este dimensiunea (in octe<?>i) a paginilor
              utilizate pentru nodurile din arbore. Dimensiunea minima a
              paginii este de 512 octe<?>i, iar dimensiunea maxima a paginii
              este de 64Kio. Daca psize este 0 (nu se specifica dimensiunea
              paginii), dimensiunea paginii este aleasa pe baza dimensiunii
              blocului de intrare/ie<?>ire a sistemului de fi<?>iere
              subiacent.

       compare
              compare este func<?>ia cheie de comparare. Aceasta trebuie sa
              returneze un numar intreg mai mic, egal sau mai mare decat zero
              daca primul argument cheie este considerat a fi mai mic, egal
              sau mai mare decat al doilea argument cheie. Aceea<?>i func<?>ie
              de comparare trebuie sa fie utilizata pentru un anumit arbore de
              fiecare data cand acesta este deschis. In cazul in care compare
              este NULL (nu este specificata nicio func<?>ie de compara<?>ie),
              cheile sunt comparate lexical, cheile mai scurte fiind
              considerate mai mici decat cele mai lungi.

       prefix prefix este func<?>ia de comparare a prefixelor. Daca este
              specificata, aceasta rutina trebuie sa returneze numarul de
              octe<?>i ai celui de-al doilea argument cheie care sunt necesari
              pentru a determina ca acesta este mai mare decat primul argument
              cheie. In cazul in care cheile sunt egale, trebuie returnata
              lungimea cheii. Re<?>ine<?>i ca utilitatea acestei rutine
              depinde in mare masura de date, dar, in unele seturi de date,
              poate produce o reducere semnificativa a dimensiunii arborelui
              <?>i a timpului de cautare. Daca prefix este NULL (nu este
              specificata nicio func<?>ie de prefix), <?>i nu este specificata
              nicio func<?>ie de compara<?>ie, se utilizeaza o rutina de
              compara<?>ie lexicala implicita. Daca prefix este NULL <?>i este
              specificata o rutina de comparare, nu se face nicio compara<?>ie
              de prefix.

       lorder Ordinea octe<?>ilor pentru numerele intregi din metadatele
              stocate in baza de date. Numarul ar trebui sa reprezinte ordinea
              ca numar intreg; de exemplu, ordinea big endian ar fi numarul
              4,321. Daca lorder este 0 (nu se specifica nicio ordine), se
              utilizeaza ordinea curenta a gazdei.

       In cazul in care fi<?>ierul exista deja (<?>i nu este specificat
       fanionul O_TRUNC), valorile specificate pentru argumentele flags,
       lorder <?>i psize sunt ignorate in favoarea valorilor utilizate la
       crearea arborelui.

       Scanarile secven<?>iale inainte ale unui arbore se fac de la cheia cea
       mai mica la cea mai mare.

       Spa<?>iul eliberat prin <?>tergerea perechilor cheie/date din arbore nu
       este niciodata recuperat, de<?>i in mod normal este disponibil pentru
       reutilizare. Aceasta inseamna ca structura de stocare btree este de tip
       ,,grow-only" (doar-cre<?>tere). Singurele solu<?>ii sunt evitarea
       <?>tergerilor excesive sau crearea periodica a unui nou arbore din
       scanarea unuia existent.

       Cautarile, inserarile <?>i <?>tergerile intr-un arbore btree se vor
       finaliza in O lg baza N, unde baza este factorul mediu de umplere.
       Adesea, inserarea de date ordonate in btrees are ca rezultat un factor
       de umplere scazut. Aceasta implementare a fost modificata pentru a face
       ca inserarea ordonata sa fie cel mai bun caz, ceea ce duce la un factor
       de umplere a paginii mult mai bun decat 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 biblioteca
       dbopen(3).

ERORI
       Se accepta 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 in limba romana a acestui manual a fost facuta de Remus-
       Gabriel Chelu <remusgabriel.chelu@disroot.org>

       Aceasta traducere este documenta<?>ie gratuita; citi<?>i Licen<?>a
       publica generala GNU Versiunea 3
       <https://www.gnu.org/licenses/gpl-3.0.html> sau o versiune ulterioara
       cu privire la condi<?>ii privind drepturile de autor.  NU se asuma
       NICIO RESPONSABILITATE.

       Daca gasi<?>i erori in traducerea acestui manual, va rugam sa
       trimite<?>i un e-mail la <translation-team-ro@lists.sourceforge.net>.

Pagini de manual de Linux 6.06 31 octombrie 2023                      btree(3)