Definition

# tree structure

A tree structure is an 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. A node can have as few as two branches (also called children), or as many as several dozen. The structure is straightforward, but in terms of the number of nodes and children, a tree can be gigantic.

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. The starting point is called the root. The maximum number of children per node is called the order of the tree. The maximum number of access operations required to reach the desired record is called the depth. In some trees, the order is the same at every node and the depth is the same for every record. This type of structure is said to be balanced. Other trees have varying numbers of children per node, and different records might lie at different depths. In that case, the tree is said to have an unbalanced or asymmetrical structure.

The illustration shows three examples of tree structures. (Note that the portrayals are upside-down compared to real tree plants.) Structures A and B are balanced, and structure C is unbalanced. Roots are at the top, and are represented by red arrows and red lines. Nodes are shown as gray dots. Children are solid black lines. Leaves are at the bottom, and are represented by green dots. As the process moves toward the leaves and away from the root, children can branch out from a node, but children never merge into a node.

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 trees shown here are simple enough to be rendered in two dimensions, but with some large databases, three dimensions are needed to clearly depict the structure.

Also see binary tree, B-tree, M-tree, quad tree, splay tree, and X-tree.

This was last updated in November 2005

## Content

Find more PRO+ content and other member only offers, here.

#### Start the conversation

Send me notifications when other members comment.

## File Extensions and File Formats

• ### Infographic: The evolution of the chief data officer role

The CDO role, which has never been rigidly defined, is undergoing a face-lift as emerging technologies present new opportunities ...

• ### Predictive analytics projects can bolster business decisions

Blind faith in predictive models can result in flawed business decisions. Analytics teams need to manage predictive processes ...

• ### How predictive analytics techniques and processes work

Predictive analytics is no longer confined to data scientists and other highly skilled analysts. But other users need to ...

## SearchAWS

• ### IaaS providers weigh new tech against core offerings

Like its rivals, AWS continues to push itself up the stack -- and capture headlines in the process. But user demand still ...

• ### AWS Auto Scaling simplifies management across services

Amazon's Auto Scaling service can reduce duplicate efforts by users. It's also the latest example of Amazon's effort to ...

• ### Three Amazon AI-based projects to get your dev team rolling

Amazon AI technologies expand capabilities for enterprise developers. Try out these sample AI projects to familiarize yourself ...

## SearchContentManagement

• ### Agile content management leads to iterative value

An Agile approach to enterprise content management enables companies to continually improve ECM systems and add value steadily ...

• ### Intelligent information management the next wave for ECM

In a 2018 upgrade, M-Files allows users to search for content in multiple repositories, while also being able to automatically ...

• ### SharePoint integration and implementation best practices

Here are some expert advice and tips, as well common definitions, to help make your SharePoint integration and implementation a ...

## SearchOracle

• ### Oracle Blockchain Cloud Service: What it is and what it does

Oracle's cloud-based blockchain service uses Hyperledger Fabric to support distributed transaction ledgers for corporate users on...

• ### Using Oracle 12c Unified Auditing to set database audit policies

Oracle Database 12c's built-in Unified Auditing feature streamlines the database auditing process, including creation and ...

• ### Top Oracle tips and tricks of 2017 you won't want to forget

We've rounded up five of the most notable tip articles we published in 2017, with advice that can help make Oracle projects ...

## SearchSAP

• ### SAP S/4HANA Cloud and indirect access will dominate 2018

Industry experts say SAP S/4HANA Cloud migrations, Leonardo and Cloud Platform are the technology issues for SAP in 2018; on the ...

When a Dutch energy grid provider needed to develop new business apps on top of SAP ERP, it turned to the Mendix RAD platform to ...

• ### SAP's Timo Elliott on enterprise chatbot AI technology

The SAP global innovation evangelist expects AI to affect businesses in three ways: human-computer interaction, automation of ...

## SearchSQLServer

• ### Meltdown and Spectre fixes eyed for SQL Server performance issues

Microsoft has responded to the Spectre and Meltdown chip vulnerabilities with patches and other fixes. But IT teams need to sort ...

• ### Five SQL Server maintenance steps you should take -- ASAP

Putting off SQL Server administration tasks can lead to database problems. Enact these often-neglected maintenance items to help ...

• ### Microsoft Cosmos DB takes Azure databases to a higher level

Azure Cosmos DB brings a new element to the database lineup of Microsoft's cloud platform, offering multiple data models and a ...

Close