Definition of B-tree terms

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

Figure 1 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.
Figure 1. Full B-Tree Structure
begin figure description - The paragraph that precedes this figure describes the content of the figure. - end figure description

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.