hfs_fs-0.95: hfs_hfind: corrupted b-tree 4

Paul H. Hargrove hfs-interest@ccs.neu.edu
Thu, 21 Jan 1999 15:51:59 -0800 (PST)

Hal Sadofsky is correct, there is no fsck available for hfs.  This is
the one area where you will still need the mac.  Frankly if Norton and
Disk FirstAid are both unable to fix the problem, then I doubt you
could do it automatically.  I think the only option other than
recovery from backups is a professional data recovery service.
However, the data is in principle probably still accessible.

"b-tree 4" is the catalog tree, a sort of database of directory
entries, holding the name, size, type, etc. of all files and
directories.  Unlike in DOS or Un*x where the tree has the same
structure as the directory structure, HFS throws all the entries
together in a single balanced tree (a b-tree).  Each entry is sorted
in the tree by a key composed of its name preceded by the ID number of
its parent directory.  Thus all the files in the same directory are
adjacent in the tree (because there keys start with the same parent
ID).  Corresponding to the '..'  directory entry, each group of files
belonging to the same directory is preceded by a special type of entry
called a thread entry.  It's key is just the ID number of the
directory, with an empty filename appended.  It holds the ID of the
directory's parent.  When any directory is accessed to list its
contents, it is the thread record which is read first.  If it cannot
be found the system decides that the directory doesn't exist, even
though it knows its name.

What appears likely is that one of more "pointers" in the tree have
become corrupted and so the thread records for the "missing"
directories are inaccessible.  This surely means that the entries for
at least some of the entries in those directories are also
inaccessible, but not necessarily ALL of them.  It may still be
possible to access some files or directories in the "missing" ones by
name, but not by 'ls', 'find', 'du' or anything else which tries to do
the equivalent of an 'ls' in the "missing" directories.  If you know
the names of files under the "missing" directories, then give it a

In principle the "extents tree", which holds to info on what blocks
are used by what files, should still know about the files with
inaccessible catalog entries.  If an fsck existed, it would do as
Michael Knox suggests: find all catalog entries is COULD get to and
then find al the extents that weren't accounted for by the accesible
catalog entries and make them into files again, thought there names,
types, and otehr vital statistics would be lost.  This is what Norton
tries to do too, but I imagine that the catalog tree is too badly
damaged for it to be able to create any entries for the lost files.  I
think you should assume that is the case any not try to create of
delete any files or directories on the disk for fear of further
corrupting the catalog tree.

My only USEFULL suggestion is to be sure you have the newest Norton
Utilities for Mac which you can find.  There is always the hope that a
newer version can fix the problem.

Paul H. Hargrove                   All material not otherwise attributed
hargrove@sccm.stanford.edu         is the opinion of the author or a typo.