B-drzewa

Projekty użytkowników forum zarówno sprzętowe, jak i związane z programowaniem w dowolnym języku.
Awatar użytkownika
gaweł
Geek
Geek
Posty: 1259
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

B-drzewa

Postautor: gaweł » wtorek 17 gru 2019, 01:53

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:

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.
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:

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 ;

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.
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse

Awatar użytkownika
gaweł
Geek
Geek
Posty: 1259
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

Re: B-drzewa

Postautor: gaweł » niedziela 22 gru 2019, 12:59

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]:

Kod: Zaznacz cały

#include <stdio.h>
#include <stdlib.h>
#include "TBTREETY.H"
#include "TBTREEFI.H"
#include "TBTREEPL.H"
#include "TINBTREE.H"
#include "TOUTBTRE.H"
#include "TSTRINGS.H"
#include "STRINGS.H"

#define EndLoop 64

#define AllocPage(x,y) (PtrBTPageT)LocalAlloc(x,y)
#define AllocFPage(x) (PtrFirstInxRecT)LocalAlloc(sizeof(FirstInxRecT),x)
#define NotReady(x) !(Ready&x)

static void Tree ( ULONG                Entry ,
                   USHORT               KeyLength ,
                   USHORT               Pagesize ,
                   USHORT               Itemsize ,
                   PtrAPFILE            IndexFile ,
                   PtrBTreeInstanceRecT BTreeInstance )
{
  USHORT CurrPos ;
  USHORT ReplyWord ;
  USHORT Loop ;
  PtrBTPageT CurrPage ;
  PtrBTItemT CurrItem ;
  UCHAR Key [ 32 ] ;
  /*------------------------------------------------------------------------*/
  if ( Entry != BTreeNil )
  {
    CurrPage = AllocPage ( Pagesize , BTreeInstance ) ;
    BTreeInstance -> GetPageServ ( IndexFile , CurrPage , Entry , Pagesize ,
                                   & ReplyWord , BTreeInstance ) ;
    Tree ( CurrPage -> BackwardPage , KeyLength , Pagesize , Itemsize ,
           IndexFile , BTreeInstance ) ;
    for ( CurrPos = 1 ; CurrPos <= CurrPage -> ItemsOnPage ; CurrPos ++ )
    {
      CurrItem = ItemAddress ( CurrPage -> ItemArray , CurrPos , Itemsize ) ;
      for ( Loop = 0 ; Loop < 32 ; Loop ++ )
        Key [ Loop ] = 0 ;
      for ( Loop = 0 ; Loop < KeyLength ; Loop ++ )
        Key [ Loop ] = CurrItem -> Key [ Loop ] ;
      printf ( "   Key: %s\n" , Key ) ;
      Tree ( CurrItem -> ForwardPage , KeyLength , Pagesize , Itemsize ,
             IndexFile , BTreeInstance ) ;
    } /* for */ ;
  } /* if ... else */ ;
} /* Tree */


static void PrintTree ( PtrAPFILE            IndexFile ,
                        PtrIndexDescr        InxDescr ,
                        PtrBTreeInstanceRecT BTreeInstance )
{
  USHORT Itemsize ;
  USHORT Pagesize ;
  USHORT ReplyWord ;
  PtrFirstInxRecT FirstBuck ;
  /*------------------------------------------------------------------------*/
  CreateMemory ( BTreeInstance ) ;
  FirstBuck = AllocFPage ( BTreeInstance ) ;
  GInfoPage ( IndexFile , FirstBuck , & ReplyWord , BTreeInstance ) ;
  if ( NotReady ( ReplyWord ) )
  {
    FreeMemory ( BTreeInstance ) ;
    return ;
  } /* if */ ;
  printf ( "\n\nWydruk zawartosci stron BTREE\n" ) ;
  Itemsize = ItemSize ( InxDescr -> SupKeyLgt ) ;
  Pagesize = InxDescr -> SupPageLgt ;
  Tree ( FirstBuck -> TopPage , InxDescr -> SupKeyLgt ,
         Pagesize , Itemsize , IndexFile , BTreeInstance ) ;
  FreeMemory ( BTreeInstance ) ;
} /* PrintTree */


