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.
and a B*-Tree is defined as : 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.
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