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: