OSDev.org
https://forum.osdev.org/

How does the file system store a b-tree?
https://forum.osdev.org/viewtopic.php?f=15&t=22600
Page 1 of 1

Author:  KodyKinzel [ Thu Oct 07, 2010 7:56 am ]
Post subject:  How does the file system store a b-tree?

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.

Author:  JamesM [ Thu Oct 07, 2010 9:21 am ]
Post subject:  Re: How does the file system store a b-tree?

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

Author:  KodyKinzel [ Thu Oct 07, 2010 6:26 pm ]
Post subject:  Re: How does the file system store a b-tree?

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

Author:  gerryg400 [ Thu Oct 07, 2010 7:02 pm ]
Post subject:  Re: How does the file system store a b-tree?

Quote:
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 ?

Author:  JamesM [ Fri Oct 08, 2010 1:57 am ]
Post subject:  Re: How does the file system store a b-tree?

gerryg400 wrote:
Quote:
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!

Author:  JamesM [ Fri Oct 08, 2010 4:55 pm ]
Post subject:  Re: How does the file system store a b-tree?

berkus wrote:
Quote:
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.

Page 1 of 1 All times are UTC - 6 hours
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/