int main(int argc, char* argv[])
{
  BTreeInstanceRecT BTreeInstance ;
  APFILE Index ;
  IndexDescr Description ;
  ResponseAreaType AA ;
  USHORT Reply ;
  USHORT Loop ;
  ULONG BaseEntry ;
  UCHAR Number[20];
  UCHAR Number2[20];
  /*------------------------------------------------------------------------*/
  InitStandBTree ( & BTreeInstance , NIL , NIL ) ;
  Reply = CreateIndex ( ( UCHAR * ) "TBTREE1.INX" , 4 , 0 , 0 ,
                        TRUE , TRUE , TRUE ,
                        TRUE , TRUE , TRUE , 3 , 0 , 0 , & BTreeInstance ) ;
  Reply = OpenIndex ( & Index , Commune_Open_Mode , ( UCHAR * ) "TBTREE1.INX" ,
                      & Description , & BTreeInstance ) ;
  for ( Loop = 1 ; Loop <= EndLoop ; Loop ++ )
  {
    BaseEntry = ( ULONG ) Loop ;
    UCardToStr ( Number , 4 , '0' , Loop ) ;
    ULCardToStr ( Number2 , 5 , ' ' , BaseEntry ) ;
    AddKey1(&Index, Number,&Description, BaseEntry, &Reply, &BTreeInstance );
    if ( ! ( Ready & Reply ) )
    {
      printf ( "Dodanie klucza %s [%s]- wynik: nie powiodlo sie\n" ,
               Number , Number2 ) ;
    }
    else
    {
      printf ( "Dodanie klucza %s [%s]- wynik: akcja zakonczona sukcesem\n" ,
               Number , Number2 ) ;
    } ;
    PrintTree ( & Index , & Description , & BTreeInstance ) ;
  } /* for */ ;
  for ( Loop = 1 ; Loop <= EndLoop ; Loop ++ )
  {
    UCardToStr ( Number , 4 , '0' , Loop ) ;
    SearchKey1 ( & Index , Number , & Description , & AA , & BTreeInstance ) ;
    if ( ! ( Ready & AA . Reply ) )
    {
      printf ( "Poszukiwanie klucza %s - wynik: nie znaleziono\n" , Number ) ;
    }
    else
    {
      ULCardToStr ( Number2 , 5 , ' ' , AA . DataPos ) ;
      printf ( "Poszukiwanie klucza %s - wynik: %s: akcja zakonczona sukcesem\n" ,
               Number , Number2 ) ;
    } ;
  } /* for */ ;
  CloseIndex ( & Index , & BTreeInstance ) ;
  return 0 ;
} /* main */
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).
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse

Awatar użytkownika
gaweł
Geek
Geek
Posty: 1259
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

Re: B-drzewa

Postautor: gaweł » środa 25 gru 2019, 17:43

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:

Kod: Zaznacz cały

#include <iostream>
#include <stdlib.h>
#include "TBTREETY.H"
#include "TBTREEFI.H"
#include "TBTREEPL.H"
#include "TINBTREE.H"
#include "TOUTBTRE.H"
#include "TSTRINGS.H"
#include "STRINGS.H"

#define EndLoop    32
#define DuplLimit  4
#define AddVal     10000

#define AllocPage(x,y) ( PtrBTPageT ) LocalAlloc ( x , y )
#define AllocFPage(x) ( PtrFirstInxRecT ) LocalAlloc ( sizeof ( FirstInxRecT ) , x )
#define NotReady(x) ! ( Ready & x )


static void Tree ( ULONG                Entry ,
                   USHORT               KeyLength ,
                   USHORT               Pagesize ,
                   USHORT               Itemsize ,
                   PtrAPFILE            IndexFile ,
                   PtrBTreeInstanceRecT BTreeInstance )
{
  ULONG DuplEntry ;
  DuplPageType DuplPage ;
  USHORT CurrPos ;
  USHORT ReplyWord ;
  USHORT Loop ;
  PtrBTPageT CurrPage ;
  PtrBTItemT CurrItem ;
  UCHAR Key [ 32 ] ;
  /*--------------------------------------------------------------------------*/
  if ( Entry != BTreeNil )
  {
    CurrPage = AllocPage ( Pagesize , BTreeInstance ) ;
    BTreeInstance -> GetPageServ ( IndexFile , CurrPage , Entry , Pagesize ,
                                   & ReplyWord , BTreeInstance ) ;
    Tree ( CurrPage -> BackwardPage , KeyLength , Pagesize , Itemsize ,
           IndexFile , BTreeInstance ) ;
    for ( CurrPos = 1 ; CurrPos <= CurrPage -> ItemsOnPage ; CurrPos ++ )
    {
      CurrItem = ItemAddress ( CurrPage -> ItemArray , CurrPos , Itemsize ) ;
      for ( Loop = 0 ; Loop < 32 ; Loop ++ )
        Key [ Loop ] = 0 ;
      for ( Loop = 0 ; Loop < KeyLength ; Loop ++ )
        Key [ Loop ] = CurrItem -> Key [ Loop ] ;
      printf ( "   Key: %s, dataref=%lu\n" , Key , CurrItem -> DataRef ) ;
      DuplEntry = CurrItem -> DuplicatePage ;
      while ( DuplEntry != BTreeNil )
      {
        BTreeInstance->GetPageServ(IndexFile,&DuplPage,DuplEntry,sizeof(DuplPageType),
                                   & ReplyWord , BTreeInstance ) ;
        printf ( "              dataref=%lu\n" , DuplPage . DataRef ) ;
        DuplEntry = DuplPage . ForwardPage ;
      } /* while */ ;
      Tree ( CurrItem -> ForwardPage , KeyLength , Pagesize , Itemsize ,
             IndexFile , BTreeInstance ) ;
    } /* for */ ;
  } /* if ... else */ ;
} /* Tree */


static void PrintTree ( PtrAPFILE            IndexFile ,
                        PtrIndexDescr        InxDescr ,
                        PtrBTreeInstanceRecT BTreeInstance )
{
  USHORT Itemsize ;
  USHORT Pagesize ;
  USHORT ReplyWord ;
  PtrFirstInxRecT FirstBuck ;
  /*--------------------------------------------------------------------------*/
  printf ( "\n\nWydruk zawartosci drzewa BTREE\n" ) ;
  CreateMemory ( BTreeInstance ) ;
  FirstBuck = AllocFPage ( BTreeInstance ) ;
  GInfoPage ( IndexFile , FirstBuck , & ReplyWord , BTreeInstance ) ;
  if ( NotReady ( ReplyWord ) )
  {
    FreeMemory ( BTreeInstance ) ;
    return ;
  } /* if */ ;
  Itemsize = ItemSize ( InxDescr -> SupKeyLgt ) ;
  Pagesize = InxDescr -> SupPageLgt ;
  Tree ( FirstBuck -> TopPage , InxDescr -> SupKeyLgt ,
         Pagesize , Itemsize , IndexFile , BTreeInstance ) ;
  FreeMemory ( BTreeInstance ) ;
} /* PrintTree */


