3

I'm curious about how an OS finds files in the file system.
For example I know in the FAT file system there is a DB of the files.

I know the OS finds files very fast,
so I want to know if it uses binary search to go through the FAT Database?
Or is there a faster method to do this?

and Is there a method for the OS to deduce the location of the files in the file system straight away without searching the FAT Database?

5
  • This probably isn't the place to ask such a question. At best, we can get this migrated to the Programmers site. But this is also very broad. I'd suggest you google linked lists and B tree.
    – surfasb
    Jul 29, 2011 at 16:11
  • @TheCompWiz has summarized it anyway: > The real question is... Why do you want to know... and what are you trying to accomplish? If you want more specific answers... give more specifics about what OS/platform/file-system you are talking about.
    – slhck
    Jul 29, 2011 at 16:54
  • I tried googling and wikipedia and there's a lot of information but not realy about the method the OS uses to find the file, but I understand that it's different for each OS and filesystem as you say so I'll try to post a more specific question probably in the Unix forum since I use linux.
    – fiftyeight
    Jul 29, 2011 at 18:01
  • The FAT does not list files; it is just an array of pointers, one for each cluster on the fs. Each one points to the next cluster that logically follows this one in whatever file this one is a part of, or is one of several reserved values for things such as free/unused, end of file, and bad sectors. Directories are what lists files, and they are linearly searched.
    – psusi
    Jul 29, 2011 at 19:14
  • hmmm... so say I request from the OS a listing of files on the directory "/usr", how does it know the address of this directory on the HDD?
    – fiftyeight
    Jul 29, 2011 at 19:40

1 Answer 1

0

Honestly... this question has many answers... too many to enumerate here. Largely this depends on the type of file-system... and the OS reading it... and also what features of the file-system are enabled.

Every file system has some sort of "database" as you described to translate a name/path to one or more locations on the disk. How this "database" works is what makes each file-system different. Some methods are better for some tasks than others. Some are more recoverable & redundant in the event of a failure... some are strictly geared towards speed and have almost no recovery in the event of a single failure.

Depending on the OS, and the file-system type, the "database" can be partially or even completely loaded into RAM in order to help speed-up the process of locating the position on the disk. Some file-systems make use of linked-lists & b-trees or other types of ordered trees in order to quickly locate files. Journaling can also speed-up the read/write processes dramatically (given the right conditions). There are even file-systems (mostly proprietary) that truly ARE a database.

The real question is... Why do you want to know... and what are you trying to accomplish? If you want more specific answers... give more specifics about what OS/platform/file-system you are talking about.

4
  • I'm not trying to accomplish anything specific just get an image in my head of how the file systems usually work, I didn't realize there's such a difference. But I did mention the FAT file system in my post that can be used as an example since it's pretty common
    – fiftyeight
    Jul 29, 2011 at 18:06
  • Well... there are actually several variants on the FAT file system... but they all follow a similar structure. If you want to get into the guts of it, here's a good read on FAT: pjrc.com/tech/8051/ide/fat32.html Unfortunately, a lot of that info might be waaaay overly complex for you... but at least it will point you in a direction.
    – TheCompWiz
    Aug 2, 2011 at 15:13
  • Or even more information: en.wikipedia.org/wiki/File_Allocation_Table
    – TheCompWiz
    Aug 2, 2011 at 15:23
  • They first link was pretty good, thanx a lot.
    – fiftyeight
    Aug 2, 2011 at 16:24

Not the answer you're looking for? Browse other questions tagged .