Daten in Baumstruktur speichern

[Andreas Korthaus]

Hallo!

Der wohl eintscheidene Vorteil eines Volltext-Index im Gegensatz zu einer einfachen Tabelle ist doch wohl, dass die Daten im Volltext-Index(zumindest bei MySQL) in einer Baumstruktur gespeichert werden, was dann natürlich erheblich beim suchen ist. Nur wie sieht das praktisch aus? Wie speichere ich denn Daten in einer Baumstruktur, wie macht MySQL das? Kann man das irgendwie mit XML oder in einer Flat-File oder mit beliebig vielen Flat-Files nachbilden?

Viele Grüße
Andreas

[Frank Schönmann]

hi!

Wie speichere ich denn Daten in einer Baumstruktur, wie macht MySQL
das?

Wenn man seine Daten in Baumstrukturen auf der Festplatte speichern
möchte, verwendet man normalerweise B-Bäume. Das sind Bäume mit
relativ hohem Verzweigungsgrad, die aber ansonsten relativ analog
zu normalen, sortierten Binärbäumen funktionieren. Informationen
darüber findest du in jedem guten Algorithmik-Buch, und wenn du Glück
hast auch im Netz.

In einem Seminar habe ich mal einen Vortrag gehalten, in dem es auch
zum Teil um B-Bäume ging. Für einen kleinen Einblick kannst du dir
da mal einen Teil der Ausarbeitung durchlesen:
  http://www.defined.de/home/prog/own-rbtrees.shtml

bye, Frank!

[Michael Schröpl]

Hi Andreas,

Der wohl eintscheidene Vorteil eines Volltext-Index im Gegensatz zu einer einfachen Tabelle ist doch wohl, dass die Daten im Volltext-Index(zumindest bei MySQL) in einer Baumstruktur gespeichert werden, was dann natürlich erheblich beim suchen ist.

Keineswegs.
Ein Volltext-Index wird nicht viel anders funktionieren als jeder andere Index auch.

Das, was Dir mySQL-Fulltext tatsächlich abnimmt, ist:
1. Definition einer separaten Tabelle mit zwei Spalten "wort" und "dokument_id".
2. Anlegen eines non-unique Index über die Spalte "wort".
3. Implementieren eines Wort-Zerlegers, der bei einem INSERT auf Deine Original-Tabelle den Inhalt eines Dokuments in Worte zerlegt und pro Wort ein INSERT in diese separate Tabelle macht.
4. Implizites Generieren einer JOIN-artigen Konstruktion bei Verwendung von MATCH() in einer WHERE-Klausel.
Das sind alles Dinge, die Du auch per Hand machen kannst (das macht dann allerdings etwas mehr Mühe). Dies ist der Grund dafür, weshalb ich Deine mySQL-FULLTEXT-Experimente als wertvoll für eine künftige Forums-Archiv-Suche einstufe, selbst wenn auf dem entsprechenden Server tatsächlich ein anderes RDMBS laufen wird. FULLTEXT ist für ein RDBMS kein Quantensprung, sondern eher ein nice to have ... bei Triggern oder Constraints sähe es anders aus, beides läßt sich nicht so ohne weiteres simulieren.

Wie speichere ich denn Daten in einer Baumstruktur, wie macht MySQL das?

Dazu kannst Du Dir ja mal den Quelltext der Implementierung von CREATE INDEX durchlesen ... ist ja schließlich Open Source. ;-)

Kann man das irgendwie mit XML oder in einer Flat-File oder mit beliebig vielen Flat-Files nachbilden?

Mit beliebig vielen Flat-files - sicher. Denn wie auch immer eine Baumstruktur tatsächlich codiert ist, sie wird auf Speicherseiten abgelegt, und Du kannst mit Flat-files natürlich Speicherseiten emulieren ... ;-)

Im Ernst: Jeder innere Knoten eines Baums kann durch eine Datei oder eine gleichwertige Datenstruktur abgebildet werden.
Um innerhalb eines Baums navigieren zu können, muß ein solcher Knoten eine Liste aller Tochterknoten enthalten (bei einem binären Baum sind das überschaubar viele Einträge ... ;-) sowie zu jedem dieser Tochterknoten ein Werteintervall der durch diesen Teilbaum abgedeckten Indexwerte. Beim rekursiven Abstieg innerhalb dieses Baums navigierst Du von Knoten zu Knoten und ignorierst dabei jeweils alles, was außerhalb Deines gewünschten Werteintervalls liegt ... das ist der Grund, weshalb Du bei LIKE eine Wildcard hinten verwenden darfst und trotzdem den Index nutzen kannst (Du isolierst einfach innerhalb des Baums alles, was mit dem Suchbegriff präfix-matched, und traversierst dann die verbleibenden Teilbäume vollständig), während eine Wildcard vorne den Zugriff auf den nach Präfix sortierten Indexbaum unmöglich macht.
Würdest Du beispielsweise eine Aufgabenstellung haben, "LIKE '%xyz'" und "LIKE 'xyz%'" effizient zu implementieren, dann könntest Du also beispielsweise _zwei_ solcher Indexe anlegen, einen über den normalen Spaltenwert und einen über seine Umkehrung ... "LIKE '%xyz%'" kriegst Du via Index in den Griff, wenn Du _jeden_ Suffix eines _jeden_ Worts in die zusätzliche Tabelle aufnimmst und gegen diese Tabelle dann Präfix-Matches durchführst. Das wird dann _viel_ Zeug ... aber es _kann_ sehr schnell werden, sofern Du nicht an mangelnden Ressourcen zugrunde gehst. Ich verwende dies in einer realen Suchmaschine ... 20 Millionen Tabelleneinträge importieren plus Indexen dauert bei mir 45 Minuten täglich.

Mit dieser Datenstruktur im Kopf sollte klar sein, wie Einfügen und Löschen funktionieren:
1. Suchen der entsprechenden Stelle innerhalb des Baums
2. Zuweisen oder Entfernen des Blatts
3. Anpassen der darüberliegenden Indexseite - dies kann ggf. rekursiv durch den gesamten Baum bis zur Wurzel notwendig sein, wenn diese Operation das jeweilige Intervall des Teilbaums ändert, also wenn Du ein Minimum bzw. Maximum des Intervalls löschst bzw. hinzufügst).

