String table or a tree for virtual filesystem

Question

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.

Answer 1

The tree approach will only provide a benefit in one specific scenario: Obtaining all files within a specific directory subnode. If that's your most common access pattern, then this structure might be useful.

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.

Note that an unordered_map can also be used to speed up tree traversal if you put the entries for the directory nodes into it, because it will make it faster to find the directory node from which you want to find the children.

Possible drawback: Hashmaps have quite a lot of memory overhead compared to other data structures. But I suspect that this overhead will be nothing compared to the memory taken by the actual file data in your virtual filesystem.