आप नेस्टेड सेट मॉडल का उपयोग करके संग्रहीत पेड़ को कैसे क्रमबद्ध करते हैं?

When I refer to nested set model I mean what is described here.

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

root
    finances
        budgeting
            fy08
    projects
        research
        fabrication
        release
    trash

मैं चाहता हूं कि इसे सॉर्ट किया जाए ताकि यह इस प्रकार प्रदर्शित हो सके:

root
    finances
        budgeting
            fy08
    projects
        fabrication
        release
        research
    trash

ध्यान दें कि शोध से पहले निर्माण प्रकट होता है।

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

भले ही, मैं यह पता लगाने में सक्षम था कि कैसे (नेस्टेड सेट मॉडल का उपयोग करना):

  1. एसक्यूएल में एक नया पेड़ शुरू करें
  2. पेड़ में किसी अन्य नोड के बच्चे के रूप में नोड डालें
  3. पेड़ में एक भाई नोड के बाद नोड डालें
  4. पूरे पेड़ को पदानुक्रम संरचना के साथ SQL
  5. से खींचें
  6. पदानुक्रम में गहराई सीमा के साथ या बिना किसी विशिष्ट नोड (रूट सहित) से एक उपट्री खींचें
  7. पेड़ में किसी भी नोड के माता-पिता को ढूंढें

तो मुझे लगा कि # 5 और # 6 का इस्तेमाल सॉर्टिंग करने के लिए किया जा सकता था, और इसका इस्तेमाल पेड़ को क्रमबद्ध क्रम में पुनर्निर्माण के लिए भी किया जा सकता था।

हालांकि, अब मैंने इन सभी चीजों को देखा है जो मैंने करना सीखा है, मुझे लगता है कि सॉर्ट किए गए आवेषण करने के लिए # 3, # 5, और # 6 का एक साथ उपयोग किया जा सकता है। अगर मैंने आवेषण को हल किया है तो इसे हमेशा हल किया जाए। हालांकि, अगर मैंने कभी भी प्रकार के मानदंडों को बदल दिया है या मैं एक अलग सॉर्ट ऑर्डर चाहता हूं तो मैं स्क्वायर वन पर वापस आऊंगा।

क्या यह सिर्फ नेस्टेड सेट मॉडल की सीमा हो सकती है? क्या इसका उपयोग आउटपुट की क्वेरी सॉर्टिंग में अवरुद्ध है?

17

8 उत्तर

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

उदाहरण के लिए, यदि आपका फ्रंटएंड एक फ्लेक्स ऐप है, और नोड के बच्चे आईसीओलेक्शन व्यू में संग्रहीत होते हैं, तो आप सॉर्ट प्रॉपर्टी का उपयोग अपने इच्छित तरीके से प्रदर्शित करने के लिए कर सकते हैं।

एक और उदाहरण, यदि आपका फ्रंटएंड एक PHP स्क्रिप्ट से कुछ आउटपुट है, तो आप प्रत्येक नोड के बच्चों को सरणी में रख सकते हैं और अपनी सॉर्टिंग करने के लिए PHP के सरणी सॉर्टिंग फ़ंक्शंस का उपयोग कर सकते हैं।

बेशक, यह केवल तभी काम करता है जब आपको सॉर्ट करने के लिए वास्तविक डीबी प्रविष्टियों की आवश्यकता नहीं है, लेकिन क्या आप?

4
जोड़ा

मुझे लगता है कि यह वास्तव में नेस्टेड सेट मॉडल की एक सीमा है। आप बच्चे के नोड्स को अपने संबंधित माता-पिता नोड के भीतर आसानी से सॉर्ट नहीं कर सकते हैं, क्योंकि पेड़ संरचना के पुनर्निर्माण के लिए परिणाम सेट का क्रम आवश्यक है।

मुझे लगता है कि नोड्स डालने, अपडेट करने या हटाने के दौरान पेड़ को क्रमबद्ध रखने के लिए शायद यह सबसे अच्छा तरीका है। यह प्रश्नों को बहुत तेज बनाता है, जो इस डेटा संरचना के मुख्य लक्ष्यों में से एक है। यदि आप सभी परिचालनों के लिए संग्रहीत प्रक्रियाओं को लागू करते हैं, तो इसका उपयोग करना बहुत आसान है।

आप एक पूर्व निर्धारित पेड़ के क्रम क्रम को भी उलट सकते हैं। आपको बस ऑर्डर द्वारा node.rgt डीईएससी के बजाय ऑर्डर द्वारा node.lft ASC का उपयोग करना होगा।

