microgeek.eu

Koncepcja, filozofia, własności, struktura

Rozważania są kontynuacją tematu
dotyczącego drzew binarnych,
jednak ze względu na swoje indywidualne cechy
jest wydzielone jako niezależny temat.

Filozofia działania b-drzew jest bardzo podobna do filozofii drzew binarnych. Tu również typowym rozwiązaniem jest zastosowanie algorytmów rekurencyjnych. Podstawową różnicą pomiędzy elementem węzła drzewa binarnego i elementu b-drzewa jest liczba kluczy przechowywanych w pojedynczym elemencie. W przypadku drzew binarnych, każdy element przechowuje jeden element wraz z konsekwencjami tego faktu: ma wskazanie do elementów młodszych oraz starszych. W przypadku b-drzewa, każdy element zawiera kilka kluczy. By nie wnosić nieporozumień, element struktury b-drzewa będę nazywał stroną. Istotną cechą strony b-drzewa jest jej wielkość, czyli liczba kluczy wraz z informacjami stowarzyszonymi. Taki element w dalszej części będzie nazywany Item'em. Ważną cechą strony jest liczba Item'ów zawartych na pojedynczej stronie. W rzeczywistości istotna jest liczba Item'ów tworzących półstronę, gdyż ta wielkość na istotne znaczenie dla algorytmów równoważenia b-drzewa. Można na to spojrzeć również z z takiej perspektywy, że strona b-drzewa zawiera 2n elementów (Item'ów). Cechy charakterystyczne dla b-drzewa są następujące:

• klucze zawarte w strukturach elementów Item na danej stronie są uporządkowane w określony sposób (najczęściej rosnący ale to nie jest jedyne możliwe rozwiązanie),
• każda strona (z wyjątkiem strony będącej szczytem drzewa) zawiera od n do 2n elementów, czyli stopień wypełnienia tablicy Item'ów na danej stronie jest równy lub większy od 50%.

Strukturę strony pokazuje poniższa ilustracja:

btree01_01.png

Zawiera ona następujące pola (oczywiście struktura może zostać rozbudowana o specyficzne w danym zastosowaniu elementy dodatkowe):

• ItemsOnPage - liczba ważnych Item'ów na stronie, nie ma obowiązku, by cała strona, czyli cała tablica Item'ów była wypełniona ważnymi informacjami, toteż przechowywana jest informacja o liczbie Item'ów zawierających istotne dane,
• BackwardPage - wskaźnik przeniesienia do elementów młodszych, filozoficznie odpowiadający wskaźnikowi LeftLink w drzewach binarnych, tutaj BackwardPage jest wskazaniem na stronę zawierającej klucze młodsze od klucza zapisanego na pozycji Item[0],
• Items - tablica Item'ów (na powyższej ilustracji n=3, wielkość półstrony wynosi 3 elementy, cała strona to 2n=6 elementów).

Zagłębiając się z kolei w strukturę pojedynczego Item'u, to mamy:

btree01_02.png

• Key - klucz, informacja zależna od danego zastosowania: może być tablicą znakową przechowującą napis i wtedy jako funkcja porządkująca Item'y na stronie musi być funkcją porównującą napisy dającą wynik w sensie kolejności alfabetycznej; może być liczbą binarną, wtedy funkcja porządkująca musi traktować dane jako liczba o określonej liczbie bajtów,
• DatRef - wskaźnik użytkowy o znaczeniu zależnym od zastosowania, przykładowo może być wskazaniem na położenie skojarzonego z kluczem rekordu bazy danych,
• ForwardPage - wskaźnik do strony zawierającej klucze starsze od klucza zapisanego w danym Item'ie (jednak młodsze od klucza zapisanego w następnym Itemie), jest filozoficznym odpowiednikiem wskaźnika RightLink w drzewie binarnym,
• DuplPage - wskaźnik do listy liniowej duplikatów, ten element nie jest obowiązkowy a jego istnienie wynika z zastosowania algorytmu b-drzewa do określonych celów.

