User Guide

SAP AG November 2002
B* Trees for Tables [Page 104]
Root/Index Page
Entries in root pages and index pages in a B* tree [Page 128] contain two sections.
• First section: This section contains an initial segment of the key fields of a table row. This
section is called the separator. SAP DB uses only this part of the primary key [Page
101], which is required to distinguish the subsequent entries, thereby minimizing the
storage space used in these pages.
The first separator in the leftmost page of each level (including the root level) contains
only the pointer to the leftmost page of the next level down.
The average length of the separators depends on the structure and the selectivity of the
primary key. If a very large number of key fields have to be evaluated to enable the
entries (records) to be distinguished from each other, this results in longer separators.
• Second section: This section contains the logical address of a page at a lower index
level or at the leaf level. The number of entries in this section depends on the length of
the separators.
Leaf Page
Leaf pages in a B* tree [Page 128] contain the content of table rows. The number of entries
in a leaf page depends on the total length of the table rows.
The leaf pages in the B* tree are sorted from left to right in ascending order. In other words,
each leaf page contains only the table rows that fit its sort area.
The table rows are located in the first section (data section) of the leaf page. The rows in the
data section are not sorted by default. The last section of the leaf page contains a position
list with addresses that point to the corresponding table rows. The information in the position
list is sorted.
The storage space required to store the entire table depends on the length of the separators
and on the total length of table rows.
Table Access
The logical term table denotes possible primary data, including data in columns of type LONG
and data of secondary key structures.
• As specified by its schema definition, a table has exactly one B* tree [Page
128] for the
primary data, and exactly one B* tree for each secondary key [Page
102].
• If the table definition contains columns of data type LONG, an additional B* tree is
created to accommodate all data of this type that does not exceed a specified length
(data of type short LONG). Data items of type LONG that exceed this specific length are
each stored in separate B* trees (data of type long LONG).
All searches and changes in the table are executed in the computer’s main memory via SQL
statements (SELECT, INSERT, UPDATE, DELETE,...), which means that they are carried out
very quickly. The B* tree structure changes in all cases of INSERT, UPDATE and DELETE
statements if there is not enough space in the target page for the new information or the fill
level of a page falls below the predefined fill level.
User Manual: SAP DB 103