# String table or a tree for virtual filesystem

I am developing a binary file format to store my game's assets and I am thinking about how to implement the "file table". One option to would be to create a structure for file entries like this:

    struct Entry
{
uint16_t nameLength; //< This basically stores the whole path e.g "dir1/file1.txt"
char*    name;
uint64_t dataSize;
uint64_t dataOffset;
};


Or i could use a method, which I think is more elegant and is based off the ISO 9660 filesystem, however I think it may have a performance impact on traversing the file tree.

    struct Entry
{
uint16_t entrySize; //< This is used for going to the next entry (next = current + current.entrySize)
uint8_t  entryType; //< 0 for file, 1 for directory + may be extended later
uint16_t nameLength; //< Now this only stores the concrete file/directory name
char*    name;
uint64_t dataSize;
uint64_t dataOffset;
Entry*   children; //< Actually an array where entrySize is used for iterating
// and the last entry is a "null entry" which has entrySize = 0
};


So which one of theese will be better considering that the resource files are "read only" and cannot be modified, only created again? Or is there a solution better tailored for virtual filesystems?

Because in the first case the system only needs to traverse all the entries lloking for "dir1/file1.txt", but in the second case it will have to first search for "dir1" in the root entry, and the for "file1.txt".

I hope that I was clean enough.

• What are you trying to solve? If it's loading times, then there's probably no significant difference between these methods. Reading from disk is the bottleneck. Nov 2 '17 at 18:32
• @MickLH Well kinda. Performance is the most significant thing I care about, however I don't know if the second method is suitable for a resource file or if is there something specifically made for resource files Nov 2 '17 at 18:42

If you want to get a single file by its full path and name, then you will be far better off if you create a separate std::unordered_map<std::string, Entry*> which maps filenames (with complete path) to Entrys. An unordered_map is (practically always) internally implemented as a hash table, so finding an entry in it by key is a constant time operation. Finding one in your tree can potentially take much longer, especially if you happen to have many directories in the hierarchy which have a lot of entries which come before the one you are looking for.