Show TOC

Logical Access StructuresLocate this document in the navigation structure

Use

The database system uses the following organizational structures to store data in the database:

  • Page chains

  • B* trees

Page Chains

The database system uses page chains to store undo log entries and SAP liveCache data (C++ objects).

A page chain is a sequence of pages that logically belong together. 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.

Figure 1: Page Chain

B* Trees

The database system creates B* trees for the following database objects:

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.

Figure 2: 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.

Figure 3: 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, thus making it unnecessary to reorganize the data manually (see Rebalancing).