Provided by: manpages-pl-dev_0.5-1_all bug

NAZWA

       btree - metoda dostępu do bazy btree

SKŁADNIA

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

OPIS

        Uwaga! To tłumaczenie może być nieaktualne!

       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.

INFORMACJE O TŁUMACZENIU

       Powyższe tłumaczenie pochodzi z nieistniejącego już Projektu Tłumaczenia  Manuali  i  może
       nie  być  aktualne.  W  razie  zauważenia  różnic  między  powyższym opisem a rzeczywistym
       zachowaniem opisywanego programu lub  funkcji,  prosimy  o  zapoznanie  się  z  oryginalną
       (angielską) wersją strony podręcznika za pomocą polecenia:

              man --locale=C 3 btree

       Prosimy  o  pomoc  w  aktualizacji stron man - więcej informacji można znaleźć pod adresem
       http://sourceforge.net/projects/manpages-pl/.

                                            1994-08-18                                   BTREE(3)