Daten in flexibler Baumstruktur für schnelle Zugriffe speichern

[Andreas Korthaus]

Hallo!

Ich überlege gerade, wie ich hierarchische Daten am besten speichere, und wie ich am besten darauf zugreife.

Ich habe Daten vergleichbar mit denen von e-class:

http://eclass.de/hauptseite.phtml?nav=suchen&lang=germ&nav2=hsuche&hsuche_x=x&e1=19&e1des=Informations-%2C+Kommunikations-%2C+und+Medientechnik&e2=01&e2des=Hardware+(Informationstechnik)&pe=01~System+(Informationstechnik)

Die Daten sind außerdem überschaubar, das heißt maximal 10 MB, zumeist unter 1 MB.

Das heißt z.B. ich habe folgende Daten

Hardware (Informationstechnik)
  System (Informationstechnik)
    Mainframe
    Cluster-Rechner
    Server
    Workstation
    Personal Computer
    Terminal
    Notebook
  Zubehör für Hardware und Peripheriegeräte
    Laufwerk
      Diskettenlaufwerk
      CD-Laufwerk
      CD-Brenner
      DVD-Laufwerk
      DVD-Brenner
      Bandlaufwerk
      Festplatte
Software
  Server-Software
    Datensicherung
    Groupware
    Firewall
    Intranet-Lösung

Ich muss diese Hiearchie speichern und wiederherstellen können, jede Kategorie braucht eine feste, eindeutige ID, und jetzt kommt das doofe: Die Reihenfolge der Unterkategorien in einer Kategorie muss veränderbar sein. Die Anzahl der Hierachie-Ebenen soll nicht begrenzt sein. Der Baum soll genau so aufgeklappt werden wie im eclass-Beispiel oben, das heißt es gibt immer nur einen "offenen Pfad", nicht wie im Windows-Explorer, wo alle Kategorien(Verzeichnisse) so lange offen bleiben, bis man sie wieder schließt.

Als Programmiersprache verwende ich PHP (was auch sonst ;-)).

Daten in XML-Format zu speichern und mit PHP(4) zu parsen finde ich bei der Größe nicht wirklich sinnvoll. 2. Möglichkeit wäre die Daten wie in Henryks Forum-Artikel in einer relationalen DB zu speichern, und die Daten ggfs. rekursiv zu durchlaufen.

Auf der anderen Seite ist in PHP ja die mit Abstand schnellste Zugriffs-Methode die Verwendung von Arrays - zumindest in dieser Größenordnung. Dazu kommt, dass man Arrays recht einfach im Shared Memory ablegen kann. Prinzipiell würde ja folgende Struktur ausreichen:

Hardware
  System
    Mainframe
    Cluster-Rechner
    Server

Ließe sich mit Hilfe von 2 Arrays z.B. so abbilden:

