Index Management › Structure of Indexes

Structure of Indexes

Index Creation

The creation of an index is transparent to application programs. An index is created according to your specifications, but the actual creation and storage of the index is performed by CA IDMS/DB. An index is composed of SR8 system record occurrences chained (by next, prior, and owner pointers) to the owner occurrence and each other.

SR8 Records in an Index

Thus, an index is a chained set between the indexed set's owner record and the SR8 records. An index contains SR8 records chained by next, prior, and owner pointers to the indexed set's owner record. For simplicity, prior and owner pointers are not included in the next figure):

Initially, the index is composed of a single SR8 member record. When the first SR8 record is full, additional SR8 records are added to the index as chained records.

Bottom-Level SR8 Record and Database Record Occurrences

An SR8 record, shown in the following diagram, contains from 3 to 8,180 index entries (as specified in the schema or segment definition) and a cushion (that is, a field the length of the largest possible index entry).

The SR8 record in the diagram contains four entries and a cushion. Each index entry contains an index pointer that points to a database occurrence that is a member of the indexed set; each member occurrence contains an index pointer that points to that SR8 record. (Note that, for simplicity, prior and owner pointers are not included in this figure.)

Content of an Index Entry

The actual content of an index entry depends on the indexed set's characteristics, as follows:

• Unsorted set—An index entry contains only the db-key of a member record occurrence.
• Sorted set—SR8 records for sorted indexed sets are arranged in levels to form a tree structure to facilitate a binary search. Consequently, an index entry contains the db-key of a member record occurrence or the db-key of another SR8 record occurrence. Additionally, for indexed sets sorted on a symbolic key, an index entry is composed of a db-key and a symbolic key. A symbolic key is a key constructed of one or more record elements (or columns) in the order specified in the schema (up to 256 bytes in length). (For a detailed discussion of indexed set structure for sorted indexed sets, see 38.3.2, “Connecting Members to Sorted Indexed Sets".)

Example

In this example, there is a single SR8 record chained to the indexed set's owner. The SR8 record contains three entries. Each entry contains an index pointer that points to a member database occurrence; each member occurrence contains an index pointer that points to that SR8 record. Additionally, the member occurrences contain owner pointers that point back to the set's owner.

Indexed Set with Sorted Set Order

For sorted indexed sets, you can specify that CA IDMS/DB keep the index entries within the SR8 records in ascending, descending, or mixed order according to the member record's db-key or symbolic key. You can also specify whether numeric fields should be collated so that negative values are lower than positive values (natural sequence) or whether they should collate based on their bit pattern. If you specify that an indexed set be sorted on symbolic key, you can also specify whether duplicate symbolic keys are allowed or disallowed. Even if you specify that duplicate symbolic keys are allowed, CA IDMS/DB does not store the same symbolic key more than once in the index. For example, the first time a record with a symbolic key ADAMS is added to the indexed set, CA IDMS/DB adds the symbolic key ADAMS to the index and associates the record occurrence's db-key to the key ADAMS. Later, if you add another record with the symbolic key ADAMS to the indexed set, CA IDMS/DB associates the db-key of the new record to the existing symbolic key of ADAMS in the SR8 record.

Specifying Compression

Additionally, you can specify that CA IDMS/DB store symbolic keys in either compressed or uncompressed format. (Note that CA IDMS/DB always strips trailing pad characters from an indexed set's symbolic keys.) If you specify compression, CA IDMS/DB applies a 2-level compression algorithm to the symbolic key before inserting the key into the index, as follows:

• Prefix compression—CA IDMS/DB compares (left to right) the symbolic key of the record being inserted into the index with adjacent symbolic keys and removes like characters. For example, if there are two symbolic keys, JOHNSON and JONES, CA IDMS/DB stores the JOHNSON key in its entirety and stores JONES as NES.
• Repeating character compression—CA IDMS/DB compresses three or more repeating single characters within each symbolic key into two bytes, and compresses 2 through 64 repeating blanks or nulls into one byte.

Specify compression of symbolic keys if the keys have either of the following characteristics:

• Commonly share the same prefix
• Contain many repeating characters (including blanks or nulls)

How the Index is Organized

To facilitate the process of locating an index entry for sorted sets, CA IDMS/DB organizes an index for sorted records into levels. In this case, when the first (top-level) SR8 record is full, CA IDMS/DB performs the following processing:

1. Splits the SR8 record into two parts. These two SR8 records stay at the same level.
2. Constructs a new higher level with two entries. Each entry points to one of the SR8 records created by Step 1.

CA IDMS/DB repeats this process as the index expands. Indexes can have any number of intermediate levels. As CA IDMS/DB adds new entries, it splits SR8 records and spawns new levels of SR8 records. An entry on one level points to an SR8 record at a lower level; the bottom-level entries point to the indexed database records themselves.

Therefore, in a sorted indexed set with three levels (top, intermediate, and bottom), the index is structured as follows:

• The top level is made up of one SR8 record that contains index entries. Each entry is composed of a pointer to (that is, the database key of) an intermediate-level SR8 record and the highest symbolic key contained therein.
• The intermediate level is made up of one SR8 record for each entry in the top level. Each entry is composed of a pointer to a bottom-level SR8 record and the highest symbolic key contained therein.

  The bottom level is made up of one SR8 record for each entry in the intermediate level. Each entry is composed of a symbolic key and a pointer to a database record occurrence.

Example

For example, the sample database includes the indexed set EMP-LNAME-NDX. The EMP-LNAME-NDX set, shown in the following diagram and table shows the function of index levels and the search process. This simple index contains only three entries per SR8 record. The figure represents index and database records. (For simplicity, prior and owner pointers are not included in this figure.) The table shows the index pointers and symbolic keys.

To locate LONG in this 3-level index, CA IDMS/DB performs the following steps:

1. Accesses the SR7 owner record by using the set name as the CALC key

   Note: For SQL-defined indexes, it uses a CALC key based on a number assigned to each index.

2. Accesses the top-level SR8 record by using the next pointer in the SR7 record
3. Searches this top-level SR8 record for the first entry with a symbolic key equal to or greater than LONG
4. Uses the db-key in this entry to access an intermediate-level SR8 record (that is, the NELSON/WEST SR8 record)
5. Searches this intermediate-level SR8 record (that is, the NELSON/WEST SR8 record) for the first entry equal to or greater than LONG
6. Uses the db-key in this entry to access a lower level SR8 record (that is, the JONES/NELSON SR8 record at the bottom level)
7. Searches this bottom-level SR8 record (the JONES/NELSON SR8 record) for the LONG entry
8. Uses the db-key in the LONG entry to access the requested member database record occurrence

Note: Since previous processing deleted indexed records, not all of the index entries in each SR8 record are presently used (for instance, the STUART and UPTON/WEST SR8 records at the bottom level). Consequently, this index has space for expansion without spawning a new level.

In this example, each SR8 record is composed of a maximum of three entries. Each entry is composed of a symbolic key value and a db-key. The shaded entries are used to locate the LONG record in the database. In the top and intermediate levels, the db-key in each entry points to another SR8 record. In the bottom level, the db-key in each entry points to a database record. (Note that, for simplicity, prior and owner pointers are not included in this figure; also, since two employees are named BENN, there are two database member occurrences with that name.)

The entries in the 3-level index are shown next. Each entry is composed of a symbolic key and a db-key. The shaded entries are used to locate the LONG record in the database. The index entries in the top and intermediate levels point to SR8 records at the next lowest level. Only the bottom-level entry points to the database record. Note that since two employees are named BENN, there are two db-keys (one to each database member occurrence) for that symbolic key.