struktura drzewiasta Opcje

[lukier]

chciałbym skonsultować pewien mój pomysł odnośnie trzymania i zarządzania artykułami w bazie (CMS), wymyśliłem coś takiego:

tabela articles, pola:
id INT (PK)
parent INT - id ojca artykułu, badź null gdy strona głowna
children TEXT - id dzieci artykułu separowane dwukropkami, badź pusto
typ INT - typ (artykuł, dział, link do innego id itp)
autor INT, tytul TEXT itp

łatwo jest to prezentować jako drzewko w panelu administracyjnym strony,
łatwo też wygenerować "pasek nawigacyjny" na stronie lecz chciałbym
poznać opinie forumowiczów odnośnie takiego rozwiązania

[bela]

Spójrz na wortal, eZ ma możliwość zagnieżdzania folderów w których są trzymane miedzy innymi artykuły. To rozwiązanie jest chyba we wszystkich CMSach ( nie systemach portalowych )

Najlepiej poczytaj o drzewkach, bo z twoim rozwiązaniem to będzie trzeba wykonywać za każdym razem zapytanie o wyższy poziom. Po co trzymać dane o dzieciach ?

Ja się osobiście przychylam koncepcji, że wszystko jest treścią i tylko różny jest sposób jej prezentacji. Treść trzymam w XMLu i sobie później przekształcam do porządanego kształtu ( RSS, PDF, XHTML etc ), następnie to keszuje, bo przetwarzanie XML w php jest powolne.

Mam tzn chcialbym miec zaimplementowane Mam w planach

[lukier]

o dzewkach czytałem troche (Cormen,Knuth) lecz nie przepadam za akademickim
podejściem (bo na uczelni drzewo to nie drzewo a spójny acykliczny graf nieskierowany)

trzymanie danych o dzieciach jest o tyle przydatne że
moge sobie łazic po drzewku w góre i w dół oraz zapisywać kolejność pod-węzłów
(te operacje są szczególnie wykożystywane w panelu. adm witryny)

oczywiscie można by miec tylko id - parent a zeby mieć dzieci robic wymyśne selecty
lecz wtedy nie ma takiej swobody i tracimy pewną częśc informacji

np moge mieć:

ArtA:
- ArtP
- ArtW
- ArtC

a nie z select orderby jakims:

ArtA:
- ArtC
- ArtP
- ArtW

to jest o tyle ważne ze gdy typ artykułu = dzial to jego dzieci mogą być
prezentowane jako taki "spis treści"

hm mam jeszcze jedno pytanie, otoz zrobilem wlasnie swego rodzaju parser w php
w witrynie, polega to na tym ze gdy ktos w panelu adm. wpisze w treści artykułu np:
@@NEWSY@@
albo
@@SUBARTICLES@@
to odpowiednie rzeczy zamiast tego sie wstawią,
tylko ze ta cała machina parsera jest uruchamiana co odświeżenie strony, robic
jakis cache czy inne metody stosować?

[halfik]

children TEXT - id dzieci artykułu separowane dwukropkami, badź pusto

to u gory nie jest specjalnie estetyczne. ja bym to upcahl do osobnej tabeli jesli juz musialbym trzymac id "dzieci".

a o drzewkach jzu gdzeis bylo na forum i tam tez byl link do dobrego artykulu w sprawie.

p.s knutha to mozna pociskac studentom ze niby to czy tamto, ale to hala jest. multum teorii, durnych wzorow etc. po cholere pisac ksiazke ceglowke jak mozna to opisac prosciej na kilkudziesieciu stronach, co by przecietny kowalski nawet zrozumial? walic teoretykow

[bendi]

a o drzewkach jzu gdzeis bylo na forum i tam tez byl link do dobrego artykulu w sprawie.

bylo bylo bylo

[hawk]

o dzewkach czytałem troche (Cormen,Knuth) lecz nie przepadam za akademickim
podejściem (bo na uczelni drzewo to nie drzewo a spójny acykliczny graf nieskierowany)

No i co z tego? Drzewo naprawdę jest grafem, uwierz mi .
Można sobie narzekać, ale to teoretycy wymyślają algorytmy operowania na drzewach. Gdzie byłyby bazy danych gdyby nie opracowano algorytmów B-drzewa?
Jak myślisz, kto pracuje np. w Oraclu nad rozwojem silnika? Na pewno nie programiści.

