Database Reference
In-Depth Information
INDEX STRUCTURE
The nonleaf pages always contain a (possibly truncated) key value, the highest
key together with a pointer, to a page at the next lower level, as shown in
Figure 2.1. Several index levels may be built up in this way, until there is only
a single page, called the root page , at the top of the index structure. This type of
index is called a B-tree index (a balanced tree index) because the same number
of nonleaf pages are required to find each index row.
TABLE ROWS
Each index row shown in Figure 2.1 points to a corresponding row in the table;
the pointer usually identifies the page in which the row resides together with
some means of identifying its position within the page. Each table row contains
some control information to define the row and to enable the DBMS to handle
insertions and deletions, together with the columns themselves.
The sequence in which the rows are positioned in the table, as a result of a
table load or row inserts, may be defined so as to be the same as that of one of
its indexes. In this case, as the index rows are processed, one after another in key
sequence, so the corresponding table rows will be processed, one after another
in the same sequence. Both index and table are then accessed in a sequential
manner that, as we will see shortly, is a very efficient process.
Obviously, only one of the indexes can be defined to determine the sequence
of the table rows in this way. If the table is being accessed via any other index,
as the index rows are processed, one after another in key sequence, the corre-
sponding rows will not be held in the table in the same sequence. For example,
the first index row may point to page 17, the next index row to page 2, the
next to page 85, and so forth. Now, although the index is still being processed
sequentially and efficiently, the table is being processed randomly and much less
efficiently.
BUFFER POOLS AND DISK I/OS
One of the primary objectives of relational database management systems is
to ensure that data from tables and indexes is readily available when required.
To enable this objective to be achieved as far as possible buffer pools, held
in memory, are used to minimize disk activity. Each DBMS may have sev-
eral pools according to the type, table or index, and the page size. Each pool
will be large enough to hold many pages, perhaps hundreds of thousands of
them. The buffer pool managers will attempt to ensure that frequently used
data remains in the pool to avoid the necessity of additional reads from disk.
How effective this is will be extremely important with respect to the perfor-
mance of SQL statements, and so will be equally important for the purposes of
this topic. We will return to this subject on many occasions where the need
Search WWH ::




Custom Search