Zaproponowane rozwiązania pozwalają na realizację całkiem „dorosłej” realizacji bazy danych z rekordami o stałej długości a ich implementacja pozwalała sortować dosyć efektywnie miliony rekordów zawartych w pliku (przykładowo b-drzewo o wielkości półstrony = 8 jako jednopokoleniowe zawiera 16 kluczy, dwupokoleniowe zawiera 272 klucze, 3-pokoleniowe to już ponad 4000 kluczy). Z filozoficznego punktu widzenia b-drzewa to taka „wszechwiedząca istota”, którą można zapytać o cokolwiek (podając klucz) i uzyskać odpowiedź (w postaci DataRef).
Moja pierwsza implementacja algorytmów b-drzewa była zrealizowana w języku MODULA-2 (to taka ulepszona wersja PASCAL'a). Zawierała ona kompletną realizację operacji związanych z przetwarzaniem stron b-drzewa. Powyższe definicje typów mogą być następujące:Język MODULA-2 jest bardzo wdzięcznym językiem do programowania, zapisy algorytmów są zwięzłe i eleganckie. Jednak ma on jedną wadę: jest mało popularny. Narzędzia do tworzenia oprogramowania (kompilator) dotyczą jedynie komputerów PC. Chcąc mieć możliwość szerszego wykorzystania swego czasu dokonałem transkrypcji z języka MODULA-2 na język C. Niestety w kilku miejscach „elegancja” zapisu modulowego poszła „w pole” (pewnych konstrukcji z PASCALA czy MODULI nie daje się przenieść do języka C), rozwiązanie jest trochę mniej eleganckie (jednak technicznie sprawne). Powyższe w języku C wygląda następująco:Dodanie elementu do b-drzewa nie odbiega znacząco od rozwiązań z drzewami binarnymi. Algorytm jest identycznie (rekurencyjnie) zrealizowany. Dodanie pierwszego elementu generuje nową stronę i jej wskazanie doczepia się do wskazania na szczyt drzewa (jakkolwiek będzie on reprezentowany: jako zmienna w pamięci RAM, jakieś „znane” miejsce w pliku podające ofset, gdzie znajduje się treść strony).

btree01_03.png

Dodanie kolejnego elementu poszerza tablicę Item'ów i zwiększa licznik „ważnych” elementów.

btree01_04.png

Czasem, a właściwie w większości wypadków, dodanie kolejnego elementu wymaga przesunięć w tablicy Item'ów. Te zawsze muszą byś uporządkowane a dodawany element nie zawsze musi się wpasować na koniec tablicy. W przypadku wkładania nowego Item'u do środka, konieczne jest zrobienie miejsca nowemu, co sprowadza się do przepisania niektórych Item'ów o jedną pozycję.

btree01_05.png

Dodanie nowego nie zaburza dotychczasowego uporządkowania.

btree01_06.png

Dodanie kolejnych elementów doprowadzi do poniższego stanu.

btree01_07.png

W przypadku dodania elementu do strony, która zawiera zajęte wszystkie Item'y, dochodzi do przenosin (czasem jest to związane ze zbudowaniem nowego lokum). W przypadku budowy nowej strony efekt będzie jak na ilustracji niżej. Tworzony jest nowy poziom b-drzewa, który będzie zawierał jeden element (środkowy z dotychczas znajdujących się). Ponieważ nowa liczba elementów jest nieparzysta, łatwo jest wydzielić dokładnie środkowy (liczba elementów na stronie 2n jest parzysta plus dodany jeden nowy).

btree01_08.png

W przypadku, gdy istnieje bardziej rozbudowana struktura (istnieje strona bezpośrednio nadrzędna do bieżącej), element środkowy przeprowadza się do strony nadrzędnej. Zachodzi przypadek swoistego dodania elementu w strukturze nadrzędnej. Oczywiście może zdarzyć się przypadek, że strona bezpośrednio nadrzędna również jest w 100% wypełniona, więc fraktalnie również zostaje wydzielony element środkowy, który przechodzi do kolejnej strony nadrzędnej. W szczególnej sytuacji, gdzie wszystkie strony są wypełnione w 100% (a za taki przypadek można uważać jeden z powyższych rysunków), dochodzi to utworzenia kolejnej „warstwy” b-drzewa (jak na powyższym rysunku).
W przypadku drzew binarnych, istnieją sytuacje, gdzie poszczególne gałęzie mają różną długość: przykładowo drzewo o 4 elementach ma jednego „rodzica”, dwoje „dzieci” i jednego „wnuka”. Jak na to nie patrzeć, istnieje gałąź o innej długości od każdej pozostałej. W przypadku b-drzewa ten przypadek nie zaistnieje i uzyskuje się go przez zmienny stopień wypełnienia strony. Poprawnie zbudowane b-drzewo ma zawsze wszystkie gałęzie identycznej długości.

Budowanie drzewa

Wstawianie elementów do B-drzewa jest w zasadzie prostą operacją, a w stosunku do drzew binarnych, to można rzec, że wręcz trywialną. Znacząco prostsze algorytmy wynikają z dosyć istotnej cechy B-drzewa. W poprzednim odcinku rozważań jest napisane, że w przypadku przepełnienia strony, ulega ona podziałowi z przeniesieniem odpowiedniego elementu do strony nadrzędnej. Zauważmy, że przy takim podejściu, B-drzewo zawsze rozrasta się w stronę korzenia. Implikacją tego faktu jest to, że „dół” drzewa jest „równo przycięty” → co oznacza, że wszystkie gałęzie są identycznej długości → nie wymaga równoważenie → algorytmy się upraszczają. By nie być gołosłownym, przykład programu [BTREE1EX.C]:Pamiętając, że podstawowym zadaniem stawianym dla B-drzewa jest kojarzenie informacji: treści klucza (podstawowej informacji, hasła na jakie ma zareagować algorytm) oraz wskaźnika z nim związanego (wynikowej informacji o różnej interpretacji wynikającej z zastosowania: tu jako zagadnienie bazodanowe → wskazaniem, położeniem danych związanych z kluczem w pliku bazy). Zadaniem programu jest wygenerowanie kluczy jako napisów (ciągu znaków) z kolejnych liczb, dodanie do tego wskaźnika jako liczby 32-bitowej (tej samej) i utworzenie z tych informacji B-drzewa.
Zdaję sobie sprawę, że wiele informacji na razie brzmi dziwnie i tajemniczo, jednak postaram się wszystko wyjaśnić. Wymaga to trochę czasu, więc pewne szczegóły warto „przyjąć na wiarę”. Przykłady programów są współczesne, obecne, jednak wszystkie procedury zostały wycmonione wiele lat temu. Było to głównie przeznaczone do stosowania w PC'ach jednak rozwiązanie jest tak skonstruowane by dało się łatwo adaptować przykładowo w mikrokontrolerach. Uzyskane jest to dzięki „wyeksportowaniu” ściśle określonych operacji do jednego miejsca, które mogą być łatwo zastąpione inną implementacją. W rozważaniach występują pojęcia typowe dla komputerów (jak choćby plik), to nie należy do tego podchodzić zbyt dosłownie i jako plik można uważać strumień danych: wczytywanych lub zapisywanych (gdziekolwiek). Podstawowym elementem „programowym” pozwalającym uzyskać dużą elastyczność jest coś, co nazywam instancją (takie coś podobne do komponentu w językach obiektowych).
Jeszcze jedno drobne wyjaśnienie:
CreateIndex ( ( UCHAR * ) "TBTREE1.INX" , 4 , 0 , 0 , ….. , 3 , 0 , 0 , & BTreeInstance ) ;
oznacza, że zostanie utworzony i używany zbiór reprezentujący na dysku B-drzewo z kluczem znakowym o wielkości 4 znaków i wielkością półstrony 3 (6 kluczy na stronie B-drzewa).
Po dodaniu pierwszego klucza, B-drzewo będzie wyglądało następująco (co chyba nie powinno dziwić):

btree02_01.png

Dodając kolejne klucze do jednogałązkowego drzewka, powstaje:

btree02_02.png

Dodanie kolejnego elementu spowoduje przepełnienie tablicy Item'ów.

btree02_03.png

Środkowy element jest przenoszony do strony nadrzędnej (ewentualnie do strony nowoutworzonej, jeżeli nie ma strony nadrzędnej). Zawartość tablicy Item'ów jest dzielona na dwie połowy.

btree02_04.png

Dalsze dokładanie elementów do B-drzewa doprowadzi ponownie do przepełnienia strony.

btree02_05.png

Kropla, która ją przeleje, spowoduje ponowny podział strony.

btree02_06.png

Dodając kolejne elementy do B-drzewa, w sposób monotoniczny, ponownie zaistnieje podział strony z przeniesieniem elementu środkowego do strony nadrzędnej.

btree02_07.png

Kolejne dodawane elementy doprowadzą do sytuacji jak na poniższym rysunku:

btree02_08.png

Ponowne przepełnienie strony da w efekcie kolejny nowy element rzeczywistości → mamy nowy szczyt strony.

btree02_09.png

O ile dodawanie już uporządkowanych kluczy do drzewa binarnego równoważonego daje „piękną” strukturę drzewa, w B-drzewach jest wyjątkowo upierdliwym przypadkiem (ze względu na wypełnienie stron). Znacząco lepsze rezultaty wychodzą przy bardziej losowej kolejności wkładania kluczy. Nie po raz pierwszy wychodzi, że określona kolejność zdarzeń implikuje określone skutki.
Poruszanie się po drzewie jest praktycznie identyczne jak w drzewie binarnym. Powyższy program, po utworzeniu całego B-drzewa realizuje jego wydruk. Koncepcja jest zbieżna z metodologią stosowaną w drzewach binarnych (wydrukuj lewe poddrzewo, wydrukuj siebie i wydrukuj prawe poddrzewo) i w szczegółach wygląda następująco: wydrukuj strony młodsze [wywołanie rekurencyjne], z tablicy Item'ów poczynając od pierwszej pozycji druknij siebie (klucz zawarty w danym Item'ie) druknij całe drzewo przypięte do wskaźnika starszeństwa dla klucza [wywołanie rekurencyjne], przejdź do kolejnego Item'u, druknij siebie i całe drzewo przypięte. I tak do samego końca (dokładniej do liczby Item'ów zawartych na stronie).

