Stack Overflow
Stack Overflow

Questions tagged [nested-sets]

The nested set model is a particular technique for representing nested sets (also known as trees or hierarchies) in relational databases.

From Wikipedia:

The nested set model is a particular technique for representing nested sets (also known as trees or hierarchies) in relational databases.

In the nested set model, nodes are numbered according to a tree traversal which visits each node twice, assigning numbers in the order of visiting, and at both visits. This leaves two numbers for each node, which are stored as two attributes. Querying becomes inexpensive: hierarchy membership can be tested by comparing these numbers. Updating requires renumbering and is therefore expensive. Refinements that use rational numbers instead of integers can avoid renumbering, and so are faster to update, although much more complicated.

392 questions
25
votes
13 answers

Move node in nested set

I'd need a MySQL query that moves a node and all its children within a nested set. I found this site, but that function just seems so illogical - there's no universeid or treeid in a nested set model, and the code itself is just longer than what…
Ivar
  • 4,344
  • 6
  • 38
  • 53
24
votes
4 answers

How to repair a corrupted MPTT tree (nested set) in the database using SQL?

I have an MPTT tree of over 100,000 records stored in MySQL using lft, rght and parent_id columns. Now the left/right values became corrupted, while the parent ids are still intact. It would require tons of queries to repair it in the application…
deceze
  • 510,633
  • 85
  • 743
  • 889
23
votes
6 answers

Building hierarchy objects from flat list of parent/child

I have a list of items in a hierarchy, and I'm attempting to parse this list out into an actual hierarchy of objects. I'm using modified pre-order tree traversal to store/iterate through this list, and so what I have is a subset of the tree,…
gregmac
  • 24,276
  • 10
  • 87
  • 118
21
votes
2 answers

How do you convert a parent-child (adjacency) table to a nested set using PHP and MySQL?

I've spent the last few hours trying to find the solution to this question online. I've found plenty of examples on how to convert from nested set to adjacency... but few that go the other way around. The examples I have found either don't work or…
mrbinky3000
  • 4,055
  • 8
  • 43
  • 54
21
votes
7 answers

Getting a modified preorder tree traversal model (nested set) into a

I am trying to get my data which is hierarchically set up with a tree traversal model into an < ul> in order to show on my site. Here is my code: function getCats($) { // retrieve all children of $parent $query = "SELECT max(rght) as max from…
sanders
  • 10,794
  • 27
  • 85
  • 127
18
votes
8 answers

How do you sort a tree stored using the nested set model?

When I refer to nested set model I mean what is described here. I need to build a new system for storing "categories" (I can't think of better word for it) in a user defined hierarchy. Since the nested set model is optimized for reads instead of…
Bernard
12
votes
8 answers

MySQL Nested Sets - How to find parent of node?

I have your run of the mill nested set hierarchy type setup with the following columns: table name: myset columns: id, name, lft, rgt Does anyone know a query to determine the parent of a node? I read a couple places that it's handy to also have a…
Jake Wilson
  • 88,616
  • 93
  • 252
  • 370
12
votes
4 answers

Does allowing a category to have multiple parents make sense? Are there alternatives?

Short question: How should product categories that appear under multiple categories be managed? Is it a bad practice to do so at all? Background info: We have a product database with categories likes this: Products -Arts and Crafts Supplies …
Cory House
  • 14,235
  • 13
  • 70
  • 87
11
votes
2 answers

Are nested intervals a viable solution to nested set (modified pre-order traversal) RDBMS performance degredation?

Among the known limitations of Joe Celko's nested sets (modified pre-order traversal) is marked degredation in performance as the tree grows to a large size. Vadim Tropashko proposed nested intervals, and provides examples and theory explanation in…
None
11
votes
5 answers

How to get structed result using nested set in MySQL and PHP?

There is no limitation on the depth. How to get the structured branch or even entire tree? The definition is from here: Managing Hierarchical Data in MySQL
user198729
  • 61,774
  • 108
  • 250
  • 348
9
votes
8 answers

Getting nested set model into a

Based on Getting a modified preorder tree traversal model (nested set) into a
    One of answers gave right code to display full tree. What i need is to always show first level (depth=0) and siblings+childrens for active list item. Goal is to…
Māris Kiseļovs
  • 16,957
  • 5
  • 41
  • 48
9
votes
3 answers

Mysql: Optimizing finding super node in nested set tree

I have hierarchical data in a nested set model (table:projects): My table (projects): id, lft, rgt 1, 1, 6 2, 2, 3 3, 4, 5 4, 7, 10 5, 8, 9 6, 11, 12 7, 13, 14 ... Pretty printed: 1 2 3 4 5 6 7 To find the nearest super node of node 3…
Joernsn
  • 2,319
  • 4
  • 25
  • 33
9
votes
3 answers

Improving scalability of the modified preorder tree traversal algorithm

I've been thinking about the modified preorder tree traversal algorithm for storing trees within a flat table (such as SQL). One property I dislike about the standard approach is that to insert a node you have to touch (on average) N/2 of the nodes…
Mark Renouf
  • 30,697
  • 19
  • 94
  • 123
8
votes
1 answer

Hierarchy commenting system php

i want to do discus/reddit/ like commenting system, i have an "id_answer" (set to 0 by defaut) field in my comment database and when user answer to another comment this field is the "id" of the parent comment. I have the comments of the thread in an…
Tahola
  • 1,040
  • 3
  • 19
  • 38
8
votes
3 answers

get all products of category and child categories (rails, awesome_nested_set)

having an e-commerce application under development i am trying to get my head around the following problem: I have my categories realized through the awesome_nested_set plugin. If I list my articles through selecting one category everything works…
tmaximini
  • 8,403
  • 6
  • 47
  • 69
1
2 3
…
26 27