splay tree

A splay tree is a self-adjusting search algorithm for placing and locating files (called records or keys) in a database.

This Content Component encountered an error
This Content Component encountered an error

A splay tree is a self-adjusting search algorithm for placing and locating files (called records or keys) in a database. The algorithm finds data by repeatedly making choices at decision points called nodes.

In a splay tree, as in a binary tree, a node has two branches (also called children). Records are stored in locations called leaves. This name derives from the fact that records always exist at end points; there is nothing beyond them. The starting point is called the root. The number of access operations required to reach the desired record is called the depth. In a practical tree, there can be thousands, millions, or billions of nodes, children, leaves, and records. Not every leaf necessarily contains a record, but more than half do. A leaf that does not contain data is called a null.

The splay tree scheme is unique because the tree organization varies depending on which nodes are most frequently accessed. This structural change takes place by means of so-called splaying operations, also called rotations. (In general, to splay is to spread or extend out or apart.) There are several ways in which splaying can be done. It always involves interchanging the root with the node in question. One or more other nodes might change position as well. The purpose of splaying is to minimize the number of access operations required to recover desired data records over a period of time.

Also see binary tree, B-tree, and tree structure.

This was first published in September 2005

Continue Reading About splay tree

Dig deeper on Oracle database design and architecture

Pro+

Features

Enjoy the benefits of Pro+ membership, learn more and join.

0 comments

Oldest 

Forgot Password?

No problem! Submit your e-mail address below. We'll send you an email containing your password.

Your password has been sent to:

-ADS BY GOOGLE

File Extensions and File Formats

Powered by:

SearchDataManagement

SearchBusinessAnalytics

SearchSAP

SearchSQLServer

TheServerSide

SearchDataCenter

SearchContentManagement

SearchFinancialApplications

Close