Beachte, daß Deine Datenstruktur zur Aufnahme von Tochterknoten _endlich_ ist. Solltest Du einen solchen Knoten hinzufügen müssen, aber keinen Platz mehr dafür haben, dann ist eine Seitenteilung fällig: Du ersetzt den Knoten durch einen neuen Knoten mit Verweisen auf neue Unterknoten, die jeweils Teilabschnitte der bisherigen Verweisliste enthalten. (Dadurch wird dieser Teilbaum um eine Stufe tiefer!) Umgekehrt kann das Löschen eines Knotens das Zusammenfalten des Teilbaums auslösen, der dabei wieder flacher wird.
In der effizienten Implementierung dieser beiden (häufigen) Operationen besteht ein signifikanter Teil des Geheimnisses einer performanten Datenbank. Wobei es hier nicht nur darum geht, die einzelne Operation möglichst schnell durchzuführen, sondern insbesondere sie möglichst selten durchführen zu _müssen_! Beim Seitenteilen hast Du möglicherweise Freiheitsgrade, die Du für eine "vorausschauende" Behandlung der Operation nutzen kannst (Oracle erlaubt Dir beispielsweise, zu definieren, welchen Fullungsgrad in Prozent ein Indexblock maximal erreichen darf, bevor präventiv eine Seitenteilung ausgelöst wird - diesen Wert paßt man dann an die erwartete Änderungshäufigkeit der Tabelle an, bei einer readonly-Tabelle sinnvollerweise 100%) ...
Die Theorie der B*-Bäume habe ich selbst nicht mehr wirklich verstanden, das wird dann wohl nur noch für die echten Cracks von Interesse sein. Eines der wichtigen Ziele dabei muß es jedoch sein, zu verhindern, daß ein Baum durch wiederholtes Einfügen und Löschen zu einer Liste degeneriert, wodurch der logarithmische Aufwand beim Zugriff wieder linear zu werden drohen würde. Auch solche Aspekte muß ein wirklich guter 'Indexverwalter' berücksichtigen ...
Ich denke, jetzt ist klar geworden, wieso ein INSERT in eine Tabelle mit vielen Indexen signifikant langsamer werden kann als ohne diese Indexe, und wieso ein DELETE ALL _sehr_ viel teurer sein kann als ein DROP.

Beachte auch, daß (genau wie bei der Indexierung selbst) eine Meta-Ebene höher ebenfalls noch Optimierungspotential denkbar ist.
Eine _sehr_ gute Datenbank könnte beispielsweise merken, daß sie gerade unterbeschäftigt ist, und im Hintergrund automatisch (und prioritätsgesteuert) ihre Indexstrukturen bewerten (mittlerer Füllungsgrad eines Baums bzw. Anzahl der Knoten eines Teilbaums vs. dessen Höhe) und damit eine aktive Schwachstellenanalyse und -behebung durchführen ... mit demselben Ziel wie der Index selbst: Die tatsächliche Arbeit wird schon geleistet, bevor der Anwender mit der Maus geklickt hat, um dessen Online-Wartezeit minimal zu halten.

Viele Grüße
      Michael

[Andreas Korthaus]

Hallo Miachel!

Danke für die ausführliche Erklährung, habe es zwar noch nicht "umfassend verstanden", aber es wird... ;-)

Keineswegs.
Ein Volltext-Index wird nicht viel anders funktionieren als jeder andere Index auch.

Also wird der Index nicht als binär-baum sondern als interne (index-)Tabelle abgespeichert?
Das verstehe ich aber nicht. Es ist doch genau so linear den Text der Tabelle Datensatzweise zu durchsuchen, als alle Wörter in eine Tabelle zu schreiben um die dann linear zu durchsuchen?!

Das, was Dir mySQL-Fulltext tatsächlich abnimmt, ist:

1. Definition einer separaten Tabelle mit zwei Spalten "wort" und "dokument_id".
2. Anlegen eines non-unique Index über die Spalte "wort".
3. Implementieren eines Wort-Zerlegers, der bei einem INSERT auf Deine Original-Tabelle den Inhalt eines Dokuments in Worte zerlegt und pro Wort ein INSERT in diese separate Tabelle macht.

Ist das </archiv/2002/11/30580/#m165087> in etwa das was Du damit gemeint hast?

Mit beliebig vielen Flat-files - sicher. Denn wie auch immer eine Baumstruktur tatsächlich codiert ist, sie wird auf Speicherseiten abgelegt, und Du kannst mit Flat-files natürlich Speicherseiten emulieren ... ;-)

ich habe eine Idee wie man das vielleicht machen könnte:
Man könnte den Wortzerleger über das Archiv laufen lassen, mit stopwords und allem Schnick-Schnack, und dann aus den erhaltenen Wörtern je ein Verzeichnbis erstellen. Jedes Wort darf nur einmal vorkommen. In Das Verzeichnis kommen dann symb. links auf jedes Posting in dem das Wort vorkam und zwar auf ein unabhängiges Posting-Verzeichnis, in dem alle Postings mit der ID als Dateinamen stehen und mit den Meta-daten als Inhalt: Titel, Autor, Zeitpunkt...
Wie ich  mir das jetzt in meiner Naivität gedacht habe, dürfte der Zugriff auf ein spezielles Verzeichnis doch extrem schnell sein, oder?
 Auch wenn das dann einige 100.000 Verzeicnisse in einer Ebene sind, es ist doch ein Unique-Name, ich habe keien Ahnung wie sowas vom OS implementiert ist, nur ich hoffe das es sehr schnell ist.
Vemutlich ist da irgendwo ein Haken, oder wieso macht das keiner? Ich stelle mir den Suchvorgang dann so vor:
Jemand gibt in die Suche ein: "Javascript opener"
dann kommt einfach

• öffne Verzeichnis "/bla/bla/javascript" und lese alle enthaltenen Dateien ein
• öffne Verzeichnis "/bla/bla/opener" und lese alle enthaltenen Dateien ein

Die Dateien ggfs. noch auswerten(AND...) und fertig.

Naja, jetzt wo ich das schreibe, dann dürfen im Verzeichnis "javascript" wohl ein paar mehr Dateien stehen die erst geöffnet werden müßten. OK. Das ist blöd. Wenn denn AND-Verknüpfungen vorliegen, dann reicht es ja auch, erstmal nur die Dateinamen, wobei es sich wie gesagt um Posting-IDs handelt, einzulesen, die mit dem anderen Verzeichnis abzugleichen und nur die Schnittmenge zu öffenen. Sollte das denn nciht gehen? Zumal alle diese Vorgänge doch sehr schnell sein sollten, oder irre ich mich?

