[hfs-user] Algorithm of B* tree Implementation

Gordon Beatty gbeatty@cpc.gc.ca
Thu, 7 Feb 2002 22:30:33 -0500


This is a multi-part message in MIME format.

------=_NextPart_000_0001_01C1B027.0F49EA40
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit

    The technote number is 1150 but if you point your browser to


http://developer.apple.com/techpubs/macos8/Files/FileManager/filemanager.htm
l

the links to the original HFS spec in "Inside Macintosh" and the HFS+ spec
in TechNote 1150 are listed there (although the way OS X uses and interprets
some of the fields in HFS+ does not seem completely reflected in the
TechNote).  Also, the technote refers to Robert Sedgewick's book 'Algorithms
in C - Parts 1-4' -- and similarly 'Algorithms in C++ - Parts 1-4' -- which
should prove a fairly clear reference for the purposes of understanding.
The 'File Structures' book (previous or current version) by Michael Folk
could help in this regard as well.

    At the end of the day though, a solid C implementation is certainly the
best reference.


    Gord Beatty

  -----Original Message-----
  From: hfs-user-admin@lists.mars.org
[mailto:hfs-user-admin@lists.mars.org]On Behalf Of Patrick Dirks
  Sent: Thursday, February 07, 2002 1:57 PM
  To: hfs-user@lists.mars.org
  Cc: Biswaroop Banerjee
  Subject: Re: [hfs-user] Algorithm of B* tree Implementation


  "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:


    Hi All,

      Can anybody of you give me the algorithm of implementating a B* tree
which is the prominent data structure in a HFS formatted volume.

    Waiting  for your help.
     Regards
    Biswaroop Banerjee.


    The essence of Success lies in its Struggle
                                                                     -Bisban


------=_NextPart_000_0001_01C1B027.0F49EA40
Content-Type: text/html;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">


<META content=3D"MSHTML 5.00.3315.2870" name=3DGENERATOR></HEAD>
<BODY>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN=20
class=3D493180020-07022002>&nbsp;&nbsp;&nbsp; The technote number is =
1150 but if=20
you point your browser to</SPAN></FONT></DIV>
<DIV>&nbsp;</DIV>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN=20
class=3D493180020-07022002>&nbsp;&nbsp;&nbsp; <A=20
href=3D"http://developer.apple.com/techpubs/macos8/Files/FileManager/file=
manager.html">http://developer.apple.com/techpubs/macos8/Files/FileManage=
r/filemanager.html</A></SPAN></FONT></DIV>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN=20
class=3D493180020-07022002></SPAN></FONT>&nbsp;</DIV>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN =
class=3D493180020-07022002>the=20
links to the original HFS spec in "Inside Macintosh" and the HFS+ spec =
in=20
TechNote 1150 are listed there (although the way OS X uses and =
interprets some=20
of the fields in HFS+&nbsp;does not seem&nbsp;completely reflected in =
the=20
TechNote).&nbsp; Also, the technote refers to Robert Sedgewick's book=20
'Algorithms in C - Parts 1-4' -- and similarly 'Algorithms in C++ - =
Parts 1-4'=20
-- which should prove a fairly clear reference for the purposes of=20
understanding.&nbsp; The 'File Structures' book (previous or current =
version) by=20
Michael Folk could help in this regard&nbsp;as well.</SPAN></FONT></DIV>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN=20
class=3D493180020-07022002></SPAN></FONT>&nbsp;</DIV>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN=20
class=3D493180020-07022002>&nbsp;&nbsp;&nbsp; At the end of the day =
though, a=20
solid C implementation is certainly the best =
reference.</SPAN></FONT></DIV>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN=20
class=3D493180020-07022002></SPAN></FONT>&nbsp;</DIV>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN=20
class=3D493180020-07022002></SPAN></FONT>&nbsp;</DIV>
<DIV><FONT color=3D#0000ff face=3DArial size=3D2><SPAN=20
class=3D493180020-07022002>&nbsp;&nbsp;&nbsp; Gord =
Beatty</SPAN></FONT></DIV>
<DIV>&nbsp;</DIV>
<BLOCKQUOTE style=3D"MARGIN-RIGHT: 0px">
  <DIV align=3Dleft class=3DOutlookMessageHeader dir=3Dltr><FONT =
face=3DTahoma=20
  size=3D2>-----Original Message-----<BR><B>From:</B>=20
  hfs-user-admin@lists.mars.org =
[mailto:hfs-user-admin@lists.mars.org]<B>On=20
  Behalf Of </B>Patrick Dirks<BR><B>Sent:</B> Thursday, February 07, =
2002 1:57=20
  PM<BR><B>To:</B> hfs-user@lists.mars.org<BR><B>Cc:</B> Biswaroop=20
  Banerjee<BR><B>Subject:</B> Re: [hfs-user] Algorithm of B* tree=20
  Implementation<BR><BR></DIV></FONT>"The algorithm" is a bit hard to =
lay out in=20
  an e-mail message - it's wrapped up in a series of design and =
implementation=20
  aspects. Read up on B*-Trees and you should have a good idea what the =
data=20
  structure's supposed to look like at any given time. Read "Inside =
Macintosh"=20
  and you'll find a more detailed explanation of the exact details of =
the=20
  HFS/HFS+ B*-Tree structure. More helpful than "Inside Macintosh", =
perhaps, is=20
  the tech note that Apple's published on the subject - "must read" for =
anyone=20
  implementing a version of HFS/HFS+. I can't remember the tech note =
number=20
  offhand but it's freely available through Apple's web site - do a =
search=20
  there.<BR><BR>Finally, note that the Darwin code, which Apple has open =

  sourced, includes a complete "C" implementation of the B*-Tree code as =
part of=20
  a 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 =
"bsd"=20
  directory of "xnu". That's the ultimate answer right =
there.<BR><BR>Hope that=20
  helps,<BR>-Pat Dirks.<BR><BR>On Thursday, February 7, 2002, at 02:04 =
AM,=20
  Biswaroop Banerjee wrote:<BR><BR>
  <BLOCKQUOTE><?fontfamily><?param Arial><?smaller>Hi =
All,<?/smaller><?/fontfamily><BR>&nbsp;<BR><?fontfamily><?param =
Arial><?smaller>&nbsp;=20
    Can anybody of you give me the algorithm of implementating a B* tree =
which=20
    is the prominent data structure in a HFS formatted =
volume.<?/smaller><?/fontfamily><BR>&nbsp;<BR><?fontfamily><?param =
Arial><?smaller>Waiting&nbsp;=20
    for your help.<?/smaller><?/fontfamily><BR><?fontfamily><?param =
Arial><?smaller>&nbsp;Regards<?/smaller><?/fontfamily><BR><?fontfamily><?=
param Arial><?smaller>Biswaroop=20
    =
Banerjee.<?/smaller><?/fontfamily><BR>&nbsp;<BR>&nbsp;<BR><?fontfamily><?=
param Arial><?smaller>The=20
    essence of Success lies in its=20
    =
Struggle<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&=
nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&n=
bsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nb=
sp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbs=
p;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp=
;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=20
    =
-Bisban&nbsp;<?/smaller><?/fontfamily><BR></BLOCKQUOTE></BLOCKQUOTE></BOD=
Y></HTML>

------=_NextPart_000_0001_01C1B027.0F49EA40--