Wie vergleicht Trie und B + Baum für die Indexierung lexikographisch sortierten Strings [in der Größenordnung von einigen Milliarden]? Es sollte auch Bereichsabfragen unterstützen.Trie vs B + Baum
Von perf. sowie Sicht auf die Komplexität der Implementierung.
Ich würde sagen, es hängt davon ab, was Sie von Bereich bedeuten.
Wenn Ihr Bereich als ausgedrückt wird Alle Wörter beginnend mit, dann ist eine Trie die richtige Wahl, die ich sagen würde. Auf der anderen Seite, Trie sind nicht für Anfragen wie Alle Wörter zwischen XX und ZZ gemeint.
Beachten Sie, dass der Verzweigungsfaktor des B+ Tree seine Leistung beeinflusst (die Anzahl der Zwischenknoten). Wenn h die Höhe des Baums ist, dann n max ~~ b h. Daher h ~~ log (n max)/log (b).
Mit n = 1 000 000 000 und b = 100 haben wir h ~~ 5. Daher bedeutet es nur 5 Zeiger Dereferenzierung für den Übergang von der Wurzel zum Blatt. Es ist Cache-freundlicher als ein Trie.
Schließlich ist B+ Tree zugegebenermaßen schwieriger als ein Trie zu implementieren: es mehr auf einem Red-Black Tree Komplexitätsniveau ist.
Hängt von Ihrer eigentlichen Aufgabe:
N Kinder von einem substree erhalten möge, dann eine Trie ist die beste Wahl.Einige Varianten von Versuchen, die ich verwende, sind nicht nur platzsparender als BTrees, sondern auch schneller für die meisten Abfragen (direkter Zugriff, Wortvervollständigung, Bereichsabfrage). –
Wenn Sie schlau über Ihre Trie Implementierung als "alle Wörter zwischen xx und zz" ist nicht so schwierig. Wenn Sie die Kanten in lexikografischer Reihenfolge speichern, sind die Strings ebenfalls lexikografisch geordnet. –
Es ist jedoch ein bisschen schwieriger, die Reichweite auszunutzen. In einem 'B + Baum' kann ein Bereich durch zwei Zeiger (Anfang/Ende) definiert werden und Sie können diese wie in einem Deque durchlaufen. In einem 'Trie' muss man Iteration implementieren (von einem zufälligen Zeiger zu einem anderen), um das gleiche zu tun, es ist weniger natürlich, aber natürlich nicht unmöglich und ich fürchte, es ist weniger effizient. Oder Sie kopieren einfach den Bereich in eine andere Struktur, aber das könnte teuer werden. –
fälschte es versehentlich ab, sollte es verbessern. Ich bin nicht in der Lage, es jetzt zurück zu ändern :( –