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