[hfs-user] Index nodes of a catalog B-Tree

Patrick Dirks pwd@apple.com
Mon, 11 Feb 2002 12:13:38 -0800


Yes, every leaf node should have a record in some index node at the next 
level.  Each one of those, in turn, should have a record pointing to 
them in the next higher level, etc.

If you have a leaf record that isn't directly pointed to by an index 
record a search by name for any entries in there will fail, although 
opening the folder and enumerating the contents of a folder will show 
all the entries.

Hope that helps,
-Pat Dirks.

On Monday, February 11, 2002, at 01:15 AM, Entwicklung wrote:

>> Simon Bazley,
>> Thanks for replying !
>>  I managed to figure out what the problem was-  I had mentioned this 
>> in my
>> previous email to the list.
>> I have a question to which maybe you or someone from the list knows the
>> answer -
>> At the moment I'm wondering how to determine the number of index nodes
>> needed for a catalog tree. I have determined the number of catalog 
>> nodes
>> needed and my question is : Does every leaf node in the catalog-tree 
>> have
> to
>> be referenced in the index-nodes?
>> In a broadly logical sense I would say that it has to ...since a leaf
>> without an index in a 'real' tree would probably be like a leaf falling
> off
>> a branch in autumn :). The HFS reference (Inside Macintosh) has this
> figure
>> of a sample B-Tree where a reference to every leaf-node is maintained 
>> in
> the
>> index nodes.
>> But I came across a sample HFS-image (which is readable on my Mac) 
>> which
>> shattered all my illusions since the root-node (the only index node in
> this
>> image) doesn't maintain references to all leaf nodes, only to a few of
> them.
>> Does anyone from Apple (or others) maybe know how the index nodes are 
>> to
>> built up i.e. to which leaf-nodes (if not to all) a reference has to
>> necessarily be maintained ? I guess a Mac internally should be doing 
>> some
>> kind of optimization to reduce the search-time in finding a
> leaf-record....
>> but all I need to know is what I should take into account while
> constructing
>> my index-nodes to make the job easier for the Mac when an external
>> HFS-volume is mounted.
>> Would be grateful for any tips.
>> Regards,
>> Nandini Hengen
>> ----- Original Message -----
>> From: "Simon Bazley <sibaz@sibaz.com>" <simon@sibaz.com>
>> To: "Entwicklung" <entwicklung@whengenibk.de>
>> Cc: <hfs-user@lists.mars.org>
>> Sent: Monday, February 11, 2002 2:41 AM
>> Subject: Re: [hfs-user] Volume-Names in HFS
>>> Have you checked Inside Macintosh Files to see what it says about the
>>> record (assuming its an HFS volume) or the equivalent in the HFS+
> Technote
>>> (assuming its HFS+).  My understanding was that volume name was pretty
>>> bullet proof.
>>> Simon
>>> On Thu, 7 Feb 2002, Entwicklung wrote:
>>>> Hello,
>>>>         My HFS-Volume seems to be recognized if I give the Volume a
> name
>> with an odd no. of characters say "NEW" but fails to be recognized if 
>> the
>> name is say "NAND_HFS". Does anybody know of a possible reason why 
>> this is
>> happening ?
>>>> I think this had something to do with the key length field. In my
> case -
>> if the volume name is even hence implying that the associated key does 
>> not
>> end on an even byte boundary (where applicable), i byte is added for
> padding
>> but the key-length and name length fields are maintained as before. In
> those
>> keys which have to be of size=maximum key length the padding with 
>> zeroes
> is
>> done in any case.
>>>> Does anybody know if something else needs to be changed ?
>>>> TIA,
>>>> Nandini Hengen