tree structure

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.

Learn more about Data warehouse software

Data Warehouse Platforms Product Directory: Inside this data warehouse platform product directory you'll find basic information about the major vendors in the data warehouse market and the products they sell.
How to evaluate data warehouse software in five steps: What's the process for evaluating data warehouse software?
How to choose between the Inmon vs. Kimball approach for data warehouse design: What's your take on the Ralph Kimball vs. Bill Inmon approaches to data warehouse design?
Data Warehouse Platforms Product Directory: Inside this data warehouse platform product directory you'll find basic information about the major vendors in the data warehouse market and the products they sell.
SearchDataManagement.com product directory library: These product directories are designed to assist organizations in evaluating and purchasing data management software
Data warehouse appliances -- in a nutshell: This guide provides an overview of data warehouse appliance trends and concepts. Get tips for advancing a data warehouse strategy, learn the benefits of data warehousing and more.
	Data management books: Read sample chapters from industry-renowned data management books. Browse free excerpts about BI, compliance and security, EDI, data warehousing, data quality and data governance.
Data model patterns: A metadata map: Read this excerpt from Data Model Patterns: A Metadata Map for a guide to all things metadata. That is, data about data.

Do you have something to add to this definition? Let us know. Send your comments to techterms@whatis.com

FILE EXTENSION AND FILE FORMAT LIST File Extension and File Format List: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

RELATED CONTENT In-database analytics pulls together SAS, data warehouse vendors SAS is working on in-database analytics initiatives with several data warehouse vendors that want its data mining applications to run inside their... Teradata takes a logical approach to data warehousing appliances Mark Whitehorn, fresh from the Teradata user conference, discusses the company's approach toward data warehousing appliances. While it may seem... BT taps open source BI software, homegrown DW to unlock customer data Telecommunications giant British Telecom built its own data warehouse from the ground up, then added open source software from JasperSoft to unlock...

RELATED GLOSSARY TERMS Terms from Whatis.com − the technology online dictionary data modeling  (SearchDataManagement.com) Data modeling is the analysis of data objects that are used in a business or other context and the identification of the relationships among these... extract, transform, load  (SearchDataManagement.com) In managing databases, extract, transform, load (ETL) refers to three separate functions combined into a single programming tool.