Wenn das dann doch zu viele Verzeichnisse auf eienr Eben sind, könnte man ja noch mal vorsortieren, meinetwegen mit den 2 oder 3 Anfangsbuchstaben, dann sollte es auf alle Fälle gehen, also so:
"/bla/bla/JAV/Javascript/", oder "/bla/bla/JAV/ascript/"

Und sonst hatte ich noch überlegt, pro Buchstabe einn Verzeichnis, also bei Javascript:
"/bla/bla/J/A/V/A/S/C/R/I/P/T/"

Was sagt Ihr dazu, was habe ich übersehen oder unterschätzt?

Ich habe mir auch Dank Franks Posting ein paar Sachen dazu durchlesen können, bin wie gesagt auch auf Implementierung von B-Bäumen in PERL gestoßen, aber da muß erst der komplette Inhalt in einen Hash geladen werden und der Baum zur Laufzeit erstellt werden, das hate ich unten bereits geschreiben das ich das für wenig optimal halte!

Grüße
Andreas

[Michael Schröpl]

Hi Andreas,

Ein Volltext-Index wird nicht viel anders funktionieren als jeder andere Index auch.
Also wird der Index nicht als binär-baum sondern als interne (index-)Tabelle abgespeichert?

Ein Index ist ein Index.
Nur arbeitet der FULLTEXT auf einer Spalte einer Tabelle, die Du nicht explizit siehst.

Ist das </archiv/2002/11/30580/#m165087> in etwa das was Du damit gemeint hast?

Ja. Ich habe diesen Thread nachträglich gelesen, hatte Christians guten Ausführungen aber nichts hinzuzufügen.

Man könnte den Wortzerleger über das Archiv laufen lassen, mit stopwords und allem Schnick-Schnack, und dann aus den erhaltenen Wörtern je ein Verzeichnis erstellen. Jedes Wort darf nur einmal vorkommen. In Das Verzeichnis kommen dann symb. links auf jedes Posting in dem das Wort vorkam und zwar auf ein unabhängiges Posting-Verzeichnis, in dem alle Postings mit der ID als Dateinamen stehen und mit den Meta-daten als Inhalt: Titel, Autor, Zeitpunkt...
Wie ich  mir das jetzt in meiner Naivität gedacht habe, dürfte der Zugriff auf ein spezielles Verzeichnis doch extrem schnell sein, oder?

Ich hatte mal eine Implementierung, die versucht hat, eine solche Indexstruktur über das Solaris-Dateisystem abzubilden. Die war auch ziemlich schnell. Ich habe diese Implementierung dann aber durch mySQL abgelöst, weil das Aufbauen der Verzeichnisstruktur mit Hilfe von mkdir (lineare Einträge innerhalb eines Verzeichnisses müßten ggf. auch wieder linear gelesen werden - deshalb einen Verzeichnisbaum) zwei Tage (!) Realzeit dauerte, bei konstant 60+% IOWAIT. Für den Normalbetrieb war das prima, aber schon kleinere Änderungen in diesem Baum dauerten Stunden.

Auch wenn das dann einige 100.000 Verzeicnisse in einer Ebene sind,

Dann wird es nicht schnell. Es sei denn, Dein Betriebssystem hasht diese komplette Struktur, hält sie also als sortierten Baum im RAM. Das wiederum hängt vom Treiber Deines Dateisystems ab ... bei Solaris war dieser Caching-Effekt sehr stark beobachtbar.

Vemutlich ist da irgendwo ein Haken, oder wieso macht das keiner?

Das Aufbauen dauert zu lange. Und mir lief ein 10-GB-Dateisystem über, weil mir die inodes ausgingen.

Jemand gibt in die Suche ein: "Javascript opener"
dann kommt einfach

• öffne Verzeichnis "/bla/bla/javascript" und lese alle enthaltenen Dateien ein
• öffne Verzeichnis "/bla/bla/opener" und lese alle enthaltenen Dateien ein
  Die Dateien ggfs. noch auswerten(AND...) und fertig.

Im Prinzip ja, aber ... ;-)

Naja, jetzt wo ich das schreibe, dann dürfen im Verzeichnis "javascript" wohl ein paar mehr Dateien stehen die erst geöffnet werden müßten. OK. Das ist blöd.

Gut erkannt. Jetzt sind wir nämlich wieder linear und nicht mehr logarithmisch schnell.

Wenn denn AND-Verknüpfungen vorliegen, dann reicht es ja auch, erstmal nur die Dateinamen, wobei es sich wie gesagt um Posting-IDs handelt, einzulesen, die mit dem anderen Verzeichnis abzugleichen und nur die Schnittmenge zu öffenen.

So ähnlich würdest Du den JOIN implementieren, richtig. Und genau deshalb tut es weh, wenn einer der Suchterme viele Treffer produziert ... Schnittmengen berechnen erfordert, die Teilmengen zu sortieren, und das wiederum kostet n * log(n).

Und sonst hatte ich noch überlegt, pro Buchstabe einn Verzeichnis, also bei Javascript:
"/bla/bla/J/A/V/A/S/C/R/I/P/T/"

Genau so hatte ich das damals tatsächlich realisiert. In jeder Datei stand dann eine lineare Liste der IDs aller zugehörigen Dokumente.

Was sagt Ihr dazu, was habe ich übersehen oder unterschätzt?

Für den Normalbetrieb denkst Du exakt in den Bahnen wie ich vor knapp zwei Jahren. Die Wartung solcher Strukturen ist aber - gelinde gesagt - eine Katastrophe.
Außerdem ist das Traversieren von Teilbäumen sehr langsam. Wenn Du mit Deinem Modell ein "LIKE 'java%'" emulieren willst (ich wollte das, weil ich Substrings finden können mußte), dann wird es ziemlich teuer, und die Festplatte kommt ordentlich ins Rotieren. Dann noch mehrere Suchanfragen gleichzeitig, die allesamt den Kopf der Festplatte gegeneinander positionieren ... aua. Offenbar war der Dateisystemcache bei Solaris nicht groß genug.