int main ( int argc , char** argv )
{
  BTreeInstanceRecT BTreeInstance ;
  APFILE Index ;
  IndexDescr Description ;
  ResponseAreaType Response ;
  USHORT Reply ;
  USHORT Loop ;
  USHORT IntLoop ;
  ULONG BaseEntry ;
  UCHAR Number[10];
  UCHAR Number2[10];
  /*--------------------------------------------------------------------------*/
  InitStandBTree ( & BTreeInstance , NIL , NIL ) ;
  Reply = CreateIndex ( ( UCHAR * ) "TBTREE1.INX" , 4 , 0 , 0 ,
                        TRUE , TRUE , TRUE ,
                        TRUE , TRUE , TRUE , 8 , 0 , 0 , & BTreeInstance ) ;
  Reply = OpenIndex ( & Index , Commune_Open_Mode , ( UCHAR * ) "TBTREE1.INX" ,
                      & Description , & BTreeInstance ) ;
  for ( Loop = 1 ; Loop <= EndLoop ; Loop ++ )
  {
    BaseEntry = ( ULONG ) Loop + ( ULONG ) AddVal ;
    UCardToStr ( Number , 4 , '0' , Loop ) ;
    for ( IntLoop = 1 ; IntLoop <= DuplLimit ; IntLoop ++ )
    {
      ULCardToStr ( Number2 , 5 , ' ' , BaseEntry ) ;
      AddKey1 ( &Index , Number , &Description , BaseEntry , &Reply , &BTreeInstance ) ;
      if ( ! ( Ready & Reply ) )
      {
        printf ( "Dodanie klucza %s [%s]- wynik: nie powiodlo sie\n" ,
                 Number , Number2 ) ;
      } /* if ... */
      else
      {
        printf ( "Dodanie klucza %s [%s]- wynik: akcja zakonczona sukcesem\n" ,
                 Number , Number2 ) ;
      } /* if ... else */ ;
      BaseEntry += ( ULONG ) AddVal ;
    } /* for */ ;
  printf ( "-----------------------------\n" ) ;
  } /* for */ ;
  for ( Loop = 1 ; Loop <= EndLoop ; Loop ++ )
  {
    UCardToStr ( Number , 4 , '0' , Loop ) ;
    SearchKey1 ( & Index , Number , & Description , & Response , & BTreeInstance ) ;
    for ( ; ; )
    {
      if ( ! ( Ready & Response . Reply ) )
      {
        break ;
      } /* if ... */
      else
      {
        ULCardToStr ( Number2 , 5 , ' ' , Response . DataPos ) ;
        printf ( "Poszukiwanie klucza %s - wynik: %s: akcja zakonczona sukcesem\n" ,
                 Number , Number2 ) ;
      } /* if ... else */ ;
      SearchDuplKey ( & Index , & Description , & Response , & BTreeInstance ) ;
     } /* for */ ;
  } /* for */ ;
  PrintTree ( & Index , & Description , & BTreeInstance ) ;
  CloseIndex ( & Index , & BTreeInstance ) ;
  return 0 ;
} /* main */
Przed jakąkolwiek akcją związaną z B-drzewami, konieczne jest zainicjowanie instancji związanej z B-drzewami:

Kod: Zaznacz cały

  InitStandBTree ( & BTreeInstance , NIL , NIL ) ;
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):

Kod: Zaznacz cały

 CreateIndex ( ( UCHAR * ) "TBTREE1.INX" , 4 , 0 , 0 ,
                TRUE , TRUE , TRUE ,
                TRUE , TRUE , TRUE , 8 , 0 , 0 , & BTreeInstance ) ;
  • 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).

Kod: Zaznacz cały

 Reply = OpenIndex ( & Index , Commune_Open_Mode , ( UCHAR * ) "TBTREE1.INX" ,
                      & Description , & BTreeInstance ) ;
Dodanie klucza do B-drzewa to wywołanie funkcji

Kod: Zaznacz cały

AddKey1 (  & Index, Number, & Description, BaseEntry, & Reply, & BTreeInstance);
gdzie 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 funkcji

Kod: Zaznacz cały

SearchKey1( & Index , Number , & Description , & Response , & BTreeInstance ) ;
jako 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.

Kod: Zaznacz cały

SearchDuplKey ( & Index , & Description , & Response , & BTreeInstance ) ;
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):

Kod: Zaznacz cały