[lukier]

No i co z tego? Drzewo naprawdę jest grafem, uwierz mi .
Można sobie narzekać, ale to teoretycy wymyślają algorytmy operowania na drzewach. Gdzie byłyby bazy danych gdyby nie opracowano algorytmów B-drzewa?
Jak myślisz, kto pracuje np. w Oraclu nad rozwojem silnika? Na pewno nie programiści.

doskonale o tym wiem że drzewo jest grafem, nie mam nic przeciwko algorytmom
wręcz przeciwnie , po prostu nie przepadam za akademickim niepotrzebnym komplikowaniem różnych rzeczy, na uczelni nie działa chyba brzytwa Ockhama

to jest cos w stylu : matematyk na uczelni nie umie dodawać , umie tylko całkować
oczywiście po przeczytaniu paru grubych tomisk niektórzy popadaja w taki samozachwyt : "znam trudne słowa jestem więc mądry"

keep it simple

[Krolik]

Jak myślisz, kto pracuje np. w Oraclu nad rozwojem silnika? Na pewno nie programiści.

Maly OT: W Oraclu nie wiem jak jest, ale znam goscia, ktory pracuje nad DB/2. No i wyglada to tak, ze najpierw jakis doswiadczony projektant, zwykle doktor lub wyzej, wpada na jakis genialny pomysl wprowadzenia nowej optymalizacji. Pozniej daje sie ten pomysl zespolowi studentow i maja go ROZWINAC, ZAPROJEKTOWAC, ZAPROGRAMOWAC i PRZETESTOWAC. Jesli w testach wychodzi, ze dziala, to kod jest wlaczany do glownego strumienia projektu, do wersji komercyjnej. Jesli dziala slabo, to laduje na smietniku, a studenci robia inny kawalek kodu dla innego doktora... Tak czy siak wiekszosc kodu tworza studenci a wiekszosc pomyslow pochodzi z kregow naukowych.

[acztery]

[PHP] pobierz, plaintext 
<?
 
