Как найти абсолютный путь к узлу (файлу или каталогу) в этой модели файловой системы - PullRequest
Новая
       28

Как найти абсолютный путь к узлу (файлу или каталогу) в этой модели файловой системы

2 голосов
/ 22 апреля 2011

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

Вопрос состоял в том, чтобы спроектировать базу данных для представления файловой системы, в которой -

  • есть корневой каталог и много файлов / каталогов внутри него.
  • внутри каталога может быть любое количество каталогов / файлов.

Требования

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

Условие - Для модели должна быть одна таблица базы данных.Не обязательно, но хорошо иметь, поскольку вопрос об интервью имел это условие.

Я не знал, что создание дерева и нумерация его, как показано на следующей диаграмме, делает его намного более оптимизированным -

enter image description here

Полезное свойство вышеуказанной древовидной структуры заключается в том, что -

  • С учетом любых двух поддеревьев, например, поддерева A (dir2 и его дочерних элементов) и поддерева B (dir3 иего дочерние элементы), номера всех узлов в поддереве A будут меньше, чем Next_Subtree_First_Node, который в данном случае равен dir3.

Тогда, если мы сохраним информацию в структуре базы данных следующим образом - 

_______________________________________________________________________
Sequence_Number    Name                 type   
-----------------------------------------------------------------------
0                  Parent Directory     Dir  
1                  dir1                 Dir  
2                  file1                File  
3                  file2                File  
4                  file3                File  
5                  dir2                 Dir  
...

________________________________________________________________________

NOTE - Приведенная выше структура - это то, что я помню во время обсуждения.Возможно, это не лучшая структура для решения проблемы.Пожалуйста, дайте мне знать, если какие-то изменения необходимы.

Первый запрос будет выглядеть так:

Найти все файлы в одном каталоге 

Select Name From File_System 
  where Sequence_Number Between Next_Subtree_First_Node 
    and Previous_Subtree_Last_Node 
    and type = "File";

Мои вопросы

  • Приведенный выше запрос вернет все необходимые файлы, но как мне заранее знать Next_Subtree_First_Node и Previous_Subtree_Last_Node.

Например, для file4,

Next_Subtree_First_Node = 7 и Previous_Subtree_Last_Node = 4.

  • Я не уверен, какой должна быть логика поиска абсолютного путизапрос.Пожалуйста, дайте несколько идей.

Например, для данного файла7 результат должен быть -

Родительский каталог / dir3 / dir4 / file7.

Ответы [ 2 ]

2 голосов
/ 22 апреля 2011

Если файловая система имеет одно имя на файл (как в Windows; нет жестких ссылок, как в Unix), тогда вы можете сохранить каталог с каждым файлом и проследить путь до корня снизу вверх.

В терминах базы данных у вас будет отношение один-ко-многим между каталогами и файлами, которые они содержат, и итеративно SELECT родительский элемент, пока вы не окажетесь в корне.

0 голосов
/ 22 апреля 2011

Я думаю, вам нужно создать таблицы, где.

1: root_table: Где есть дети (включая: каталоги и файлы).

2: childe_table: Теперь здесь вы указываете каждый с типом каждого и Id root.

3: directory_table: где имя каталога и идентификатор родителя.

4: file_table: Где имя файла, идентификатор родительского каталога.

Итак, вы создаете отношение ...

А для запроса вам понадобится объединиться, чтобы найти всех детей и абсолютный путь.

...