Linux Certif

Toute la documentation sur la certification Linux LPI

btree

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.