nicht angemeldet
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