OSDev.org

I was reading about the implementation details of a few major file systems (namely HFS+ and NTFS) and came across a detail that I don't quite understand. They both store important file system data on the disk as a b-tree (or b+tree for NTFS). I read about these structures and managed to implement one in memory, but I am confused still about one thing. Since data structures are to be held in memory, how does the file system store a data structure as a file? I know that HFS+ stores a Catalog File, which is an actual file in non-reserved space, on the disk. The part I don't understand is how it is stored in a way that all the features of a b-tree, such as searching, inserting, and deleting nodes, properly operate on it. I would really appreciate it if someone could point me in the right direction at least.

Hi,

If you've implemented a b-tree in memory, you're 90% of the way there conceptually. The only difference between a b-tree in memory and one on disk is how pointers are represented.

In memory, each node points to memory containing the child nodes - obviously nodes on disk can't point to RAM, so you need some sort of mapping from pointers to disk addresses. That is fairly simple - write the nodes out so they are contiguous on disk, storing the address that you stored each node at. Then, go through and for every pointer in each node, look up in your pointer->disk mapping you just created.

Obviously this would be best done in a memory buffer and then written out to disk to avoid unnecessary seeking.

In fact, writing out to disk-time is one of the best times to optimise your B-tree - Hans Reiser's "dancing trees" (in ext4) do this. No wife murdering jokes please.

James

Thank you! Your answer was very informative and helpful. I appreciate you taking your time to help me solve this problem.

In fact, writing out to disk-time is one of the best times to optimise your B-tree - Hans Reiser's "dancing trees" (in ext4) do this

You mean in Reiser4 fs ?

gerryg400 wrote:

In fact, writing out to disk-time is one of the best times to optimise your B-tree - Hans Reiser's "dancing trees" (in ext4) do this

You mean in Reiser4 fs ?

Apologies, I remembered incorrectly!

berkus wrote:

In fact, writing out to disk-time is one of the best times to optimise your B-tree - Hans Reiser's "dancing trees" (in ext4) do this

He would be Hans Ext in this case.

I know he made ReiserFS (all incarnations), but I thought he also put design into ext4. I was mistaken, it seems.