GDS structures the data into multiple balanced trees, or B-trees. A new B-tree, called a Global Variable Tree (GVT), is created each time a new global variable is defined. Each GVT stores the data for one global name (gvn). Global Variable Trees contain both index and data blocks and can span several levels. The data blocks contain actual global variable values, while the index blocks point to the next level of block.

At the root of the B-tree structure is a special Fidelity Information Services tree called a Directory Tree (DT). The Directory Tree contains pointers to the GVT. A data block in the Directory Tree contains an unsubscripted global variable name and a pointer to the root block of that global variable's GVT.

All GDS blocks in the trees have level numbers. Level zero (0) identifies the terminal nodes (i.e., data blocks). Levels greater than zero (0) identify non-terminal nodes (i.e., index blocks). The highest level of each tree identifies the root. All the B-trees have the same structure. Block one (1) of the database always holds the root block of the Directory Tree.

When a SET results in the first use of a global name by referring to a subscripted or unsubscripted global variable that has not previously appeared in the database, GT.M creates a new Global Variable Tree. GVT's continue to exist even after all nodes associated with their unsubscripted name are KILLed. Deletion of an empty tree requires a reorganization of the database file using MUPIP EXTRACT, CREATE, and LOAD.

The remainder of the chapter describes the details of the database structures.