Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

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?

share|improve this question

closed as not a real question by surfasb, Hello71, Linker3000, Mehper C. Palavuzlar, slhck Jul 29 '11 at 16:53

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
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 '11 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 '11 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 '11 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 '11 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 '11 at 19:40

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer
    
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 '11 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 '11 at 15:13
    
Or even more information: en.wikipedia.org/wiki/File_Allocation_Table –  TheCompWiz Aug 2 '11 at 15:23
    
They first link was pretty good, thanx a lot. –  fiftyeight Aug 2 '11 at 16:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.