B-DRZEWO z duplikatami

Wracając do rysunku ilustrującego strukturę pojedynczego Item'u na stronie BTree:

btree03_01.png

Znajduje się tam pole przewidziane do rozwiązana problemu duplikatów, czyli w jaki sposób w strukturze B-drzewa są przechowywane informacje o duplikatach; parze skojarzenia typu: klucz ↔ wskaźnik (DataRef) związany z tym kluczem. W ogólnym przypadku, identyczna wartość klucza nie oznacza, że związany z tym kluczem wskaźnik jest również identyczny. Chcąc „zaoszczędzić” trochę miejsca w przestrzeni, w przypadku identycznego klucza, możne w strukturach danych przechowywać już jedynie sam wskaźnik danych. Przy tej koncepcji, wręcz jako naturalne rozwiązanie, nasuwa się zastosowanie listy liniowej.

btree03_02.png

Z zagadnieniem budowy listy liniowej kojarzą się dwa warianty dotyczące kolejności elementów występujących na liście: lista liniowa wprost oraz lista liniowa odwrócona. Lista liniowa wprost odpowiada filozofii FIFO: element pierwszy włożony jest jako pierwszy dostępny. W drugim przypadku jest to rozwiązanie typu First In, Last out. O ile wariant drugi jest prostszy w implementacji (nie występuje potrzeba poszukiwania końca listy, by tam dołączyć nowy element), to w omawianym oprogramowaniu zastosowane jest rozwiązanie FIFO. W tym przypadku konieczne staje się odszukanie takiego elementu na liście, w którym następnik nie wskazuje już na żaden element (ma wartość BTreeNil). Po odszukaniu takiego elementu, jako następnik wpisuje się wskazanie na nowy element. To z jednej strony jest naturalne rozwiązanie, gdyż większość zastosowań jest zgodna z wariantem FIFO. Z drugiej strony uzyskuje się pewną cechę dodaną: w przypadku „jazdy” dwóch procesów jednocześnie (jeden piszący [dodający elementy], drugi czytający [poszukujący elementów]) może zaistnieć jednoczesna akcja na liście liniowej. Dodawanie na końcu listy to takie „budowanie przyszłości” przez jeden proces dla drugiego procesu. Proces czytający zawsze będzie miał szansę natrafić na nowe elementy. Dodawanie nowych elementów „za plecami” będzie wymagało powtórki całego procesu przetwarzania. Rozumiem, że prawdopodobieństwo takiego zdarzenia jest nikłe, jednak nie jest zerowe. To oprogramowanie było używane w „środowiskach wielodostępnych i wieloprocesowych”, gdzie jednocześnie po tych samych plikach bazy „jeździło” kilka programów jednocześnie, których „interesy” są czasami wręcz „sprzeczne i konfliktowe”, a soft „narzędziowy” musiał takie konflikty rozstrzygać. Do „konfliktowego” poruszania się po samym B-drzewie, jest zastosowane inne rozwiązanie, ale o tym to może już innym razem.