array (
  1 => array (
    2 => array (
       3 => array(),
       4 => array(),
       5 => array()));

array (
  1 => 'Hardware',
  2 => 'System',
  3 => 'Mainframe',
  4 => 'Cluster-Rechner',
  5 => 'Server'
);

Das wäre auch alles schön und gut, man könnte die Schlüssel ja als feste IDs verwenden, nur kann man dann nicht so ohne weiteres Elemente verschieben. Sagen wir mal, es soll nicht

Hardware
  System
    Mainframe
    Cluster-Rechner
    Server

sondern

Hardware
  System
    Server
    Mainframe
    Cluster-Rechner

angezeigt werden, dann weiß ich nicht wie ich das machen soll, wenn der Schlüssel "5" dem "Server" fest zugeordnet sein soll (sonst wäre es mit array_splice() kein großes Problem).

Dann stellt sich auch die Frage, wie man effizient einen Teilbaum für eine gegebene Unterkategorie erstellt. Sagen wir mal

Hardware
  System
    Mainframe
    Cluster-Rechner
    Server

wäre ein Teilbaum von dem gesamten E-Class Baum, und ich wollte auf einer Webseite jetzt eben nur den Pfad zur ID "4", also "Cluster-Rechner" anzeigen.

Da man jetzt nicht weiß auf welcher Ebene sich "4" befindet, muss man der Reihe nach(linear) alle Ebenen abklappern... das wäre ja absoluter Overkill, oder? Also braucht es hier noch ein Array in dem hierfür nützliche Informationen gespeichert werden, also am besten einfach eine Liste mit Parent IDs:

das heißt für das Beispiel:
$index = array (
  1 => 0,
  2 => 1,
  3 => 2,
  4 => 2,
  5 => 2
);

$find = 4;

Daraus lässt sich sehr schnell ermitteln über welchen Pfad man zur gesuchten Kategorie kommt.

while ($find > 0) {
  $find = $index[$find];
  $pfad[] = $find;
}

Prinzipiell bräuchte ich dann den ersten Array auch gar nicht mehr, weil dieser hier ja alle notwendigen Informationen enthält, hm.

Das Problem welches ich leider nicht vernünftig gelöst bekomme ist wie ich jetzt die Reihenfolge der Unterkategorien innerhalb einer Kategorie ändern kann. Hat da vielleicht jemand eine Idee wie man das "ordentlich" machen könnte?

Viele Grüße,
Andreas

[Rolf Rost]

Hallo Andreas!

Also. Auf der PerlBase mach ich das so, das die Daten hierarchisch in virtuellen Ordnern abgelegt sind.

Ich verrate auch wies geht

http://perlbase.xwolf.de/cgi-bin/perlbase.cgi?display=16&id=10

Und verrate auch dass sich auf diese Art und Weise so ziemlich alles , außer Kaffe , in einer DB speichern lasst. *g

Rolf

[Andreas Korthaus]

Hallo Rolf!

Also. Auf der PerlBase mach ich das so, das die Daten hierarchisch in virtuellen Ordnern abgelegt sind.
http://perlbase.xwolf.de/cgi-bin/perlbase.cgi?display=16&id=10

Kannte ich doch schon ;-)

Und verrate auch dass sich auf diese Art und Weise so ziemlich alles , außer Kaffe , in einer DB speichern lasst. *g

Das bezweifele ich nicht. Und es isz ja auch nicht so dass ich keienn Weg wüsste wie ich es überhaupt hinbekomme, aber ich finde keinen "schönen Weg" ;-)

Was Du machst - Du verwendest zusammengesetzte IDs - klar, könnte ich auch machen, aber habe ich mich bisher noch nicht so richtig mit anfreunden können. Wenn Dir die Reihenfolge innerhalb einer Kategorie egal ist - kämst Du mit "echten"(nicht zusammengesetzten) IDs aus - btw. ;-) (So wie ich das sehe kannst Du auch mit diesem System keine Reihenfolge ändern, oder Kategorien "umziehen", oder?)

Auf der anderen Seite hat dieses Zusammensetzen auch Vorteile, weil man einige Informationen direkt zur Verfügung hat(nämlich alle IDs der Eltern-Kategorien - den Pfad wie ich es bezeichnet habe), die man sich sonst erst erarbeiten müsste. Auf der anderen Seite verlasse ich mich hier wieder auf Angaben des Users, was ich aus Prinzip nicht gerne mache, ist immer ein potentielles Risiko.

Außerdem löst Deine Version _nicht_ das Problem mit der Änderung der Reihenfolge. Denn auch Du verwendest feste IDs, wenn sich die auch zusammensetzen. Es geht mir nicht nur ums einfache Sortieren, sondern z.B. will ich statt:

* Perlmodule (3 Dokumente)
    * Perlmodule/Config::IniFiles (1 Dokument)
    * Perlmodule/HTML (1 Dokument)
    * Perlmodule/Image (1 Dokument)
    * Perlmodule/Installation (2 Dokumente)

auf einmal sowas:

