This section explains how a B-tree index is organized. Information about index structure can help you understand how indexes are used and why re-creating an index might improve index efficiency.
As Figure 26 shows, a B-tree index is arranged as a hierarchy of pages, which is technically a B+ tree. The top level of the hierarchy contains a single root page. Intermediate levels, when needed, contain branch pages. Each branch page contains entries that refer to 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 refer to 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.
For example, 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.
For more information about the structure of B-tree indexes, refer to the IBM Informix: Extended Parallel Server Administrator's Reference.
Home | [ Top of Page | Previous Page | Next Page | Contents | Index ]