Структура данных, используемая для структуры каталогов?
-
05-07-2019 - |
Вопрос
Я создаю программу, в которой пользователь создает каталоги (не в Windows, в моем приложении), и в этих папках есть вложенные папки и так далее;каждая папка должна содержать либо папки, либо документы.Какую структуру данных лучше всего использовать?Обратите внимание, что пользователь может выбрать вложенную папку и выполнять поиск документов в ней и в ее вложенных папках.И я не хочу ограничивать количество папок или вложенных папок по уровням.
Решение
Это то, что я делаю:
Каждая запись в базе данных содержит два поля:Идентификатор и родительский идентификатор.Идентификаторы состоят из 4-5 символов (Base36, a-z: 0-9 или что-то подобное).Родительские идентификаторы представляют собой объединение полной структуры родительского элемента...
Итак...
Эта структура:
Root
Folder1
Folder2
Folder3
Folder4
Folder5
Folder6
Было бы представлено следующим образом:
ID ParentID Name
0000 NULL ROOT
0001 0000 Folder1
0002 0000 Folder2
0003 00000002 Folder3
0004 0000 Folder4
0005 00000004 Folder5
0006 000000040005 Folder6
Мне нравится эта структура, потому что, если мне нужно найти все файлы в папке, я могу выполнить запрос типа:
SELECT * FROM Folders WHERE ParentID LIKE '0000%' -- to find all folders under Folder1
Как удалить папку и все ее дочерние элементы:
DELETE FROM Folders WHERE ID='0004' AND ParentID LIKE '00000004%'
Чтобы переместить папку и ее дочерние элементы, необходимо обновить все записи, использующие один и тот же родительский элемент, на новый родительский элемент.
И я не хочу ограничивать уровни папок или вложенных папок
Очевидным ограничением этого является то, что количество вложенных папок ограничено размером вашего поля ParentID.
Другие советы
Я могу придумать несколько способов структурирования, но ничто не сравнится с очевидным:
Используйте настоящую файловую систему.
Я хотел бы изучить использование какой-то древовидной структуры данных
Я должен порекомендовать B + Tree .... Вы можете легко использовать индексацию (страницу, папку и т. д.) и все.
Дерево B + http://commons.wikimedia.org/wiki/File:Btree .png р>
для получения дополнительной информации: http://ozark.hendrix.edu/~burch/ CS / 340 / чтение / ВТКЕЕ / index.html
Я знаю, что вопрос конкретно касается структуры данных, но ...
Если вы используете объектно-ориентированный язык, возможно, вы можете использовать композитный шаблон проектирования, который идеально подходит для этого типа иерархического древовидного типа структуры. Вы получаете то, что просите.
Большинство ОО-языков поставляются с какой-то абстракцией для файловой системы, поэтому я бы начал с этого. Затем подкласс это, если вам нужно.
Я бы ожидал, что каталоги - это массив объектов, например, каталогов или файлов.
вы можете использовать m-way древовидную структуру данных