एक नोस्कल डेटाबेस में पेड़ संरचना

Question

मैं Google App Engine के लिए एक एप्लिकेशन विकसित कर रहा हूं जो इसके डेटास्टोर के लिए बिगटेबल का उपयोग करता है।

यह एक कहानी को सहयोगी रूप से लिखने के बारे में एक आवेदन है। यह एक बहुत ही सरल शौक परियोजना है कि मैं सिर्फ मस्ती के लिए काम कर रहा हूं। यह खुला स्रोत है और आप इसे यहां देख सकते हैं: http://story.multifarce.com/

विचार यह है कि कोई भी अनुच्छेद लिख सकता है, जिसे दो अन्य लोगों द्वारा सत्यापित किया जाना चाहिए। किसी भी अनुच्छेद पर एक कहानी भी ब्रांच की जा सकती है, ताकि कहानी का एक और संस्करण दूसरी दिशा में जारी रहे।

निम्नलिखित वृक्ष संरचना की कल्पना कीजिए:

हर नंबर एक पैराग्राफ होगा। मैं हर अनूठी कहानी रेखा में सभी पैराग्राफ चुनने में सक्षम होना चाहता हूं। असल में, उन अद्वितीय कहानी रेखाएं हैं (2, 7, 2); (2, 7, 6, 5); (2, 7, 6, 11) और (2, 5, 9, 4)। अनदेखा करें कि नोड "2" दो बार प्रकट होता है, मैंने अभी विकिपीडिया से पेड़ संरचना आरेख लिया है।

मैं भी एक प्रस्तावित समाधान का एक चित्र बनाया: https://docs.google.com/drawings/edit?id=1fdUISIjGVBvIKMSCjtE4xFNZxiE08AoqvJSLQbxN6pc&hl=en

मैं कैसे निर्धारित कर सकते हैं एक संरचना प्रदर्शन कुशल दोनों लिखने के लिए, लेकिन सबसे महत्वपूर्ण पढ़ने के लिए है?

Answer 1

डेटाबेस में पेड़ का प्रतिनिधित्व करने के लिए कई प्रसिद्ध तरीके; उनमें से प्रत्येक के पास उनके पेशेवर और विपक्ष हैं। यहां सबसे आम हैं:

• Adjacency list, जहां प्रत्येक नोड अपने माता-पिता की आईडी संग्रहीत करता है।
• Materialized path, जो कि रणनीति कुंजीर वर्णन करता है। यह ऐप इंजन में इकाई समूहों (जैसे, मूल संस्थाओं) द्वारा उपयोग किया जाने वाला दृष्टिकोण भी है। यह आपके अपडेट में जो भी वर्णन कर रहा है वह उतना ही कम है।
• Nested sets, जहां प्रत्येक नोड में 'बाएं' और 'दाएं' आईडी हैं, जैसे कि सभी बाल नोड्स उस सीमा में निहित हैं।
• जड़ आईडी के साथ जमा होने वाली एडजैकेंसी सूचियां।

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

भौतिक मार्ग लागू करने के लिए आसान हैं और अद्यतन करने के लिए सस्ते हैं, और मनमाने ढंग से उप-क्वेरी पूछताछ की अनुमति देते हैं, लेकिन गहरे पेड़ के लिए बढ़ते ओवरहेड लगाते हैं।

नेस्टेड सेट लागू करने के लिए कठिन हैं, और प्रत्येक बार जब आप प्रविष्टि करते हैं, तो औसतन आधे नोड अपडेट करने की आवश्यकता होती है। बढ़ते कुंजी लंबाई के मुद्दे के भौतिक मार्ग के बिना, वे आपको मनमाने ढंग से उप-प्रश्न पूछने की अनुमति देते हैं।

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

Answer 2

एक समाधान जो मैं सोच सकता हूं - नोड का मार्ग भी उस नोड की कुंजी है। तो नोड 11 की कुंजी "2/7/6/11" है। आप पथ में सभी चाबियों के एक साधारण कुंजी लुकअप द्वारा पथ को पार कर सकते हैं - "2/7/6/11", "2/7/6", "2/7", "2"