Background documentationB* Trees for Tables with Indexes Locate this document in the navigation structure

 

The database system creates a B* tree for every index of a base table.

It stores the inversion lists of the index as follows:

  • 1:1 relationship between index (secondary key) 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 index and primary keys:

    The database system also 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 large for the leaf page, the database system creates another B* tree for this inversion list. The leaf page of the B* tree of the index then 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

(Primary Key)

name

(Index)

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

Index

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.

More Information

Logical Access Structures