Structure of conventional index pages
A conventional index is arranged as a hierarchy of pages (technically, a B-tree).
The following figure shows the B-tree structure of an index. The topmost level of the hierarchy contains a single root page. Intermediate levels, when needed, contain branch pages. Each branch page contains entries that see a subset of pages in the next level of the index. The bottom level of the index contains a set of leaf pages. Each leaf page contains a list of index entries that see rows in the table.
The number of levels needed to hold an index depends on the number of unique keys in the index and the number of index entries that each page can hold. The number of entries per page depends, in turn, on the size of the columns being indexed.
If the index page for a given table can hold 100 keys, a table of up to 100 rows requires a single index level: the root page. When this table grows beyond 100 rows, to a size between 101 and 10,000 rows, it requires a two-level index: a root page and between 2 and 100 leaf pages. When the table grows beyond 10,000 rows, to a size between 10,001 and 1,000,000 rows, it requires a three-level index: the root page, a set of 100 branch pages, and a set of up to 10,000 leaf pages.
Index entries contained within leaf pages are sorted in key-value order. An index entry consists of a key and one or more row pointers. The key is a copy of the indexed columns from one row of data. A row pointer provides an address used to locate a row that contains the key. A unique index contains one index entry for every row in the table.
For information about special indexes for Informix®, see Indexes on user-defined data types.