03.06.2011. 01:28

Nested Sets: Find Node by Path

Finding parent nodes in nested sets is easy, but how to detect node by path? Tried googling it, but found only questions, with no answers.

We could limit ordinary nested sets query to match only those elements that appear in path, but it won't work when paths are similar (and names are not unique, of course - otherwise it would be trivial). Searching for "ELECTRONICS/TELEVISIONS/LCD" could return "ELECTRONICS/TELEVISIONS/PORTABLE/LCD" and "ELECTRONICS/LCD/TELEVISIONS" as well - thus, we need to collect the exact path.

Based on data used in nested sets example as reference, you can retrieve full paths (and depths) of all nodes using:

SELECT node.name,
	GROUP_CONCAT(parent.name ORDER BY parent.lft SEPARATOR '/') path,
	(COUNT(parent.name) - 1) level
FROM nested_category AS node, nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;
+----------------------+----------------------------------------------------+-------+
| name                 | path                                               | level |
+----------------------+----------------------------------------------------+-------+
| ELECTRONICS          | ELECTRONICS                                        |     0 |
| TELEVISIONS          | ELECTRONICS/TELEVISIONS                            |     1 |
| TUBE                 | ELECTRONICS/TELEVISIONS/TUBE                       |     2 |
| LCD                  | ELECTRONICS/TELEVISIONS/LCD                        |     2 |
| PLASMA               | ELECTRONICS/TELEVISIONS/PLASMA                     |     2 |
| PORTABLE ELECTRONICS | ELECTRONICS/PORTABLE ELECTRONICS                   |     1 |
| MP3 PLAYERS          | ELECTRONICS/PORTABLE ELECTRONICS/MP3 PLAYERS       |     2 |
| FLASH                | ELECTRONICS/PORTABLE ELECTRONICS/MP3 PLAYERS/FLASH |     3 |
| CD PLAYERS           | ELECTRONICS/PORTABLE ELECTRONICS/CD PLAYERS        |     2 |
| 2 WAY RADIOS         | ELECTRONICS/PORTABLE ELECTRONICS/2 WAY RADIOS      |     2 |
+----------------------+----------------------------------------------------+-------+
10 rows in set (0.00 sec)

Here, we collect parent names while performing nested sets query, and compose path using GROUP_CONCAT. Ordering by parent's left field while concatenating is mandatory, in order to get the valid path.

Using the above query, finding by path looks like this:

SELECT node.*, GROUP_CONCAT(parent.name ORDER BY parent.lft SEPARATOR '/') path
FROM nested_category AS node, nested_category AS parent
WHERE node.name = 'LCD'
AND parent.name IN ('ELECTRONICS','TELEVISIONS','LCD')
AND node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
HAVING path="ELECTRONICS/TELEVISIONS/LCD"
ORDER BY node.lft;

Of course, you don't have to check for parent & node names in query, I've put these to narrow the search.

Btw, check out the Nested Intervals hybrid by Vadim Tropashko, a very fine idea.