auf Implementierung von B-Bäumen in PERL gestoßen, aber da muß erst der komplette Inhalt in einen Hash geladen werden und der Baum zur Laufzeit erstellt werden, das hatte ich unten bereits geschreiben das ich das für wenig optimal halte!

Wenn das bei jedem Zugriff gemacht werden muß, dann ist es aus exakt demselben Grund schlecht wie die Verwendung einer HEAP-Tabelle aus mySQL (Du siehst, die Konzepte sind immer dieselben, nur die Namen ändern sich).
Wenn das aber ein daemon permanent im Speicher hält und Deine CGI-Programme sich per UNIX domain socket mit diesem verbinden, so wie dies im neuen Self-Forum der Fall ist ...

Viele Grüße
      Michael

[Andreas Korthaus]

Hallo!

Ein Index ist ein Index.
Nur arbeitet der FULLTEXT auf einer Spalte einer Tabelle, die Du nicht explizit siehst.

Ja, aber wo ist das jetzt logarithmisch? Es werden doch _linear_ alle Wörter abgearbeitet, oder? Wo ist der Vorteil(10er Potenzen) Gegenüber Deiner VErsion die ebenfalls linear halt die ganzen postings, und nicht die Wörter einzelnd durchsucht, was aber am Ende wohl aufs selbe rauskommt, oder? Die Anzahl der zu durchsuchenden Wörter ist dieselbe(zumindest wenn ich das richtig Verstanden habe), nur die Andordnung ist anders.

Ist das </archiv/2002/11/30580/#m165087> in etwa das was Du damit gemeint hast?

Ja. Ich habe diesen Thread nachträglich gelesen, hatte Christians guten Ausführungen aber nichts hinzuzufügen.

Ich wollte auch nur sicher gehen ;-) Solang ich den Fulltext Index verwende brauch ich die ja nicht, aber bei einer eigenen Tabelle sollte ich mit Hilfe dieser Funktion die Datensätze generieren oder?

Für den Normalbetrieb war das prima, aber schon kleinere Änderungen in diesem Baum dauerten Stunden.

OK, hatte mir schon sowas gedacht. Ist ja auch Quatsch, denn dann hänge ich wieder an der Festplatte feste, aber schnell sollte es sein. Nur eigentlich will ich ja eher von der Lösung "alles im RAM" weg, denn das kann zumindest _ich_ mir nicht erlauben, außerdem könnte ich dann auch das gesamte Filsystem wo ich das mache in den RAM legen, was verutlich nochmal gut für den Speed wäre, naja, aber vermutlich erzeugt diese Lösung noch ne ganze Menge an Overhead den ich nicht haben will.

Dann wird es nicht schnell. Es sei denn, Dein Betriebssystem hasht diese komplette Struktur, hält sie also als sortierten Baum im RAM. Das wiederum hängt vom Treiber Deines Dateisystems ab ... bei Solaris war dieser Caching-Effekt sehr stark beobachtbar.

Bei Linux wird glaube ich alles im RAM gerhalten, was man zuletzt verwendet hat, da gibt es irgendeinen Automatismus. Aber wie gesagt, ich hab nicht genug RAM, und Ihr auch nicht, wenn Du alle Archive... da reinpacken wolltest, dann würde es schon Eng für andere Anwendungen.

Das Aufbauen dauert zu lange. Und mir lief ein 10-GB-Dateisystem über, weil mir die inodes ausgingen.

Wieviele Dateien/Verzeichisse hattest Du denn da grob geschätzt? Gibt doch bestimmt Dateisysteme die hier besonders spendabel sind, oder nicht?

Für den Normalbetrieb denkst Du exakt in den Bahnen wie ich vor knapp zwei Jahren. Die Wartung solcher Strukturen ist aber - gelinde gesagt - eine Katastrophe.
Außerdem ist das Traversieren von Teilbäumen sehr langsam. Wenn Du mit Deinem Modell ein "LIKE 'java%'" emulieren willst (ich wollte das, weil ich Substrings finden können mußte), dann wird es ziemlich teuer, und die Festplatte kommt ordentlich ins Rotieren. Dann noch mehrere Suchanfragen gleichzeitig, die allesamt den Kopf der Festplatte gegeneinander positionieren ... aua. Offenbar war der Dateisystemcache bei Solaris nicht groß genug.

Also fasse ich das zusammen dass das Lesen sehr schnell ist, aber das Schreiben extrem lange dauert.
Was ich aber nicht verstehe, die Datenbank müßte doch erheblich langsamer sein, denn die hat ja nicht nur den Zugriff aufs Dateisystem, genau wie ich(bei 2 Suchwörtern muß ich auch nur 2 Dateien in bekannten Verzeichnissen öffenen, da wird schonma nichts gesucht, dann werden ein paar 100-1000 IDs verglichen, was auch recht schnell ist, und dann einige Posting-Dateien mit den metadaten direkt geöffnet), die DSatenbank hat darüber hinaus ja noch den Aufwand die _gesamten_ Daten in der Tabellen-Datei zu parsen und und zu filtern, das _muss_ doch einfach erheblich langsamer sein, oder? Und wenn man für das ganze ein schönes Fronntend und schöne Wartungsscripte schreibt, meinst Du bei dem Daten-Aufkommen wie hier im Fourm wäre ein Server wie der vorhandene überfordert beim Ändern und Erzeugen des Baums? Vielleicht kann man dann noch einen eigenen "Cache" bauen indem man die 2-5% am meisten Vorkommenden Suchwörter auf eine RAMdisk schreibt!?

Wenn das bei jedem Zugriff gemacht werden muß, dann ist es aus exakt demselben Grund schlecht wie die Verwendung einer HEAP-Tabelle aus mySQL (Du siehst, die Konzepte sind immer dieselben, nur die Namen ändern sich).
Wenn das aber ein daemon permanent im Speicher hält und Deine CGI-Programme sich per UNIX domain socket mit diesem verbinden, so wie dies im neuen Self-Forum der Fall ist ...

schön, aber da ist es wieder das Problem mit dem beschränkten RAM. Der Hash ist ja gerade die Datenquelle die nur für ein Jahr erheblich über 100MB beträgt.
So mal ganz blöd gefragt, ist das von der Performance was ganz anders als z.B. in PHP so einen Hash(array) zu erzeugen, die print_r() Ausgabe zu puffern und in eine Variable und dann in eine Datei schreiben, die dann auf einer RAMdisk speichern und dann in andere PHP-Scripte einbinden?  (wenn Du das nachvollziehen konntest ;-))