* Perlmodule (3 Dokumente)
    * Perlmodule/Config::IniFiles (1 Dokument)
    * Perlmodule/Image (1 Dokument)
    * Perlmodule/HTML (1 Dokument)
    * Perlmodule/Installation (2 Dokumente)

Oder geht das mit Deinem System?

Grüße
Andreas

[Carsten]

'nabend!

hab leider nicht viel zeit es genauer zu erläutern, aber vieleicht solltest du dir 'nested sets' mal anschauen (habe so schon wirklich komplexe navigationsstrukturen abgebildet). ist aber nur zu gebrauchen, wenn du die struktur nicht oft ändern mußt.

http://klempert.de/php/nested_sets/literatur/

c ya
Carsten

[Andreas Korthaus]

Hi!

hab leider nicht viel zeit es genauer zu erläutern, aber vieleicht solltest du dir 'nested sets' mal anschauen (habe so schon wirklich komplexe navigationsstrukturen abgebildet). ist aber nur zu gebrauchen, wenn du die struktur nicht oft ändern mußt.

http://klempert.de/php/nested_sets/literatur/

Vielen Dank, sehr interessanter Link. Hatte davon zwar schonmal gehört, aber habe mich nie näher mit beschäftigt. Wirklich eine interessante Alternative! Prinzipiell müsste das auch mit einem Array gehen... hm. Wie ich das sehe, kann man hier jedenfalls wenigstens theoretisch Elemente verschieben.

(ich "klau" mir mal eben ein Bild...)

<img src="http://ffm.junetz.de/members/reeg/DSP/img10.png" border="0" alt="">

Hierzu müsste man dann allerdings einen großen Teil des Baumes, das heißt je nach Ebene möglicherweise so ziemlich jeden Datensatz verändern.

Auf der anderen Seite ist diese Variante vermutlich mit die effizienteste wenn man die Daten liest, denn bei allen anderen Varianten muss ich die Reihenfolge in irgendeiner Form extra abspeichern, und dann nachträglich sortieren...

Also wenn ich diese Datan mal mit der "Vater-ID" Variante organisiere:

ID  Name  Vater-ID
1  Root  0
2  A  1
3  B  1
4  C  1
5  A1  2
6  B1  3
7  B2  3
8  C1  4
9  A1I  5
10  C1I  8
11  C1II  8

Müsste ich hier ja nur ein weiteres Feld einfügen, "Reihenfolge" oder sowas, welches die Sortierreihenfolge für die eine Ebene festlegt. Das heißt, wenn ich anstatt

root

/   |   \

A     B     C

sowas möchte:

root

/   |   \

B     A     C

ID  Name  Vater-ID   Reihenfolge
1  Root  0          1
2  A  1          2
3  B  1          1
4  C  1          3
...

Man stelle sich vor welchen Aufwand dies für "Nested Sets" oben bedeutet, in diesem Fall müsste ich 6 von 11 Elementen verändern. Aber das hast Du ja auch geschrieben ;-)

Um irgendwas in der Art komme ich dann wohl nicht herum, oder?

Viele Grüße
Andreas

[Carsten]

moin!

Man stelle sich vor welchen Aufwand dies für "Nested Sets" oben bedeutet, in diesem Fall müsste ich 6 von 11 Elementen verändern. Aber das hast Du ja auch geschrieben ;-)

Um irgendwas in der Art komme ich dann wohl nicht herum, oder?

