Suche nach Strings in einem adaptiven Radix-Baum

Question

Ich habe die Forschungsarbeit von "The Adaptive Radix Tree: ARTEful Indexing für Hauptspeicherdatenbanken" durchgelesen. Ich hatte eine Abfrage, wie Sie Strings mit übereinstimmen könnten die Schlüssel des Knotens. Zum Beispiel: Wenn ich ein Wort hätte: Iota, welches der Primärschlüssel (Bezeichner) eines der Tupel in meiner Tabelle ist. Und ich musste es von Werten ausgehend von A wie Alpha bis Zeta suchen. Bitte beachten Sie zur Vereinfachung nur 10 Werte: Alpha, Beta, Delta, Gamma, Kappa, Iota, Phi, Psi, Rho, Zeta. Wie würdest du das machen?

Verweis auf die Forschungsarbeit: https://db.in.tum.de/~leis/papers/ART.pdf

Answer 1

Für mich sieht es aus wie das Papier nur eine regelmäßige Trie Struktur mit unterschiedlichen inneren Knotentypen beschreibt (mit 4, 16 oder 256 Einträgen und eine binäre Suche int die kleineren Fälle erfordern). Die Autoren scheinen auch Ketten von einzelnen Kindknoten in irgendeiner Weise zu komprimieren.

Ich denke nicht, dass es möglich ist, die Struktur sehr gut mit Ihren Beispielschlüsseln zu beschreiben, da sie alle separaten Einträge auf dem Wurzelknoten hätten (mit Ausnahme von Phi und Psi wären sie vom Typ 16). wobei der "P" -Eintrag zu einem 4-Knoten mit Einträgen für "h" und "s" führen würde. Alle verbleibenden Einträge wären optimierte Einzelknoten-Ketten.

Beachten Sie, dass es in realen Fällen normalerweise nicht so viele verschiedene Wörter im Vergleich zu Heapspeichergrößen heute gibt, also würde ich "exotische" Datenstrukturen abwägen, bis es einen echten Fall gibt, der sehr wahrscheinlich ist davon profitieren.