Trie vs B + tree - algoritmo

Como as árvores Trie e B + se comparam para indexar sequências lexicograficamente ordenadas [na ordem em alguns bilhões]? Deve também suportar consultas de intervalo.

Do perf. bem como ponto de vista da complexidade da implementação.

Respostas:

Eu diria que depende do que você entende por Alcance.

Se o seu alcance é expresso como Todas as palavras que começam por, então uma Trie é a escolha certa que eu diria. Por outro lado, Trie não são para pedidos como Todas as palavras entre XX e ZZ.

Observe que o fator de ramificação do B+ Tree afeta seu desempenho (o número de nós intermediários). E se h é a altura da árvore, então n_máximo ~~ b^h. Portanto h ~~ log (n_máximo) / log (b).

Com n = 1 000 000 000 e b = 100, temos h ~~ 5. Portanto, significa apenas 5 referências de ponteiro para ir da raiz para a folha. É mais amigável ao cache do que um Trie.

Finalmente, B+ Tree é reconhecidamente mais difícil de implementar do que um Trie: é mais sobre um Red-Black Tree nível de complexidade.

Depende da sua tarefa real:

• Se você quiser obter o subárvore inteira, uma Árvore B + é a sua melhor escolha porque é eficiente em termos de espaço.
• Mas se você quiser obter o primeiro N crianças de um substree, então um Trie é a melhor escolha porque você simplesmente visita menos nós do que em um cenário B + Tree.
• A tarefa mais popular que é bem tratada por um Trie é um conclusão de prefixo de palavra.

A Wikipedia tem alguns fatos de complexidade algorítmica: Árvore B + (características da seção), Trie (infelizmente espalhados por todo o artigo). Espero que ajude.