I’m creating a pseudo-file system for my game, using a MySQL database as the FAT. I thought it would be fairly simple at first, but as I was about to program it, I realised that my method I planned on using is hugely expensive. Since it’s a call that’ll be used hundreds of times each time the player plays for a short period I really can’t do with it being a resource intensive feature.

ER model of directory table (I'll change this to a prettier one when I have the energy and time to play around in GIMP)

Basically, it’s just navigating directories. Here’s how they’re stored in the database, according to the ER model to the right:

harddrive_directories (directoryID, directoryName, parent)

The foreign key inside the same table with the primary key through me for a second, but I understand that now.

My problem is when a user gives me a string like “/foo/bar/alien/”, and I then have to find the ID for the directory labeled “alien”. I obviously can’t just search for directories called “alien” because there could be a “/foo/alien/” or any other combination. (Though to cut out any needless directory traversing, it would be faster to do that; see if there are any directories called “alien”, if there’s only one work backwards, which is much easier to check if it’s what I’m looking for, if there’s more than one, we don’t have much choice.)

So, I look for a root directory called “foo”. There can only be one, so that’s fairly simple. Now I have foo’s ID, I can look up all of the directories called “bar” whose parent is fooID. And so on, untill I get to a directory called “alien”.

Now I’ve said it outloud, there’s really only n lookups (where n is the number of directories in the path), which isn’t so bad. Is there a better way of doing this though?