Оптимальная структура данных на диске для поиска файла?

Я потратил пару часов на чтение сообщений, связанных с вопросом, пытаясь найти решение, но мне не удалось его найти.

Итак, вот: меня однажды спросили в интервью, какую структуру данных я бы использовал для поиска, если бы определенное слово существовало в файле. Файл также предположительно достаточно велик, чтобы не поместиться в памяти, и интервьюер действительно искал решение на диске.

Является ли B-Tree структурой данных на диске?

Двоичное дерево поиска — это структура данных в памяти, не так ли?


java data-structures binary-search-tree b-tree
person user183037    schedule 22.02.2011    source источник
comment
Я воспринял ваш вопрос как «Есть ли B-дерево на диске?». Двоичное дерево находится на диске? Кажется, вы пишете что-то, а на самом деле имеете в виду другое :-) Удивительно, но люди, читающие этот вопрос, похоже, поняли, чего вы на самом деле хотите!   -  person    schedule 23.02.2011
comment
Извините, если я запутал вас - я пытался создать контекст, а затем задать вопросы. На самом деле я хотел выяснить, есть ли какие-либо структуры данных, о которых я не слышал, а также выяснить, были ли мои ответы (данные интервьюеру) правильными. :)   -  person user183037    schedule 23.02.2011

Ответы (3)


arrow_upward
4
arrow_downward

Здесь действительно два разных возможных вопроса:

  1. Учитывая массивный файл и слово, как проверить, существует ли это слово в файле?

  2. Учитывая массивный файл, как построить индекс, чтобы можно было эффективно проверять, существует ли в файле произвольное слово?

Первая проблема эффективно решается с помощью Бойера-Мура и линейного поиска по файлу. Если вы ищете только один раз, создание индекса — пустая трата времени.

Что касается второй проблемы, похоже, что интервьюер действительно продвигает B-деревья.

person Anon.    schedule 22.02.2011
comment
наверное так, я ему тоже так говорил :) - person user183037; 23.02.2011

arrow_upward
2
arrow_downward

Оба являются просто структурами данных и могут быть как на диске, так и в памяти. Это зависит от того, как вы решите их использовать.

Кстати, B-деревья были мотивированы необходимостью иметь структуры на диске. Двоичные деревья поиска — это всего лишь частный случай B-деревьев в одном отношении.

person Community    schedule 22.02.2011
comment
@Moron (смеется!) - Как указать, будет ли структура данных использоваться на диске или в памяти? (извините, если это очень наивный вопрос!) - person user183037; 23.02.2011
comment
@user: Это не похоже на параметр конфигурации! Вы должны учитывать, что потребуется для хранения структуры данных на диске. Например, в двоичном дереве поиска (или даже в B-дереве) указатель на другой узел может быть преобразован в смещение, которое вы ищете в файле. - person ; 23.02.2011
comment
Это должен быть принятый ответ, любой DS можно использовать где угодно, речь идет об эффективности. - person humble_wolf; 19.05.2019

arrow_upward
2
arrow_downward

Вы хотите использовать структуру данных, которая сопоставляет один узел с одной страницей дискового пространства. Это сведет к минимуму активность диска.

Потому что для этого часто используется B-Tree. См. http://en.wikipedia.org/wiki/B-tree, в частности раздел «Время поиска в отсортированном файле».

person corsiKa    schedule 22.02.2011
comment
Итак, B-дерево — лучшая структура данных для этой цели? (Просто подтверждаю) - person user183037; 23.02.2011