Logical Access Structures 
The database system uses the following organizational structures to store data in the database:
● Page chains
● Pages in B* trees
Page Chains
The database system uses page chains to store undo log entries and SAP liveCache data (C++ objects) and later access them.
A page chain is a sequence of pages that belong together logically. Each page has exactly one page that follows it. The first page in a page chain is called the root page. The root page contains internal administration information, such as the ID of the last page in the chain.
Page Chain
B* Trees
The database system creates B* trees for the following database objects:
● One B* tree for each table for the data records (application data)
● One or more additional B* trees for the LONG values of a table
See B* Trees for Tables with LONG Columns.
● An additional B* tree for each index of a table
See B* tree for each index of a table
A B* tree consists of a root level, one or more B* tree index levels and a leaf level. Each level consists of one or more pages. When the database system searches for a data record, it starts at the root page of the B* tree and narrows the search area step by step.
B* Tree with Three Levels
The pages of the root and B* tree index levels in a B* tree contain the separators.
A separator points to the logical addresses (page numbers) of pages on the next lower level. The separator contains the significant part of the primary key that is required to differentiate it from the next entry. In this way, the memory space that is required by these pages is minimized. The average length of the separators depends on the structure and selectivity of the key.
The first separator in the far left page for each level (including the root level) contains only the pointer to the far left page on the next level down.
Root page of the B* tree
The pages of the leaf level (leaf pages) contain the actual data records (table rows) and a position list. Each data record has an entry in the position list that points to the physical location of the data record in the page. The database system stores the data records on a single page randomly, but it always stores the position entries in the position list in ascending order.
The number of data records on a leaf page depends on the total length of the data records.
The database system automatically rebalances the B* trees, thereby making it unnecessary to reorganize the data manually. See Rebalancing.
See also: