Adjacency lists employ a parentID, so every node knows who it's parent
is, but that's it. Nested sets use a set of numbers (starting at
'left' and ending at 'right', typically) for each node, and the
relationships between the sets dictate hierarchy.
Adjacency list are simple and fast for tree manipulation, but
extracting data can be cumbersome. There also isn't any way to order
the children of a given node.
Nested sets, on the other hand, are more complex to work with, and
slower for tree manipulation. However, they are both very fast and
very simple to make complex queries against, once you understand how
they work. Nested sets also have implicit ordering of ALL nodes, both
hierarchially, and within a given level of the hierarchy. So with a
nested set you can swap two children of a node, and the tree structure
itself will remember that, without the need for a separate ordering
key.
For example, with your "ancestors" query, using adjacency list, you
have to find the node's parent, if it's not null, find it's parent,
etc., repeating until you reach a node that has a null parent (the
root). With a nested set, you do this:
SELECT id, name
FROM myTable
WHERE left < (
SELECT left
FROM myTable
WHERE id = #nodeId#
)
AND right > (
SELECT right
FROM myTable
WHERE id = #nodeId#
)
ORDER BY left
That'll return a recordset that contains all the ancestors of the
given node. Change the < and > to <= and >= and you'll get the node
itself, and all it's ancestors. Reverse the < and > and you'll get
decendants of the node. Etc.
>From what you describe, nested sets is probably better for your
scenario. You have a relatively static tree hierarchy (compared to
the amount of recall), and the recall you need is very tree-centric.
Consequently you'll probably find things easier with nested sets than
with an adjacency list, and you might get a performance boost out of
it as well.
cheers,
barneyb
On 2/1/06, Mike Little <[EMAIL PROTECTED]> wrote:
> >I'm not sure what you wish to do with this level count, but be careful
> >if you plan on storing it in the original table. The level count is
> >already stored inherently in the table through its structure
>
> brad, are you saying that i could do without the level column and rely
> instead on the query to determine which level each category is on? the reason
> i wanted this column was so that i could create breadcrumbs with a simple
> query.
>
> also, from the other posts (thanks heaps by the way) is it not necessary to
> utilise a parent_id column using nested sets?
>
> my client wishes to be able to move categories to any other category and also
> reorder a category within a particular level, so you can imagine i am all
> twisted about on this at the moment.
>
> mike
--
Barney Boisvert
[EMAIL PROTECTED]
360.319.6145
http://www.barneyb.com/
Got Gmail? I have 100 invites.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
Message: http://www.houseoffusion.com/lists.cfm/link=i:4:231017
Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4
Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4
Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=89.70.4
Donations & Support: http://www.houseoffusion.com/tiny.cfm/54
