Struktura bazy oraz podstawowe założenia.

Do analizy wykorzystałem następujące drzewko:

0            SYSTEMY OPERACYJNE
           /                    \
1     LINUX                    WINDOWS
     /      \               /           \
2  SLACK   DEBIAN         NT              NO NT
                        /   \         /      |    \
3                WIN 2000 WIN XP   WIN 95  WIN 98  WIN MILENIUM

Postanowiłem umieścić cala strukturę w jednej tabeli. Tabela zawierała id elementu, nazwę elementu oraz opis zajmowanej pozycji w kolumnie level.

Wyglądało to tak:

+----+--------------+---------+
| id | name         | level   |
+----+--------------+---------+
| 55 | Win 2000     | 1210000 |
| 54 | Win Milenium | 1130000 |
| 53 | Win 98       | 1120000 |
| 51 | NT           | 1200000 |
| 52 | Win 95       | 1110000 |
| 49 | NO NT        | 1100000 |
| 48 | linuks       | 2000000 |
| 47 | windows      | 1000000 |
| 46 | systems      | 0000000 |
| 57 | Win 2003     | 1230000 |
| 56 | Win XP       | 1220000 |
| 61 | Slack        | 2100000 |
| 62 | Debian       | 2200000 |
+----+--------------+---------+

O ile zawartości dwóch pierwszych kolumn nie musze tłumaczyć to należy zrozumieć działanie kolumny level. Ma ona za zadanie opisać pozycje danej grupy w drzewie. Składa się ona z góry ustalonej liczbie cyfr. Ilości cyfr zależy od maksymalnego poziomu zagnieżdżenia, jaki chcemy uzyskać. Zmienia się ona zawsze w zależności [liczba cyfr] = [poziom zagnieżdżenia] + 2.

Format levelu można opisać w sposób następujący. Ciąg cyfr 1 - 9 i reszta zer ("/^[1-9]+0+0{1}$/"). Taki format jest bardzo wygodny, kiedy dochodzi do operacji na danych, o czym przekonacie się później. Ciąg cyfr określa pozycję danej wartości w hierarchii drzewa. Każda następna cyfra różna od zera od lewej, reprezentuje ścieżkę, jaka trzeba przebyć, aby dojść do wartości. Ostatnia cyfra różna od zera reprezentuje to, którym dzieckiem z kolei jest dana wartość. Weźmy na przykład wartość "WIN 98" ma ona, level, 112 czyli aby dojść do tej wartości należy przejść przez wartość 1000000 (Windows) oraz 1100000 (NO NT). Dodatkowo na początku zawsze dodajemy korzeń 0000000 ("SYSTEMY OPERACYJNE"). W ten sposób uzyskaliśmy prosta ścieżkę:

SYSTEMY OPERACYJNE -> WINDOWS -> NO NT -> WIN 98.

Wiec, po co jeszcze następna wartość liczby przypisana do levelu? Otóż jest to informacja dla ewentualnych dzieci "WIN 98". Jeśli chcieli byśmy do grupy "WIN 98" dodać dziecko "SECOND EDICTION" to nie wystarczy nam level 1100000 ponieważ po wartości "NO NT" zgubilibyśmy ścieżkę i nie odnaleźlibyśmy wartości "WIN 98". Dzięki dodatkowej informacji jesteśmy w stanie stworzyć ścieżkę dla, WINDOWS SE, która wyglądałaby tak: 112+1(numer dla grupy SE)+000. W ten sposób można opisać zależności dla maksymalnie 9 dzieci danego rodzica. Ujawnia się tu pierwsze ograniczenie tej metody - dany rodzic może posiadać tylko dziewięcioro dzieci. Można ten problem ominąć, ale o tym później.

Wspomniałem, że przed uzyskaną ścieżką dopisujemy jeszcze jedna wartość hierarchii - 0000000. Jest to powodowane tym, iż level = 0000000 odpowiada głównemu rodzicowi drzewa, który reprezentuje cala resztę jako korzeń. Ta wartość jest wyjątkiem od zasad, które się tyczą już jej wszystkich dzieci.

Zauważmy, że w ten sposób "zajmujemy" całą tabelę na potrzeby tylko jednego drzewka. Nie jest to zbyt wygodne jeśli chcemy tworzyć więcej drzew niezależnych od siebie. Dodałem wiec kolumnę cluster ( grupa ) która oddziela poszczególne drzewka przez nadanie każdemu indywidualnego numeru. Nie jest to konieczne jeśli chcemy użyć tylko jednego drzewa do obsługi np. systemu nawigacyjnego strony.

Ostatecznie więc struktura bazy wygląda następująco:

#
# Table structure for table `groups`
#

CREATE TABLE `groups` (
`id` int(11) NOT NULL auto_increment,
`cluster` int(11) NOT NULL default '0',
`name` varchar(100) NOT NULL default '',
`level` decimal(10,0) NOT NULL default '0',
UNIQUE KEY `id` (`id`)
) TYPE=MyISAM;

#
# Dane do ćwiczeń
#

INSERT INTO `groups` VALUES (55, 1, 'Win 2000', '1210000');
INSERT INTO `groups` VALUES (54, 1, 'Win Milenium', '1130000');
INSERT INTO `groups` VALUES (53, 1, 'Win 98', '1120000');
INSERT INTO `groups` VALUES (51, 1, 'NT', '1200000');
INSERT INTO `groups` VALUES (52, 1, 'Win 95', '1110000');
INSERT INTO `groups` VALUES (49, 1, 'NO NT', '1100000');
INSERT INTO `groups` VALUES (48, 1, 'linuks', '2000000');
INSERT INTO `groups` VALUES (47, 1, 'windows', '1000000');
INSERT INTO `groups` VALUES (46, 1, 'systems', '0000000');
INSERT INTO `groups` VALUES (57, 1, 'Win 2003', '1230000');
INSERT INTO `groups` VALUES (56, 1, 'Win XP', '1220000');
INSERT INTO `groups` VALUES (61, 1, 'Slack', '2100000');
INSERT INTO `groups` VALUES (62, 1, 'Debian', '2200000');

#
# select * from groups
#

+----+---------+--------------+---------+
| id | cluster | name         | level   |
+----+---------+--------------+---------+
| 64 |       1 | Windows Ce   | 1300000 |
| 55 |       1 | Win 2000     | 1210000 |
| 54 |       1 | Win Milenium | 1130000 |
| 53 |       1 | Win 98       | 1120000 |
| 51 |       1 | NT           | 1200000 |
| 52 |       1 | Win 95       | 1110000 |
| 49 |       1 | NO NT        | 1100000 |
| 48 |       1 | linuks       | 2000000 |
| 47 |       1 | windows      | 1000000 |
| 46 |       1 | systems      | 0000000 |
| 57 |       1 | Win 2003     | 1230000 |
| 56 |       1 | Win XP       | 1220000 |
| 61 |       1 | Slack        | 2100000 |
| 62 |       1 | Debian       | 2200000 |
+----+---------+--------------+---------+