How does the file system store a b-tree?
-
KodyKinzel
- Posts: 7
- Joined: Tue Jan 05, 2010 7:37 pm
- Contact:
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.
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
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
-
KodyKinzel
- Posts: 7
- Joined: Tue Jan 05, 2010 7:37 pm
- Contact:
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.
Re: How does the file system store a b-tree?
You mean in Reiser4 fs ?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
If a trainstation is where trains stop, what is a workstation ?
Re: How does the file system store a b-tree?
Apologies, I remembered incorrectly!gerryg400 wrote:You mean in Reiser4 fs ?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
Re: How does the file system store a b-tree?
I know he made ReiserFS (all incarnations), but I thought he also put design into ext4. I was mistaken, it seems.berkus wrote:He would be Hans Ext in this case.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