Determining the Size of the Database › Allocating Space for Indexes › Index Structure

Index Structure

Indexes are built and maintained by the DBMS for:

• System indexes—These are standalone index structures providing alternate access to entity occurrences. They are defined using the OWNER IS SYSTEM clause of the non-SQL ADD SET statement or the CREATE INDEX statement in SQL.

  The root (or top entity) of a system index is an SR7 entity. This is an internal record type with a location mode of CALC. For non-SQL-defined indexes, the CALC key is the name of the index. For SQL-defined indexes, it is an internally generated name.

• Indexed relationships—These are index structures associated with each occurrence of a parent entity in an indexed relationship and are used to point to the associated child entity occurrences.

  They are defined using the MODE IS INDEX clause of the non-SQL ADD SET statement where the set is not defined as SYSTEM-OWNED or the LINKED INDEX clause of an SQL CREATE CONSTRAINT statement. The root of an indexed relationship is an occurrence of the parent entity.

Structure of an index

The structure of an index consists of internally maintained records called SR8s. Each SR8 is chained (by next, prior, and owner pointers) to the parent entity occurrence (or SR7 in the case of a system index) and to each other. An index is therefore structured as a chained relationship between the parent entity (or SR7) and the SR8s.

An SR8 contains from 3 to 8,180 index entries and a cushion (that is, a field that is the length of the largest possible index entry). The content of an index entry depends on the index characteristics:

• For sorted indexes, SR8s are arranged in levels to facilitate searching. Each index entry contains the db-key of an indexed entity occurrence or the db-key of another SR8. Additionally, for indexes sorted on a symbolic key, each index entry also contains a symbolic key. A symbolic key is a key constructed of one or more data elements in the order specified in the schema (up to 256 bytes in length).
• For unsorted indexes, SR8s are arranged in a single level. Each index entry is the db-key for an entity occurrence.

An unsorted index

The following diagram shows the structure for a simple unsorted indexed relationship. In this example, there is a single SR8 chained to the indexed set's parent. The SR8 contains three entries. Each entry contains an index pointer that points to a child entity occurrence. Each child occurrence contains an index pointer that points to that SR8 and an owner pointer that points back to the set's parent. (The owner pointer is optional.)

Structure of a three-level index

The following diagram shows the structure for a sorted index arranged in three levels. In this example, each SR8 has a maximum of three entries. Each entry consists of a symbolic key value and a db-key. The bold entries show how the LONG entity is located during an index search. In the top and intermediate levels, the db-key in each entry points to another SR8. (For simplicity, prior and owner pointers are not included in this figure.)

Entries in a 3-level index

The following diagram shows the index pointers and symbolic keys for a three-level sorted index. Each entry consists of a symbolic key and a pointer (db-key). The bold entries show how the LONG entity is located in the database. The pointers in the top and intermediate levels point to SR8s at the next lowest level. Only the bottom-level entry points to the indexed entity. (For simplicity, prior and owner pointers are not included in this figure; in addition, there are two pointers for the symbolic key for BENN, since there are two employees with that name.)

Number of levels in an index

The number of levels in an index directly affects database performance. The number of levels determines:

• The number of I/Os required to access the indexed entities. An index that has few levels (four or fewer) typically incurs a minimum number of I/Os to access the indexed entities.
• How much contention will occur for access to the SR8 records. An index that has several levels typically reduces contention among application programs that require access to SR8s.

An index is considered efficient if there is little contention for the SR8s and few I/Os are required to access the indexed entities. To develop an efficient index, you should usually plan an index that has three levels of SR8s. An index that has more than eight or ten levels is likely to degrade processing performance by causing the system to access many SR8s when searching for a particular indexed entity occurrence. A system index that consists of fewer than three levels may incur contention if frequently updated. Indexed relationships should usually have fewer than three levels since contention is less likely because there are multiple index structures (one for each relationship occurrence).

Since the structure of an index depends on several dynamic factors, it is often difficult to make a precise calculation of the number of levels that the DBMS will create. CA IDMS/DB therefore provides schema syntax that can be used to influence the number of levels that will be generated for a particular index.

The number of levels generated by CA IDMS/DB for a sorted index depends on the number of index entries in each SR8. You can specify the maximum number of entries that can be contained in an SR8 by using the INDEX BLOCK CONTAINS clause of the index definition in the schema.

You can improve the efficiency of an index by performing one of the following procedures:

• Decrease the number of levels in the index by increasing the number of entries in each SR8. This action can enhance efficiency by decreasing the number of SR8s that the DBMS must access when searching for a particular entry.
• Increase the number of levels in the index by decreasing the number of entries in each SR8. This action can enhance efficiency by reducing the likelihood of contention for SR8s.

For further information on the structure of an index, see CA IDMS Database Administration Guide.