Provided by: manpages-pl-dev_20060617-3_all bug

NAZWA

       btree - metoda dostpu do bazy btree

SK/LADNIA

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

OPIS

       Funkcja  dbopen  stanowi  interfejs  biblioteczny do plikow baz danych.
       Jednym z obslugiwanych formatow s pliki btree. Ogolny opis metod dostpu
       do  baz  danych znajduje si w dbopen(3), a ta strona podrcznika opisuje
       jedynie informacje specyficzne dla btree.

       Struktura  danych  btree  stanowi  uporzdkowan,   zrownowaon   struktur
       drzewiast, przechowujc powizane pary klucz/dane.

       Specyficzna  dla  metody  dostpu  btree  struktura  danych uywana przez
       dbopen jest zdefiniowana w pliku naglowkowym <db.h> nastpujco:

       typedef struct {
              u_long flags;
              u_int cachesize;
              int maxkeypage;
              int minkeypage;
              u_int psize;
              int (*compare)(const DBT *key1, const DBT *key2);
              size_t (*prefix)(const DBT *key1, const DBT *key2);
              int lorder;
       } BTREEINFO;

       Struktura ta zawiera nastpujce elementy:

       flags  Wart znacznika jest  okrelona  lubokrela  dowoln  z  nastpujcych
              wartoci:

              R_DUP  Zezwala  na powtarzajce si w drzewie klucze, tzn. pozwala
                     dodawa klucze, ktore  ju  w  drzewie  istniej.   Domylnym
                     zachowaniem,  jak  opisano w dbopen(3), jest nadpisywanie
                     istniejcego pasujcego klucza podczas wprowadzania  nowego
                     klucza,   lub  niepomylne  zakoczenie,  gdy  podany  jest
                     znacznik R_NOOVERWRITE.  Znacznik R_DUP jest  nadpisywany
                     przez  znacznik R_NOOVERWRITE; gdy znacznik R_NOOVERWRITE
                     jest podany, proba dodania do  drzewa  klucza,  ktory  ju
                     istnieje, zakoczy si niepowodzeniem.

                     Jeli  baza  danych zawiera powtarzajce si klucze, kolejno
                     pobierania  kluczy/danych  za  pomoc  funkcji  get   jest
                     niezdefiniowana,   jednake,   wywolania   funkcji  seq  z
                     ustawionym znacznikiem R_CURSOR  zawsze  zwroc  logicznie
                     ``pierwszy'' z dowolnej drupy powtarzajcych si kluczy.

       cachesize
              Sugerowany  maksymalny  rozmiar  (w  bajtach)  bufora  w pamici.
              Warto ta stanowi jedynie zalecenie,  wic  metoda  dostpu  raczej
              przydzieli  wicej  pamici ni zawiedzie.  Ze wzgldu na to, e kade
              poszukiwanie bada stron korzenia drzewa,  buforowanie  najczciej
              uywanych stron istotnie skroci czas dostpu.  Dodatkowo, fizyczne
              zapisy bd  oponione  na  tyle,  na  ile  bdzie  to  moliwe,  wic
              umiarkowany   bufor   moe   istotnie  zmniejszy  liczb  operacji
              wejcia/wyjcia. Oczywicie,  korzystanie  z  bufora  zwiksza  (ale
              jedynie   zwiksza)   prawdopodobiestwo  uszkodzenia  lub  utraty
              danych, jeli system  ulegnie  awarii  podczas  gdy  drzewo  jest
              modyfikowane.   Jeli  cachesize  wynosi  0 (nie podano rozmiaru)
              uywany jest bufor domylny.

       maxkeypage
              Maksymalna  liczba  kluczy,  ktore  bd  przechowywane  w  ramach
              pojedynczej strony. Aktualnie nie zaimplementowane.

       minkeypage
              minimalna  liczba  kluczy  przechowywanych  w ramach pojedynczej
              strony.   Warto  ta  sluy  do   okrelania,   ktore   klucze   bd
              przechowywane  w  stronach  nadmiarowych,  tzn.  jeli  klucz lub
              element danych jest wikszy ni rozmiar  strony  podzielony  przez
              warto  minkeypage, bdzie on przechowywany w stronie nadmiarowej,
              zamiast w stronie  wlaciwej.   Jeli  minkeypage  wynosi  0  (nie
              podano minimalnej liczby kluczy), uyta zostanie warto 2.

       psize  Rozmiar  strony  jest rozmiarem (w bajtach) stron uywanych przez
              wzly drzewa.  Minimalny rozmiar  strony  wynosi  512  bajtow,  a
              maksymalnym rozmiarem jest 64K.  Jeli psize wynosi 0 (mie podano
              rozmiaru strony), rozmiar strony  jest  wybierany  w  oparciu  o
              rozmiar bloku uywanego systemu plikow.

       compare
              Compare  jest funkcj porownywania kluczy.  Musi ona zwraca liczb
              calkowit mniejsz,  rown  lub  wiksz  od  zera,  gdy  klucz  bdcy
              pierwszym  argumentem jest, odpowiednio, mniejszy, rowny, wikszy
              ni klucz bdcy drugim argumentem.  Dla danego drzewa  przy  kadym
              jego  otwarciu  musi by uywana ta sama funcja porownawcza.  Jeli
              compare ma warto NULL (nie podano funkcji porownawczej),  klucze
              bd  porownywane  leksykalnie, przy czym krotsze klucze bd uwaane
              za mniejsze ni klucze dlusze.

       prefix Prefix jest funkcj  porownywania  przedrostkow.   Jeli  zostanie
              podana,  musi  ona  zwraca  liczb bajtow argumentu bdcego drugim
              kluczem, ktore s niezbdne dla okrelenia czy jest  on  wikszy  ni
              klucz  bdcy  pierwszym argumentem.  Gdy klucze bd rowne, powinna
              zosta zwrocona dlugo  klucza.   Uwaga,  przydatnoc  tej  funkcji
              silnie  zaley  od  danych, jednak dla pewnych zbiorow danych jej
              uywanie moe prowadzi do istotnie zmniejszonych rozmiarow  drzewa
              i krotszych czasow poszukiwania.  Jeli prefix ma warto NULL (nie
              podano funkcji prefix), i nie podano funkcji porownawczej,  uyta
              zostanie domylna funkcja porownywania leksykalnego.  Jeli prefix
              ma warto NULL, i podano funkcj porownawcz, nie bdzie  wykonywane
              porownywanie przedrostkow.

       lorder Kolejno   bajtow   dla   liczb   calkowitych  w  przechowywanych
              metadanych bazy.  Liczba powinna reprezentowa kolejno jao liczba
              calkowita;  na  przyklad,  porzdek  grubokocy bylby liczb 4,321.
              Jeli lorder  wynosi  0  (nie  podano  kolejnoci)  uyta  zostanie
              aktualna, systemowa kolejno.

       Jeli  plik  ju istnieje (i nie podanoznacznika O_TRUNC), wartoci podane
       dla parametrow flags, lorder  i  psize  zostan  zignorowane,  na  rzecz
       wartoci uywanych w czasie tworzenia drzewa.

       Liniowe  przegldanie  drzewa  "do  przodu"  odbywa  si od najmniejszego
       klucza do najwikszego.

       Przestrze zwolniona przez usunicie par klucz/dane  z  drzewa  nie  jest
       nigdy  odzyskiwana,  jednake,  jest ona normalnie dostpna dla ponownego
       uycia. Oznacza to, e struktura przechowujca drzewo  btree  moe  jedynie
       rosn.  Jedynym  rozwizaniem  jest  unikanie  nadmiernego  usuwania  lub
       okresowe tworzenie wieego drzewa na podstawie  przegldania  istniejcego
       drzewa.

       Przeszukiwania,  wstawiania i usunicia w btree odbywaj si w czasie O lg
       base N,  gdzie  base  jest  czynnikiem  redniego  wypelnienia.   Czsto,
       wprowadzanie  do drzew btree danych uporzdkowanych prowadzi do niskiego
       czynnika wypelnienia.   Ta  implementacja  zostala  zmodyfikowana,  aby
       uczyni   uporzdkowane   wprowadzanie   najkorzystniejszym  przypadkiem,
       uzyskujc w wyniku tego duo  lepszy  ni  normalnie  czynnik  wypelnienia
       stron.

