Jordan3 wrote:
I have mostly designed a custom filesystem for my OS, now then the only problem is that with its index system to store names and such there really is no way to fastly get to a file especially in layers of directories with many files and this is because basically the index is a linked list with each index sectors last few bytes or whatever telling where the next index sector is- I have thought about using a map type thingy but i don't really think that'll help since you still have to go through each one.
btw
index entries are allocated by first free
Well... this is a problem that's easily abstracted - you have an N-tree of string names which you need to traverse and keep up to date. You need to either look at it as a traverse/seek problem or abstract it to a higher layer where you only have the seek problem left. In other words, do you seek per directory or over the entire partition/disk at the same time?
The generic solution is per directory, since there's little chance that files in other directories have anything to do with it, and directories are usually pretty small, making the traverse/seek faster than a seek would normally be.
Traverse can only be done in one way, find entry, go to it, find subentry etc. You can cache intermediate results by the way, to make future searches faster.
Then there's seeking. You can do a linear search on an unsorted array (order N seeking, order 1 inserting at end, order 1 inserting if last empty positions are kept in a linked list for any location, order N inserting at any location otherwise), you can store them in a sorted array (order log(N) seeking, order N insertion, more bandwidth & more writing (which is a point for flash storage)), in a tree (binary tree for example), hash table or any other common storage method.
Try looking up a bit more wikipedia articles and OSFAQ entries on the generic subjects of storage and seeking...
A few helpful keywords: B-tree, B+ tree, hashing, binary search.
You also might want to search for the book about the design of BeFS, which is open and free to download from the internet in pdf format (and probably others too). You should be able to find it on google. IIRC BeFS uses B+ trees to store filenames at a directory-local basis.