Data structure to use for a basic file system

Question

I am practicing a few interview questions and I found an interesting one which was to build a basic file system / terminal. Because this is an interview question, this file system is probably a basic one that involves adding files and directories, and adding files and directories within directories. Another feature would be to print out all the directories and files in a logical manner. This all has to be done without using the Collections library

I was curious to what data structures I would use to implement this file system? What I had in mind was either a hashtable or a B tree.

Hashtable would a really fast look up time. However it would use up a lot of memory. I was planning to use prime numbers as my bucket size.

B tree would be much more memory efficient. However look up times would be slower.

Or possibly both?

ex:

all files stored in hashtable node while directories are storied in a tree node that can branch out to other directory nodes or hashtable.

Another question I have is: which one would seem easier to code or implement the print all function?

Answer 1

The best datastructure for a file system is a Tree. If you think of it, it naturally models the hierarchy of a directory structure

dir1
  dir2
    dir2a
      file2b
  dir3
    dir3a
      file3b
      file3c
      dir4
        file4a