Как дерево Trie и B + сравнивается для индексации лексикографически отсортированных строк [порядка нескольких миллиардов]? Он также должен поддерживать запросы диапазона.
От пер. а также с точки зрения сложности реализации.
Trie vs B + дерево
Ответ 1
Я бы сказал, это зависит от того, что вы подразумеваете под диапазоном.
Если ваш диапазон выражен как все слова, начинающиеся с, то Trie - правильный выбор, который я бы сказал. С другой стороны, Trie не предназначены для запросов, таких как все слова между XX и ZZ.
Обратите внимание, что коэффициент ветвления B+ Tree влияет на его производительность (количество промежуточных узлов). Если h - высота дерева, то n max ~~ b h. Поэтому h ~~ log (n max)/log (b).
С n = 1 000 000 000 и b = 100 имеем h ~~ 5. Поэтому это означает только 5 разыменований указателей для перехода от корня к листу. Он более удобен для кэширования, чем Trie.
Наконец, B+ Tree, по общему признанию, сложнее реализовать, чем a Trie: это больше на уровне сложности Red-Black Tree.
Ответ 2
Зависит от вашей фактической задачи:
- Если вы хотите получить целое поддерево, B + Tree - ваш лучший выбор, потому что он эффективен в пространстве.
- Но если вы хотите получить сначала
Nдетей из подстроки, тогда Trie - лучший выбор, потому что вы просто посещаете меньше узлов, чем в B + Дерево сценарий. - Самая популярная задача, которая хорошо обрабатывается Trie, - это префикс префикса .
Ответ 3
В Википедии есть некоторые алгоритмические факты сложности: B + tree (раздел Характеристики), Trie (к сожалению, распространяется по всей статье). Надеюсь, что это поможет.