Dodanie klucza 0001 [10001]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0001 [20001]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0001 [30001]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0001 [40001]- wynik: akcja zakonczona sukcesem
-----------------------------
Dodanie klucza 0002 [10002]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0002 [20002]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0002 [30002]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0002 [40002]- wynik: akcja zakonczona sukcesem
-----------------------------
Dodanie klucza 0003 [10003]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0003 [20003]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0003 [30003]- wynik: akcja zakonczona sukcesem
Dodanie klucza 0003 [40003]- wynik: akcja zakonczona sukcesem
-----------------------------
( . . . )
-----------------------------
Poszukiwanie klucza 0001 - wynik: 10001: akcja zakonczona sukcesem
Poszukiwanie klucza 0001 - wynik: 20001: akcja zakonczona sukcesem
Poszukiwanie klucza 0001 - wynik: 30001: akcja zakonczona sukcesem
Poszukiwanie klucza 0001 - wynik: 40001: akcja zakonczona sukcesem
Poszukiwanie klucza 0002 - wynik: 10002: akcja zakonczona sukcesem
Poszukiwanie klucza 0002 - wynik: 20002: akcja zakonczona sukcesem
Poszukiwanie klucza 0002 - wynik: 30002: akcja zakonczona sukcesem
Poszukiwanie klucza 0002 - wynik: 40002: akcja zakonczona sukcesem
Poszukiwanie klucza 0003 - wynik: 10003: akcja zakonczona sukcesem
Poszukiwanie klucza 0003 - wynik: 20003: akcja zakonczona sukcesem
Poszukiwanie klucza 0003 - wynik: 30003: akcja zakonczona sukcesem
Poszukiwanie klucza 0003 - wynik: 40003: akcja zakonczona sukcesem
( . . . )

Wydruk zawartosci drzewa BTREE
   Key: 0001, dataref=10001
              dataref=20001
              dataref=30001
              dataref=40001
   Key: 0002, dataref=10002
              dataref=20002
              dataref=30002
              dataref=40002
( . . . )


Całość softu (projekt w Dev C):
btree03.7z
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse

Awatar użytkownika
gaweł
Geek
Geek
Posty: 1259
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

Re: B-drzewa

Postautor: gaweł » środa 25 gru 2019, 19:03

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:

Kod: Zaznacz cały

  InitMyFileStructure ( ) ;
  InitStandBTree ( & BTreeInstance , NIL , NIL ) ;
  BTreeInstance . OpenFileServ = PrivateOpenFile ;
  BTreeInstance . CloseFileServ = PrivateCloseFile ;
  BTreeInstance . LockFileServ = PrivateLockTotalFile ;
  BTreeInstance . UnLockFileServ = PrivateUnLockTotalFile ;
  BTreeInstance . AppendFileServ = PrivateAppendFile ;
  BTreeInstance . ReadFileServ = PrivateReadFile ;
  BTreeInstance . WriteFileServ = PrivateWriteFile ;
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):

Kod: Zaznacz cały

static ULONG FileInx ;
static UCHAR FileBody [ 0x10000 ] ;

static void InitMyFileStructure ( void )
{
  for ( FileInx = 0 ; FileInx < 0x10000 ; FileInx ++ )
    FileBody [ FileInx ] = 0 ;
  FileInx = sizeof ( FirstInxRecT ) ;
} /* InitMyFileStructure */
Operacje otwarcia i zamknięcia pliku w „nowym świecie” wyglądają następująco:

Kod: Zaznacz cały

static void _cdecl PrivateOpenFile ( PtrAPFILE File ,
                                     UCHAR *   FileName ,
                                     USHORT    OpenMode ,
                                     USHORT    WaitMode )
{
  /*----------------------------------------------------*/
  File -> file_Answer = 0 ;
  File -> file_Handle = ( FHandle ) 1 ;
} /* PrivateOpenFile */


static void _cdecl PrivateCloseFile ( PtrAPFILE File )
{
  /*----------------------------------------------------*/
  File -> file_Answer = 0 ;
  File -> file_Handle = ( FHandle ) 0xFFFF ;
} /* PrivateCloseFile */

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:

Kod: Zaznacz cały

static void _cdecl PrivateLockTotalFile ( PtrAPFILE File ,
                                          USHORT    LockingMode ,
                                          ULONG     Position ,
                                          USHORT    Size ,
                                          USHORT    WaitMode )
{
  /*----------------------------------------------------*/
  File -> file_Answer = 0 ;
} /* PrivateLockTotalFile */


static void _cdecl PrivateUnLockTotalFile ( PtrAPFILE File ,
                                            ULONG     Position ,
                                            USHORT    Size )
{
  /*----------------------------------------------------*/
  File -> file_Answer = 0 ;
} /* PrivateUnLockTotalFile */
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:

Kod: Zaznacz cały

static void _cdecl PrivateAppendFile ( PtrAPFILE File ,
                                       ADDRESS   BuffAdr ,
                                       USHORT    Size ,
                                       USHORT    WaitMode )
{
  UCHAR * Destination ;
  UCHAR * Source ;
  /*----------------------------------------------------*/
  File -> file_Answer = 0 ;
  File -> file_Pointer = FileInx ;
  Destination = FileBody + FileInx ;
  FileInx += Size ;
  Source = ( UCHAR * ) BuffAdr ;
  while ( Size )
  {
    * Destination ++ = * Source ++ ;
    Size -- ;
  } /* while */
} /* AppendFile */
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).

Kod: Zaznacz cały

