The nested sets model is a way to store hierarchical data in relational databases, with each node assigned two numbers. It provides fast access but is complicated for inserts, deletes, and reordering. It is best for lightweight content management systems with minimal posting and editing.
The nested sets model is also known as the modified preorder tree traversal algorithm and is a way to store hierarchical data within relational databases. This model has the advantage of providing very fast access and is best implemented in hierarchies that are read more frequently than those to which they are written. Each node within the information model is assigned two numbers which are stored as attributes. Querying the nested set model is simple enough because either value can be used to extract the data you need. Doing inserts, deletes, moves, and updates, however, is much more complicated because it might involve renumbering nodes.
Typically used to represent nested sets or hierarchical information in the form of trees, the nested sets model was introduced by Joe Celko. A tree, in this case, is a data structure that contains a number of connected nodes. For example, a parent node can connect to several child nodes and this structure is repeated through the tree through several levels.
Trees are a great way to store information in a particular order within a relational database, which is a dataset that stores data based on common characteristics. For example, product information within the food section of a store might start with food, branching out into fruits, vegetables, and meats. Fruits can be further divided into berries, melons and apples and vegetables into tubers, greens and others, and meat into pork, mutton and veal.
A relational database stores all of this information in an easy-to-understand form, and a nested sets model allows you to efficiently manage the tree structure. Using the example above, the root node would be food, which is represented by two values. Given the left value for food of 1, the other items in the tree are assigned a number to the left in order. Fruits would have a value of 2 left, berries 3, and so on. Values are then assigned on the right side, working up the tree, bottom up, through each branch until the last value is assigned to the food on the right side.
Each element in the tree ends up with two values, say lft for left and rgt for right, which can be used to identify them and indicate their relationship to other elements. For example, if fruits have values of 2 and 15, then all nodes that have left-hand values greater than 2 and right-hand values less than 15 are descendants of fruit tree 2–15. It becomes easy to extract information about all fruits at once because these values can be specified in a single database query.
This model is great for storing frequently accessed information, but inserting, deleting, and reordering information in the nested sets model becomes very tedious. Rewriting indexes and renumbering information can crash the database, especially if the tree grows to include hundreds of thousands of nodes. The nested model is best for lightweight content management systems that have minimal posting and editing. Insertions can be done much faster in the nested range model because it stores each node’s position in the tree using floating-point decimals and also encodes the path information.
Protect your devices with Threat Protection by NordVPN