Viele Grüße
Andreas

[Michael Schröpl]

Hi Andreas,

Ein Index ist ein Index.
Nur arbeitet der FULLTEXT auf einer Spalte einer Tabelle, die Du nicht explizit siehst.
Ja, aber wo ist das jetzt logarithmisch? Es werden doch _linear_ alle Wörter abgearbeitet, oder?

Keineswegs. Du arbeitest ja mit dem Index über diese Tabelle. Und der rekursive Abstieg innerhalb des Indexbaums ist im günstigsten Fall (UNIQUE INDEX) ein logarithmischer Zugriff.
Sind die Treffer nicht unique, dann müssen die gefundenen Teilbäume traversiert werden ... das ist dann etwas lästiger, aber hoffentlich immer noch besser als linear. (Der Super-GAU ist ein Indexbaum mit lauter identischen Suchbegriffen ... deshalb muß ein intelligenter Query Optimizer die mittlere Projektivität eines jeden Index kennen.)

Ist das </archiv/2002/11/30580/#m165087> in etwa das was Du damit gemeint hast?
Ja. Ich habe diesen Thread nachträglich gelesen, hatte Christians guten Ausführungen aber nichts hinzuzufügen.
Ich wollte auch nur sicher gehen ;-) Solang ich den Fulltext Index verwende brauch ich die ja nicht, aber bei einer eigenen Tabelle sollte ich mit Hilfe dieser Funktion die Datensätze generieren oder?

Ja. Dieser "Wort-Zerschlager" inklusive seiner wordchar-Funktion ist etwas, das Du dann selbst implementieren müßtest, um das INSERT/UPDATE/DELETE in die zusätzliche Tabelle hinzukriegen. (Und was ich selbst implementiert habe, um anschließend meine Stopwortliste zu bauen.)

Dann wird es nicht schnell. Es sei denn, Dein Betriebssystem hasht diese komplette Struktur, hält sie also als sortierten Baum im RAM. Das wiederum hängt vom Treiber Deines Dateisystems ab ... bei Solaris war dieser Caching-Effekt sehr stark beobachtbar.
Bei Linux wird glaube ich alles im RAM gerhalten, was man zuletzt verwendet hat, da gibt es irgendeinen Automatismus. Aber wie gesagt, ich hab nicht genug RAM, und Ihr auch nicht, wenn Du alle Archive... da reinpacken wolltest, dann würde es schon Eng für andere Anwendungen.

Eben. Du wirst nicht besser als bei FULLTEXT, was von mySQL sicherlich ebenfalls intelligent geswappt wird.

Das Aufbauen dauert zu lange. Und mir lief ein 10-GB-Dateisystem über, weil mir die inodes ausgingen.
Wieviele Dateien/Verzeichisse hattest Du denn da grob geschätzt? Gibt doch bestimmt Dateisysteme die hier besonders spendabel sind, oder nicht?

Bei Solaris kann ich die inodes nicht beliebig genau angeben. Dort nimmt das Dateisystem eine Mindestgröße pro Datei an, d. h. es beschränkt die Menge der inodes pro MB Dateisystem.
Meine 10-GB-Platte war bezüglich inodes voll, bezüglich Dateien nahezu leer ...

Also fasse ich das zusammen dass das Lesen sehr schnell ist, aber das Schreiben extrem lange dauert.

Ja. "mkdir" unter Solaris ist viel langsamer als "md" unter Windows NT4, beispielsweise - ich habe dasselbe Programm auf beiden Maschinen laufen lassen, und ein Pentium 800 schlug den fetten Solaris-Hobel um Faktor 10. Es kann natürlich sein, daß dies bei bestimmten Dateisystemtreibern unter *NIX weniger krass ausfällt ...

die Datenbank hat darüber hinaus ja noch den Aufwand die _gesamten_ Daten in der Tabellen-Datei zu parsen und und zu filtern

Wieso? Um das zu verhindern, legst Du doch die Indexe an.

Und wenn man für das ganze ein schönes Fronntend und schöne Wartungsscripte schreibt, meinst Du bei dem Daten-Aufkommen wie hier im Forum wäre ein Server wie der vorhandene überfordert beim Ändern und Erzeugen des Baums?

In Deinem Fall müßte immerhin nur eingefügt werden und nicht gelöscht. In meinem Fall war das schlimmer - da konnten von Tag zu Tag mal 10% des Datenbestands an Änderungen anfallen.

Ich verwende das von uns diskutierte Verfahren mit mySQL-FULLTEXT für eine Datenbank mit einer Million "Postings", die allerdings im Schnitt kleiner sind (ca. 1500 Bytes). Ich habe pro Tag etwa 30000 Zugriffe auf diese Tabelle ... und mySQL frißt im Schnitt keine 10% Maschinenlast dabei, obwohl simultan auch noch neue Postings eingefügt und geindext werden (ca. 5000 Stück pro Tag). Was die Sache bei mir so schnell macht (die meisten Suchanfragen dauern deutlich weniger als 5 Sekunden), das ist die Qualität der Suchbegriffe, die in meinem Fall aufgrund der Natur der Daten meistens ziemlich gut ist. Ich habe auch einige wenige Anfragen pro Tag, die länger als 30 Sekunden dauern ... der Mittelwert ist allerdings hinreichend gut.

Vielleicht kann man dann noch einen eigenen "Cache" bauen indem man die 2-5% am meisten Vorkommenden Suchwörter auf eine RAMdisk schreibt!?

Das habe ich nicht verstanden. Meinst Du die Suchworte oder die zugehörigen Postings? Das erste macht m. E. wenig Sinn, das zweite kann 90+% aller Postings ausmachen.

So mal ganz blöd gefragt, ist das von der Performance was ganz anders als z.B. in PHP so einen Hash(array) zu erzeugen, die print_r() Ausgabe zu puffern und in eine Variable und dann in eine Datei schreiben, die dann auf einer RAMdisk speichern und dann in andere PHP-Scripte einbinden?  (wenn Du das nachvollziehen konntest ;-))

Über PHP kann ich keinerlei Aussagen machen.

Viele Grüße
      Michael

[Christian Kruse]

