Post by: pendragon on December 07, 2006, 05:00:24 PM
Indeed I want my attribute B-trees rebuilt. After all, who doesn’t? But what in the world are they? And if they are not repaired & rebuilt, what happens?
Post by: bil207 on December 07, 2006, 05:33:59 PM
Mac OS: Technical overview of disk volume structures
QUOTE
Indeed I want my attribute B-trees rebuilt. After all, who doesn’t? But what in the world are they? And if they are not repaired & rebuilt, what happens?
From the last paragraph in the article:
"B-tree structures are complex. If one becomes damaged, erroneous information is read by the File Manager and the referenced files can also become damaged. This is why it is vital to run Disk First Aid or similar utilities on a regular basis."
P.S. Previous versions of DW as well as Disk Utility also repaired damaged B-trees.
Post by: Paddy on December 07, 2006, 06:49:50 PM
QUOTE
The B-tree's creators, Rudolf Bayer and Ed McCreight, have not explained what, if anything, the B stands for. The most common belief is that B stands for balanced, as all the leaf nodes are at the same level in the tree. B may also stand for Bayer, or for Boeing, because they were working for Boeing Scientific Research Labs at the time.
Post by: Xairbusdriver on December 07, 2006, 07:37:17 PM
I vaguely remember studying data structures back when the Apple ][ had only 140K floppies! A buddy and I were trying to come up with a system to allow easy access to data that would end up on a dozen or so disks. ( Can you say, swap disks? ) Naturally, cheaper and larger drives saved the need for such a crazy system; it actually came built in to the OS!
Post by: pendragon on December 08, 2006, 06:45:33 AM
to you all. The data/links were most helpful. Now all I need do is understand it. Arrrgh, learning is not always easy.
Post by: tacit on December 08, 2006, 12:36:25 PM
B-trees are data structures used in many, many places in computer programming, not just disk directories. A type of parser used in writing compilers called a "recursive descent parser" takes a computer program written in a high-level language, generates a "parse tree" that is a B-tree, and then emits object code as it walks the tree. A program I once wrote that plays the game Othello makes a B-tree of all the possible moves, then walks the tree looking for the best move. Compression programs that use a type of compression called Huffman encoding work by generating a B-tree of the data to be compressed. Some sophisticated sort algorithms construct a B-tree of the information to be sorted.
Edited to add: It is important to understand that the Attribute B-Tree in a Mac disk directory is not the same as the catalog B-tree.
The catalog B-tree is a binary tree that keeps track of all the files and folders on your disk. It also makes use of another data structure, the Extents B-tree, which is a binary tree that keeps track of files that are broken up in multiple pieces on a disk. f either of these things is damaged or corrupt, you're in trouble--you may lose track of files and folders on the disk.
The Attribute B-Tree is new in HFS+ (Mac OS Extended), and is not really used quite yet, except (I believe) in a very limited way by Tiger's Spotlight. The Attribute B-Tree is not used to store information about where the files are located on a disk. It is, in theory, used to store "metadata." In a future version of Mac OS, Apple has talked about allowing you to tag a file with any sort of descriptions, comments, or keywords that you want. For example, you could write a letter to your mother in Microsoft Word,and you could save it as "letter-to-mom.doc" with the tags "family," "mother," "personal letters," and "recipes for pie." You could then, for example, use Spotlight to say something like "Find a list of all files on my hard drive that are personal letters" or "Find a list of all files on my hard drive that have something to do with my family." Spotlight would search the attributes B-tree looking for those attributes, and find the files.
Right now, Spotlight can not do this. It can search for words inside a file, but if the letter you wrote to your mom does not contain the word "family," then Spotlight won't find it. With attributes, you can tag files with names or keywords or any other kind of association and Spotlight will find it. You could even, for example, make a Spotlight "smart folder" with the attribute "family," and whenever you open that folder, all your files that have something to do with your family would be inside it.
But that has not been implemented yet. The Attributes B-tree is not really used for anything of note yet. I don't know if Leopard will make use of file attributes or not.
Post by: RNKIII on December 08, 2006, 07:38:52 PM
Thanks Tacit.
Bob K. rnkiii
Post by: jcarter on December 08, 2006, 07:54:12 PM
I was going to post a picture of the most lovely tree in our town, our HUGE Holly covered with red berries. No, seriously, you have really explained this, and you have clearly explained other things which have mystified me about computers in the past.
Thanks,
Jane
Post by: Gregg on December 08, 2006, 09:41:33 PM
Post by: pendragon on December 09, 2006, 05:10:47 AM
again!