Definition of B-tree terms

The database server uses a B-tree structure to organize index information.

Full B-Tree Structure shows that a fully developed B-tree index is composed of the following three different types of index pages or nodes:

One root node
A root node contains node pointers to branch nodes.
Two or more branch nodes
A branch node contains pointers to leaf nodes or other branch nodes.
Many leaf nodes
A leaf node contains index items and horizontal pointers to other leaf nodes.

Each node serves a different function. The following sections describe each node and the role that it plays in indexing.

begin figure description - The paragraph that precedes this figure describes the content of the figure. - end figure description — Figure 1: Full B-Tree Structure

Index items

The fundamental unit of an index is the index item. An index item contains a key value that represents the value of the indexed column for a particular row. An index item also contains rowid information that the database server uses to locate the row in a data page.

Index nodes

A node is an index page that stores a group of index items.

Forest of trees indexes as alternatives to traditional B-Tree indexes

Unlike a traditional B-tree index, a forest of trees index is a large B-tree index that is divided into smaller subtrees with multiple root nodes and fewer levels. You can create a forest of trees index as an alternative to a B-tree index when you want to alleviate root node contention and allow more concurrent users to access the index without waiting.