btree(3) Library Functions Manual btree(3) NAZWA btree - metoda dostepu do bazy btree BIBLIOTEKA Standardowa biblioteka C (libc, -lc) SKLADNIA #include #include OPIS Note well: This page documents interfaces provided up until glibc 2.1. Since glibc 2.2, glibc no longer provides these interfaces. Probably, you are looking for the APIs provided by the libdb library instead. Funkcja dbopen() stanowi interfejs biblioteczny do plikow baz danych. Jednym z obslugiwanych formatow sa pliki btree. Ogolny opis metod dostepu do baz danych znajduje sie w dbopen(3), a ta strona podrecznika opisuje jedynie informacje specyficzne dla btree. Struktura danych btree stanowi uporzadkowana, zrownowazona strukture drzewiasta, przechowujaca powiazane pary klucz/dane. Specyficzna dla metody dostepu btree struktura danych uzywana przez dbopen(3) jest zdefiniowana w pliku naglowkowym nastepujaco: typedef struct { unsigned long flags; unsigned int cachesize; int maxkeypage; int minkeypage; unsigned 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 nastepujace elementy: flags Wartosc znacznika jest okreslona przez alternatywe bitowa (OR) dowolnych z nastepujacych wartosci: R_DUP Zezwala na powtarzajace sie w drzewie klucze, tzn. pozwala dodawac klucze, ktore juz w drzewie istnieja. Domyslnym zachowaniem, jak opisano w dbopen(3), jest nadpisywanie istniejacego pasujacego klucza podczas wprowadzania nowego klucza lub niepomyslne zakonczenie, 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 juz istnieje, zakonczy sie niepowodzeniem. Jesli baza danych zawiera powtarzajace sie klucze, kolejnosc pobierania kluczy/danych za pomoca funkcji get jest niezdefiniowana, jednakze, wywolania funkcji seq z ustawionym znacznikiem R_CURSOR zawsze zwroca logicznie "pierwszy" z dowolnej grupy powtarzajacych sie kluczy. cachesize Sugerowany maksymalny rozmiar (w bajtach) bufora w pamieci. Wartosc ta stanowi jedynie zalecenie, wiec metoda dostepu raczej przydzieli wiecej pamieci niz zawiedzie. Ze wzgledu na to, ze kazde poszukiwanie bada strone korzenia drzewa, buforowanie najczesciej uzywanych stron istotnie skroci czas dostepu. Dodatkowo, fizyczne zapisy beda opoznione na tyle, na ile bedzie to mozliwe, wiec umiarkowany bufor moze istotnie zmniejszyc liczbe operacji wejscia/wyjscia. Oczywiscie, korzystanie z bufora zwieksza (ale jedynie zwieksza) prawdopodobienstwo uszkodzenia lub utraty danych, jesli system ulegnie awarii podczas gdy drzewo jest modyfikowane. Jesli cachesize wynosi 0 (nie podano rozmiaru) uzywany jest bufor domyslny. maxkeypage Maksymalna liczba kluczy, ktore beda przechowywane w ramach pojedynczej strony. Aktualnie nie zaimplementowane. minkeypage Minimalna liczba kluczy przechowywanych w ramach pojedynczej strony. Wartosc ta sluzy do okreslania, ktore klucze beda przechowywane w stronach nadmiarowych, to jest jesli klucz lub element danych jest wiekszy niz rozmiar strony podzielony przez wartosc minkeypage, bedzie on przechowywany w stronie nadmiarowej, zamiast w stronie wlasciwej. Jesli minkeypage wynosi 0 (nie podano minimalnej liczby kluczy), uzyta zostanie wartosc 2. psize Rozmiar strony jest rozmiarem (w bajtach) stron uzywanych przez wezly drzewa. Minimalny rozmiar strony wynosi 512 bajtow, a maksymalnym rozmiarem jest 64KiB. Jesli psize wynosi 0 (nie podano rozmiaru strony), rozmiar strony jest wybierany w oparciu o rozmiar bloku uzywanego systemu plikow. compare Compare jest funkcja porownywania kluczy. Musi ona zwracac liczbe calkowita mniejsza, rowna lub wieksza od zera, gdy klucz bedacy pierwszym argumentem jest, odpowiednio, mniejszy, rowny, wiekszy niz klucz bedacy drugim argumentem. Dla danego drzewa przy kazdym jego otwarciu musi byc uzywana ta sama funcja porownawcza. Jesli compare ma wartosc NULL (nie podano funkcji porownawczej), klucze beda porownywane leksykalnie, przy czym krotsze klucze beda uwazane za mniejsze niz klucze dluzsze. prefix Prefix jest funkcja porownywania przedrostkow. Jesli zostanie podana, musi ona zwracac liczbe bajtow argumentu bedacego drugim kluczem, ktore sa niezbedne dla okreslenia czy jest on wiekszy niz klucz bedacy pierwszym argumentem. Gdy klucze beda rowne, powinna zostac zwrocona dlugosc klucza. Uwaga, przydatnosc tej funkcji silnie zalezy od danych, jednak dla pewnych zbiorow danych jej uzywanie moze prowadzic do istotnie zmniejszonych rozmiarow drzewa i krotszych czasow poszukiwania. Jesli prefix ma wartosc NULL (nie podano funkcji prefix) oraz nie podano funkcji porownawczej, uzyta zostanie domyslna funkcja porownywania leksykalnego. Jesli prefix ma wartosc NULL i podano funkcje porownawcza, nie bedzie wykonywane porownywanie przedrostkow. lorder Kolejnosc bajtow dla liczb calkowitych w przechowywanych metadanych bazy. Liczba powinna reprezentowac kolejnosc jako liczbe calkowita; na przyklad, porzadek grubokoncy bylby liczba 4,321. Jesli lorder wynosi 0 (nie podano kolejnosci) uzyta zostanie aktualna, systemowa kolejnosc. If the file already exists (and the O_TRUNC flag is not specified), the values specified for the arguments flags, lorder, and psize are ignored in favor of the values used when the tree was created. Liniowe przegladanie drzewa "do przodu" odbywa sie od najmniejszego klucza do najwiekszego. Przestrzen zwolniona przez usuniecie par klucz/dane z drzewa nie jest nigdy odzyskiwana, jednakze, jest ona normalnie dostepna dla ponownego uzycia. Oznacza to, ze struktura przechowujaca drzewo btree moze jedynie rosnac. Jedynym rozwiazaniem jest unikanie nadmiernego usuwania lub okresowe tworzenie swiezego drzewa na podstawie przegladania istniejcego drzewa. Przeszukiwania, wstawiania i usuniecia w btree odbywaja sie w czasie O lg base N, gdzie base jest czynnikiem sredniego wypelnienia. Czesto, wprowadzanie do drzew btree danych uporzadkowanych prowadzi do niskiego czynnika wypelnienia. Ta implementacja zostala zmodyfikowana, aby uczynic uporzadkowane wprowadzanie najkorzystniejszym przypadkiem, uzyskujac w wyniku tego duzo lepszy niz normalnie czynnik wypelnienia stron. BLEDY Funkcje metod dostepu btree moga zawiesc i ustawic errno dla dowolnego z bledow podanych w podreczniku funkcji bibliotecznej dbopen(3). USTERKI Obsluguje jedynie ostrokoncy i grubokoncy porzadek bajtow. ZOBACZ TAKZE 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. TLUMACZENIE Autorami polskiego tlumaczenia niniejszej strony podrecznika sa: Andrzej Krzysztofowicz , Robert Luberda i Michal Kulach Niniejsze tlumaczenie jest wolna dokumentacja. Blizsze informacje o warunkach licencji mozna uzyskac zapoznajac sie z GNU General Public License w wersji 3 lub nowszej. Nie przyjmuje sie ZADNEJ ODPOWIEDZIALNOSCI. Bledy w tlumaczeniu strony podrecznika prosimy zglaszac na adres listy dyskusyjnej . Linux man-pages 6.06 31 pazdziernika 2023 r. btree(3)