Structure of a B-tree Table
A B-tree can be viewed as four separate parts:
• A free list header page, which is used to keep track of allocated pages that are not currently being used
• One or more index pages, which contain leaf page numbers and the range of key values to expect on each leaf page
• One or more leaf pages, which identify the data page and row where the data is stored
• One or more data pages, where the user data is actually stored
The smallest B-tree has four pages, one of each type.
Note: If a secondary index is modified to B-tree, it cannot contain data pages. Instead, the leaf pages of the secondary index reference the main table’s data pages. For more information, see
Secondary Indexes.
The index level is similar to the ISAM index, except that the ISAM index points to data pages, whereas the B-tree index level points to leaf pages. The number of index pages is dependent on the width of the key and the number of leaf pages, because eventually the index pages point to a particular leaf page. Usually the index level is small, because it needs to point to only the leaf pages.
The leaf page level is considered a dense index because it tells the location of every row in the table. In dense indexes, rows on data pages do not move during a split; that causes their tids to change. Tids identify every row on every data page. For a complete discussion of tids, see
Tids.
The index level is considered a sparse index, because it contains only a key value and a pointer to a page.
The following diagram illustrates the three B-tree levels: index page, leaf page, and data page. It illustrates the relationship between the three levels, but cannot be realistic. In actuality, if the key width name were only 30 characters, the row width were 500 bytes, and there were only 31 employees, this B-tree has only a free list header page, one index page, one leaf page, and 8 data pages (instead of 4 leaf pages and 3 index pages).
+----------------------------------+
| ROOT |
| |
| <= McShane |
INDEX PAGE +----------------------------------+
LEVEL / \
/ \
+-------------------------------------+ +---------------------------------+
| Key Leaf Page | | Key Leaf Page |
| | | |
| <= Giller 1 | | > McShane <= Shigio 3 |
| > Giller <= McShane 2 | | > Shigio 4 |
+-------------------------------------+ +---------------------------------+
LEAF PAGE LEVEL
Leaf Page 1 Leaf Page 2 Leaf Page 3 Leaf Page 4
Aitken 1,0 Gordon 3,0 McTigue 5,0 Smith 7,0
Blumberg 1,1 Green 3,3 Ming 5,1 Stannich 7,1
Brodie 1,3 Gregori 3,2 Ramos 5,2 Stein 7,2
Cameron 1,2 Huber 3,1 Robinson 5,3 Stover 7,3
Clark 2,0 Kay 4,0 Ross 6,0 Sullivan 8,0
Curan 2,1 Kreseski 4,1 Sabel 6,1 Verducci 8,1
Curry 2,2 Mandic 4,2 Saxena 6,2 Zimmerman 8,2
Giller 2,3 McShane 4,3 Shigio 6,3
DATA PAGE LEVEL
+-------------------------------------------+
Page 1 0 |Aitken | 1| 49| 50000.000 |
1 |Blumberg | 2| 33| 32000.000 |
2 |Cameron | 4| 37| 35000.000 |
3 |Brodie | 3| 42| 40000.000 |
|-------------------------------------------|
Page 2 0 |Clark | 5| 43| 40000.000 | Associated Data
1 |Curan | 6| 30| 30000.000 | Page for Leaf
2 |Curry | 7| 34| 32000.000 | Page 1
3 |Giller | 8| 47| 46000.000 |
|-------------------------------------------|
Page 3 0 |Gordon | 9| 28| 27000.000 |
1 |Huber | 12| 35| 32000.000 |
2 |Gregori | 11| 32| 31000.000 |
3 |Green | 10| 27| 26000.000 |
|-------------------------------------------|
Page 4 0 |Kay | 13| 41| 38000.000 | Associated Data
1 |Kreseski | 14| 25| 24000.000 | Page for Leaf
2 |Mandic | 15| 46| 43000.000 | Page 2
3 |McShane | 16| 22| 22000.000 |
|-------------------------------------------|
Page 5 0 +McTigue | 17| 44| 41000.000 +
To look for an employee named Kay, the search starts from the root node, where a name that precedes McShane in the alphabet directs you down the left side of the index.
The index page on the left shows that leaf Page 2 is the appropriate page on which to look, because Kay comes between Giller and McShane in the alphabet.
On leaf Page 2, Kay’s record is identified as being on data Page 4, row 0. Going directly to data Page 4, row 0, Kay’s record is located.