leider nein :-(
aber wenn es darum geht ab und an mal eine navigationsstruktur zu aendern, ist das voll und ganz ok. das auslesen ist halt extrem flexiebel, wenn du es ausliest - zum anderen gibt es auch schon einen brauchbaren editor fuer solche strukturen.

gruesse
Carsten

[Andreas Korthaus]

Hallo!

Um irgendwas in der Art komme ich dann wohl nicht herum, oder?

leider nein :-(
aber wenn es darum geht ab und an mal eine navigationsstruktur zu aendern, ist das voll und ganz ok. das auslesen ist halt extrem flexiebel, wenn du es ausliest - zum anderen gibt es auch schon einen brauchbaren editor fuer solche strukturen.

Hab gedacht - vielleicht wäre das auch ein Kandidat für ein PEAR-Paket... und bei der Gelegenheit nochmal einen Blick auf PEAR::Tree geworfen - das enthält ja bereits als Speichermethode "nested trees", und kann sowohl mit DB als auch XML_Datei umgehen. Eigentlich nicht schlecht, nur leider noch beta. In Kombination mit PEAR::Cache oder CacheLite, vielleicht wirklich eine bedenkenswerte Alternative. Hm, mal überlegen, habe dann aber immer noch das Problem, dass ich die Datenstruktur ja auch an anderer Stelle brauche, wobei ich es ja dort dann in xml speichern kann... mal sehen. Irgendwie gefällt mir der Stil von PEAR::Tree nicht wirklich.

Viele Grüße
Andreas

[Rolf Rost]

Moin Andreas,

* Perlmodule (3 Dokumente)
    * Perlmodule/Config::IniFiles (1 Dokument)
    * Perlmodule/HTML (1 Dokument)
    * Perlmodule/Image (1 Dokument)
    * Perlmodule/Installation (2 Dokumente)

auf einmal sowas:

* Perlmodule (3 Dokumente)
    * Perlmodule/Config::IniFiles (1 Dokument)
    * Perlmodule/Image (1 Dokument)
    * Perlmodule/HTML (1 Dokument)
    * Perlmodule/Installation (2 Dokumente)

Oder geht das mit Deinem System?

Da hab ich lediglich die Möglichkeit, die Sortierung zu ändern. Entweder nach den Keys

1
1.1
1.2

usw.

oder alphanumerisch. In letzteren Fall kann ich zum Sortieren die Vorteile des DBMS nutzen (ORDER BY ...), für einen Dokumentenserver bevorzuge ich auch die alphanumerische Sortierung.

Für den Fall jedoch, dass ich nach der numerischen Reihenfolge der Kapitel sortieren will, ist order by bei meiner derzeitigen Tabellenstruktur nicht möglich. Da bräuchte ich ein anderes Design. Was aber auch geht: ich behalte meine Tabellenstruktur und verzichte beim SELECT auf ORDER BY. Die Schlüssel sortiere ich dann mit einer eigenen PERL Funktion.

Gruss, Rolf

[Andreas Korthaus]

Hi Rolf!

Da hab ich lediglich die Möglichkeit, die Sortierung zu ändern. Entweder nach den Keys

1
1.1
1.2

usw.

oder alphanumerisch. In letzteren Fall kann ich zum Sortieren die Vorteile des DBMS nutzen (ORDER BY ...), für einen Dokumentenserver bevorzuge ich auch die alphanumerische Sortierung.

mir geht es nicht um eine Sortierung, sondern um ein willkürliche  Änderung der Reihenfolge. Jemand möchte möglicherweise irgendeinen Punkt in der Mitte um eine Position nach oben schieben...
Das heißt das lässt sich nicht mit einer Sortierung der Werte festmachen. Man muss mit irgendeiner Methode die Reihenfolge separat speichern, zumindest wenn man die Schlüssel beibehalten will. Wäre diese Verbindung egal, könnte man einfach die Werte 2er Elemente vertauschen, aber wie gesagt, zwischen Schlüssel und Wert muss es einen festen Zusammenhang geben.

ich versuche es halt mir einer möglichst einfachen Datenstruktur abzubilden, die sich möglichst schnell abfragen lässt. Aber wenn die Reihenfolge veränderbar sein muss geht das glaube ich nicht ganz so einfach. Es ist so wunderbar einfach wenn die Reihenfolge egal ist, oder nur sortiert werden muss.

Grüße
Andreas

[Danny]

Hi,

ich versuche es halt mir einer möglichst einfachen Datenstruktur abzubilden, die sich möglichst schnell abfragen lässt. Aber wenn die Reihenfolge veränderbar sein muss geht das glaube ich nicht ganz so einfach. Es ist so wunderbar einfach wenn die Reihenfolge egal ist, oder nur sortiert werden muss.

Vielleicht stelle ich es mir zu simpel vor, aber in einer DB-Lösung kannst Du doch die Reihenfolge einfach mit einem zusätzlichen Feld abbilden, in dem eine Zahl, bzw. ID gespeichert ist, welche die Reihenfolge vorgibt, oder? Verschieben, Hinzufügen und Löschen sollte dann kein Problem mehr sein.

MfG
Danny

[Andreas Korthaus]

Hi!

ich versuche es halt mir einer möglichst einfachen Datenstruktur abzubilden, die sich möglichst schnell abfragen lässt. Aber wenn die Reihenfolge veränderbar sein muss geht das glaube ich nicht ganz so einfach. Es ist so wunderbar einfach wenn die Reihenfolge egal ist, oder nur sortiert werden muss.

Vielleicht stelle ich es mir zu simpel vor, aber in einer DB-Lösung kannst Du doch die Reihenfolge einfach mit einem zusätzlichen Feld abbilden, in dem eine Zahl, bzw. ID gespeichert ist, welche die Reihenfolge vorgibt, oder? Verschieben, Hinzufügen und Löschen sollte dann kein Problem mehr sein.

Ja, das ist schon richtig, [pref:t=79033&m=457801], ich hatte gehofft irgendwie ohne sowas auszukommen, was auch ginge, wenn ich keine festen Ids bräuchte.
Die Sache ist halt, solange ich nur einen Schlüsel und einen Wert habe, reicht mir ein einfaches Array, für alles Weitere wird es mehrdimensional, das wollte ich vermeiden, naja, scheint so als wäre es nicht zu vermeiden ;-)

Grüße
Andreas

[Danny]

Kennst Du die PHP-Funktion xml_parse_into_struct ?

In der zurückgegebenen Struktur steht die Tiefe des XML-Tags direkt im Array-Index 'level', d.h. man braucht keine Rekursion zum Durchlaufen der Einträge, die Tiefe wird also nicht durch Verschachtelung repräsentiert. Damit würde sich auch Deine Stuktur vereinfachen lassen, etwa

array(
  array(
    'level' => 0, // Ebene (Verschacheltungstiefe)
    'pos' => 0, // Position (Reihenfolge)
    'type' => 'folder' (Art des Elements)
    'name' => 'test', (Name, bzw. ID)
    // weitere Informationen
  ),
);

[Andreas Korthaus]

Hi!

Kennst Du die PHP-Funktion xml_parse_into_struct ?

Ja

In der zurückgegebenen Struktur steht die Tiefe des XML-Tags direkt im Array-Index 'level', d.h. man braucht keine Rekursion zum Durchlaufen der Einträge, die Tiefe wird also nicht durch Verschachtelung repräsentiert. Damit würde sich auch Deine Stuktur vereinfachen lassen, etwa

array(
  array(
    'level' => 0, // Ebene (Verschacheltungstiefe)
    'pos' => 0, // Position (Reihenfolge)
    'type' => 'folder' (Art des Elements)
    'name' => 'test', (Name, bzw. ID)
    // weitere Informationen
  ),
);

Also ich mag diese Funktion nicht so besonders, was mir gefallen könnte wäre simplexml (http://de3.php.net/manual/de/ref.simplexml.php), gibts leider erst in PHP5. Das Problem bei XML ist schonmal, dass es sehr langsam wird wenn die Datei etwas größer wird, da PHP immer die gesamte XML-Datei verarbeiten muss, und XML ist auch recht komplex, so dass die von PHP verwendeten XML-Parser auch nicht gerade schnell sind. Natürlich wäre eine Datenhaltung in Form von XML nicht schlecht, aber gerade dann bräuchte ich in jedem Fall einen PHP-Array der gecached wird. Gut, da könnte man dann auch direkt den von xml_parse_into_struct() erzeugten Array nehmen, das ganze kann man ja gut anpassen, allerdings weißich nicht ob man auf diese Weise auch einen einen oder mehrere Arrays hinbekommt, die sich schön effektiv abfragen lassen. Effektiv heißt für mich, dass ich imer wo möglich Daten _direkt_ lesen kann, also $var = $array[$_GET['bla']... und nicht erst foreach ($array as $val) if ($val['bla']==$_GET['bla'])...

Im Moment sehe ich die Datenbank-Version mit Vater-ID als die effizienteste. Das doofe an der Geschichte - ich will das ganze auch nutzen können, wenn ich keine Datenbank habe (man, ich will PHP5 mit simplexml und/oder sqlite ;-))

Hierzu ist XML natürlich eine Möglichkeit. Ich versuche es erstmal mit reinen PHP-Arrays. Sicher ist das kein besonders portables Format, aber eine Import/Export-Schnittstelle kann ja unabhängig von der Datenhaltung funktionieren.

Ich hab mir jetzt Folgendes überlegt:

Struktur:
1 Hardware
  2 System
    5 Server
    4 Cluster-Rechner
    3 Mainframe

Arrays:
$titles = array (
  1 => 'Hardware',
  2 => 'System',
  3 => 'Mainframe',
  4 => 'Cluster-Rechner',
  5 => 'Server'
);

$parend_ids = array (
  1 => 0,
  2 => 1,
  3 => 2,
  4 => 2,
  5 => 2
);

$sort_ids = array (
  1 => array (2),
  2 => array (5,4,3),
);

Ich denke damit speichere ich alle relevanten Informationen - wenn teilweise auch redundant(wie ein Index halt), aber dafür kann ich die Daten so recht effektiv abfragen.

Jetzt kann ich anhand einer gegebenen ID (z.B. 2) den Baum sehr schnell erzeugen.

• mit $parend_ids[2] frage ich die Parent ID ab(evtl. rekursiv oder in einer Schleife, bis zum Root-Element, sind in der Praxis vielleicht im Schnitt 4 Ebenen, maximal vielleicht 10 oder 12)
  Und dann kann ich mit foreach($sort_ids[2] as $id) {...} sehr einfach alle Elemente in einer Kategorie ausgeben. Das gute hieran, mit array_splice() kann ich die IDs hier so Anordnen wie ich lustig bin. IM Prinzip bräuchte ich auch 3 Arrays, selbst wenn ich die Reihenfolge nicht beeinflussen wollte, nur könnte ich das dann in diesem Fall evtl. etwas effizienter machen, durch den Array wie im ersten Posting beschrieben - diese würde nicht linear durchlaufen, sondern die Elemente würde direkt durch alle Parent-IDs der gesuchten Kategorie bestimmt. Auf der anderen Seite dürfte ein Array der als Opcode im RAM gehalten wird, schneller abzufragen sein als jeder DB-Index, also halb so wild IMHO.

Die Elemente gebe ich dann in Form von "echo $titles[$id]" aus.

Der größte Array würde wohl der mit den Titeln werden, die anderen verhältnismäßig klein. Das speichere ich dann entweder per serialize, oder evtl. sogar mit meiner in [pref:t=78998&m=457720] beschriebenen Methode in ausführbaren PHP-Dateien.

Was haltet Ihr von dieser Methode?

Viele Grüße
Andreas

[Danny]

Moin Andreas!

Hab' gerade wenig Zeit, kann daher nicht auf Deine Frage eingehen.

Was ich aber unbedingt loswerden will: Ich meinte nicht, dass Du XML als Speicherformat nehmen sollst, sondern wollte lediglich auf die Array-Struktur hinweisen, die parse_into_struct zurückgibt. Also nur als Denkanstoss.

Was die Performance angeht, scheidet XML für Deine Lösung schonmal aus, das Parsen wäre ein ziemlicher Overhead. SimpleXML finde ich davon abgesehen aber auch gut. Was für Dich auch interessant sein könnte ist PEAR::tree, was Du aber bestimmt schon kennst.

mit freundlichem Gruß
Danny