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 first published in November 2005

## Content

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

Oldest

## File Extensions and File Formats

• ### SQL engines boost Hadoop query processing for big data users

Organizations with big data environments are turning to SQL-on-Hadoop software to speed up analytical queries and data ...

• ### Reality check needed to assess AI applications

When assessing the reality behind today's AI technology, businesses need to think about how it can perform in specific tasks ...

When it comes to building a data science team, businesses should expect to find workers from a variety of backgrounds rather than...

## SearchAWS

• ### Amazon Inspector gives dev automated security assessment

Cloud vulnerabilities can quickly evolve into security threats; vigilance is a key in identifying weaknesses. Amazon Inspector ...

• ### AWS, partners' balancing act weighs on users, too

AWS partners are a critical part of the growing ecosystem, but the choice between third-party services and the waiting game for ...

• ### Words to go: AWS data storage

If you're confused about which data storage option is ideal for your enterprise, refer to our reference sheet on AWS tools and ...

## SearchContentManagement

• ### Document control practices in the age of HIPAA

The time has come to bring information governance stakeholders together to develop a practical plan for document management and ...

• ### E-signature application saves insurer time and money

Insurance company Unum has experienced a dramatic reduction in document-processing time throughout the company since adopting ...

• ### Slack kicks up dust in collaboration software tool market

Slack is taking aim at traditional communication tools like instant messenger and email. But its integration with other services ...

## SearchOracle

• ### OAUG head Dues talks tech plans, Oracle cloud applications

OAUG president Patricia Dues talks about the technology that has the OAUG's attention and why it's important to learn about the ...

• ### ECCU shares ups, downs of Oracle Fusion Financials migration

Moving to Oracle Fusion Financials has been a mixed blessing for the Evangelical Christian Credit Union. It saved money, but had ...

• ### Oracle Enterprise Manager 13c gives DBAs new cloud tools

The latest version of Oracle Enterprise Manager is designed to make life easier for DBAs working in the cloud. Oracle Enterprise ...

## SearchSAP

• ### Integrate cloud to on-premises with HANA Cloud Integration

SAP offers a raft of prebuilt integrations that handle many of the key business processes between major cloud and on-premises ...

• ### Courtroom lessons from a failed SAP ERP implementation

A consulting firm's expert witness explains what SAP and a global manufacturer did -- and didn't do -- that led to a major SAP ...

• ### Building data visualization with SAP Fiori tools

Some BI developers will get by fine with features such as the Fiori Launchpad and Overview pages. Here's what's built into Fiori ...

## SearchSOA

• ### Finding harmony between middleware tools and emerging apps

Tom Nolle explains how developers and architects can navigate the bewildering world of middleware tools and create harmony ...

• ### Why model-driven software development deserves another look

Model-driven development has been around a long time, but in today's complicated app world, it may be time to give this ...

• ### Mobile enterprise solutions: A mobile strategy that'll work

Mobile technology changes rapidly. It's a challenge for any company to keep up to date. But some techniques can be applied to ...

## SearchSQLServer

• ### SQL Server 2016 T-SQL features add to DBCC CHECKDB and more

Expert Ashish Kumar Mehta shares some of the enhancements to T-SQL ahead in SQL Server 2016. This includes a DROP IF EXISTS ...

• ### Database trends to watch after SQL Server 2005 end of life

Two database industry experts discuss infrastructure and analytics trends to consider for database upgrades following the end of ...

• ### Why SQL Server 2005 end of life is good news for DBAs

Two database experts explain how to take advantage of the opportunity created by SQL Server 2005 end of life and how to build a ...

Close