B* Trees for Tables with Indexes

Use

The database system creates a B* tree for every index that is defined for a base table.

The index of a base table is defined explicitly with an SQL statement and has nothing to do with the B* tree index level.

The database system stores the inversion lists of the index as follows:

?     1:1 relationship between the secondary key (index entry) and primary key:

The database system stores the inversion list directly on the corresponding leaf page of the B* tree of the index.

?     1:n relationship between secondary key and primary keys:

The database system stores the inversion list directly on the corresponding leaf page of the B* tree of the index (flat list).

If the inversion list becomes too big for the leaf page, the database system creates another B* tree for the inversion list. The leaf page of the B* tree of the index then only contains only the reference to the B* tree of the inversion list.

Example

The CUSTOMER table contains the names of all the customers of a hotel.

?     Primary key: customer number cno

?     Index: last name name

CUSTOMER Table

cno

surname

firstname

2003

Miller

Frank

2011

Griffith

Mary

2078

Miller

Jane

2104

Miller

Susan

2295

Miller

Sally

The index contains the following inversion lists:

Inversion Lists

Name

Secondary Key

Primary Key

Inversion list 1

Griffith

2011

Inversion list 2

Miller

2003, 2078, 2104, 2295

The database system stores inversion list 1 directly on the leaf page of the B* tree of the index.

For inversion list 2, the database system creates an additional B* tree because there is not enough space on the leaf page of the B* tree of the index.

See also:

Logical Access Structures