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

Mark Day mday@apple.com
Mon, 25 Mar 2002 09:52:09 -0800


On Sunday, March 24, 2002, at 10:59  AM, Entwicklung wrote:

> 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 ?

It's just an imprecise use of terminology.  Both HFS and HFS Plus can 
use the same implementation for B-trees (and they do in Mac OS 8, 9 and 
Mac OS X).

Actually, I think "B+-Tree" is more accurate.  A B+-Tree is really just 
a B-tree where all of the data is kept in leaf nodes (and interior nodes 
contain only keys and pointers).  The B-trees in HFS and HFS Plus do 
have that characteristic.

The difference between B-tree and B*-Tree is a difference in how full 
the nodes are kept in the face of inserts and deletes.  Apple's code 
splits an overly full node into two nodes (not splitting two siblings 
into three like a B*-tree).  However, Apple's code does have an extra 
optimization that tends to keep nodes fuller than a plain B-tree.  When 
a node is too full to insert a new record, it first tries to "rotate" 
one or more records to a sibling.  I know it tries rotating to the left; 
I can't remember whether it tries rotating to the right.  If rotation is 
not possible, the node is split into two.

-Mark