[hfs-user] Clarification needed wrt B/B*-Trees

Entwicklung entwicklung@whengenibk.de
Sun, 24 Mar 2002 19:59:21 +0100


This is a multi-part message in MIME format.

------=_NextPart_000_0007_01C1D36E.63ED8BA0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

Hello listers,
                  The technical notes for HFS+ TN1150 refers to =
'B-Trees' and the documentation for HFS in 'Inside Macintosh - Data =
Organisation on volumes' refers to 'B*- Trees'

Going by the definitions provided by NIST (the national institute of =
standards) a B-Tree is defined as
Definition: A balanced search tree in which every node has between t-1 =
and 2t-1 children, where t is an arbitrary constant. This is a good =
structure if much of the tree is in slow memory (disk), since the =
height, and hence the number of accesses, can be kept small, say one or =
two, by picking a large t.=20


and a B*-Tree is defined as :=20
Definition: A B-tree in which nodes are kept 2/3 full by redistributing =
keys to fill two child nodes, then splitting them into three nodes.=20

As far as I can gather from the definitions and the documentation, HFS =
uses a B*-Tree and HFS+ uses a B-Tree.... does anybody know why ?  Does =
this mean that in case of HFS I would have to perform an additional =
redistribution of keys to keep the nodes just 2/3 full ( which I am not =
considering right now ) ? The HFS-Specs as such do not mention anything =
about keeping the nodes just 2/3 full ...or am I wrong there ?

Would be glad to hear your comments/feedback ...

Regards,

Nandini Hengen






------=_NextPart_000_0007_01C1D36E.63ED8BA0
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 content=3D"text/html; charset=3Diso-8859-1" =
http-equiv=3DContent-Type>
<META content=3D"MSHTML 5.00.2920.0" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>Hello listers,</FONT></DIV>
<DIV><FONT face=3DArial=20
size=3D2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbs=
p;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;=20
The technical notes for HFS+ TN1150 refers to 'B-Trees' and the =
documentation=20
for HFS in 'Inside Macintosh - Data Organisation on volumes' refers to =
'B*-=20
Trees'</FONT></DIV>
<DIV>&nbsp;</DIV>
<DIV><FONT face=3DArial size=3D2>Going by the definitions provided by =
NIST (the=20
national institute of standards)&nbsp;a B-Tree is defined =
as</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>
<P><STRONG>Definition:</STRONG> A balanced search tree in which every <A =

href=3D"http://hissa.nist.gov/dads/HTML/node.html"><EM>node</EM></A> has =
between=20
t-1 and 2t-1 <A=20
href=3D"http://hissa.nist.gov/dads/HTML/child.html"><EM>children</EM></A>=
, where t=20
is an arbitrary constant. This is a good structure if much of the tree =
is in=20
slow memory (disk), since the <A=20
href=3D"http://hissa.nist.gov/dads/HTML/height.html"><EM>height</EM></A>,=
 and=20
hence the number of accesses, can be kept small, say one or two, by =
picking a=20
large t. </P></FONT></DIV>
<DIV>&nbsp;</DIV>
<DIV><FONT face=3DArial size=3D2>and a B*-Tree is defined as :=20
<P><STRONG>Definition:</STRONG> A <A=20
href=3D"http://hissa.nist.gov/dads/HTML/btree.html"><EM><B=20
style=3D"BACKGROUND-COLOR: #ffff66; COLOR: black">B</B>-<B=20
style=3D"BACKGROUND-COLOR: #a0ffff; COLOR: black">tree</B></EM></A> in =
which <A=20
href=3D"http://hissa.nist.gov/dads/HTML/node.html"><EM>nodes</EM></A> =
are kept 2/3=20
full by redistributing <A=20
href=3D"http://hissa.nist.gov/dads/HTML/key.html"><EM>keys</EM></A> to =
fill two <A=20
href=3D"http://hissa.nist.gov/dads/HTML/child.html"><EM>child</EM></A> =
nodes, then=20
splitting them into three nodes. </P>
<P>As far as I can gather from the definitions and the documentation, =
HFS uses a=20
B*-Tree and HFS+ uses a B-Tree.... does anybody know why ?&nbsp; Does =
this mean=20
that in case of HFS I would have to perform an additional redistribution =
of keys=20
to keep the nodes just 2/3 full ( which I am not considering right now ) =
? The=20
HFS-Specs as such do not mention anything about keeping the nodes just =
2/3 full=20
...or am I wrong there ?</P>
<P>Would be glad to hear your comments/feedback ...</P>
<P>Regards,</P>
<P>Nandini Hengen</P>
<P>&nbsp;</P>
<P>&nbsp;</P></FONT></DIV></BODY></HTML>

------=_NextPart_000_0007_01C1D36E.63ED8BA0--