Использование B-Tree вместо Trie

Это вопрос интервью, а не домашнее задание.Использование B-Tree вместо Trie

«У вас есть N документов, где N очень велико. В каждом документе есть набор слов, позволяющих говорить w1, w2..wm, где m может отличаться для каждого документа. Теперь вам предоставляется список слов K, которые можно сказать q1, q2 ... qk. Напишите алгоритм для печати списка документов, в которых есть слова K. "

Теперь я мог бы найти решения, используя Hashing и trie. Но тот, кто разместил этот вопрос, также написал, что интервьюеру понадобилось решение с использованием B-дерева.

Я не могу понять, как использовать B-Tree для этого и насколько это эффективно. Может ли кто-нибудь помочь?

источник

2015-02-16 ankitG

Это требует алгоритма, который _uses_ B-Tree, вам не нужно, как его писать. Это просто реализация Словаря. На этом уровне решение «trie или B-Tree» не должно быть релевантным. –

B-Tree предпочтительнее, чем Trie, если наш набор данных хранится на носителях с медленным произвольным доступом, например, на обычных жестких дисках. Заметка интервьюера о том, что N очень велика, может означать, что она просто достаточно велика, чтобы не вписываться в память и должна быть помещена на диск.

Как отмечено в комментариях: , когда данные действительно огромны и хранятся на диске, эффективность структуры данных в большей степени зависит от количества обращений к дисковым блокам, а не от общего количества всех операций. B-Tree содержит много записей в одном узле (который можно рассматривать как «блок данных»), поэтому требуется значительно меньше доступа к блокам, чем Trie.

Именно по этой причине большинство БД хранят свои индексы в B-Tree. Им нужен быстрый поиск по индексу, расположенному на обычном жестком диске. На самом деле, ваша проблема может быть решена посредством перевода (слова - documentId) пара в таблице БД и создание индекса на словах столбца или всю пару.

источник

2015-02-16 18:30:25

Так будет ли это более эффективно, чем использование Trie? – ankitG

Кроме того, то же слово присутствует во многих документах. – ankitG

Было бы более эффективно, если наше дерево хранится на диске, потому что B-Tree требует меньше случайного доступа к данным, чем Trie. –

Вы можете попробовать тройное trie. Это не занимает столько места. Вы также можете посмотреть Карт-три. Он использует ключ и 2 листа: http://code.dogmap.org/kart/.

источник

2015-02-16 20:02:41 Bytemain

Не получил ничего на Карт-три. Не могли бы вы передать ресурс, где я могу прочитать об этом? Благодарю. – ankitG

Но trie все равно будет в памяти ... так или иначе вы все равно будете хранить все слова в trie, что, вероятно, невозможно, потому что «N» велико, и, следовательно, количество слов слишком велико. Кроме того, что будет содержать лист-узел? Он должен иметь список всех идентификаторов документа, которые содержат это слово. То, что умножено на количество листьев, будет действительно огромным. – ankitG

@ankitG: http: //code.dogmap.org/kart/. – Bytemain

Использование B-Tree вместо Trie

ответ

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