static void _cdecl PrivateReadFile ( PtrAPFILE File ,
                                     ADDRESS   BuffAdr ,
                                     USHORT    Size ,
                                     ULONG     SeekPos ,
                                     USHORT    WaitMode )
{
  UCHAR * Destination ;
  UCHAR * Source ;
  /*----------------------------------------------------*/
  Source = FileBody + SeekPos ;
  Destination = ( UCHAR * ) BuffAdr ;
  while ( Size )
  {
    * Destination ++ = * Source ++ ;
    Size -- ;
  } /* while */
  File -> file_Answer = 0 ;
  File -> file_Pointer = SeekPos ;
} /* ReadFile */


static void _cdecl PrivateWriteFile ( PtrAPFILE File ,
                                      ADDRESS   BuffAdr ,
                                      USHORT    Size ,
                                      ULONG     SeekPos ,
                                      USHORT    WaitMode )
{
  UCHAR * Destination ;
  UCHAR * Source ;
  /*----------------------------------------------------*/
  Destination = FileBody + SeekPos ;
  Source = ( UCHAR * ) BuffAdr ;
  while ( Size )
  {
    * Destination ++ = * Source ++ ;
    Size -- ;
  } /* while */
  File -> file_Answer = 0 ;
  File -> file_Pointer = SeekPos ;
} /* WriteFile */
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.
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse

Awatar użytkownika
gaweł
Geek
Geek
Posty: 1259
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

Re: B-drzewa

Postautor: gaweł » niedziela 29 gru 2019, 13:12

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:

Kod: Zaznacz cały

#include <iostream>
#include <stdlib.h>
#include "TBTREETY.H"
#include "TBTREEFI.H"
#include "TBTREEPL.H"
#include "TINBTREE.H"
#include "TOUTBTRE.H"
#include "TBTREEDE.H"
#include "TSTRINGS.H"
#include "STRINGS.H"

#define EndLoop    16
#define EndLoop2   8
#define DuplLimit  4
#define AddVal     10000

#define AllocPage(x,y) ( PtrBTPageT ) LocalAlloc ( x , y )
#define AllocFPage(x) ( PtrFirstInxRecT ) LocalAlloc ( sizeof ( FirstInxRecT ) , x )
#define NotReady(x) ! ( Ready & x )


static void Tree2 ( UCHAR *              SupKey ,
                    ULONG                Entry ,
                    USHORT               KeyLength ,
                    USHORT               Pagesize ,
                    USHORT               Itemsize ,
                    PtrAPFILE            IndexFile ,
                    PtrIndexDescr        InxDescr ,
                    PtrBTreeInstanceRecT BTreeInstance )
{
  ULONG DuplEntry ;
  USHORT CurrPos ;
  USHORT ReplyWord ;
  USHORT Loop ;
  PtrBTPageT CurrPage ;
  PtrBTItemT CurrItem ;
  DuplPageType DuplPage ;
  UCHAR Key [ 32 ] ;
  /*--------------------------------------------------------------------------*/
  if ( Entry != BTreeNil )
  {
    CurrPage = AllocPage ( Pagesize , BTreeInstance ) ;
    BTreeInstance -> GetPageServ ( IndexFile , CurrPage , Entry , Pagesize ,
                                   & ReplyWord , BTreeInstance ) ;
    Tree2 ( SupKey , CurrPage -> BackwardPage , KeyLength , Pagesize , Itemsize ,
           IndexFile , InxDescr , BTreeInstance ) ;
    for ( CurrPos = 1 ; CurrPos <= CurrPage -> ItemsOnPage ; CurrPos ++ )
    {
      CurrItem = ItemAddress ( CurrPage -> ItemArray , CurrPos , Itemsize ) ;
      for ( Loop = 0 ; Loop < 32 ; Loop ++ )
        Key [ Loop ] = 0 ;
      for ( Loop = 0 ; Loop < KeyLength ; Loop ++ )
        Key [ Loop ] = CurrItem -> Key [ Loop ] ;
      printf ( "   Key: %s, %s, dataref=%lu\n" , SupKey , Key , CurrItem -> DataRef ) ;
      DuplEntry = CurrItem -> DuplicatePage ;
      while ( DuplEntry != BTreeNil )
      {
        BTreeInstance -> GetPageServ ( IndexFile , & DuplPage , DuplEntry , sizeof ( DuplPageType ) ,
                                       & ReplyWord , BTreeInstance ) ;
        printf ( "                    dataref=%lu\n" , DuplPage . DataRef ) ;
        DuplEntry = DuplPage . ForwardPage ;
      } /* while */ ;
      Tree2 ( SupKey , CurrItem -> ForwardPage , KeyLength , Pagesize , Itemsize ,
              IndexFile , InxDescr , BTreeInstance ) ;
    } /* for */ ;
  } /* if ... else */ ;
} /* Tree2 */