Hallo Andreas, hallo Michael,

Dann wird es nicht schnell. Es sei denn, Dein
Betriebssystem hasht diese komplette Struktur, hält sie
also als sortierten Baum im RAM.

Etwas 'hashen' ist aber was anderes ;) Du meinst 'cachen'?
Tatsaechlich muss ueberigens eine Verzeichnis-Struktur nicht
komplett im Speicher gehalten werden, um einen Baum zu haben.

Das wiederum hängt vom Treiber Deines Dateisystems ab
... bei Solaris war dieser Caching-Effekt sehr stark
beobachtbar.
Bei Linux wird glaube ich alles im RAM gerhalten, was man
zuletzt verwendet hat, da gibt es irgendeinen
Automatismus.

Das haengt vom verwendeten Dateisystem ab. Hoert auf von
Betriebssystemen zu reden und fangt an ueber Dateisysteme zu
reden. Auch bei Solaris gibt es verschiedene Datei-Systeme
(und auch verschiedene Versionen von Dateisystemen!), die man
einsetzen kann.

Tatsaechlich ist z. B. ext2fs nicht zwingend gecached.

So mal ganz blöd gefragt, ist das von der Performance was
ganz anders als z.B. in PHP so einen Hash(array) zu
erzeugen, die print_r() Ausgabe zu puffern und in eine
Variable und dann in eine Datei schreiben, die dann auf
einer RAMdisk speichern und dann in andere PHP-Scripte
einbinden?  (wenn Du das nachvollziehen konntest ;-))

Es gibt wesentlich sinnvollere Speicherarten fuer Hashes als
die Ausgabe von print_r. Und das Einbinden wuerde ich eh ganz
abraten, da gibt es wirklich schnellere und bessere
Speicherarten, einen Hash aufzubauen.
Aber alle Verfahren werden darauf hinauslaufen, dass sie im
guenstigsten Fall linear sind. Wenn du Pech hast, auch
quadratisch.

Gruesse,
 CK

[Andreas Korthaus]

Hallo Christian!

Etwas 'hashen' ist aber was anderes ;) Du meinst 'cachen'?

oh ja ;-)

Tatsaechlich muss ueberigens eine Verzeichnis-Struktur nicht
komplett im Speicher gehalten werden, um einen Baum zu haben.

Beziehst Du Dich auf meinen vorherigen Verzeichnis-Baum in dem die Postings gespeichert werden könnten?

Das haengt vom verwendeten Dateisystem ab. Hoert auf von
Betriebssystemen zu reden und fangt an ueber Dateisysteme zu
reden. Auch bei Solaris gibt es verschiedene Datei-Systeme
(und auch verschiedene Versionen von Dateisystemen!), die man
einsetzen kann.

OK. Glaube so langsam verstehe ich das besser, die Verschiedenen Dateisysteme haben eigene Caching-Mechanismen, und lagern wenn der Ram "voll" ist Daten in den SWAP-Space aus, so machst das zumindest mein Linux( ;-) ich weiß, aber bin gerade nicht sicher welches Dateisystem ich da habe, glaube ext2fs).

Es gibt wesentlich sinnvollere Speicherarten fuer Hashes als
die Ausgabe von print_r. Und das Einbinden wuerde ich eh ganz
abraten, da gibt es wirklich schnellere und bessere
Speicherarten, einen Hash aufzubauen.
Aber alle Verfahren werden darauf hinauslaufen, dass sie im
guenstigsten Fall linear sind. Wenn du Pech hast, auch
quadratisch.

Leider beschränkt sich meine Sichtweise noch meist auf die mir in PHP bekannten Möglichkeiten udn Funktionen. Das PHP aber außerhalb von Web-Anwendungen wirklich etas beschränkt ist im Gegensatz zu PERL oder C, bekomme ich mit der Zeit immer mehr zu spüren. Aber leider kann ich PERL nicht gut genug, C bzw. C++ schon gar nicht.
Soweit ich das jetzt verstanden habe gibt es sowohl die Möglichkeit in PERL einen B-Baum zu speichern, wo ich mir halt noch nicht wirklich vorstellen kann wie das funkionieren soll, genausowenige verstehe ich wei man eine Hash speichern können soll, was nicht heitß das ich was dagegen sagen wollte, ganz im Gegenteil, nur habe ich mit solchen Dingen noch nie zu tun gehabt und kann es mir halt nicht vorstellen. Ich kann bisher nur Daten wie auch immer ein Flat-Files schreiben, ob über eine DB oder direkt, mit irgendeine schlauen Struktur, nur würde mir hier keine Struktur für einen Hash und einen B-Baum einfallen, daher vermute ich das das nicht in FlatFiles gespeichert wird, sondern in irgendeinem binären Format, was ich mir sowieso nicht angucken kann... naja, ich muß noch vieles lernen ;-)
Vor allem PERL und C(++)

Grüße
Andreas

[Christian Kruse]

Hallo Andreas,

Tatsaechlich muss ueberigens eine Verzeichnis-Struktur
nicht komplett im Speicher gehalten werden, um einen
Baum zu haben.
Beziehst Du Dich auf meinen vorherigen Verzeichnis-Baum in
dem die Postings gespeichert werden könnten?

Ich beziehe mich auf Michaels Aussage, dass bestimmte
Dateisysteme ihre Datei- und Verzeichnis-Listen als
Baum-Strukturen im Speicher cachen. Man muss die Listen nicht
cachen, um Baumstrukturen zu haben.

Das haengt vom verwendeten Dateisystem ab. Hoert auf von
Betriebssystemen zu reden und fangt an ueber
Dateisysteme zu reden. Auch bei Solaris gibt es
verschiedene Datei-Systeme (und auch verschiedene
Versionen von Dateisystemen!), die man einsetzen kann.
OK. Glaube so langsam verstehe ich das besser, die
Verschiedenen Dateisysteme haben eigene
Caching-Mechanismen,

Korrekt.

und lagern wenn der Ram "voll" ist Daten in den SWAP-Space
aus,

Nein, in den Swap-Space werden nur Daten ausgelagert, wenn
der RAM zu klein ist. Will heissen, der Speicher jeder
Applikation wird in den Swapspace ausgelagert, wenn der
Hauptspeicher zu voll wird.