// url.class.php
$o=$_GET[&#092;"o\"];
$c=intval($_GET[&#092;"c\"]);
$start=intval($_GET[&#092;"start\"]);
$defaultorder=intval($cat[&#092;"defaultorder\"]);
if ($defaultorder<0 || $defaultorder>3) $defaultorder=0;
if (($o<0 && $o>3) || !isset($o)) $o=$defaultorder;
 
$r=mysql_query(&#092;"SELECT name,html FROM \".$db[\"prefix\"].\"templates;\") or die(mysql_error());
while ($a=mysql_fetch_assoc($r)) $TMPL[$a[&#092;"name\"]]=$a[\"html\"];
 
function ShowParts($cid) {
    GLOBAL $cat,$TMPL,$db;
 
    $r=mysql_query(&#092;"SELECT name,cid,count FROM \".$db[\"prefix\"].\"cat WHERE parent='$cid' ORDER BY name\") or die(mysql_error());
    $num=0;
    $cnt=mysql_num_rows($r);
    if ($cnt==0) return;
    print $TMPL[&#092;"partstop\"];
    for ($i=0;$i<$cnt;$i++) {
        $num++;
        if ($num==1) print $TMPL[&#092;"partsdelimtop\"];
 
        $template=$TMPL[&#092;"partsbit\"];
        $template=str_replace(&#092;"%CTITLE\",mysql_result($r,$i,0),$template);
        $template=str_replace(&#092;"%CID\",mysql_result($r,$i,1),$template);
        $template=str_replace(&#092;"%CCOUNT\",mysql_result($r,$i,2),$template);
        print $template;
            }
       
    }
    
    
    $pp=10;
    $cid=$c;$l=&#092;"\";
    do {
        $r=mysql_query(&#092;"SELECT parent,name,cid FROM \".$db[\"prefix\"].\"cat WHERE cid='$cid';\") or die(mysql_error());
        if (mysql_num_rows($r)==1) {
            $id=mysql_result($r,0,2);
            $title=mysql_result($r,0,1);
            if ($cid==$c)
                $l=mysql_result($r,0,1).$l;
            else
                $l=&#092;"<a class=bold href=./?c=\".$id.\">\".$title.\"</a> &raquo; \".$l;
            $cid=mysql_result($r,0,0);
            }
        else $cid=0;
        } while ($cid!=0);
    $r=mysql_query(&#092;"SELECT name FROM \".$db[\"prefix\"].\"cat WHERE cid='$c';\") or die(mysql_error());
    if (mysql_num_rows($r)!=0) $title=mysql_result($r,0,0).&#092;" / \".$CATNAME;
    else $title=$CATNAME;
 
 
 
?>
[PHP] pobierz, plaintext 

Wywołanie adresu :

[PHP] pobierz, plaintext 
<?php print &#092;"$CATNAME $l\"; ?>
[PHP] pobierz, plaintext 

Wywołanie drzewka

[PHP] pobierz, plaintext 
<? ShowParts($c); ?>
[PHP] pobierz, plaintext 

Struktura bazy

[SQL] pobierz, plaintext 
-- 
-- Struktura tabeli dla  `a4_cat`
-- 
 
CREATE TABLE `a4_cat` (
  `cid` int(11) NOT NULL AUTO_INCREMENT,
  `name` text,
  `parent` int(11) DEFAULT NULL,
  `count` int(11) DEFAULT '0',
  PRIMARY KEY  (`cid`)
) TYPE=MyISAM AUTO_INCREMENT=1212 ;
 
-- --------------------------------------------------------
 
-- 
-- Struktura tabeli dla  `a4_templates`
-- 
 
CREATE TABLE `a4_templates` (
  `name` varchar(16) NOT NULL DEFAULT '',
  `html` text NOT NULL,
  `parent` int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY  (`name`)
) TYPE=MyISAM;
[SQL] pobierz, plaintext 

w parametrze $c przenosiny Id kategori

To tyle jeśli chodzi o drzewka

Ten post edytował acztery 30.03.2005, 12:59:13

[hawk]

@acztery:

[acztery]

nie kumam ? coś źle?

[Vengeance]

@acztery: sorry, nie mam czasu zgłębiać się w kod (troche nieczytelny) ale mam pytanie. Ile zapytań generuje "to coś" przy np. 1000 rekordów (1000 zagniezdzonych kategorii). Bo widze ze tam jakies zapytania w petli wywolujesz, co jest tragiczne przy duzych ilosciach danych :]

[acztery]

zobacz jak działa w niegotowym jeszcze projekcie.. http://shop.acztery.info/index.php ( ok. 1300 rekordów )

Ten post edytował acztery 30.03.2005, 18:39:30

[darkspirit]

@acztery: bo przy takiej ilości wyświetlanych zagnieżdżeń(jedno) to to się sprawdza, ale jakbyś naprzykład, wyświetlał całe drzewko z all zagnieżdżeniami(i w tym wiele "odrostów") itp. to było by to kitu, rozwiązanie dobre ale tylko w szeczególny przypadku przynajmniej na mój chłopski rozum

paps

Ten post edytował darkspirit 30.03.2005, 19:59:39

[tarlandil]

Ja znam 3 rodzaje drzewek:

1) wezel pamieta tylko id ojca (czyli to co podal lukier)
liczba zapytan na wczytanie calego poddrzewa: tyle ile jego wysokosc
liczba zapytan na aktualizacje: 1
rozmiar drzewa: O(n) - n liczba wezlow

2) pamietane sa polaczenia miedzy kazdym dzieckiem i kazdym jego przodkiem
(tabelka:
int id
int parent,
int odleglosc
)
liczba zapytan na wczytanie calego poddrzewa: 1
liczba zapytan na aktualizacje: 1
rozmiar drzewa: O(n^2)

3)pamietane sa polaczenia miedzy kazdym dzieckiem i kazdym jego przodkiem, ale tylko takich ktorych odleglosc jest potega 2ki
(tabelka:
int id
int parent,
int odleglosc //tylko potegi 2
)
liczba zapytan na wczytanie calego poddrzewa: log h
liczba zapytan na aktualizacje: log n
rozmiar drzewa: O(n log n)

Ten post edytował tarlandil 29.04.2005, 08:30:12

[Ace]

Tez mam problem ze struktura drzewiasta... Musze pomyslec spokojnie nad jakas metoda ktora pomoze w latwy sposob zapisac nowa galaz oraz latwo zmodyfikowac i wyswietlic cale drzewo. - Przejze notatki z Algorytmow bo mialem cos o drzewach, jak cos znajde to podrzuce na forum.

[ebe]

W moim przypadku trzymam drzewo w bazie stosując algorytm przedstawiony przez depesz.com. W php drzewo ma postać drzewa obiektów (dzięki skorzystaniu z _get i _set) tj.

[PHP] pobierz, plaintext 
<?php
 $content->newsyOstatnie10->news1
$content->newsy->news2
$content->articles->category1->article1
$content->articles->category1->article2->page1
$content->articles->category1->article2->page2
.
.
.
 
?>
[PHP] pobierz, plaintext 

Drzewko takie trzymam w bazie do każdego node'a podłączony jest obiekt (dowolny!) np. newsContainer to node newsy a news1 ma podwiązany obiekt klasy News. W bazie danych trzymam parametry oraz metodę jaką ma zostać zbudowany dany obiekt. Do obiektów podłączanych pod gałęzie dobieram się za pomocą metody getObject() np

[PHP] pobierz, plaintext 
<?php
$content->newsy->news1->getObject()
?>
[PHP] pobierz, plaintext 

I już mam obiekt danego newsa.

Rozwiązanie takie jest bardzo elastyczne, ponieważ obiekt newsa nie ma pojęcia jakiej jest kategorii, o tym decyduje drzewo. Dany element contentu mogę trzymać w dowolnej gałęzi (a raczej referencję do niego). Takie drzewo trzymam zserializowane w pliku (oczywiście samo drzewo bez obiektów podwiązanych ) dzięki czemu baza danych nie jest przeciążona, jeśli w panelu zmienię coś w drzewie to nadpisuje plik i po kłopocie. Innym plusem takiego drzewa jest możliwość prostego zastosowania RecursiveIteratora np. w smartym. Kolejnym plusem są prawa dostępu, możliwość tworzenia zagnieżdżonych grup użytkowników i podwiązywania użytkowników do dowolnej grupy. Jednym słowem w takim drzewie trzymam wszystko.

[radziel]

jeśli w panelu zmienię coś w drzewie to nadpisuje plik i po kłopocie.

Tutaj ujawnia się dla mnie dość istotna wada, mianowicie, nadpisujesz cały plik. Przy małych plikach i drzewach jest to niezauważalne, ale spróbuj serializować tablicę z 10 000 elementów. Przy czym zmieniasz tylko jeden z nich... Nie za duże obciążenie, dla tak małej zmiany?

[ebe]

Tutaj ujawnia się dla mnie dość istotna wada, mianowicie, nadpisujesz cały plik. Przy małych plikach i drzewach jest to niezauważalne, ale spróbuj serializować tablicę z 10 000 elementów. Przy czym zmieniasz tylko jeden z nich... Nie za duże obciążenie, dla tak małej zmiany?

Masz rację jest to wada, pocieszeniem jest to, że taka aktualizacja - dodanie newsa, nowej kategorii jest wykonywana średnio kilka razy dziennie, pozatym narazie max to ok 1000 gałęzi i drzewko działa (na localhoście). Moja metoda jest jeszcze w powijakach i wymaga dopracowania, być może zrezygnuję z serializowania i deserializowania na rzecz klasycznego odczytu z bazy albo wymyślę coś innego. Jak tylko uporam się z problemami wydajności i uznam, że klasa jest gotowa zamieszczę na forum.

[chmolu]

System, którego używa acztery jest korzystny przy usuwaniu i uaktualnianiu rekordów. Tyle, że w świecie www o wiele częściej dane muszą być wyświetlone niż uaktualnione. Zajrzyj tutaj: http://www.sitepoint.com/article/1105 i zapoznaj się z drugim sposobem. Jest już mniej wygodny dla usuwania i update'owania, ale za to o wiele bardziej efektywny dla pobierania rekordów. Poza tym w sieci znajdziesz różne wariacje tej metody, która pozwoli na zwiększenie wydajności.