Indexes

Generally the fastest way to the data required is via an index. Within Informix, indexes are organised into B+ trees. A B+ tree is a hierarchical structure of nodes that contain keys and pointers to the rowids within a table. An important feature of the B+ tree is that it is balanced ie there are an equal number of levels in all parts of the tree. Therefore, no matter where the key or pointer lies within the structure the number of reads required to retrieve the value is constant throughtout the index. The bottom level, level-0 or leaf node contains the information required to retrieve the data.

To access a row using the index the top level or root node is used and for a small table might point directly to the data required. More usually it will point to another level as the indexes on most tables have more than one level. So if the index requires three levels then the engine must make three reads to access the information required to access the data. Each node is the size of a page, either 2 or 4KB depending on the platform

When a node gets full, it must he split into two nodes. Attempting to add a key into a full node forces a split into two nodes and promotion of the middle key value into a node at a higher level.

After a split of a full node, the two resulting nodes are only half full. This leaves room in each node to add more keys as needed. However, there are some problems with a great deal of splits occurring on an index:

	Splitting a node takes time. A split operation requires some extra processing. The keys must be re-arranged into two pages; also, the affected index pages will be locked during the split operation.
	Half-full nodes increase the size of the overall B+ tree. More disk space is used for the index, and there is some chance that the number of levels will increase.
	Half-full nodes decrease the number of keys that can be cached. Since the pages are half-full, more pages are needed to buffer the same amount of data as when the pages are full.

Indexes are extremely useful in accessing a row quickly. However, it is important for the administrator to realize the overhead required to maintain an index for INSERT, UPDATE and DELETE statements. Each INSERT and DELETE statement requires that every index for the table be read. The INSERT statement must locate the correct index page to place the key. The DELETE statement must locate the key in order to mark it for deletion.

When a key value is updated as part of an UPDATE statement, the old key value must be located and deleted, and the page for the new key value must be inserted. This means that each index that is part of the UPDATE statement may be read twice! The first B+ tree level, and perhaps the second level, will most likely be cached in the shared memory buffer pooi. Depending upon the size of the buffer pool and the number of pages in the index, you will probably perform a disk read to access the third and fourth level pages. The index fill factor is the percentage of each index page that will be filled during the index build. This percentage can be set with the CREATE INDEX statement. If it is not specified with CREATE INDEX, the default becomes the value specified in the ONCONFIG parameter FILLFACTOR. Both examples are shown above. If the fill factor is not specified in either location, the default fill factor is 90 percent. If you do not anticipate many new inserts into the table after the index is built, you can set the FILLFACTOR higher when you create the index. If you are expecting a large number of inserts into the table, you can leave the FILLFACTOR at the default value or set it lower. If the FILLFACTOR is set too low, you risk a decrease in the cache rate and an unnecessary increase in the amount of disk space needed for the index. The fill factor is not kept during the life of the index. It is only applied once as the index is built.

Note: The dbschema utility will not list the fill factor if it is specified in an index. In fact, the fill factor percentage is not saved once the index is created.