¿Cómo se comparan Trie y B + tree para indexar cadenas ordenadas lexicográficamente [en el orden algunos miles de millones]? También debe admitir consultas de rango.Trie vs B + tree
De perf. así como el punto de vista de la complejidad de la implementación.
Yo diría que depende de lo que quiere decir con Rango.
Si su rango se expresa como Todas las palabras que empiezan por, a continuación, un Trie es la elección correcta diría yo. Por otro lado, Trie no son para solicitudes como Todas las palabras entre XX y ZZ.
Tenga en cuenta que el factor de bifurcación de B+ Tree afecta su rendimiento (la cantidad de nodos intermedios). Si h es la altura del árbol, entonces n máximo ~~ b h. Por lo tanto, h ~~ log (n max)/log (b).
Con n = 1 000 000 000 y b = 100, tenemos h ~~ 5. Por lo tanto, solo significa desreferencia de 5 punteros para pasar de la raíz a la hoja. Es más compatible con la caché que un Trie.
Finalmente, B+ Tree es ciertamente más difícil de implementar que un Trie: está más en un nivel de complejidad Red-Black Tree.
depende de su tarea actual:
N niños de un substree, a continuación, un Trie es la mejor opción, ya que simplemente visitar menos nodos que en un escenario + Tree B.Algunas variaciones de intentos que estoy usando no solo son más eficientes en espacio que BTrees, sino también más rápidas para la mayoría de las consultas (acceso directo, finalización de palabras, consulta de rango). –
Si es inteligente acerca de su implementación de Trie que "todas las palabras entre xx y zz" no es tan difícil. Si está almacenando los bordes en orden lexicográfico, entonces las cadenas están en orden lexicográfico también. –
Aunque es un poco más difícil explotar el rango. En un 'B + Tree' un rango puede definirse por dos punteros (inicio/fin) y puede iterar a través de ellos como en un deque. En un 'Trie' tienes que implementar la iteración (de un puntero al azar a otro) para poder hacer lo mismo, es menos natural, aunque por supuesto no es inviable y me temo que es menos eficiente. O simplemente puede copiar el rango en otra estructura, pero eso podría ser costoso. –
votado por error, se suponía que debía votarlo. No puedo volver a cambiarlo ahora :( –