Advanced Search
Apple Developer Connection
Member Login Log In | Not a Member? Contact ADC

Previous Book Contents Book Index Next

Inside Macintosh: Files /
Chapter 2 - File Manager / Data Organization in Memory

B*-Tree Control Blocks

When the File Manager mounts a volume, it reads the B*-tree header node for both the catalog file and the extents overflow file found on that volume and, for each file, creates a B*-tree control block in memory. (See the section "Header Nodes" on page 2-67 for a description of B*-tree header nodes.) The structure of a B*-tree control block is defined by the BTCB data type.

TYPE BTCB         =           {B*-tree control block}
   btcFlags:      SignedByte; {flag byte}
   btcResv:       SignedByte; {reserved}
   btcRefNum:     Integer;    {file reference number}
   btcKeyCr:      ProcPtr:    {pointer to key comparison routine}
   btcCQPtr:      LongInt;    {pointer to cache queue}
   btcVarPtr:     LongInt;    {pointer to B*-tree variables}
   btcLevel:      Integer;    {current level}
   btcNodeM:      LongInt;    {current node mark}
   btcIndexM:     Integer;    {current index mark}
   btcDepth:      Integer;    {current depth of tree}
   btcRoot:       LongInt;    {number of root node}
   btcNRecs:      LongInt;    {number of leaf records in tree}
   btcFNode:      LongInt;    {number of first leaf node}
   btcLNode:      LongInt;    {number of last leaf node}
   btcNodeSize:   Integer;    {size of a node}
   btcKeyLen:     Integer;    {maximum length of a key}
   btcNNodes:     LongInt;    {total number of nodes in tree}
   btcFree:       LongInt;    {number of free nodes}
Field Description
A flag byte. Currently the following bits are defined:
 4Set if an existing index record must be deleted
 5Set if a new index record must be created
 6Set if the index key must be updated
 7Set if the block has changed since it was last flushed
The file reference number of the catalog or extents overflow file corresponding to this control block.
A pointer to the routine used to compare keys.
A pointer to the cache queue.
A pointer to B*-tree variables.
The current level.
The current node mark.
The current index mark.
The current depth of the B*-tree.
The node number of the root node. The root node is the start of the B*-tree structure; usually the root node is the first index node, but
it might be a leaf node if there are no index nodes.
The number of data records (records contained in leaf nodes).
The node number of the first leaf node.
The node number of the last leaf node.
The size (in bytes) of a node. Currently, this is always 512.
The length of the key records in each node.
The total number of nodes in the B*-tree.
The total number of free nodes in the B*-tree.

Previous Book Contents Book Index Next

© Apple Computer, Inc.
2 JUL 1996

Get information on Apple products.
Visit the Apple Store online or at retail locations.

Copyright © 2004 Apple Computer, Inc.
All rights reserved. | Terms of use | Privacy Notice