static void Tree ( ULONG                Entry ,
                   USHORT               KeyLength ,
                   USHORT               Pagesize ,
                   USHORT               Itemsize ,
                   PtrAPFILE            IndexFile ,
                   PtrIndexDescr        InxDescr ,
                   PtrBTreeInstanceRecT BTreeInstance )
{
  USHORT CurrPos ;
  USHORT ReplyWord ;
  USHORT Loop ;
  PtrBTPageT CurrPage ;
  PtrBTItemT CurrItem ;
  UCHAR Key [ 32 ] ;
  /*--------------------------------------------------------------------------*/
  if ( Entry != BTreeNil )
  {
    CurrPage = AllocPage ( Pagesize , BTreeInstance ) ;
    BTreeInstance -> GetPageServ ( IndexFile , CurrPage , Entry , Pagesize ,
                                   & ReplyWord , BTreeInstance ) ;
    Tree ( CurrPage -> BackwardPage , KeyLength , Pagesize , Itemsize ,
           IndexFile , InxDescr , BTreeInstance ) ;
    for ( CurrPos = 1 ; CurrPos <= CurrPage -> ItemsOnPage ; CurrPos ++ )
    {
      CurrItem = ItemAddress ( CurrPage -> ItemArray , CurrPos , Itemsize ) ;
      for ( Loop = 0 ; Loop < 32 ; Loop ++ )
        Key [ Loop ] = 0 ;
      for ( Loop = 0 ; Loop < KeyLength ; Loop ++ )
        Key [ Loop ] = CurrItem -> Key [ Loop ] ;
      Tree2 ( Key , CurrItem-> DataRef , InxDescr -> InfKeyLgt ,
              InxDescr -> InfPageLgt , 
              ItemSize ( InxDescr -> InfKeyLgt ) , IndexFile ,
              InxDescr , BTreeInstance ) ;
      Tree ( CurrItem -> ForwardPage , KeyLength , Pagesize , Itemsize ,
             IndexFile , InxDescr , BTreeInstance ) ;
    } /* for */ ;
  } /* if ... else */ ;
} /* Tree */


static void PrintTree ( PtrAPFILE            IndexFile ,
                        PtrIndexDescr        InxDescr ,
                        PtrBTreeInstanceRecT BTreeInstance )
{
  USHORT Itemsize ;
  USHORT Pagesize ;
  USHORT ReplyWord ;
  PtrFirstInxRecT FirstBuck ;
  /*--------------------------------------------------------------------------*/
  printf ( "\n\nWydruk zawartosci drzewa BTREE\n" ) ;
  CreateMemory ( BTreeInstance ) ;
  FirstBuck = AllocFPage ( BTreeInstance ) ;
  GInfoPage ( IndexFile , FirstBuck , & ReplyWord , BTreeInstance ) ;
  if ( NotReady ( ReplyWord ) )
  {
    FreeMemory ( BTreeInstance ) ;
    return ;
  } /* if */ ;
  Itemsize = ItemSize ( InxDescr -> SupKeyLgt ) ;
  Pagesize = InxDescr -> SupPageLgt ;
  if ( FirstBuck -> TopPage == BTreeNil )
    printf ( "Drzewo jest puste\n" ) ;
  else
    Tree ( FirstBuck -> TopPage , InxDescr -> SupKeyLgt ,
           Pagesize , Itemsize , IndexFile , InxDescr , BTreeInstance ) ;
  FreeMemory ( BTreeInstance ) ;
} /* PrintTree */


