Trie vs B + tree

Как сравнить дерево Trie и B + для индексации лексикографически отсортированных строк [на порядок несколько миллиардов]? Он также должен поддерживать запросы диапазона.Trie vs B + tree

От пер. а также с точки зрения сложности реализации.

источник

2010-04-22 Fakrudeen

Я бы сказал, что это зависит от того, что вы подразумеваете под Диапазон.

Если ваш диапазон выражен как Все слова, начинающиеся с, то 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.

источник

2010-04-22 07:33:40

Если вы умны в своей реализации Trie, чем «все слова между xx и zz», это не так сложно. Если вы сохраняете ребра в лексикографическом порядке, то строки также находятся в лексикографическом порядке. –

Это немного сложнее, хотя использовать диапазон. В «B + Tree» диапазон может быть определен двумя указателями (начало/конец), и вы можете прокручивать их, как в deque. В «Trie» вам нужно реализовать итерацию (от случайного указателя к другому), чтобы иметь возможность сделать то же самое, она менее естественна, хотя, конечно, небезопасна, и я боюсь, что она менее эффективна. Или вы можете просто скопировать диапазон в другой структуре, но это может быть дорогостоящим. –

проголосовал за это по ошибке, должен был его продвигать. Я не могу изменить его сейчас :( –

Википедия имеет некоторые алгоритмические факты сложности: B+ tree (раздел Характеристики), Trie (к сожалению, распространяется по всей статье). Надеюсь, это поможет.

источник

2010-04-22 06:34:29 thSoft

Зависит от вашей реальной задачи:

Если вы хотите, чтобы получить все поддерево, B + Tree это ваш лучший выбор, потому что это пространство эффективно.
Но если вы хотите получить первые N детей из substree, то Trie является лучшим выбором, потому что вы просто посетить меньше узлов, чем в В сценарии + Tree.
Самая популярная задача, которая хорошо обрабатывается Trie является слово префикс завершения.

источник

2010-04-22 06:39:24

Некоторые варианты попыток, которые я использую, не только более эффективны по сравнению с BTrees, но и быстрее для большинства запросов (прямой доступ, завершение слова, запрос диапазона). –

Trie vs B + tree

ответ

Смежные вопросы