Я провів пару годин, читаючи дописи, пов'язані з питанням, намагаючись знайти рішення, але я не був дуже успішним у пошуку одного.
Отже, ось що: Мене одного разу в інтерв'ю запитали, яку структуру даних я б використав для пошуку, якщо певне слово існувало у файлі. Файл також, мабуть, досить великий, щоб не міг поміститися в пам'яті, і інтерв'юер дійсно шукав рішення на диску.
Чи є B-Tree структура даних на диску?
Бінарне дерево пошуку - це структура даних в пам'яті, чи не так?
Відповіді:
4 для відповіді № 1Тут справді можливі два різні питання:
З огляду на масивний файл та слово, як перевірити, чи існує слово у файлі?
Зважаючи на масивний файл, як ви будуєте індекс, щоб можна було ефективно перевірити, чи існує довільне слово у файлі?
Перша проблема ефективно вирішується за допомогою Бойєра-Мура та лінійного пошуку через файл. Якщо ви шукаєте лише один раз, створення індексу - це повна витрата часу.
Щодо другої проблеми, то здається, що інтерв'юер справді штовхає B-Trees.
2 для відповіді № 2
Ви хочете використовувати структуру даних, яка відображає один вузол на одну сторінку дискового простору. Це зведе до мінімуму активність диска.
Тому що для цього часто використовують B-дерево. Побачити http://en.wikipedia.org/wiki/B-tree, зокрема розділ "Час пошуку відсортованого файлу".
1 для відповіді № 3
Обидва є лише структурами даних і можуть бути як на диску, так і в пам'яті. Це залежить від того, як ви вирішили їх використовувати.
btw, B-Дерева були мотивовані потребою мати дискові структури. Бінарні дерева пошуку - це лише окремий випадок B-дерев.