Comparison of Different Tree Implementations
Let's decide what design we should use.
We'll cover the following
Each of the designs has its own strengths and weaknesses. The strengths and weaknesses are discussed in this lesson, and a table summarizes them all.
Pros and cons of different tree implementations
Here are some of the strengths and weaknesses of each design that we may consider:
- Adjacency List is the most conventional design, and many software developers recognize it.
- Recursive Queries using
WITH
orCONNECT BY PRIOR
make it more efficient to use the Adjacency List design, provided that we use one of the database brands that support the syntax. - Path Enumeration is good for breadcrumbs in user interfaces, but it’s fragile because it fails to enforce referential integrity and stores information redundantly.
- Nested Sets is a clever solution — maybe too clever. It fails to support referential integrity. It’s best used when we need to query a tree more frequently than we need to modify it.
- Closure Table is the most versatile design and the only design in this chapter that could allow a node to belong to multiple trees. It requires an additional table to store the relationships. This design also uses a lot of rows when encoding deep hierarchies, increasing space consumption as a trade-off for reducing computing.
We choose the design on the basis of how efficiently we can perform the operation we need to perform using that design. In the table below, operations are marked as either easy or hard to perform when using each of the respective tree designs.
Get hands-on with 1200+ tech skills courses.