यदि आपको वास्तव में किसी अन्य प्रकार के मानदंडों का समर्थन करने की आवश्यकता है, तो आप प्रत्येक नोड में दूसरा lft और rgt अनुक्रमणिका जोड़कर इसे कार्यान्वित कर सकते हैं और इसे प्रत्येक मानदंड से क्रमबद्ध रखें सम्मिलित/अपडेट/हटा सकते हैं।

4
जोड़ा

मैंने अभी निम्नलिखित लिखना समाप्त कर दिया है जो पूरे घोंसले वाले सेट पेड़ को क्रमबद्ध करने में मेरे लिए काम करता है।

The sort (ideally) requires a view that lists the current level of each node in the tree and a procedure for swapping two nodes - both are included below, the sibling swap code comes from Joe Celkos ' Tree & Hierarchies' book which I strongly recommend to anyone using nested sets.

इस प्रकार को 'INSERT INTO @t' कथन में बदला जा सकता है, यहां यह 'नाम' पर एक साधारण अल्फान्यूमेरिक प्रकार है

यह विशेष रूप से सेट आधारित कोड के लिए कर्सर का उपयोग करने का एक खराब तरीका हो सकता है लेकिन जैसा कि मैंने कहा है कि यह मेरे लिए काम करता है, उम्मीद है कि इससे मदद मिलती है।

अद्यतन:

नीचे कोड अब क्यूसर का उपयोग किए बिना संस्करण दिखाता है। मैं लगभग 10x गति सुधार देखता हूं

CREATE VIEW dbo.tree_view

AS

SELECT t2.NodeID,t2.lft,t2.rgt ,t2.Name, COUNT(t1.NodeID) AS level  
FROM dbo.tree t1,dbo.tree t2
WHERE t2.lft BETWEEN t1.lft AND t1.rgt
GROUP BY t2.NodeID,t2.lft,t2.rgt,t2.Name

GO

----------------------------------------------

  DECLARE @CurrentNodeID int
DECLARE @CurrentActualOrder int
DECLARE @CurrentRequiredOrder int
DECLARE @DestinationNodeID int
DECLARE @i0 int
DECLARE @i1 int
DECLARE @i2 int
DECLARE @i3 int

DECLARE @t TABLE (TopLft int,NodeID int NOT NULL,lft int NOT NULL,rgt int NOT NULL,Name varchar(50),RequiredOrder int NOT NULL,ActualOrder int NOT NULL)


INSERT INTO @t (toplft,NodeID,lft,rgt,Name,RequiredOrder,ActualOrder)
    SELECT tv2.lft,tv1.NodeID,tv1.lft,tv1.rgt,tv1.Name,ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.ColumnToSort),ROW_NUMBER() OVER(PARTITION BY tv2.lft ORDER BY tv1.lft ASC)
    FROM dbo.tree_view tv1 
    LEFT OUTER JOIN dbo.tree_view tv2 ON tv1.lft > tv2.lft and tv1.lft < tv2.rgt and tv1.level = tv2.level+1
    WHERE tv2.rgt > tv2.lft+1

    DELETE FROM @t where ActualOrder = RequiredOrder


WHILE EXISTS(SELECT * FROM @t WHERE ActualOrder <> RequiredOrder)
BEGIN


    SELECT Top 1 @CurrentNodeID = NodeID,@CurrentActualOrder = ActualOrder,@CurrentRequiredOrder = RequiredOrder
    FROM @t 
    WHERE ActualOrder <> RequiredOrder
    ORDER BY toplft,requiredorder

    SELECT @DestinationNodeID = NodeID
    FROM @t WHERE ActualOrder = @CurrentRequiredOrder AND TopLft = (SELECT TopLft FROM @t WHERE NodeID = @CurrentNodeID) 

    SELECT @i0 = CASE WHEN c.lft < d.lft THEN c.lft ELSE d.lft END,
            @i1 =  CASE WHEN c.lft < d.lft THEN c.rgt ELSE d.rgt END,
            @i2 =  CASE WHEN c.lft < d.lft THEN d.lft ELSE c.lft END,
            @i3 =  CASE WHEN c.lft < d.lft THEN d.rgt ELSE c.rgt END
    FROM dbo.tree c
    CROSS JOIN dbo.tree d
    WHERE c.NodeID = @CurrentNodeID AND d.NodeID = @DestinationNodeID

    UPDATE dbo.tree
    SET lft = CASE  WHEN lft BETWEEN @i0 AND @i1 THEN @i3 + lft - @i1
                    WHEN lft BETWEEN @i2 AND @i3 THEN @i0 + lft - @i2
            ELSE @i0 + @i3 + lft - @i1 - @i2
            END,
        rgt = CASE  WHEN rgt BETWEEN @i0 AND @i1 THEN @i3 + rgt - @i1
                    WHEN rgt BETWEEN @i2 AND @i3 THEN @i0 + rgt - @i2
            ELSE @i0 + @i3 + rgt - @i1 - @i2
            END
    WHERE lft BETWEEN @i0 AND @i3 
    AND @i0 < @i1
    AND @i1 < @i2
    AND @i2 < @i3

    UPDATE @t SET actualorder = @CurrentRequiredOrder where NodeID = @CurrentNodeID
    UPDATE @t SET actualorder = @CurrentActualOrder where NodeID = @DestinationNodeID

    DELETE FROM @t where ActualOrder = RequiredOrder

