9.4. Service information

For correct operation of the data management subsystem in external memory, it is necessary to maintain information that is used only by this subsystem and is not visible to the language-level subsystem. The set of service information structures depends on the overall organization of the system, but usually requires the maintenance of the following service data:

• Internal directories describing the physical properties of database objects, for example, the number of relation attributes, their size, and possibly data types; description of the indices defined for the relationship, etc.
• Descriptors of free and used memory in relation pages. Such information is required to find free space when entering a tuple. Separately, we have to solve the problem of finding free space in cases of nonclustered and clustered relations (in the latter case, we must additionally use a clustered index). As we have already noted, the problem of freeing the page in multi-access conditions is nontrivial.
• Linking pages of one relationship. If pages of several relations can be located in one external memory file (usually they are striving for this), then you need to somehow link the pages of one relationship. The trivial way to use direct links between pages often leads to difficulties in synchronizing transactions (for example, it is especially difficult to free up and get new relationship pages). Therefore, try to use indirect linking pages using service indexes. In particular, a common mechanism is known for describing free memory and linking pages based on B-trees.