X-ROUTED: Sat, 13 Nov 1999 06:47:10 -0500
Message-ID: <382D4F06.D8F75D6B@greenbelt.com>
Date: Sat, 13 Nov 1999 06:44:06 -0500
From: Ed James <edjames AT greenbelt DOT com>
Organization: GIAC
X-Mailer: Mozilla 4.51 [en] (WinNT; I)
X-Accept-Language: en
MIME-Version: 1.0
To: djgpp AT delorie DOT com
Subject: Re: How do I store a B+ Tree in a file?
References: <382D09DA DOT 622B295D AT accord-soft DOT com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reply-To: djgpp AT delorie DOT com

I'd suggest not saving tree links, since they are memory pointers which may or may
not be available to you next time you construct the tree.  One technique to save such
a tree is to (1) create a pointer that keeps track of the left-most (or
lowest-valued) leaf node, and (2) when you split a leaf node, put a pointer in the
left leaf node that points to the right leaf node.  Thus, starting from the first
pointer, you can traverse the leaf (data) nodes without using the interior
(non-terminal) nodes at all.  You save by reading each data record in a given node
and writing it as a disk file record.  Then your data is saved (in sorted format), so
a new B+ tree can easily be re-created using the same code you used to create it in
the first place.

ptrFirstNode*--->[first leaf...*]--->[second leaf...*]---> ... --->[last leaf...NULL]

"Sunil V." wrote:

> Hello,
>     In my application, I have a B+ tree which stores some information.
> Now, I want to store all these information into a file along with tree
> links, so that in future i can read this file and reconstruct the  B+
> tree.  Can anyone help me as to in what format I can store it in a file
> which can facilitate future reconstruction of the tree.
>
> Thanx in advance,
> Regards
> sunil
>
> --
> _________________________________________________________________________________
>
> They call it "take home" pay, coz' you can't afford to go anywhere else
> with it.
> _________________________________________________________________________________