Przykład programu:Przed jakąkolwiek akcją związaną z B-drzewami, konieczne jest zainicjowanie instancji związanej z B-drzewami:Program tworzy B-drzewo na dysku kompa, który z punktu widzenia algorytmu B-tree ma następujące parametry (akcja tworzeniu pustego B-drzewa na dysku):

• klucz jest znakowy o wielkości 4 znaków,
• wielkość półstrony wynosi 8

Program otwiera plik do „jazdy” po B-drzewie. Z otwarcia zwrotnie jest uzyskana informacja o podstawowych parametrach dotyczących budowy B-drzewa (zmienna Description → zawiera długość klucza, wielkość półstrony i podobne szczegóły).Dodanie klucza do B-drzewa to wywołanie funkcjigdzie w parametrach wywołania jest:

• dowiązanie do otwartego pliku z B-drzewem (Index),
• dowiązanie do dodawanego klucza (Key),
• dowiązanie do szczegółów konstrukcji B-drzewa jako informacji z otwarcia zbioru B-drzewa (Description),
• wskaźnik związany z kluczem (BaseEntry),
• wynik akcji dodania klucza, interpretowane są odpowiednie bity w słowie (Reply),
• dowiązanie do instancji związanej z algorytmem B-drzewa (BtreeInstance).

