Hi,

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

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.

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" ???

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.

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.

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

Damit sich das lohnt darf es in möglichst wenigen Fällen Zugriffe auf die Platte geben, deswegen  sollten die Treffer S(H) gleich dem jeweils meistgewünschtem Schlüssel in den zugehörigen Subhashes K(H) sein, was dann einem Cashing nahekommt.

Ressourcenanfoderung:

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)

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.

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

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. Diese Reorganisation dürfte aber sehr selten vorkommen, weil das Vokabular des Forums nicht so schnell wächst.

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.(?)

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)

Ich hoffe das grobe Konzept einigermaßen rübergebracht zu haben, natürlich steckt da noch Verbesserungspotential drinnen.

Insbesondere ist wichtig wie am besten Daten auf der Platte organisiert und darauf zugegriffen wird, ich denke die DB arbeitet da schon ziemlich effizient.

... ahh essen ruft ...

Schwein gehabt, was?

ne Grünkrams...  :)

Bye
  rolf