Быстрый поиск файлов или каталогов данного пользователя и пути, когда есть много пользователей и файлов/каталогов

Question

Это вопрос интервью. Если у вас есть миллионы пользователей и файлы/каталоги, как вы планируете хороший способ найти файлы или каталоги данного пользователя и путь? Если у файлов/каталогов есть метки времени, как вы рассчитываете количество файлов/каталогов, добавленных в день для каждого пользователя? вы можете использовать свой путь для вставки файлов/каталогов.

Answer 1

Вы можете сохранить их в таблице базы данных (поля user, file, date) и сделать простой запрос на них. СУБД делают индексацию, чтобы сделать ее быстрой. Если вы не хотите использовать СУБД, например mysql или MS Access, SQL server или Oracle, вы можете использовать некоторые приложения для поиска с открытым исходным кодом, такие как Lemur.

Answer 2

Если вы не хотите использовать базу данных, вы можете использовать комбинацию Dictionary и Binary Search Tree.

keyDictionary будет user.
value его с 2 свойства:

1. Dictionary с day ы как keys и number of entries that day, как values.
2. A Binary Search Tree с path s разных файлов и папок как nodes.

Дает n общее количество разных файлов и папок.
Он построен в O(nlgn), а необходимые операции выполняются в O(lgn).