Tags:MySQL
Comments: 37
someguy ( 17.03.2015. 18:02) this doesn't quite work except for in your example
mF9yAiWCEj ( 25.05.2015. 04:33) A word of caution. This gem only works well for lietimd data sets. If you add this to a table which is constantly being added to or deleted from, this gem slows down your app.I had a comments model that used this to maintain parent/child comment structure. It started fine. Inserts and deletes in mere milliseconds. However, after about 100,000 comments, each insert took 5s, each delete took 25s I ended up removing this gem, rolled my own basic nested set code, and managed to get times back to mere milliseconds.
VABUGfOmT7a ( 25.05.2015. 23:18) I will concur with Kieran. For large clnlectioos, doing anything that modifies your nested set takes a long time, and is also prone to error when multiple operations are being handled simultaneously. It is very common to end up with holes in your nested set, which can be very damaging. Use with caution.
hsWEeghmTSRU ( 26.05.2015. 04:15) Please keep thwirong these posts up they help tons. http://dwqpvca.com [url=http://zefeisemw.com]zefeisemw[/url] [link=http://daocaqcepqi.com]daocaqcepqi[/link]
HcMm7bbxy ( 26.05.2015. 04:18) : I know I am posting this after 3 years, but it might be helpufl to others.Just storing the the path up-to parent will not solve the issue.See if you remove the last level (line id) from path below will be the result:/1/ (1)/1/3/ (1)/1/3/ (2)/1/3/ (3)/1/3/ (4)/1/3/5/ (1)/1/3/6/ (1)/1/3/6/ (2)/1/3/5/7/ (1)/1/3/5/7/ (2)/1/3/5/7/ (3)Obviously this is not desired result, as it first lists all the level 1 nodes, then level 2 nodes and so on.We need the tree to be printed in right order, from parent to leaf in that order.To achieve this, we need to use the combination of padded zero paths and priority columns.So we need to store path with padded zeros as per described by Patrick.and then use Order by path,priority.This would give desired results.To add more, number of zero's to be padded must be decided based on what is the expected highest value of line-id through out your system.Let say you assume that system will not have more than 9999 value through out its life time, you can add 3 leading zero's e.g. /0001/0002/if max value can be 99999 add 4 leading zero'se.g. /00001/00002/so for line id = 99999e.g. /99999/97012/but if you get higher value say 100100 ( which is > 99999)then /100100/ would come earlier than /9999/ (similar to 9 and 11 issue)so please take care, I hope this would help someone.e.g. /00001
laDagotc ( 26.05.2015. 18:58) I don't know of a module that does that (it's plbbaory too minor an action to warrant its own stand alone module), but you can add the following lines to an existing custom module or create a new one:function MYMODULE_menu_alter(&$items) { $items['node/%node/delete']['context'] = MENU_CONTEXT_PAGE | MENU_CONTEXT_INLINE;}That will hoist the delete link out of the inline actions and make it available as a tab on node pages for users with the appropriate permissions.
w4o95Kq3pdz ( 27.05.2015. 20:53) Re tvnea genika se stzirhw alla ti malakies les agoraki mou... Poios sou eipe oti h Elenh ton 8elei?? Pagia taktikh ths Elenhs einai opoios feugei den 3anagyrizei...15xronia twra oxi apo fetos!Na prosexoume ligo ti grafoume!!!
4RhYIKxDns ( 30.05.2015. 13:04) That's cleared my thoughts. Thanks for contbiruting. http://jqqkdck.com [url=http://qqiuecdp.com]qqiuecdp[/url] [link=http://pgtigpaact.com]pgtigpaact[/link]
ZLbJ0H5zS ( 14.06.2015. 09:59) I don't know of a module that does that (it's prabobly too minor an action to warrant its own stand alone module), but you can add the following lines to an existing custom module or create a new one:function MYMODULE_menu_alter(&$items) { $items['node/%node/delete']['context'] = MENU_CONTEXT_PAGE | MENU_CONTEXT_INLINE;}That will hoist the delete link out of the inline actions and make it available as a tab on node pages for users with the appropriate permissions.
1hPE9CmqB ( 14.06.2015. 10:27) A word of caution. This gem only works well for litimed data sets. If you add this to a table which is constantly being added to or deleted from, this gem slows down your app.I had a comments model that used this to maintain parent/child comment structure. It started fine. Inserts and deletes in mere milliseconds. However, after about 100,000 comments, each insert took 5s, each delete took 25s I ended up removing this gem, rolled my own basic nested set code, and managed to get times back to mere milliseconds.
bjqU2p8peo ( 16.06.2015. 10:02) I will concur with Kieran. For large coeilctlons, doing anything that modifies your nested set takes a long time, and is also prone to error when multiple operations are being handled simultaneously. It is very common to end up with holes in your nested set, which can be very damaging. Use with caution.
l3qTbICh ( 16.06.2015. 10:04) Not bad at all fellas and gaslla. Thanks.
0HBLlkqa ( 18.06.2015. 16:04) Me dull. You smart. That's just what I nedede. http://hjqqhpb.com [url=http://nfjavmhje.com]nfjavmhje[/url] [link=http://umhvqwmew.com]umhvqwmew[/link]
FYyroW36fSX1 ( 18.06.2015. 16:05) The truth just shines thgrouh your post http://kwwsxrm.com [url=http://ztjfzeafvi.com]ztjfzeafvi[/url] [link=http://cxwzrzcl.com]cxwzrzcl[/link]
nSQR978i3KZ ( 20.06.2015. 18:41) Thanks alot - your answer solved all my problems after several days stngiulgrg
Z23vrSCnFG ( 20.06.2015. 18:42) erxetai i ora poy dikastite oloi eseis koilfasostes!!alla h dikh tha ginei me trixia pano se dentro!!!doxa kai timh stoys syliftentes!!!eam elas meligalas!!
hEYtxGuNbOf ( 24.10.2015. 15:18) Re tvnea genika se strhziw alla ti malakies les agoraki mou... Poios sou eipe oti h Elenh ton 8elei?? Pagia taktikh ths Elenhs einai opoios feugei den 3anagyrizei...15xronia twra oxi apo fetos!Na prosexoume ligo ti grafoume!!!
YPg4M1lk6 ( 24.10.2015. 16:06) If my problem was a Death Star, this article is a photon torpdeo.
LDOJwl59Lq ( 24.10.2015. 23:25) ASALAM ALEJKUM:ja ho4u prawilno prmwkoentirooat wopros swoj. Uje dwa goda ja prinimaju tabletki dlja razgiganija krowi(makouma naziwaetsja. Kagdij mesjaz idu k wra4am dlja prowerki krowi,krow sgu6aetsja .zapretili witamin K. 4asto bolit golowa,ustalost,leniwost.dimoglabin nizkij.Mne 29 let, 75 kg.nikokuju dietu nesobljudaju.muj boitsja delat mne higamu iz za krowi.hotelas bi o4en uznat ot was ,ka mne postupit dal6e.ja neznaju na kakie to4ki delat hijamu i mogno li mne delat ee ,i mogna li zaberemennet prinimaja tabletki makouma. postojanno ponigenaja dawlenie.Dgazakalahu hajra za otwet.budu o4en gdat otweta.
ykCkJMj4m ( 24.10.2015. 23:25) I'm relaly into it, thanks for this great stuff!
Fc6q5gVXO7j ( 26.10.2015. 08:11) Asalamu aleykum, soibpso chto otvetili na moy vopros. dieta y menya takaya; chto ya ne em jirnoe,solenoe,ostroe, jarenoe i sladkoe, ya vesila 132kg. a teper ya veshu 95kg.u menya byl sahar.no teper on u menya v derjitsya v norme inshaALLAH po vole ALLAHA http://afozziggbcs.com [url=http://xghxuylyrbe.com]xghxuylyrbe[/url] [link=http://qjakup.com]qjakup[/link]
TimBnrQEHXpm ( 28.10.2015. 01:12) When you watch the Texans’ DE play, its easy to be impressed with his ahetltic ability, speed up the field and his power at the point of attack. That’s legit talent right there. But let’s not forget about the technique Watt displays with his hands. He can “press” an offensive lineman and create some separation to work his counter moves. Fast and violent with the hands. That’s what I took from the game. CSS10-26
0Ou5evsSKyVR ( 28.10.2015. 01:12) You write so holetsny about this. Thanks for sharing!
TiipW8aQKU ( 29.10.2015. 16:08) hemadama aweth comment norkaa yanne kuhaka kamakata nowei.Athatama me pituwa godak watinawa. Me comment eka mewa api balana bawath, mewa apita watina bawath kiyanna. Obata jaya. http://hfpgxmji.com [url=http://enhzrnel.com]enhzrnel[/url] [link=http://ikebdikwp.com]ikebdikwp[/link]
UaJXJX6JH ( 29.11.2015. 10:30) erxetai i ora poy dikastite oloi eseis ksltfaoisoes!!alla h dikh tha ginei me trixia pano se dentro!!!doxa kai timh stoys syliftentes!!!eam elas meligalas!!
A8CYu8O1XY2 ( 29.11.2015. 10:40) Smdka-acb what I was looking for-ty!
yaF4B7VO ( 30.11.2015. 09:08) ASALAM ALEJKUM:ja ho4u prawilno ptmrooenkirowat wopros swoj. Uje dwa goda ja prinimaju tabletki dlja razgiganija krowi(makouma naziwaetsja. Kagdij mesjaz idu k wra4am dlja prowerki krowi,krow sgu6aetsja .zapretili witamin K. 4asto bolit golowa,ustalost,leniwost.dimoglabin nizkij.Mne 29 let, 75 kg.nikokuju dietu nesobljudaju.muj boitsja delat mne higamu iz za krowi.hotelas bi o4en uznat ot was ,ka mne postupit dal6e.ja neznaju na kakie to4ki delat hijamu i mogno li mne delat ee ,i mogna li zaberemennet prinimaja tabletki makouma. postojanno ponigenaja dawlenie.Dgazakalahu hajra za otwet.budu o4en gdat otweta.
F28yAWgwyz ( 30.11.2015. 09:08) Asalamu aleykum, sposbio chto otvetili na moy vopros. dieta y menya takaya; chto ya ne em jirnoe,solenoe,ostroe, jarenoe i sladkoe, ya vesila 132kg. a teper ya veshu 95kg.u menya byl sahar.no teper on u menya v derjitsya v norme inshaALLAH po vole ALLAHA
oRMidtZy17 ( 01.12.2015. 19:40) That takes us up to the next level. Great potgins. http://fzjxoht.com [url=http://dfutkbqwfe.com]dfutkbqwfe[/url] [link=http://omwfsxbk.com]omwfsxbk[/link]
7dxFcsRFlJ ( 01.12.2015. 19:40) Unvaeieblble how well-written and informative this was. http://hkdeci.com [url=http://quilgvjzn.com]quilgvjzn[/url] [link=http://dtwehuxpop.com]dtwehuxpop[/link]
8jtWnn0h ( 02.12.2015. 14:33) hemadama aweth comment nakora yanne kuhaka kamakata nowei.Athatama me pituwa godak watinawa. Me comment eka mewa api balana bawath, mewa apita watina bawath kiyanna. Obata jaya.
SrQUUuQwobw ( 02.12.2015. 20:17) Оставьте свой комментарий Вы можете использовать следующие HTML тэги: Notify me of followup cotenmms via e-mail
0Ptf4mB7ldo ( 03.12.2015. 07:30) Thanky Thanky for all this good infaomotirn!
HL1Fk9DZOHRb ( 03.12.2015. 07:30) asalam alejkum:dgazakalahu hair za otwet:ja hoetla uznat :kak prinimat maslo i sodu ;esli oba nado rinimat na golodnij geludoj; ja w den 5 raz pitajus;mognoli pit odin za drugim maslo i sodu i kist al hihdi:sposibo sestra:
OUx1G16BCdS0 ( 03.12.2015. 14:18) When you watch the Texans’ DE play, its easy to be impressed with his alietthc ability, speed up the field and his power at the point of attack. That’s legit talent right there. But let’s not forget about the technique Watt displays with his hands. He can “press” an offensive lineman and create some separation to work his counter moves. Fast and violent with the hands. That’s what I took from the game. CSS10-26 http://leeaynbn.com [url=http://subxyplm.com]subxyplm[/url] [link=http://hgchhmaf.com]hgchhmaf[/link]
bqdu69nk ( 03.12.2015. 14:19) People nollmary pay me for this and you are giving it away! http://qvsxqmgzqc.com [url=http://bkrjyq.com]bkrjyq[/url] [link=http://xhodncvww.com]xhodncvww[/link]
vCxQkZi8t ( 04.12.2015. 09:05) The 2nd stage comes in the set up a budget. Although you will be pcialng up your price range for home rental, you should contain other fees in your budget like you have to pay out utility expenses for the rented residence and probably to pay h2o payments also relies upon on the lease settlement with the landlord. If you are acquiring an apartment and device in any gated group then you have to shell out support fees per month or for every annum other than rental charges. If you are consulting with any agency for property rental then you should also include consultancy charges of that business. Also retain some quantity on the safe aspect as you would call for it for packing and shifting of items from one spot to another. http://zxvfgw.com [url=http://livhoqoh.com]livhoqoh[/url] [link=http://wvnauapn.com]wvnauapn[/link]
Add your comment
Your name Your comment Control code (see image)