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

NAZWA

       btree - metoda dostępu do bazy btree

SKŁADNIA

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

OPIS

       Funkcja  dbopen  stanowi  interfejs  biblioteczny do plików baz danych.
       Jednym z obsługiwanych formatów  są  pliki  btree.  Ogólny  opis  metod
       dostępu do baz danych znajduje się w dbopen(3), a ta strona podręcznika
       opisuje jedynie informacje specyficzne dla btree.

       Struktura danych btree stanowi  uporządkowaną,  zrównoważoną  strukturę
       drzewiastą, przechowującą powiązane pary klucz/dane.

       Specyficzna  dla  metody  dostępu  btree struktura danych używana przez
       dbopen jest zdefiniowana w pliku nagłówkowym <db.h> następująco:

       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 następujące elementy:

       flags  Wartść   znacznika   jest   określona   lubokreśla   dowolną   z
              następujących wartości:

              R_DUP  Zezwala  na  powtarzające  się  w  drzewie  klucze,  tzn.
                     pozwala dodawać klucze, które  już  w  drzewie  istnieją.
                     Domyślnym  zachowaniem,  jak  opisano  w  dbopen(3), jest
                     nadpisywanie  istniejącego  pasującego   klucza   podczas
                     wprowadzania  nowego klucza, lub niepomyślne zakończenie,
                     gdy podany jest znacznik R_NOOVERWRITE.   Znacznik  R_DUP
                     jest   nadpisywany   przez  znacznik  R_NOOVERWRITE;  gdy
                     znacznik R_NOOVERWRITE  jest  podany,  próba  dodania  do
                     drzewa   klucza,   który   już   istnieje,  zakończy  się
                     niepowodzeniem.

                     Jeśli  baza  danych  zawiera  powtarzające  się   klucze,
                     kolejność  pobierania kluczy/danych za pomocą funkcji get
                     jest niezdefiniowana, jednakże, wywołania funkcji  seq  z
                     ustawionym  znacznikiem  R_CURSOR zawsze zwrócą logicznie
                     ``pierwszy'' z dowolnej drupy powtarzających się  kluczy.

       cachesize
              Sugerowany  maksymalny  rozmiar  (w  bajtach)  bufora w pamięci.
              Wartość ta stanowi jedynie zalecenie, więc metoda dostępu raczej
              przydzieli  więcej  pamięci niż zawiedzie.  Ze względu na to, że
              każde poszukiwanie  bada  stronę  korzenia  drzewa,  buforowanie
              najczęściej   używanych  stron  istotnie  skróci  czas  dostępu.
              Dodatkowo, fizyczne zapisy będą opóźnione na tyle, na ile będzie
              to  możliwe,  więc  umiarkowany  bufor  może istotnie zmniejszyć
              liczbę  operacji  wejścia/wyjścia.  Oczywiście,  korzystanie   z
              bufora   zwiększa   (ale  jedynie  zwiększa)  prawdopodobieństwo
              uszkodzenia lub  utraty  danych,  jeśli  system  ulegnie  awarii
              podczas  gdy drzewo jest modyfikowane.  Jeśli cachesize wynosi 0
              (nie podano rozmiaru) używany jest bufor domyślny.

       maxkeypage
              Maksymalna liczba kluczy,  które  będą  przechowywane  w  ramach
              pojedynczej strony. Aktualnie nie zaimplementowane.

       minkeypage
              minimalna  liczba  kluczy  przechowywanych  w ramach pojedynczej
              strony.  Wartość ta  służy  do  określania,  które  klucze  będą
              przechowywane  w  stronach  nadmiarowych,  tzn.  jeśli klucz lub
              element danych jest większy niż rozmiar strony podzielony  przez
              wartość   minkeypage,   będzie   on   przechowywany   w  stronie
              nadmiarowej, zamiast  w  stronie  właściwej.   Jeśli  minkeypage
              wynosi  0  (nie podano minimalnej liczby kluczy), użyta zostanie
              wartość 2.

       psize  Rozmiar strony jest rozmiarem (w bajtach) stron używanych  przez
              węzły  drzewa.   Minimalny  rozmiar  strony wynosi 512 bajtów, a
              maksymalnym rozmiarem jest  64K.   Jeśli  psize  wynosi  0  (mie
              podano rozmiaru strony), rozmiar strony jest wybierany w oparciu
              o rozmiar bloku używanego systemu plików.

       compare
              Compare jest funkcją  porównywania  kluczy.   Musi  ona  zwracać
              liczbę  całkowitą mniejszą, równą lub większą od zera, gdy klucz
              będący pierwszym argumentem jest, odpowiednio, mniejszy,  równy,
              większy  niż  klucz będący drugim argumentem.  Dla danego drzewa
              przy każdym jego  otwarciu  musi  być  używana  ta  sama  funcja
              porównawcza.   Jeśli compare ma wartość NULL (nie podano funkcji
              porównawczej), klucze będą porównywane  leksykalnie,  przy  czym
              krótsze klucze będą uważane za mniejsze niż klucze dłuższe.

       prefix Prefix  jest  funkcją porównywania przedrostków.  Jeśli zostanie
              podana, musi ona zwracać liczbę bajtów argumentu będącego drugim
              kluczem,  które  są niezbędne dla określenia czy jest on większy
              niż klucz będący pierwszym argumentem.  Gdy klucze  będą  równe,
              powinna  zostać zwrócona długość klucza.  Uwaga, przydatnośc tej
              funkcji silnie zależy od  danych,  jednak  dla  pewnych  zbiorów
              danych  jej  używanie  może  prowadzić do istotnie zmniejszonych
              rozmiarów drzewa i krótszych czasów poszukiwania.  Jeśli  prefix
              ma  wartość  NULL  (nie  podano  funkcji  prefix),  i nie podano
              funkcji   porównawczej,   użyta   zostanie   domyślna    funkcja
              porównywania  leksykalnego.   Jeśli  prefix  ma  wartość NULL, i
              podano funkcję porównawczą, nie będzie  wykonywane  porównywanie
              przedrostków.

       lorder Kolejność   bajtów   dla  liczb  całkowitych  w  przechowywanych
              metadanych bazy.  Liczba  powinna  reprezentować  kolejność  jao
              liczba  całkowita; na przykład, porządek grubokońcy byłby liczbą
              4,321.  Jeśli lorder wynosi  0  (nie  podano  kolejności)  użyta
              zostanie aktualna, systemowa kolejność.

       Jeśli  plik  już  istnieje  (i  nie  podanoznacznika O_TRUNC), wartości
       podane dla parametrów flags, lorder i  psize  zostaną  zignorowane,  na
       rzecz wartości używanych w czasie tworzenia drzewa.

       Liniowe  przeglądanie  drzewa  "do  przodu" odbywa się od najmniejszego
       klucza do największego.

       Przestrzeń zwolniona przez usunięcie par klucz/dane z drzewa  nie  jest
       nigdy  odzyskiwana, jednakże, jest ona normalnie dostępna dla ponownego
       użycia. Oznacza  to,  że  struktura  przechowująca  drzewo  btree  może
       jedynie rosnąć. Jedynym rozwiązaniem jest unikanie nadmiernego usuwania
       lub  okresowe  tworzenie  świeżego  drzewa  na  podstawie  przeglądania
       istniejcego drzewa.

       Przeszukiwania,  wstawiania i usunięcia w btree odbywają się w czasie O
       lg base N, gdzie base jest czynnikiem średniego  wypełnienia.   Często,
       wprowadzanie do drzew btree danych uporządkowanych prowadzi do niskiego
       czynnika wypełnienia.   Ta  implementacja  została  zmodyfikowana,  aby
       uczynić   uporządkowane  wprowadzanie  najkorzystniejszym  przypadkiem,
       uzyskując w wyniku tego dużo lepszy niż normalnie  czynnik  wypełnienia
       stron.

BŁĘDY

       Funkcje  metod dostępu btree mogą zawieść i ustawić errno dla dowolnego
       z błędów podanych w funkcji bibliotecznej dbopen(3).

ZOBACZ TAKŻE

       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

       Obsługuje jedynie ostrokońcy i grubokońcy porządek bajtów.

                                  1994-08-18                          BTREE(3)