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

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 Oracle's data warehouse strategy unclear after Sun acquisition With its acquisition of Sun Microsystems complete, Oracle faces a slew of questions regarding its data warehouse strategy. Mega-vendors dominate Gartner's 2010 BI, data warehouse Magic Quadrants IT heavyweights Oracle, IBM and Microsoft continue to control large segments of the BI software and data warehouse markets, according to Gartner's... Transaction processing system examples and SOA approaches Learn about transaction processing systems, processing systems components and different service-oriented architecture approaches, including...

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.