Akcja poszukiwania czegokolwiek z B-drzewie to wywołanie funkcjijako wyszukanie pierwszego wystąpienia określonego klucza. Obok znanych parametrów w wywołaniu występuje dowiązanie do odpowiedzi z akcji poszukiwania (Response). Zawiera ona między innymi treść odnalezionego klucza, wskaźnik danych związany z kluczem oraz odpowiedź z akcji poszukiwania.
Do wyszukania duplikatów używana jest inna funkcja.gdzie zmienna Response musi zawierać wyniki z poprzedniej akcji poszukiwania (lub z wyszukania pierwszego wystąpienia klucza).
Po utworzeniu B-drzewa, program wyszukuje wystąpienia wszystkich dodanych kluczy (z wydrukowaniem informacji z akcji poszukiwania).
Na zakończenie jest pokazane wydrukowanie całego B-drzewa w „technicznej” realizacji algorytmu (w zestawie kawałków znajdują się funkcja typu: daj pierwszy, daj następnik, daj duplikat). W algorytmie wydruku można dostrzec drzewiastą strukturę B-drzewa oraz liniową listę duplikatów.
Wygenerowane przez program wyniki (we fragmentach):

Całość softu (projekt w Dev C):

RAM BTREE

Teraz w tym samym programie, co jest zaprezentowany wyżej, dokonamy drobnej zamiany, korekty. Po standardowym zainicjowaniu instancji do obsługi akcji Btree, realizowane są następujące podmianki:Powyższe instrukcje zmieniają dotychczasowe implementacje odpowiednich operacji na nowe, utworzone lokalnie w programie. Wśród tych działań są operacje otwarcia i zamknięcia pliku, operacje podniesienia i opuszczenia semaforów (niektóre czynności mają charakter krytyczny i są wykonywane z gwarancją przebiegu w danym obszarze tylko jednego procesu, oprogramowanie jest przygotowane do akcji wielozadaniowych, toteż niezbędne są gwarancje realizacji określonych akcji w sposób jednoprocesowy, stabilny; w przypadku stosowania w świecie mikrokontrolerów ich implementacje mogą pozostać puste) oraz zapisu, odczytu i rozszerzenia plików. Już gdzieś wyżej wspomniałem, nie należy zbyć dosłownie interpretować pojęcia pliku. Takim plikiem może być dowolny obszar pamięci ze zrealizowanymi procedurami odczytu i zapisu.
Przykładowy poniższy program pokazuje sposób „przełączenia” idei pliku. W programie jest utworzona tablica, która jest zainicjowania w wyniku wywołania funkcji (chociaż jej wyzerowanie nie jest konieczne), zmienna FileInx ma znaczenie wielkości pliku w pamięci (symulowanej przez FileBody):Operacje otwarcia i zamknięcia pliku w „nowym świecie” wyglądają następująco:Koniecznością staje się jedynie wyzerowanie pola przeznaczonego na odpowiedź (zawsze pozytywną), nawet jakieś handle można nadać plikowi, w sumie nie ma to żadnego znaczenia.
Akcje semaforowe to:Jak widać, ich implementacja jest pusta (jedynie należy zwrócić sygnał, że akcja powiodła się całkowicie: wyzerować odpowiedź).
Akcja rozszerzenia pliku (połączona z jednoczesnym zapisem danych) to:Realizacja akcji to przesunięciu dotychczasowej „granicy” pliku i zapis (przekopiowanie) danych do obszaru, o który został rozszerzony symulowany plik. Zwrotnie należy całe oprogramowanie poinformować, że akcja się udała oraz gdzie odbyła się cała ta zadyma.
Operacje zapisu oraz odczytu to jedynie przepisanie danych z bufora do tablicy udającej dysk (zapis) lub odwrotnie (odczyt).Po skompilowaniu i uruchomieniu programu, zostało utworzone B-drzewo, które egzystuje jedynie w pamięci. Program nawet nie dotknął dysku. Co przeszkadza, by w jakimś mikrokontrolerze smarować po zewnętrznym Flash'u? Nawet nic nie trzeba specjalnie robić, wszystko jest już przygotowane.