so machst das zumindest mein Linux( ;-) ich weiß, aber
bin gerade nicht sicher welches Dateisystem ich da habe,
glaube ext2fs).

Die Ausgabe von 'mount' sollte das anzeigen:

ckruse@sunshine:~/dev/www/selfforum $ mount
/dev/ad0s2a on / (ufs, local)
/dev/ad0s1 on /mnt/win (msdos, local)
/dev/ad0s2f on /usr (ufs, local, soft-updates)
/dev/ad0s2e on /var (ufs, local, soft-updates)
procfs on /proc (procfs, local)
linprocfs on /usr/compat/linux/proc (linprocfs, local)
rain:/home/ckruse on /usr/home/ckruse/dev (nfs)
/dev/cd0c on /cdrom (cd9660, local, read-only)
ckruse@sunshine:~/dev/www/selfforum $

Es gibt wesentlich sinnvollere Speicherarten fuer
Hashes als die Ausgabe von print_r. Und das Einbinden
wuerde ich eh ganz abraten, da gibt es wirklich
schnellere und bessere Speicherarten, einen Hash
aufzubauen. Aber alle Verfahren werden darauf
hinauslaufen, dass sie im guenstigsten Fall linear
sind. Wenn du Pech hast, auch quadratisch.
Leider beschränkt sich meine Sichtweise noch meist auf die
mir in PHP bekannten Möglichkeiten udn Funktionen.

Das hat jetzt mit der Sprache aber wenig zu tun. Verabschiede
dich von der Vorstellung, dass Sprachen dir alles abnehmen.
Das meiste muss man von Hand machen.

Soweit ich das jetzt verstanden habe gibt es sowohl die
Möglichkeit in PERL einen B-Baum zu speichern, wo ich mir
halt noch nicht wirklich vorstellen kann wie das
funkionieren soll, genausowenige verstehe ich wei man
eine Hash speichern können soll, was nicht heitß das
ich was dagegen sagen wollte, ganz im Gegenteil, nur habe
ich mit solchen Dingen noch nie zu tun gehabt und kann es
mir halt nicht vorstellen.

Die einfachste Form eine Hashtable zu speichern waere es,
Key-Value-Paare in die Datei zu schreiben. Ist man naeher an
der Implementation selber, so kann man direkt die
Hashtable-Struktur speichern und so das erzeugen der
Hash-Summen sparen:

index:len:key:len:hashsum:len:data:index:len:key:len:hashsum:len:data...

Index steht dabei fuer den Tabellen-Index. Durch die
len-Felder kann man sich das Ausprobieren und das suchen nach
den Separatoren sparen. Gibt man 'len' jetzt noch ein festes
Format, kann man genau definierte Strings herumkopieren.

Aber beide Algorithmen sind nur linear. Was besseres wirst du
da nicht hinbekommen koennen.

Einen B-Baum zu speichern ist schon schwerer. Da gibt es
verschiedene Strategien. Du koenntest rekursiv zu jedem
Knoten von links nach rechts die Zweige speichern.
Auf diese Art und weise laesst sich der Baum sehr einfach
wiederherstellen.

Aber sicherlich gibt es gerade fuer B-Baeume bessere
Moeglichkeiten. Mir faellt nur gerade keiner ein und ich habe
leider gerade auch kein Algorithmen-Buch zur Hand.

Gruesse,
 CK

[Michael Schröpl]

Hi Christian,

Die Ausgabe von 'mount' sollte das anzeigen:

das sieht unter Solaris natürlich auch anders aus ... aber "mount -v" sagt mir, daß wir im Wesentlichen "ufs" verwenden.

Aber sicherlich gibt es gerade fuer B-Baeume bessere
Moeglichkeiten. Mir faellt nur gerade keiner ein und ich habe
leider gerade auch kein Algorithmen-Buch zur Hand.

Was spricht gegen "gar nichts verstehen und einfach den Hauptspeicher dumpen"? Das klingt auch linear ...

Viele Grüße
      Michael

[Christian Kruse]

Hallo Michael,

Die Ausgabe von 'mount' sollte das anzeigen:

das sieht unter Solaris natürlich auch anders aus ...

Das war zu erwarten.

aber "mount -v" sagt mir, daß wir im Wesentlichen "ufs"
verwenden.

Welche Version? :) Die aktuelle Version ist naemlich ein
journaling filesystem.

Aber sicherlich gibt es gerade fuer B-Baeume bessere
Moeglichkeiten. Mir faellt nur gerade keiner ein und
ich habe leider gerade auch kein Algorithmen-Buch zur
Hand.

Was spricht gegen "gar nichts verstehen und einfach den
Hauptspeicher dumpen"? Das klingt auch linear ...

Das ist bei tiefen Strukturen leider so ohne weiteres nicht
moeglich.

Gruesse,
 CK

[Michael Schröpl]

Hi Christian,

aber "mount -v" sagt mir, daß wir im Wesentlichen "ufs"
verwenden.
Welche Version? :) Die aktuelle Version ist naemlich ein
journaling filesystem.

wo bekomme ich das heraus? "man mount" ist nicht sehr gesprächig ... (Sun OS 5.8, meint "uname -a")

Aber sicherlich gibt es gerade fuer B-Baeume bessere
Moeglichkeiten. Mir faellt nur gerade keiner ein und
ich habe leider gerade auch kein Algorithmen-Buch zur
Hand.
Was spricht gegen "gar nichts verstehen und einfach den
Hauptspeicher dumpen"? Das klingt auch linear ...
Das ist bei tiefen Strukturen leider so ohne weiteres nicht
moeglich.

"so ohne weiteres" sicher nicht, falls absolute Pointer darin verwendet werden.
Aber bei relativen Pointern? Oder wenn man mit abspeichert, an welche Stelle des Adreßraums diese Seiten wieder geladen werden müssen? Bei einer Datenbank mit fest alloziertem Speicher ab daemon-Start könnte ich mir durchaus vorstellen, daß so etwas möglich ist.

Viele Grüße
      Michael

[Christian Kruse]

Hallo Michael,

wo bekomme ich das heraus? "man mount" ist nicht sehr
gesprächig ... (Sun OS 5.8, meint "uname -a")

Gute Frage. Wie alt ist in etwa das System? Wenn es aelter
als ein halbes Jahr ist, dann wird es noch kein journaling FS
sein.

"so ohne weiteres" sicher nicht, falls absolute Pointer
darin verwendet werden.