int main ( int argc , char** argv )
{
  BTreeInstanceRecT BTreeInstance ;
  APFILE Index ;
  IndexDescr Description ;
  ResponseAreaType AA ;
  USHORT Reply ;
  USHORT Loop ;
  USHORT Loop2 ;
  USHORT IntLoop ;
  ULONG BaseEntry ;
  UCHAR Number[10];
  UCHAR Number2[10];
  UCHAR Number3[10];
  /*--------------------------------------------------------------------------*/
  InitStandBTree ( & BTreeInstance , NIL , NIL ) ;
  Reply = CreateIndex ( ( UCHAR * ) "TBTREE1.INX" , 4 , 4 , 0 ,
                        TRUE , TRUE , TRUE ,
                        TRUE , TRUE , TRUE , 3 , 3 , 0 , & BTreeInstance ) ;
  Reply = OpenIndex ( & Index , Commune_Open_Mode , ( UCHAR * ) "TBTREE1.INX" ,
                      & Description , & BTreeInstance ) ;
  for ( Loop = 1 ; Loop <= EndLoop ; Loop ++ )
  {
    BaseEntry = ( ULONG ) Loop + ( ULONG ) AddVal ;
    UCardToStr ( Number , 4 , '0' , Loop ) ;
    for ( IntLoop = 0 ; IntLoop < 4 ; IntLoop ++ )
    {
      Number2 [ IntLoop ] = Number [ IntLoop ] + 17 ;
    } /* for */ ;
    Number2 [ 4 ] = 0 ;
    for ( Loop2 = 1 ; Loop2 <= EndLoop2 ; Loop2 ++ )
    {
      UCardToStr ( Number3 , 4 , '0' , Loop2 ) ;
      for ( IntLoop = 0 ; IntLoop < 4 ; IntLoop ++ )
      {
        Number2 [ IntLoop ] = Number3 [ IntLoop ] + 17 ;
      } /* for */ ;
      Number2 [ 4 ] = 0 ;
      for ( IntLoop = 1 ; IntLoop < DuplLimit ; IntLoop ++ )
      {
        ULCardToStr ( Number3 , 5 , ' ' , BaseEntry ) ;
        AddKey2 ( & Index , Number , Number2 , & Description , BaseEntry , & Reply , & BTreeInstance ) ;
        if ( ! ( Ready & Reply ) )
        {
          printf ( "Dodanie kluczy %s, %s dataref=%s- wynik: nie powiodlo sie\n" , Number , Number2 , Number3 ) ;
        } /* if ... */
        else
        {
          printf ( "Dodanie kluczy %s, %s dataref=%s- wynik: akcja zakonczona sukcesem\n" , Number , Number2 , Number3 ) ;
        } /* if ... else */ ;
        BaseEntry += ( ULONG ) AddVal ;
      } /* for */ ;
    } /* for */ ;
    printf ( "-----------------------------\n" ) ;
  } /* for */ ;
  for ( Loop = 1 ; Loop <= EndLoop ; Loop ++ )
  {
    UCardToStr ( Number , 4 , '0' , Loop ) ;
    for ( IntLoop = 0 ; IntLoop < 4 ; IntLoop ++ )
    {
      Number2 [ IntLoop ] = Number [ IntLoop ] + 17 ;
    } /* for */ ;
    Number2 [ 4 ] = 0 ;
    SearchKey12 ( & Index , Number , Number2 , & Description , & AA , & BTreeInstance ) ;
    for ( ; ; )
    {
      if ( ! ( Ready & AA . Reply ) )
      {
        break ;
      } /* if ... */
      else
      {
        ULCardToStr ( Number3 , 5 , ' ' , AA . DataPos ) ;
        printf ( "Poszukiwaniy klucza %s, %s, dataref= %s- wynik akcja zakonczona sukcesem\n" , Number , Number2 , Number3 ) ;
      } /* if ... else */ ;
      SearchDuplKey ( & Index , & Description , & AA , & BTreeInstance ) ;
    } /* for */ ;
  } /* for */ ;
  PrintTree ( & Index , & Description , & BTreeInstance ) ;
  for ( Loop = 1 ; Loop <= EndLoop ; Loop ++ )
  {
    BaseEntry = ( ULONG ) Loop + ( ULONG ) AddVal ;
    UCardToStr ( Number , 4 , '0' , Loop ) ;
    for ( IntLoop = 0 ; IntLoop < 4 ; IntLoop ++ )
    {
      Number2 [ IntLoop ] = Number [ IntLoop ] + 17 ;
    } /* for */ ;
    Number2 [ 4 ] = 0 ;
    for ( Loop2 = 1 ; Loop2 <= EndLoop2 ; Loop2 ++ )
    {
      UCardToStr ( Number3 , 4 , '0' , Loop2 ) ;
      for ( IntLoop = 0 ; IntLoop < 4 ; IntLoop ++ )
      {
        Number2 [ IntLoop ] = Number3 [ IntLoop ] + 17 ;
      } /* for */ ;
      Number2 [ 4 ] = 0 ;
      for ( IntLoop = 1 ; IntLoop < DuplLimit ; IntLoop ++ )
      {
        ULCardToStr ( Number3 , 5 , ' ' , BaseEntry ) ;
        DelKey2 ( & Index , Number , Number2 , & Description , BaseEntry , & Reply , & BTreeInstance ) ;
        if ( ! ( Ready & Reply ) )
        {
          printf ( "Usunicie kluczy %s, %s, dataref= %s- wynik nie powiodlo sie\n" , Number , Number2 , Number3 ) ;
        } /* if ... */
        else
        {
          printf ( "Usunicie kluczy %s, %s, dataref= %s- wynik akcja zakonczona sukcesem\n" , Number , Number2 , Number3 ) ;
        } /* if ... else */ ;
        BaseEntry += ( ULONG ) AddVal ;
      } /* for */ ;
    } /* for */ ;
    printf ( "-----------------------------\n" ) ;
  } /* for */ ;
  PrintTree ( & Index , & Description , & BTreeInstance ) ;
  CloseIndex ( & Index , & BTreeInstance ) ;
  return 0 ;
} /* main */
Z istotnych elementów w programie jest:

Kod: Zaznacz cały

  Reply = CreateIndex ( ( UCHAR * ) "TBTREE1.INX" , 4 , 4 , 0 ,
                        TRUE , TRUE , TRUE ,
                        TRUE , TRUE , TRUE , 3 , 3 , 0 , & BTreeInstance ) ;
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:

Kod: Zaznacz cały

Dodanie kluczy 0001, AAAB dataref=10001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAB dataref=20001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAB dataref=30001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAC dataref=40001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAC dataref=50001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAC dataref=60001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAD dataref=70001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAD dataref=80001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAD dataref=90001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAE dataref=00001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAE dataref=10001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAE dataref=20001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAF dataref=30001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAF dataref=40001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAF dataref=50001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAG dataref=60001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAG dataref=70001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAG dataref=80001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAH dataref=90001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAH dataref=00001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAH dataref=10001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAI dataref=20001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAI dataref=30001- wynik: akcja zakonczona sukcesem
Dodanie kluczy 0001, AAAI dataref=40001- wynik: akcja zakonczona sukcesem
( . . . )
Poszukiwaniy klucza 0001, AAAB, dataref= 10001- wynik akcja zakonczona sukcesem
Poszukiwaniy klucza 0001, AAAB, dataref= 20001- wynik akcja zakonczona sukcesem
Poszukiwaniy klucza 0001, AAAB, dataref= 30001- wynik akcja zakonczona sukcesem
( . . . )

Wydruk zawartosci drzewa BTREE
   Key: 0001, AAAB, dataref=10001
                    dataref=20001
                    dataref=30001
   Key: 0001, AAAC, dataref=40001
                    dataref=50001
                    dataref=60001
   Key: 0001, AAAD, dataref=70001
                    dataref=80001
                    dataref=90001
   Key: 0001, AAAE, dataref=100001
                    dataref=110001
                    dataref=120001
   Key: 0001, AAAF, dataref=130001
                    dataref=140001
                    dataref=150001
   Key: 0001, AAAG, dataref=160001
                    dataref=170001
                    dataref=180001
   Key: 0001, AAAH, dataref=190001
                    dataref=200001
                    dataref=210001
   Key: 0001, AAAI, dataref=220001
                    dataref=230001
                    dataref=240001