END
2
जोड़ा
बहुत बढ़िया, यह वही है जो मैं खोज रहा हूं। यह हमारे घोंसले सेट पदानुक्रम के साथ सॉर्टिंग मुद्दे को पूरी तरह हल कर रहा था।
जोड़ा लेखक Hamman359, स्रोत

हां यह नेस्टेड सेट मॉडल की एक सीमा है, क्योंकि नेस्टेड सेट पदानुक्रम का प्री-ऑर्डर किया गया प्रतिनिधित्व है। यह प्री-ऑर्डरिंग कारण है कि यह पढ़ने के लिए बहुत तेज़ है। आपके द्वारा लिंक किए गए पृष्ठ पर वर्णित आसन्नता मॉडल, सबसे लचीला सॉर्टिंग और फ़िल्टरिंग प्रदान करता है लेकिन एक महत्वपूर्ण प्रदर्शन प्रभाव के साथ।

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

1
जोड़ा

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

1
जोड़ा
यही वह वास्तविक बिंदु है जिसे मैं बनाने की कोशिश कर रहा हूं (और मैं इसे बनाने के लिए -1 हिट ले जाऊंगा ;-)। यहां तक ​​कि जस्टिन का ठीक समाधान अभी भी एक लूप लूप का उपयोग करता है जो अभी भी कर्सर शब्द के बिना एक कर्सर है। इस सब की कुंजी शुरुआत में नेस्टेड सेट को सही क्रम में बनाना है। मैं कुछ लिंक पोस्ट कर सकता हूं कि इसे ठीक से कैसे किया जाए और पर्याप्त गति के साथ आप इसे किसी भी बदलाव पर आसानी से कर सकें, लेकिन शायद मैं कोड के बजाए सिर्फ एक यूआरएल पोस्ट करने के लिए विस्फोट कर दूंगा जैसा कि मैंने पहले ही किया है। ;-)
जोड़ा लेखक Jeff Moden, स्रोत

मेरा मानना ​​है कि, आपके मामले में, जहां नोड्स आप स्वैप करना चाहते हैं, उनके पास कोई वंशज नहीं है, आप आसानी से एलएफटी और आरजीटी मूल्यों को स्वैप कर सकते हैं। इस पेड़ पर विचार करें:

   A
/  \
B     C
    /\
    D   E

यह नेस्टेड सेट के इस समूह में बदल सकता है:

1 A 10 
2 B 3  
4 C 9
5 D 6
7 E 8

अब विचार करें कि आप डी और ई को स्वैप करना चाहते हैं। निम्नलिखित नेस्टेड सेट वैध हैं और डी और ई स्वैप किए गए हैं:

1 A 10
2 B 3 
4 C 9 
7 D 8
5 E 6 

सबट्री वाले नोड्स को स्वैप करना इस तरह से नहीं किया जा सकता है, बेशक, क्योंकि आपको बच्चों के एलएफटी और आरजीटी मूल्यों को भी अपडेट करना होगा।

0
जोड़ा

You can sort thier when you render. I explained rendering here How to render all records from a nested set into a real html tree

0
जोड़ा

See my simple solution from method of my class. $this->table->order is Nette framework code to get data from DB.

$tree = Array();
$parents = Array();
$nodes = $this->table->order('depth ASC, parent_id ASC, name ASC');
$i = 0;
$depth = 0;
$parent_id = 0;

foreach($nodes as $node) {
    if($depth < $node->depth || $parent_id < $node->parent_id) {
        $i = $parents["{$node->parent_id}"] + 1;
    }
    $tree[$i] = $node;
    $parents["{$node->id}"] = $i;
    $depth = $node->depth;
    $parent_id = $node->parent_id;
    $i += (($node->rgt - $node->lft - 1)/2) + 1;
}
ksort($tree);
0
जोड़ा