B/LDY

       Funkcje  metod  dostpu  btree  mog zawie i ustawi errno dla dowolnego z
       bldow podanych w funkcji bibliotecznej dbopen(3).

ZOBACZ TAKE

       dbopen(3), hash(3), mpool(3), recno(3)

       The Ubiquitous B-tree, Douglas Comer, ACM Comput. Surv. 11, 2 (czerwiec
       1979), 121-138.

       Prefix  B-trees,  Bayer  and  Unterauer,  ACM  Transactions on Database
       Systems, t. 2, 1 (marzec 1977), 11-26.

       The Art of Computer Programming Vol. 3:  Sorting  and  Searching,  D.E.
       Knuth, 1968, str. 471-480.

USTERKI

       Obsluguje jedynie ostrokocy i grubokocy porzdek bajtow.

INFORMACJE O T/LUMACZENIU

       Powysze  tlumaczenie  pochodzi z nieistniejcego ju Projektu Tlumaczenia
       Manuali i moe nie by aktualne. W razie zauwaenia ronic  midzy  powyszym
       opisem  a  rzeczywistym  zachowaniem  opisywanego programu lub funkcji,
       prosimy o zapoznanie si z oryginaln (angielsk) wersj strony podrcznika.

                                  1994-08-18                          BTREE(3)