🛳️ 😣 👩🏾‍🔬 पुनरावर्तन के बिना एक नेस्टेड सेट ट्री बनाएं 👨🏼‍🎤 🏒 📥

डेटाबेस में पेड़ों को तीन मुख्य तरीकों से संग्रहीत किया जा सकता है: आसन्न सूची, Matherialized Path & Nested Set। जब हम AL से NS में जाना चाहते हैं, तो इसे रिकर्सन (यदि डेटाबेस नस्लीय रूप से सही है) का उपयोग करके किया जा सकता है। लेकिन MySQL के मामले में क्या करना है?

डेटाबेस में पेड़ों को संग्रहीत करने के तरीकों का एक संक्षिप्त अवलोकन

संक्षेप में, तब:

AL - जब हमारे माता-पिता को parent_id के एक कॉलम में संग्रहीत किया जाता है: '' 1 ''
एमपी - तत्व का पूरा रास्ता टाइप पथ के एक कॉलम में संग्रहीत है: '' 1.2.5 ''
NS ^{[ 2 , 3 ]} - एक जोड़ी lft और rgt कॉलम जो सभी नेस्टेड तत्वों की श्रेणी को संग्रहीत करते हैं, उदाहरण के लिए, 9 तत्वों के पेड़ की जड़ में '' 1 '' का बायां मान होगा और '18' '' के दाईं ओर।

अधिक जानकारी के लिए, कॉमरेड देखें मिखुस ^{[ १ ]} । एक अन्य क्लोजर टेबल विधि भी है, जैसा कि कॉमरेड द्वारा इंगित किया गया है। resurection , लेकिन हम इसे अब तक की प्रवृत्ति में रिकॉर्ड नहीं करेंगे।

MySQL और पुनरावर्तन

MySQL के मामले में, हमारे पास पुनरावृत्ति है, लेकिन केवल संग्रहीत प्रक्रियाओं के स्तर पर और फिर भी 255 के स्तर तक । हम प्रोग्रामिंग भाषा + डेटाबेस के एक समूह में भी पुनरावृत्ति का उपयोग कर सकते हैं, लेकिन यहां प्रश्नों की संख्या अद्भुत हो सकती है। डेटाबेस में सब कुछ करना बेहतर है।

Googling, हम सीखते हैं कि किसी भी पुनरावर्ती समस्या को जन्म चिन्ह ^{[ 4 ] के} बिना हल किया जा सकता है। इसी तरह का सवाल पूछे जाने पर, हम कोशिश कर सकते हैं और ... हम सफल होंगे! नीचे हम आपके ध्यान में पेश करते हैं समारोह rebuild_nested_set_tree, जो माता-पिता को जानते हुए भी चूक और rgt भरता है।

पुनरावृत्ति के बिना ट्री फिल फंक्शन

सादगी के लिए, कल्पना करें कि हमारे पास प्लेट में केवल एक पेड़ है और इसमें 8 तत्व हैं। फ़ंक्शन को इनपुट पर कुछ भी प्राप्त नहीं होगा। स्वाभाविक रूप से, उत्पादन संस्करण में, हमें पेड़ों के कुछ आईडी कोने प्राप्त होंगे, जिन्हें हम तर्क में ध्यान में रखेंगे। नीचे हम केवल अंतरिक्ष को बचाने के लिए फ़ंक्शन का शरीर देते हैं, और SQLFiddle पर पूर्ण पाठ और प्रश्नों को देखते हैं (इस सेवा को खोलने के लिए कॉमरेड ग्रुकरू के लिए धन्यवाद)।

फंक्शन बॉडी सोर्स rebuild_nested_set_tree

