You are here: >

Tree topology

Tree topologyA tree topology is a special type of structure in which many connected elements are arranged like the branches of a tree. For example, tree topologies are frequently used to organize the computers in a corporate network, or the information in a database.

In a tree topology, there can be only one connection between any two connected nodes. Because any two nodes can have only one mutual connection, tree topologies form a natural parent-child hierarchy.

In computer networking

In computer networks, a tree topology is also known as a star bus topology. It incorporates elements of both a bus topology and a star topology. Below is an example network diagram of a tree topology, in which the central nodes of two star networks are connected to one another.

Tree topology

In the picture above, if the main cable or trunk between each of the two star topology networks were to fail, those networks would be unable to communicate with each other. However, computers on the same star topology would still be able to communicate.

In computer programming

In computer programming, tree topologies can be used to structure many kinds of data, including a computer program itself.

For example, this is a simple computer program written in Lisp:

(+ 1 2 (if (> p 10) 3 4))

Lisp program represented as a treeThis program says "If p is greater than 10, add the numbers 1, 2, and 3. Otherwise, add the numbers 1, 2, and 4." Like all Lisp programs, it has an inherent tree topology structure. If we draw it as a graph, it looks like the tree shown at right. Representing a program this way can be useful because it clearly shows how all the operations and data are connected.

Programs in this kind of structure also have special uses. For instance, genetic programming techniques can evolve new computer programs by exchanging branches between existing tree-structured programs.

Binary Trees

A binary tree is a tree topology in which every node has a maximum of two children. The child nodes are labeled as "left child" or "right child." This type of data structure is often used for sorting and searching large amounts of data. In the binary tree shown below, each parent's left child has a value less than the right child.

Sorted binary tree

B-Trees

A B-Tree is a variation of a binary tree that was invented by Rudolf Bayer and Ed McCreight at Boeing Labs in 1971. Its nodes have a number of children that fall within a predefined minimum and maximum, usually between 2 and 7. A simple B-Tree graph might look like the image below.

A simple B-Tree

B-Trees are self-balancing, meaning that the height of the branches is managed so that they do not get arbitrarily large, and each node contains partitioning "key" values that indicate the values of the children. Their design is optimized for handling very large data files, and for writing data to memory or disk. They are used extensively in database systems like MySQL, PostgreSQL, and Redis, and filesystems such as NTFS, HFS+, and Ext4.

Also see: Network terms, Topology