[hfs-user] Algorithm of B* tree Implementation

Patrick Dirks pwd@apple.com
Thu, 7 Feb 2002 10:56:42 -0800


--Apple-Mail-1-441263988
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=ISO-8859-1;
	format=flowed

"The algorithm" is a bit hard to lay out in an e-mail message - it's=20
wrapped up in a series of design and implementation aspects.  Read up on=20=

B*-Trees and you should have a good idea what the data structure's=20
supposed to look like at any given time.  Read "Inside Macintosh" and=20
you'll find a more detailed explanation of the exact details of the=20
HFS/HFS+ B*-Tree structure.  More helpful than "Inside Macintosh",=20
perhaps, is the tech note that Apple's published on the subject - "must=20=

read" for anyone implementing a version of HFS/HFS+.  I can't remember=20=

the tech note number offhand but it's freely available through Apple's=20=

web site - do a search there.

Finally, note that the Darwin code, which Apple has open sourced,=20
includes a complete "C" implementation of the B*-Tree code as part of a=20=

UNIX kernel.  Sign up as a Darwin developer and check out a copy of the=20=

sources.  It's in the "xnu" project in the "hfs" directory inside the=20
"bsd" directory of "xnu".  That's the ultimate answer right there.

Hope that helps,
-Pat Dirks.

On Thursday, February 7, 2002, at 02:04 AM, Biswaroop Banerjee wrote:

> Hi All,
> =A0
> =A0 Can anybody of you give me the algorithm of implementating a B* =
tree=20
> which is the prominent data structure in a HFS formatted volume.
> =A0
> Waiting=A0 for your help.
> =A0Regards
> Biswaroop Banerjee.
> =A0
> =A0
> The essence of Success lies in its Struggle
> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=20
> -Bisban=A0

--Apple-Mail-1-441263988
Content-Transfer-Encoding: quoted-printable
Content-Type: text/enriched;
	charset=ISO-8859-1

"The algorithm" is a bit hard to lay out in an e-mail message - it's
wrapped up in a series of design and implementation aspects.  Read up
on B*-Trees and you should have a good idea what the data structure's
supposed to look like at any given time.  Read "Inside Macintosh" and
you'll find a more detailed explanation of the exact details of the
HFS/HFS+ B*-Tree structure.  More helpful than "Inside Macintosh",
perhaps, is the tech note that Apple's published on the subject -
"must read" for anyone implementing a version of HFS/HFS+.  I can't
remember the tech note number offhand but it's freely available
through Apple's web site - do a search there.


Finally, note that the Darwin code, which Apple has open sourced,
includes a complete "C" implementation of the B*-Tree code as part of
a UNIX kernel.  Sign up as a Darwin developer and check out a copy of
the sources.  It's in the "xnu" project in the "hfs" directory inside
the "bsd" directory of "xnu".  That's the ultimate answer right there.


Hope that helps,

-Pat Dirks.


On Thursday, February 7, 2002, at 02:04 AM, Biswaroop Banerjee wrote:


<excerpt><fontfamily><param>Arial</param><smaller>Hi =
All,</smaller></fontfamily>

=A0

<fontfamily><param>Arial</param><smaller>=A0 Can anybody of you give me
the algorithm of implementating a B* tree which is the prominent data
structure in a HFS formatted volume.</smaller></fontfamily>

=A0

<fontfamily><param>Arial</param><smaller>Waiting=A0 for your =
help.</smaller></fontfamily>

<fontfamily><param>Arial</param><smaller>=A0Regards</smaller></fontfamily>=


<fontfamily><param>Arial</param><smaller>Biswaroop =
Banerjee.</smaller></fontfamily>

=A0

=A0

<fontfamily><param>Arial</param><smaller>The essence of Success lies
in its Struggle

=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0
-Bisban=A0</smaller></fontfamily>

</excerpt>=

--Apple-Mail-1-441263988--