Legacy Document

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}
RECORD
   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}
END;

Field Description

btcFlags

A flag byte. Currently the following bits are defined:

	Bit	Meaning
	4	Set if an existing index record must be deleted
	5	Set if a new index record must be created
	6	Set if the index key must be updated
	7	Set if the block has changed since it was last flushed

btcResv

Reserved.

btcRefNum

The file reference number of the catalog or extents overflow file corresponding to this control block.

btcKeyCr

A pointer to the routine used to compare keys.

btcCQPtr

A pointer to the cache queue.

btcVarPtr

A pointer to B*-tree variables.

btcLevel

The current level.

btcNodeM

The current node mark.

btcIndexM

The current index mark.

bthDepth

The current depth of the B*-tree.

btcRoot

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.

btcNRecs

The number of data records (records contained in leaf nodes).

btcFNode

The node number of the first leaf node.

btcLNode

The node number of the last leaf node.

btcNodeSize

The size (in bytes) of a node. Currently, this is always 512.

btcKeyLen

The length of the key records in each node.

btcNNodes

The total number of nodes in the B*-tree.

btcFree

The total number of free nodes in the B*-tree.