Hi,

da ich grade eine halbe stunde tipparbeit verloren habe antworte ich mal in mehreren Posts:

Nein, da geht nix verloren, wenn da steht "Das war jetzt etwas zu lang". Aber wenn man dann etwas zu hektisch reagiert ist natürlich alles weg. Macht aber nix, passiert mir auch hin und wieder. Ist auch ganz gut gegen Abschweifungen.

Aber wahrscheinlich macht alleine schon ein Cache der letzten Abfragen einer Session auch sehr viel sinn, weil die Querys eines Nutzers oft sukzessive wachsen.

Ich meinte ein zusätzliche Caching der Abfragen der letzten x Minuten, da viele ihre Queries sukzesive anpassen, bis sie ausreichend wenige Treffer haben.

Du verfügst über eine Statistik der Forumssuche in derart hoher Auflösung? Kommen da andere auch ran?

Aber ich glaube, so langsam komme ich dahinter:
Du möchtest also gerne die sonst üblichen Linked Lists, die bei der Methode 2) entstehen durch eine weitere Hashtabelle ersetzen. Und wenn es bei dieser dann Kollisionen gibt, wiederum eine Hashtabelle anstatt einer Linked List nehmen und das ad finitum acerbum?

soll heißen  "bis zum bitteren Ende" ???

Ja.
Ist die Rache eines Humanisten am Denglisch.

Nä, das wäre ja völlig beklopft, das kann's wohl doch nicht gewesen sein?

Jein, in der 2. Stufe ist Schluss. Man kann kein beliebig großes Hash im RAM halten, deswegen soll die erste Stufe H im RAM liegen und die der 2. Stufe K(H) auf der Platte, die für jede Zelle von H seine Kollisionen  enthalten. Zahlenbeispiel: Hat H 16bit ~ 64K Zellen, brauche ich auch 65536 sekundäre Hashes K auf der Platte.

Das ist nicht sonderlich sinnvoll, da die zweite Hashtabelle ebenfalls unter Kollisionen leiden wird. Wie regelst Du die?
BTW: Du benötigst für den ganzen Schisselamäng nur eine einzige ordentliche Hashfunktion, nicht mehr. Auch wenn die Hashtabellen optisch als zusammengehörig erscheinen, so sind sie doch völlig unabhängig und Du kannst einen einmal mühselig errechneten Hashwert vollständig wiederverwenden.

Jetzt suche ich ein Wort W.

Fall 1 (Treffer): Ist das Schlüsselwort von S(H(W))=W habe ich gewonnen und erhalte eine Liste L(H(W)) aller Postings die W enthalten.

Woher weißt Du das?
Dafür mußt Du den Hashwert ausrechnen. Der zeigt auf ein Loch, darin ist entweder nix oder es ist belegt. Im Falle der Suche ist die Belegung wichtig. Um jedoch herauszufinden, ob es sich um eine Kollision handelt, mußt Du das Wort mit dem Inhalt des Loches vergleichen. Also muß im Loch auch das Wort sein. Ist es belegt aber nicht vom gesuchtem Wort ist es eine Kollision:

Fall 2 (Kollision): Ich muss ich auf die Platte zugreifen und suche W im zugehörigen Hash K(H(W)).

I/O ist als genauso teuer anzusehen, wie ein DB-Anfrage. Dieser Teil der Übung ist also zweckfrei, direkte Anfage an DB wäre günstiger.

Obige Hashtabelle wäre sehr günstig, wenn alle Anfragen Einwortanfragen wären. Bei Mehrwortanfragen wäre jedes Wort einzeln zu prüfen. Gut, das ist seltenst viel, das würde sich wahrscheinlich auch noch lohnen. Phrasensuche wäre aber schon schwieriger.
Zudem ist diese Technik auf die Serverseite beschränkt.
Ein Bloomfilter zwischen Eingabe und Cache macht da deutlich mehr Sinn.

1. Während die größe des Hashes H fix ist, und sich nach verfügbarem RAM richet, können die K(H) auf der Platte wachsen. (letzteres IMHO langsamer als eine relationale DB wächst)

Nein, können sie nicht. Du kannst sie nur statsisch einrichten. Das aber natürlich nach Bedarf: wenn an der Stelle noch nichts kollidiert ist, besteht natürlich auch noch kein Bedarf.

2. (Posting) Für jedes neue Posting müssen pro enthaltenem Wort die Liste L(W) um die Refernez auf das neue Posting erweitert werden.

Wie ist dies Liste implementiert?

3. (Neuwörter) Kommt ein neues Wort hinzu, muss es auch in im zugehörigen K auf der Platte eingetragen werden.

Klar, wenn man bei der Suche auf ein leeres Loch stößt, wird eingetragen. Aber das ist glaube ich so Usus bei Hastabellen.

4. (Reorganisation) Wenn ich dich recht verstanden habe sollten 25% der Zellen eines Hashes frei sein, sind also mehr als 75% eines K belegt, ersetzt man ihn durch einen doppelt so großen.

Ja, das ist die übliche und wohlerprobte Vorgehensweise.

Diese Reorganisation dürfte aber sehr selten vorkommen, weil das Vokabular des Forums nicht so schnell wächst.

Davon kannst Du nicht ausgehen, eher davon ds es zwischenzeitlich heftige Sprünge geben wird. Es muß nur eine andere Programmiersprache modern werden, ja, nur ein kurzes Listing in einer anderen Sprache würde einen guten Hub ergeben.

5. (Plattenbedarf): Von 4. ausgehend brauche ich im Schnitt 25% mehr Platz für die K-Hashes als Einträge da sind. Für die L-Listen schätze ich weniger als ein Viertel des Vollindexes ein, insgesamt vielleicht 250 MB.(?)

Kein Ahnung, könnte aber hinkommen.

Wichtig ist das die Hashfkt in H eineseits und den Ks unabhängig möglichst unabhängig sein muss, damit es keine unnötigen Kollisionen gibt (wären sie identisch gäbs den GAU). Der Ansatz über eine 32bit Fkt die ich in 2 kleinere zerlege war ein Versuch das zu garantieren (in diesem Fall wäre auch die Reorganisation eines K sehr billig)

Nein, Du brauchst nur eine einzige Hashfunktion, da alle Hastabellen in Deinem Gedankenexperiment unabhängig sind.

Ich hoffe das grobe Konzept einigermaßen rübergebracht zu haben,

Also um ehrlich zu sein ...
Wie wäre es mit einem kurzem Proof-of-Concept?

natürlich steckt da noch Verbesserungspotential drinnen.

Insbesondere ist wichtig wie am besten Daten auf der Platte organisiert und darauf zugegriffen wird,

Das solltest Du dem Dateisystem überlassen, die modernen wie z.B. ReiserFS sind da kaum zu überbieten. Du kannst einafch schreiben, den Rest übernimmt das FS.

ich denke die DB arbeitet da schon ziemlich effizient.

Eben.

so short

Christoph Zurnieden