Data structure used for directory structure?

Question

Hi, I'm making a program which the user build directories (not in windows, in my app) and in these folders there are subfolders and so on; every folder must contain either folders or documents. What is the best data structure to use? Notice that the user may select a subfolder and search for documents in it and in its subfolders. And I don't want to limit the folders or the subfolders levels.

Answer 1

I can think of a few ways you could structure this, but nothing would beat the obvious:

Use the actual file system.

Answer 2

This is what I do:

Every record in the database has two fields: ID and ParentID. IDs are 4-5 characters (Base36, a-z:0-9 or something similar). Parent IDs are a concatenation of the parent's complete structure...

So...

This structure:

Root
   Folder1
   Folder2
      Folder3
   Folder4
      Folder5
         Folder6

Would be represented like this:

ID     ParentID     Name

0000   NULL           ROOT
0001   0000           Folder1
0002   0000           Folder2
0003   00000002       Folder3
0004   0000           Folder4
0005   00000004       Folder5
0006   000000040005   Folder6

I like this structure because if I need to find all the files under a folder I can do a query like:

SELECT * FROM Folders WHERE ParentID LIKE '0000%' -- to find all folders under Folder1

To delete a folder and all its children:

DELETE FROM Folders WHERE ID='0004' AND ParentID LIKE '00000004%'

To move a folder and its children, you have to update all the records that use the same parent, to the new parent.

And I don't want to linit the folders or the subfolders levels

An obvious limitation to this is that the number of subfolders are limited to the size of your ParentID field.

Answer 3

I would look into using some sort of tree data structure

Cameron

Answer 4

I know that the question is specifically asking for a data structure but...

If you are using an object oriented language maybe you can use the composite design pattern which is ideally suited for this type of hierarchical tree like structure. You get what you are asking for.

Answer 5

Most OO languages come with some sort of abstraction for the file system, so there is where I would start. Then subclass it if you need to.

I would expect directories as an array of objects which are directories or files, for instance.

Answer 6

Jason's solution using base36 for IDs is what I was looking for.

Thanks for all of you

Answer 7

you can use m-way tree data structure