B* Trees for Tables with Indexes 
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 big 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
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:
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.