Das muss letztenendes zwangslaeufig gemacht werden.

Aber bei relativen Pointern?

Prinzipiell moeglich. Aber unrealistisch, man kriegt vom OS
nie soviel Speicher an einem Stueck zugeteilt. Da gibts dann
eher eine 'out of memory'-Meldung :)

Oder wenn man mit abspeichert, an welche Stelle des
Adreßraums diese Seiten wieder geladen werden müssen?

Und damit hat man dann keinen Dump mehr.

Gruesse,
 CK

[Michael Schröpl]

Hi Andreas,

Soweit ich das jetzt verstanden habe gibt es sowohl die Möglichkeit in PERL einen B-Baum zu speichern, wo ich mir halt noch nicht wirklich vorstellen kann wie das funkionieren soll

wenn Du eine Speicherstruktur irgendwohin duplizieren willst, dann gibt es (mindestens) zwei Möglichkeiten:
a) Du versuchst, sie zu verstehen, und ihren Inhalt (in einer ggf. anderen Form) auf dem Zielmedium irgendwie darzustellen. In diesem Fall ist der Aufwand mindestens linear zur Anzahl der Elemente Deiner Speicherstruktur - ganz einfach, weil Du sie elementweise verarbeitest.
b) Du verzichtest darauf, sie zu verstehen, und wendest Dich statt dessen an eine "tiefere Ebene". Im Falle eines Baums könnte dies darin bestehen, daß Du einfach den kompletten RAM-Bereich auslagerst, in welchem dieser Baum enthalten ist. Das kann bezogen auf den I/O-Traffic "etwas zuviel" sein, aber der Aufwand ist nun unabhängig davon, wieviele Knoten Du hast - er ist nur noch abhängig davon, in wie vielen Seiten diese Knoten dargestellt sind.
Während Du bei b) den exakten Originalzustand des Baums wiederherstellen wirst, hast Du bei a) die Möglichkeit, zusätzlich sekundäre Ziele zu verfolgen - beispielsweise die physikalische Struktur Deiner logischen Daten zu beeinflussen. Stell Dir vor, Du weißt, wie viele Knoten ein Baum enthält - dann kannst Du beim Kopieren des Baums nebenbei dafür sorgen, daß die Kopie wieder optimal balanciert ist ... der Ziel-Baum hat dann eine andere Struktur, aber (bezüglich der Anordnung seiner Knoten für eventuelle Traversierungsoperationen) immer noch denselben Inhalt.

genausowenige verstehe ich wei man eine Hash speichern können soll

Meinst Du hier intern oder extern? (Wobei beides im Falle von b) identisch sein könnte, im Falle von a) nicht unbedingt.)

nur habe ich mit solchen Dingen noch nie zu tun gehabt und kann es mir halt nicht vorstellen.

Informatik III, Algorithmen und Datenstrukturen. (Das gleichnamige Buch von Niklaus Wirth ist in dieser Hinsicht immer noch lesenswert, auch wenn meine uralte Auflage von 1980 drucktechnisch miserabel war und Wirth zur Notation seiner Algorithmen PASCAL verwendet.)

nur würde mir hier keine Struktur für einen Hash und einen B-Baum einfallen,

Eine Struktur ist generell nicht "an sich gut", sondern immer nur in Bezug auf eine gestellte Aufgabe. Welche Randbedingungen sollte diese Struktur erfüllen? Welche Arten von Operationen möchtest Du auf dieser Datenstruktur durchführen können? Welche Operationen soll mit welchen Kosten (komplexitätstheoretisch betrachtet) realisierbar sein?

daher vermute ich das das nicht in FlatFiles gespeichert wird, sondern in irgendeinem binären Format, was ich mir sowieso nicht angucken kann ...

Erstens kannst Du das im Quelltext des entsprechenden Programms nachlesen (beispielsweise demjenigen der mySQL-Tabellentreiber), und zweitens ist es relativ egal, ob diese Daten binär oder menschenlesbar gespeichert sind: Das ist lediglich eine zusätzliche polynomielle Transformation, die komplexitätstheoretisch nicht ins Gewicht fällt.

naja, ich muß noch vieles lernen ;-)
Vor allem PERL und C(++)

Ich denke, eher Datenstrukturen und Algorithmen. Die Umsetzung in eine konkrete Sprache ist das kleinere Problem: Entweder hat diese Sprache ein fertige Modul dafür, oder Du schreibst Dir eines.

Was ich für wichtiger halte, ist das Verständnis dafür, daß manche Datenstrukturen bestimmte Operationen auf bestimmten Daten in bestimmten Kostenfunktionen erlauben ... die Erkenntnis, _wieso_ Bäume und logarithmische Zugriffe zueinander gehören, ist ein wichtiger Lernerfolg, und die Verallgemeinerung auf B*-Bäume mit dem entsprechenden Folgen für die Komplexität der Algorithmen ist dann nicht mehr schwer.
Im Vergleich dazu funktionieren gehashte Daten (also solche, die über eine Hash-Funktion statt einen Baum adressiert werden), durchaus anders ... und Du hast dabei mehr Schräubchen, an denen Du drehen kannst (und mußt) als bei einem (binären) Baum.

Viele Grüße
      Michael

[Frank Schönmann]

hi!

Ich habe mir auch Dank Franks Posting ein paar Sachen dazu
durchlesen können, bin wie gesagt auch auf Implementierung von B-
Bäumen in PERL gestoßen, aber da muß erst der komplette Inhalt in
einen Hash geladen werden und der Baum zur Laufzeit erstellt
werden, das hate ich unten bereits geschreiben das ich das für
wenig optimal halte!

Das ist natürlich Unfug, einen derart großen Baum zur Laufzeit zu
erstellen. Sinnvoller ist es IMHO, auf der Festplatte ziemlich genau
nachzubilden, wie der Baum im Speicher aussehen würde: die Inhalte
eines Knotens werden dann durch eine Art Speicher-Dump auf die Platte
gelegt und können dann auch ohne Parsen direkt wieder in den Speicher
kopiert werden (das ist auch in Perl möglich).

Dann muss man sich nur noch darum kümmern, dass bei Zugriffen auf
Eltern- oder Kindknoten potentiell noch nicht von Platte geladene
Seiten bei Zugriff im Speicher vorhanden sind.

bye, Frank!