Las B-tree

Mając jakąś świadomość na temat budowy b-drzewa, możemy dokonać pewnej zmiany interpretacji wskaźnika danych. Podobnie jak było opisane w drzewach binarnych, niech wspomniany wskaźnik będzie wskazywał na lokalny szczyt kolejnego b-drzewa, jak na poniższym rysunku.

btree05-01.png

Oznacza to, że każdy klucz dodany do b-drzewa jest „właścicielem” kolejnego b-drzewa. Przez analogię można to nazwać b-drzewisatym lasem. Tą koncepcję może ilustrować poniższy program:Z istotnych elementów w programie jest:wywołanie funkcji tworzącej pusty plik b-drzewa (może być oparty o realny plik lub plik w pamięci RAM – taki symulator przykładowo DataFlash). W powyższym wywołaniu utworzona jest struktura pliku, w którym klucz nadrzędny zajmuje 4 bajty oraz klucz podrzędny również zajmuje 4 znaki. Kolejny szczegół, to b-drzewo dla „warstwy” nadrzędnej zawiera na stronie 6 Item'ów (podany jest parametr 3 jako wielkość półstrony), oraz b-drzewo warstwy podrzędnej również ma identyczną wielkość półstrony (podane parametry nie muszą być identyczne). Dodatkowo oba klucze mają reprezentację znakową (sortowane są stringi).
Do wypełnienia b-drzewa zastosowana jest pętla w pętli. Zewnętrzna pętla generuje wartości kluczy nadrzędnych (składających się cyfr), wewnętrzna pętla generuje klucze podrzędne (składające się z liter). Akcja jest powielona kilka razy by uzyskać klucze zduplikowane. Do tego dochodzi jakiś fikcyjny wskaźnik danych.
W dalszej części, program wykonuje kilka wyszukań (znacząco mniej niż jest zapisanych kluczy). Potem wydrukowane jest kompletne b-drzewo. Na koniec, w podobny sposób jak w akcji dodawania kluczy, wygenerowane są dane do operacji usuwania kluczy. Usunięcie wpisu wymaga zgodności kompletu kluczy i skojarzonego wskaźnika danych. Po całej akcji usuwania, ponownie jest wydrukowane całe b-drzewo. Tym razem jest puste.
Wygenerowane przez program wyniki są następujące:Sam wydruk zawartości lasu b-drzewa jest trochę bardziej złożony, choć koncepcja jest identyczna jak w wyżej zaprezentowanych programie. Mamy „zajrzenie” w każdą gałązkę jednak zamiast wydrukować skojarzone z tym informacje, realizowane jest kolejne wydrukowanie b-drzewa (identyczny algorytm).
Postępując koncepcyjnie w identyczny sposób, to prezentowane oprogramowanie umożliwia utworzenie lasu do potęgi 3 (b-drzewa wskazującego na b-drzewa, które wskazuje na b-drzewa). Filozoficznie można tak w nieskończoność, jednak zawsze warto mieć jakieś sensowne uzasadnienie. W mojej praktyce nie znalazłem sensownego zastosowania bardziej zagłębionych rozwiązań.

