Provided by:
manpages-pl-dev_20060617-3_all 
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)