Trie по сравнению с B + дерево
Как делает Trie и B +, дерево сравнивает для индексации лексикографически отсортированных строк [на порядке некоторые миллиарды]? Это должно поддерживать запросы диапазона также.
От перфекта, а также точки зрения сложности реализации.
3 ответа
Я бы сказал, это зависит от того, что вы подразумеваете под Range .
Если ваш диапазон выражен как Все слова, начинающиеся на , то 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 , по общему признанию, труднее реализовать, чем Trie : это больше на уровне сложности Red-Black Tree .
Зависит от вашей реальной задачи:
- Если вы хотите получить целое поддерево , B + дерево - ваш лучший выбор, поскольку он занимает мало места.
- Но если вы хотите получить первые
Nпотомков из поддерева, то Trie - лучший выбор, потому что вы просто посещаете меньше узлов, чем в сценарий B + Tree. - Самая популярная задача, с которой хорошо справляется Trie , - это завершение префикса слов .
В Википедии есть некоторые факты алгоритмической сложности: B + tree (раздел Характеристики), Trie (к сожалению, распространено по всей статье). Надеюсь, это поможет.