HP 3000 Manuals

TurboIMAGE/XL Database Management System Reference Manual

Data Set Internal Structures 

The following internal structures are used by TurboIMAGE/XL to manage the
information in data sets.

Pointers 

TurboIMAGE/XL uses pointers to link one data set record to another.  A
pointer is a value containing the block number in the first three bytes
plus one byte that contains the offset within the block for a given data
entry.

Data Chains 

A data chain is a set of detail data set entries that are bidirectionally
linked together by pairs of pointers.  All entries with a common search
item value are placed in the same chain.  Each chain has a first and a
last member.  The pointer pairs constitute backward and forward links to
the entry's predecessor and successor within the chain.  The first member
of a chain contains a zero backward pointer and the last member of a
chain contains a zero forward pointer.  A single chain can consist of at
most 231-1 (2,147,483,647) entries.

Chain Heads 

TurboIMAGE/XL locates the first or last member of a chain within a detail
data set by using a chain head.  The chain head for a particular chain is
stored in the corresponding master data set with the entry whose key item
value is the same as the detail search item value.  Each chain head is 12
bytes long.  The first four bytes contain a count of the number of member
entries in the referenced chain.  The count is zero if the chain is
empty.  The remaining eight bytes contain two pointers.  One points to
the last chain entry, the other to the first chain entry.  If the count
is zero, these pointers are both zero.  If the count is one, these
pointers have the same value.

Media Records 

TurboIMAGE/XL transfers information to and from a storage location on
disk in 4096-byte pages using the system storage manager.  Access to the
data in memory is synchronized through blocks of media records.  A media 
record consists of both a data entry and its pointers or a null record if
no data entry is present.

Media Records of Detail Data Sets.   

For each detail entry, the media record consists of the data entry itself
preceded by all of its related data chain pointer pairs.  The number of
pointer pairs corresponds to the number of paths specified for the data
set within the schema.  Figure 10-1  illustrates a media record for a
detail data set defined with two paths.  The first set of pointers
corresponds to the first path defined in the set part of the schema and
the second set corresponds to the second path.


          Figure 10-1.  Media Record for Detail Entry 

Media Records of Master Data Sets.   

Media records of master data entries are composed of the following:

   *   A 10-byte field serving as a synonym chain head for primary
       entries or a synonym chain link for secondary entries.

   *   A 3 times n word field in which the chain heads of all related
       detail chains are maintained.  n is the number of paths defined
       for the master data set.  Between 0 and 16 paths can be defined.

   *   The data entry itself.

Figure 10-2  illustrates the media record for a primary entry of a
master data set with two paths defined.


          Figure 10-2.  Media Record for Primary Entry 

Figure 10-3  illustrates a media record for a secondary entry of a
master data set with two paths defined.


          Figure 10-3.  Media Record for Secondary Entry 

When more than one detail chain head is present, they are physically
ordered left-to-right in the order that the associated paths are
specified in the schema.

Primary Entries 

Selection of record addresses for master entries begins with a calculated
address determined by a hashing algorithm applied to the value of each
entry's key item.  The algorithm is described later in this chapter.
Each such calculated address is known as a primary address and each entry
residing at its primary address is called a primary entry.

Secondary Entries 

A new entry with a unique key item value will be assigned the same
primary address as an existing primary entry whenever the key item values
of both entries generate the same calculated address.  When this occurs,
the entries are considered synonyms of one another.  TurboIMAGE/XL
assigns the new entry a secondary address obtained from unused records in
the vicinity of the primary entry.  Each entry residing at a secondary
address is called a secondary entry.

Synonym Chains 

When multiple data entries "arrive" at the same primary area, they are
linked together to form a synonym chain.  A synonym chain consists of the
primary entry and all of the data entries with key values that hash to
the same key location.  Each synonym chain is maintained by a 10-byte
chain head in the media record of the primary entry and 10-byte links in
the media records of the secondary entries.  A master data set entry can
contain both a synonym chain head and multiple detail chain heads.  These
are two distinct types of chain heads.

If no secondary entries are present, the synonym chain count is one (for
the total number of entries that hash to this location) and the pointers
to the first and last secondary entries are zeros.  If one or more
secondaries are present, the synonym chain count is equal to the total
number of entries that hash to the same primary address and the pointers
reference the first and last secondary entries.

The first two bytes of the 10-byte link in the media record of each
secondary entry are always zero.  The remaining eight bytes consist of
two pointers bidirectionally linking the secondary entries of the synonym
chain to each other.  As with detail chains, the first member of this
chain of secondary entries contains a zero backward pointer, and the last
member of the chain contains a zero forward pointer.

Blocks and Bit Maps 

Each group of media records involved in a single MPE file record is a
block.  The first few halfwords of each block contain a bit map employed
by TurboIMAGE/XL to indicate whether the corresponding media record is
full or empty.  There is one bit for each record in the block.  The bits
occur in the bit map in the same order that the records occur in the
block.  The bit map occupies as many integral halfwords as are required
to contain one bit for each record in the block.  If a bit is zero, the
corresponding record is empty.  If a bit is one, the record contains a
data entry preceded by the associated structure information.

The format of a block is illustrated in Figure 10-4 .  The sample
block contains four records and the third record contains no entry.


          Figure 10-4.  Block with Blocking Factor of Four 

MPE/iX 5.0 Documentation