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%.
- 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).
- 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.
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:
Kod: Zaznacz cały
DEFINITION MODULE UBTreeTypes ;
( . . . )
CONST
BTreeNil = 0FFFFFFFFH ;
(. . . )
TYPE
InxBufferType = ARRAY [ 0 .. 9999 ] OF CHAR ;
InxBufferTypePtr = POINTER TO InxBufferType ;
ItemType = RECORD
DataRef : LONGCARD ;
PageRef : LONGCARD ;
EPageRef : LONGCARD ;
Key : InxBufferType ;
END (* RECORD *) ;
ItemTypePtr = POINTER TO ItemType ;
PageType = RECORD
ItemsOnPage : CARDINAL ;
BackwardPage : LONGCARD ;
ItemArray : InxBufferType ;
END (* RECORD *) ;
PageTypePtr = POINTER TO PageType ;
BaseRecord = RECORD
RecordStatus : LONGCARD ;
RecordData : InxBufferType ;
END (* RECORD *) ;
( . . . )
END UBTreeTypes.
Kod: Zaznacz cały
#define BTreeNil 0x0FFFFFFFFL
typedef struct {
USHORT CRCSum ;
ULONG DataRef ;
ULONG ForwardRef ;
} DuplPageType ;
typedef DuplPageType * PtrDuplPageType ;
typedef struct {
ULONG DataRef ;
ULONG PageRef ;
ULONG EPageRef ;
UCHAR Key [ ] ;
} BTItemT ;
typedef BTItemT * PtrBTItemT ;
typedef struct {
USHORT CRCSum ;
USHORT ItemsOnPage ;
ULONG BackwardPage ;
UCHAR ItemArray [ ] ;
} BTPageT ;
typedef BTPageT * PtrBTPageT ;
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.