( . . . )
Usunicie kluczy 0001, AAAB, dataref= 10001- wynik akcja zakonczona sukcesem
Usunicie kluczy 0001, AAAB, dataref= 20001- wynik akcja zakonczona sukcesem
Usunicie kluczy 0001, AAAB, dataref= 30001- wynik akcja zakonczona sukcesem
Usunicie kluczy 0001, AAAC, dataref= 40001- wynik akcja zakonczona sukcesem
Usunicie kluczy 0001, AAAC, dataref= 50001- wynik akcja zakonczona sukcesem
Usunicie kluczy 0001, AAAC, dataref= 60001- wynik akcja zakonczona sukcesem
Usunicie kluczy 0001, AAAD, dataref= 70001- wynik akcja zakonczona sukcesem
( . . . )

Wydruk zawartosci drzewa BTREE
Drzewo jest puste
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ń.
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse

Awatar użytkownika
gaweł
Geek
Geek
Posty: 1259
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

Re: B-drzewa

Postautor: gaweł » poniedziałek 30 gru 2019, 04:12

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:

Kod: Zaznacz cały

USHORT
   ccrossref.c                      137  234  235  236  240  241  242  292  293  294  297  298  299  333
                                    334  335  358  391  392  477  504  562
   CSYSTYPE.H                        29
   lexicalanal.C                     58   87  118  248
   lexicalanal.h                     51   52   66   80   81   82   83   84   86   87
   STRINGS.C                        421  422  441  453  457  458  476  503  525  547  568  573  596  600
                                    628  632  655  683  696  698  725  727  729  762  764  767  816  817
                                    821
   STRINGS.H                         29   30   35   39   41   45   49   58   63   66   70   79   81   83
                                     85   87   91   92
   SYSCALLS.C                        57   63   77   78   86  181  182  249  251  252  288  319  320  343
                                    345  387  389  431  432  471  472  517  523  525  537  570  573  696
   SYSCALLS.H                        38   40   49   56   57   58   59   78   79   88   89   94   96   97
                                    101  105  106  110  112  116  118  122  123  127  128  132  134  140
                                    143  148  149  150  151  152  153  168  169
   TBTREEFI.C                        41   42   46   50   63   63   64   67   68   77   78   79   80   81
                                     82   83   84   85   86   87   88   89   94  130  131  135  136  166
                                    167  168  169  170  171  172  173  174  175  176  177  178  182  183
   TBTREEFI.H                        30   31   34   35   36   37   38   39   40   41   42   43   44   45
                                     46   49   50   53   54   55   56   57   58   59   60   61   62   63
                                     64   65
   TBTREEPL.C                        27   28   30   33   41   42   47
   TBTREEPL.H                        29   30   32   35   36
   TBTREETY.C                       295  309  321  321  338  339  355  357  358  367  376  377  386  388
                                    397  399  419  422  437  440  455  465  475  477  478  482  507  514
                                    517  521  570  571  574  591  592  595  612  613  616  633  634  637
                                    653  654  657  673  674  677  693  694  695  702  712  713  732  733
                                    768  786  797  808  819  828  828  839  840  848  849  850  886  892
                                    902  923  938  939  940  941  952  953  954  955  966  967  968  969
                                    981  982
   TBTREETY.H                        44   45   46   47   48   49   50   51   52   53   54   55   56   57
                                     58   59   60   61   70   71   72   78   88  103  104  112  118  119
                                    130  142  146  148  149  153  156  165  166  171  172  177  178  179
                                    182  188  189  194  196  197  201  205  206  210  212  248  249  258
                                    261  263  263  267  272  277  282  285  285  288  289  292  293  294
                                    300  304  308  309  310  311  314  315  316  317  320  321  322  323
   TINBTREE.C                        37   38   39   41   44   45   48   49   50  151  152  153  154  190
                                    191  192  193  233  234  235  236  308  339  341  359
   TINBTREE.H                        69   71
   TOUTBTRE.C                        37   38   39   40   41   42   50   51   63   64   65  140  153  156
                                    201  213  218  234  247  280  389  439  452  455  497  500  513  524
                                    553  557  695  696  747  760  763  806  809  822  833  862  866  884
                                    977 1004 1005 1013 1098 1115 1133 1147 1149 1152 1155 1165 1217 1219
                                   1222 1223 1234
   TOUTBTRE.H                        33   41   50   55   57   62   64
   TSTRINGS.C                        46   55   57   59   77   78   86   88   90   98  108  109  117  121
                                    139  148  152  160  170  179  183  184  213  222  226  227  256  264
                                    265  269  287  314  343  344  349  350  351  352  435  436  451  457
                                    466  467  469  476  489  490  492  499  499  506  521  544  575  578
                                    613  616  651  657  658  720  726  727  728  729
   TSTRINGS.H                        29   31   34   35   38   40   43   44   47   52   56   61   65   70
                                     74   79   83   84   90   91   97   98  100  101  104  107  110  113
                                    116  119
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).
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse


Wróć do „DIY”

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 3 gości