OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Oct 23, 2014 1:53 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: How does the file system store a b-tree?
PostPosted: Thu Oct 07, 2010 7:56 am 
Offline

Joined: Tue Jan 05, 2010 7:37 pm
Posts: 7
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.


Top
 Profile  
 
 Post subject: Re: How does the file system store a b-tree?
PostPosted: Thu Oct 07, 2010 9:21 am 
Offline
Member
Member
User avatar

Joined: Tue Jul 10, 2007 5:27 am
Posts: 2935
Location: York, United Kingdom
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

_________________
Horizon - a framework and language for SAS-OS development
Project 'Pedigree'
Practical x86 OSDev tutorials


Top
 Profile  
 
 Post subject: Re: How does the file system store a b-tree?
PostPosted: Thu Oct 07, 2010 6:26 pm 
Offline

Joined: Tue Jan 05, 2010 7:37 pm
Posts: 7
Thank you! Your answer was very informative and helpful. I appreciate you taking your time to help me solve this problem.


Top
 Profile  
 
 Post subject: Re: How does the file system store a b-tree?
PostPosted: Thu Oct 07, 2010 7:02 pm 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1503
Location: Melbourne, Australia
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 ?

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: How does the file system store a b-tree?
PostPosted: Fri Oct 08, 2010 1:57 am 
Offline
Member
Member
User avatar

Joined: Tue Jul 10, 2007 5:27 am
Posts: 2935
Location: York, United Kingdom
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!

_________________
Horizon - a framework and language for SAS-OS development
Project 'Pedigree'
Practical x86 OSDev tutorials


Top
 Profile  
 
 Post subject: Re: How does the file system store a b-tree?
PostPosted: Fri Oct 08, 2010 4:55 pm 
Offline
Member
Member
User avatar

Joined: Tue Jul 10, 2007 5:27 am
Posts: 2935
Location: York, United Kingdom
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.

_________________
Horizon - a framework and language for SAS-OS development
Project 'Pedigree'
Practical x86 OSDev tutorials


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: mallard, YaCy [Bot] and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group