--      NULL UPDATE tree t SET lft = NULL, rgt = NULL; --     SET @i := 0; UPDATE tree t SET lft = (@i := @i + 1), rgt = (@i := @i + 1) WHERE t.parent_id IS NULL; forever: LOOP --       --     SET @parent_id := NULL; SELECT t.id, t.rgt FROM tree t, tree tc WHERE t.id = tc.parent_id AND tc.lft IS NULL AND t.rgt IS NOT NULL ORDER BY t.rgt LIMIT 1 INTO @parent_id, @parent_right; --   ,        IF @parent_id IS NULL THEN LEAVE forever; END IF; --      SET @current_left := @parent_right; --       SELECT @current_left + COUNT(*) * 2 FROM tree WHERE parent_id = @parent_id INTO @parent_right; --     SET @current_length := @parent_right - @current_left; --     ,   UPDATE tree t SET rgt = rgt + @current_length WHERE rgt >= @current_left ORDER BY rgt; --     ,   UPDATE tree t SET lft = lft + @current_length WHERE lft > @current_left ORDER BY lft; --        SET @i := (@current_left - 1); UPDATE tree t SET lft = (@i := @i + 1), rgt = (@i := @i + 1) WHERE parent_id = @parent_id ORDER BY id; END LOOP; --         RETURN (SELECT MAX(rgt) FROM tree t);

हम यहां क्या कर रहे हैं?

सामान्य तौर पर, हम भरे हुए सीमाओं और अपूर्ण बच्चों के साथ सबसे ऊपरी ऊपरी तत्व को पाते हैं, अपने बच्चों की संख्या की गणना करते हैं, उन तत्वों की सीमाओं को अपडेट करते हैं जो हमारे दाईं ओर हैं और फिर उनके बच्चों की सीमाओं को अपडेट करते हैं। यह सब एक अनंत लूप में पुनरावृत्ति के बिना किया जाता है जब तक हम बिना सीमाओं के तत्वों से बाहर नहीं निकलते।

एक सरल प्रस्तुति हमें इस प्रक्रिया की कल्पना करने में मदद करेगी:

संदर्भ

10 दिसंबर, 2008 को मिखुस द्वारा पदानुक्रमित डेटा संरचनाएं और सिद्धांत , मुख्य विधियों में से प्रत्येक के उपकरणों को अच्छी तरह से वर्णित किया गया है
इंटेलीजेंट एंटरप्राइज में अक्टूबर 20, 2000 (अंग्रेजी) में जो सेल्को द्वारा एसक्यूएल में पेड़ - आसन्न सूची की तुलना में नेस्टेड सेट क्या है और दूसरे से पहली में कैसे परिवर्तित किया जाए (जो सेल्को - शब्द नेस्ट सेट के पिता)
Gijs Van Tulder द्वारा एक डेटाबेस में पदानुक्रमिक डेटा संग्रहीत करना, साइटपॉइंट.कॉम पर, 30 अप्रैल, 2003 (अंग्रेजी) - "बाएँ" और "दाएँ" अनुक्रमित, साथ ही साथ विभिन्न दृष्टिकोणों के साथ काम करने की बारीकियों का वर्णन करने के तर्क का वर्णन करने के लिए चित्र।
किसी भी पुनरावर्ती एल्गोरिदम को पुनरावृति एल्गोरिथ्म के रूप में फिर से लिखा जा सकता है ... समुदाय wiki & Kristopher Johnson द्वारा, stackoverflow.com पर, 11 दिसंबर, 2009 (अंग्रेजी) - किसी भी पुनरावर्ती एल्गोरिदम को स्टैक के साथ पुनरावृत्त में परिवर्तित किया जा सकता है।
फंक्शन के स्रोत garex द्वारा rebuild_nested_set_tree , sqlfiddle.com पर, 25 नवंबर, 2012 - एक पेड़ के साथ एक टेबल बनाना, इसे टेस्ट डेटा के साथ भरना और आगे बढ़ने के लिए एक फंक्शन बनाना।
बिना किसी पुनरावृत्ति के सेट किया गया दृश्य: गैरेक्स द्वारा विज़ुअलाइज़ेशन , स्लाइडशेयर.नेट पर, 25 नवंबर, 2012 - एक चक्र में एल्गोरिथ्म का दृश्य

बदलाव का

एक और विधि का जोड़ा - क्लोजर टेबल
प्रारंभिक डेटा में, टाइपो को ठीक किया जाता है ("फ्लश" "ट्राउजर्स" के तहत होना चाहिए)
मिनट होने के साथ विकृति समारोह के शरीर से हटा दिया गया था और सीमा 1 के साथ एक पर्याप्त क्रम के साथ बदल दिया गया था (लेकिन फ़ंक्शन अभी भी सही ढंग से काम किया है, क्योंकि यह सभी सही तत्वों को स्थानांतरित कर दिया है - मैं पहले से ही बाद में आश्चर्यचकित था)