Przykład zastosowania B-drzewa

Pomimo, że pole DataRef znajdujące się w strukturze Item'u jest przewidziane do przechowywania pozycji rekordu w bazie danych, to nie ma obowiązku, by kurczowo trzymać się tego znaczenia. To zależy wyłącznie od nas i jest możliwe dowolne podejście do interpretacji tej informacji. Poniższy program generuje alfabetyczny wydruk identyfikatorów i stałych dla programu w C. Uruchomienie programu z nazwą pliku zawierającego funkcję main podaną w parametrach prowadzi do analizy wskazanego pliku. Program nie ma aspiracji do bycia kompilatorem, więc nie skupia się nad błędami zapisu, zakłada, że program jest syntaktycznie poprawny. Jedynym elementem, któremu poświęca baczniejszą uwagę, to dyrektywa preprocesora #include. Napotkane nazwy plików są automatycznie włączane do analizy przez program. Generalnie w includach zawiera się pliki nagłówkowe, więc program (tak trochę na wyrost) automatycznie dołącza plik ze zmienionym rozszerzeniem w nazwie z „.H” na „.C”. Czasami to prowadzi do śmiesznych sytuacji, gdyż nie ma obowiązku, by każdy plik nagłówkowy musiał mieć w parze plik z implementacją owego nagłówka. Jedynie w przypadku includa, gdzie plik jest zapisany w nawiasach „<” i „>” nie dołącza automatycznie pliku typu *.C, gdyż, z definicji są one biblioteczno-systemowe.
Analizując tekst programu, wyłapuje on wszelkie identyfikatory (w tym również słowa kluczowe → instrukcje) i stałe. Uzyskane elementy programu dołącza do dwupoziomowego b-drzewa, gdzie kluczem nadrzędnym jest uzyskany identyfikator, kluczem podrzędnym jest nazwa pliku i jako dataref występuje numer wiersza, w którym występuje wyjęty element programu. To w sposób naturalny sortuje wszystkie napotkane elementy z jednoczesnym podziałem na pliki, w których wystąpił dany element programu. Obrazuje to ilustracja (jako fragment z prawdziwych danych). Sortowanie składowych tekstu programu odbywa się w uwzględnieniem polskiego alfabetu (program poprawnie obrabia polskie literki w standardzie latin 2) oraz nie jest czuły na pisownię małymi lub wielkimi literami. Każdy element dodawany do b-drzewa jest przechowywany w oryginale, jednak bez względu na pisownię jest uszeregowany jak w polskim alfabecie.

btree06-01.png

Wyniki są zapisane do pliku o takiej samej nazwie jaka została podana w parametrach wywołania ze zmienionym rozszerzeniem na „.TXT”. Program uruchomiany z testem na sobie wygenerowała ponad 13000 wierszy. Przykładowy fragment wynikowy jest następujący:Identyfikator USHORT (typ zmiennej) wystąpił w takich a takich plikach w wierszach o wymienionych numerach. Taka czasami dosyć cenna informacja może być znaczącym wsparciem w poszukiwaniach i innym roztrząsaniu typu „co programista miał na myśli pisząc te słowa” (zawsze są to jakieś wskazówki by dociekać istoty zapisów).