Efficient data structure to implement fake file system

Question

I want to implement a data structure that will hold the paths of directories, sort of fake file system.

Input:- I have a text configuration file containing the paths as follows
...
C:/temp1
C:/temp1/insideTemp1
C:/temp2/
...

I might end up storing huge amount of paths inside the data structure and I am looking for extremely low retrial time.

Here are the data structures that I think might be useful in this situation :-
B tree
B+ tree
Wavelet Tree
Trie
and B-Trie

I am not sure what data structure would be best useful in this situation.

I am not familiar with the B-trie, nor there are much resources on the internet that I can find that would help me in implementing and understanding one, but I think this might be a good choice for implementation considering it would have advantages of both b tree and trie, correct me if I am wrong.

I would like to know what would be the good data structure in implementing this problem and if you can redirect me some resource that would help me to get started that would be great!

Also, just out of curiosity, in the future if I want to expand the suggested data structure towards full-fledged file system would the suggested data structure be good enough to expand?

Every answer is appreciated.

I suspect the answer is it probably doesn't matter (yet?), and you should just pick the simplest one then write a properly encapsulated class that will make it easy to change the structure later if you do ever hit a performance bottleneck. Or do you have an existing system that's bottlenecked on this? — Ixrec, Jul 10 '15 at 22:40
No, I do not have existing system with the bottleneck. I want to reduce the pain of making changes later. I started implementing the solution with trie and I asked the same question on Facebook programming group. Many programmer suggested me to use B tree as it is the common standard to implement the file system. I am still not sure what would be the advantage of that over the other choices. — user3054204, Jul 10 '15 at 23:53
I agree with @Ixrec; premature optimization is your enemy. Do something simple now and fix its performance later if necessary. — rob, Jul 11 '15 at 01:53

umlcat · Answer 1 · 2016-03-17T20:19:33.713

Quick Short Answer

Pick a regular Tree Structure first, later look for a similar optimized version

Long Boring Extended Answer

Use a regular Tree Structure first.

I read that it seems you try to store the entire path in each node element, and that's one of the reasons your structure may requiere unnecesarily optimization.

Note: The following examples are pseudocode. These are not specific Programming Language, finished examples.

Instead of having something like these:

public struct NodeStruct
{
  public string FullPath;
  public *NodeStruct Container;
  public List<*NodeStruct> Items;
}

int main()
{
  int ErrorCode = 0;

  *NodeStruct MyFileSystem =
    new nodeStruct;
  MyFileSystem->FullPath = "FileSystem";
  MyFileSystem->Container = null;

  *NodeStruct CDrive =         
    new nodeStruct;
  CDrive->FullPath = "C:\";
  CDrive->Container = MyFileSystem;

  *NodeStruct DDrive =         
    new nodeStruct;
  DDrive->FullPath = "D:\";
  DDrive->Container = MyFileSystem;

  *NodeStruct SomeFolder = null;
  *NodeStruct SomeFile = null;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "C:\Program Files";
  SomeFolder->Container = CFolder;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "C:\My Documents";
  SomeFolder->Container = CFolder;

  SomeFile =
    new nodeStruct;
  MyFileSystem->FullPath = "C:\My Documents\Homework1.doc";
  MyFileSystem->Container = SomeFolder;

  free MyFileSystem;

  return ErrorCode;
} // int main(...)

You may want to have something like these:

public struct NodeStruct
{
  string Identifier;

  public *NodeStruct Container;
  public List<*NodeStruct> Items;
}

string GetFullPath(*NodeStruct AFileSystemItem)
{
  string ErrorCode = "";

  // code to "traverse" a tree item or tree node
  // and get the full path

  return ErrorCode;
} // string GetFullPath(...)


int main()
{
  int ErrorCode = 0;

  *NodeStruct MyFileSystem =
    new nodeStruct;
  MyFileSystem->FullPath = "FileSystem";
  MyFileSystem->Container = null;

  *NodeStruct CDrive =         
    new nodeStruct;
  CDrive->FullPath = "C:";
  CDrive->Container = MyFileSystem;

  *NodeStruct DDrive =         
    new nodeStruct;
  DDrive->FullPath = "D:";
  DDrive->Container = MyFileSystem;

  *NodeStruct SomeFolder = null;
  *NodeStruct SomeFile = null;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "Program Files";
  SomeFolder->Container = CFolder;

  SomeFolder =
    new nodeStruct;
  SomeFolder->FullPath = "My Documents";
  SomeFolder->Container = CFolder;

  SomeFile =
    new nodeStruct;
  MyFileSystem->FullPath = "Homework1.doc";
  MyFileSystem->Container = SomeFolder;

  string AFullPath = GetFullPath(SomeFile);

  // "AFullPath" should have the "C:\My Documents\Homework1.doc" value

  free MyFileSystem;

  return ErrorCode;
} // int main(...)

You didn't specify a particular Programming Language in your question. Neither if you are using an Imperative, Procedural, Functional or Object Oriented P.L., that may help suggest you a library.

Cheers.

Efficient data structure to implement fake file system

1 Answers1