Definition

binary tree

A binary tree is a method of placing and locating files (called records or keys) in a database, especially when all the data is known to be in random access memory (RAM). The algorithm finds data by repeatedly dividing the number of ultimately accessible records in half until only one remains.

In a tree, 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. Branch points are called nodes. The order of a tree is the number of branches (called children) per node. In a binary tree, there are always two children per node, so the order is 2. The number of leaves in a binary tree is always a power of 2. The number of access operations required to reach the desired record is called the depth of the tree. The image below shows a binary tree for locating a particular record among seven records in a set of eight leaves. The depth of this tree is 4.

In a practical tree, there can be thousands, millions, or billions of records. Not all leaves necessarily contain a record, but more than half do. A leaf that does not contain a record is called a null. In the example shown here, the eighth leaf is a null, indicated by an open circle.

Binary trees are used when all the data is in random-access memory (RAM). The search algorithm is simple, but it does not minimize the number of database accesses required to reach a desired record. When the entire tree is contained in RAM, which is a fast-read, fast-write medium, the number of required accesses is of little concern. But when some or all of the data is on disk, which is slow-read, slow-write, it is advantageous to minimize the number of accesses (the tree depth). Alternative algorithms such as the B-tree accomplish this.

Also see binary search and tree structure. Compare B-tree, M-tree, splay tree, and X-tree.

This was last updated in September 2005
Posted by: Margaret Rouse

Email Alerts

Register now to receive SearchSQLServer.com-related news, tips and more, delivered to your inbox.
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy

More News and Tutorials

  • Database index design and optimization: Some guidelines

    What are the latest tips and tricks for database design and optimization? Check out this tip from Basit Farooq to learn more.

  • Download SQL Server Insider

    SQL Server Insider e-zine is a quarterly online publication focusing on Microsoft’s enterprise database, SQL Server. Join the editors of SearchSQLServer.com for an in-depth look into the database trends sweeping over Microsoft, including business intelligence, cloud computing and “big data.”

  • SQL Server's Data Quality Services makes cleanup a cinch

    SQL Server Data Quality Services is Microsoft’s newest data-cleansing tool. Expert Denny Cherry examines the upcoming SQL Server 2012 feature and delves into its components and processes.

Do you have something to add to this definition? Let us know.

Send your comments to techterms@whatis.com

There are Comments. Add yours.

 
TIP: Want to include a code block in your comment? Use <pre> or <code> tags around the desired text. Ex: <code>insert code</code>

REGISTER or login:

Forgot Password?
By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy
Sort by: OldestNewest

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: