डिग्री एक रिलेशनल डेटाबेस में तेजी से पदानुक्रम की कुंजी है

होबे पर अपने पहले लेख के प्रकाशन के बाद, एक संबंधपरक डेटाबेस में पदानुक्रम के आयोजन के तरीकों में से एक के बारे में, मुझे अभी भी पूरा नहीं होने का एहसास है।
टिप्पणियों को देखते हुए, किसी व्यक्ति ने दूसरे के लिए प्रस्तावित विधि ली, पूछा कि "django-mttp" क्या पोस्टग्रेएसक्यूएल ट्री सपोर्ट के बारे में बात करने के लिए उपयुक्त नहीं है ...
उन सभी के लिए धन्यवाद, जो बिना सदस्यता के थे, लेकिन लेख में ही अराजक प्रस्तुति के कारण, मुझे लगता है कि मैं पाठक को यह नहीं बता सका कि मुझे क्या चाहिए। और "अगर मैंने कुछ तय किया है, तो मैं निश्चित रूप से इसे पीऊंगा" (ग)

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

पदानुक्रम संग्रहण विधियाँ

संबंधपरक डेटाबेस में सबसे आम पदानुक्रम कार्यान्वयन विधियों का विवरण और तुलना मिखाइल स्टैडनिक उर्फ ​​मिखुस द्वारा उत्कृष्ट लेखों में पाया जा सकता है:

पदानुक्रमित डेटा संरचनाएं और सिद्धांत
पदानुक्रमित डेटा संरचनाएं और प्रदर्शन

जो अभी तक पढ़ा नहीं है, लेकिन इस मुद्दे में दिलचस्पी है - मैं इसे सुझाता हूं। एक सुलभ प्रस्तुति और उदाहरणों के साथ एक समृद्ध पाठ मुझे सब कुछ (सभी को और अधिक, मैं निश्चित रूप से सफल नहीं हो सकता) को बचाने से बचाता हूं।

प्रविष्टि के लिए, मेरे विचार में, यह पहले से ही पर्याप्त है, इसलिए मैं मुद्दे के सार की ओर मुड़ता हूं।

वृक्ष का वर्णन

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


चित्र 1

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

टेबल - समूह
1. ID - चार
2. PARENT - चार - आईडी के लिए लिंक
...

तालिका - तत्व
1. ID - पूर्णांक
2. GROUP - चार - समूह तालिका में आईडी से लिंक करें
....

यह दृष्टिकोण काम करता है। अच्छा या बुरा, एक और सवाल। यह याद रखना चाहिए कि हमेशा पेशेवरों और विपक्ष हैं। इच्छित आवेदन के लिए, इस विधि ने मुझे अनुकूल बनाया।

कुछ विचार के बाद, मेरे साथ यह हुआ कि चरित्र के तार को पूर्णांक प्रकार की कुंजियों के साथ पूरी तरह से बदला जा सकता है (हां! यह तेजी से काम करेगा और कम जगह लेगा, और इसे लागू करना आसान है, और यह सिर्फ सुंदर दिखता है ...)। मुख्य बात गैर-अतिव्यापी नेस्टेड पर्वतमाला प्रदान करना है। क्यों नहीं?

इसके अलावा, हम केवल एक तालिका पर ध्यान केंद्रित करेंगे - पदानुक्रमित।

प्रारंभ में, मैंने पूरे पेड़ को एक बाइनरी सिस्टम में कोड के साथ चित्रित करने की कोशिश की। यह निकला। सार को समझने के बाद, मैंने प्रत्येक तत्व के लिए 3 स्तरों और 3 संभव बच्चों के साथ एक छोटा पेड़ आकर्षित किया। यह इस तरह दिखता था (प्रणाली, निश्चित रूप से, दशमलव):


Fig.2

यह निश्चित रूप से परिचित नहीं लग रहा है।
शीर्ष पर संख्या - तालिका के आकार को दिखाते हैं, सुविधा के लिए, बाईं ओर - स्तरों पर।
प्रत्येक नंबर एक तत्व आईडी (बोल्ड में) है।
एलिमेंट पर बच्चे नीचे और दाईं ओर अगले एलिमेंट तक समान स्तर पर हैं। उदाहरण के लिए, एक तत्व = 16 के लिए बच्चे 16<ID<(31+1) एक सीमा है

अंजीर में 2, पेड़ पहले से ही पूरी तरह से भरा हुआ है, ताकि यह स्पष्ट हो।

यहाँ एक और पारंपरिक दृश्य में लकड़ी का एक टुकड़ा है:


3 चित्र

इस आंकड़े में, आवधिकों को तुरंत पकड़ना अधिक कठिन है, और पेड़ अभी भी दिखाई नहीं दे रहा है। इसलिए, मैं बाईं ओर एक और कॉलम पर हस्ताक्षर करूंगा, जो हमें आगे मदद करेगा, और पेड़ को और अधिक "मूल" रूप में दिखाएगा:


चित्र 4

आश्रितों को नोटिस करना बहुत आसान है।

किसी भी तत्व में - 4 की एक डिग्री है, वह है ( + 1) ।
उच्चतम, 1 स्तर पर, यह 4^2 , 2 - 4^1 पर, 3 - 4^0 ।

दूसरे शब्दों में, ( + 1) ( - ) ( + 1) ( - ) ( + 1) को एक शक्ति के बराबर उठाया जाना चाहिए ( - ) । आवश्यक डिग्री "लाल" कॉलम में इंगित की गई है। लेकिन यह केवल निर्माण करने के लिए आवश्यक नहीं है, बल्कि माता-पिता के लिए भी जोड़ना है क्योंकि वह एक बच्चा है।

एक बदलाव के लिए, मैं एक पेड़ के लिए एक तालिका दिखाऊंगा, जिसमें स्तर = 4 और बच्चे = 2 की संख्या होगी:


चित्रा 5

सादृश्य द्वारा, आप खुद समझ सकते हैं कि आधार और डिग्री क्या है।

यदि कोई कठिनाई है, तो चित्र 5 में एक छोटा सा उदाहरण ...

मान लीजिए कि हमारे पास कोड 27 साथ एक तत्व है। अभी बच्चे नहीं हैं।

पहला बच्चा पाने के लिए, आपको चाहिए:
27 + ((2+1)^2) * 1 = 36
दूसरा बच्चा पाने के लिए:
27 + ((2+1)^2) * 2 = 45

आदि आदि ...

वह, वास्तव में, सब है। बाकी तकनीक का मामला है।

एक नए बच्चे की आईडी की गणना

यदि वृक्ष भरा हुआ है, तो वह आत्मनिर्भर है। यही है, इसके आयाम को जानते हुए, हम ID का उपयोग करके मूल स्तर और पेरेंट नोड में इसके स्थान की गणना कर सकते हैं।

लेकिन हमें केवल एक पेड़ बनाना है, और डेटाबेस के लिए अनावश्यक प्रश्नों के बिना।

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

नतीजतन, हमारे पास ऐसी पदानुक्रमित तालिका संरचना है:
ID - पूर्णांक
PARENT - पूर्णांक - आईडी का संदर्भ
LEVEL - पूर्णांक
COUNT_CHILDS - पूर्णांक

पेड़ के आयाम को बताएं:
LV - स्तर की संख्या
CH - प्रति अभिभावक बच्चों की संख्या

id - बाल कम्प्यूटेबल कोड

फिर, माता-पिता के बारे में डेटा होने पर, अगले बच्चे को मिल सकता है:

id = ((CH+1)^(LV-LEVEL-1)) * (COUNT_CHILDS+1) + ID

प्रतिबंध

यह सब अच्छा है, लेकिन पूर्णांक असीमित नहीं हैं, और इसकी एक निश्चित सीमा है। उदाहरण के लिए, int32 2^32=4 294 967 296 मूल्यों को संग्रहीत कर सकता है। यह इस विधि की प्रयोज्यता को कैसे प्रभावित कर सकता है?
जवाब है, हमेशा की तरह, यह सब वर्तमान कार्य पर निर्भर करता है। लेकिन, मुझे लगता है कि अधिकांश कार्यों के लिए, यह पर्याप्त है।

इस तरह की संरचना में तत्वों को संग्रहीत करने के लिए आवश्यक अधिकतम मूल्य सूत्र द्वारा पाया जा सकता है:
(+1)^

उदाहरण के लिए, 6 स्तरों के लिए, int32 के साथ, आप 39 बच्चे खरीद सकते हैं।
(39+1)^6 = 4 096 000 000

बस इतनी सी रकम मेरे अनुकूल थी।
कम स्तर - अधिक बच्चे होंगे, और इसके विपरीत। कौन परवाह करता है - अपने लिए विचार करें, यदि परिणाम आपके लिए अधिकतम स्वीकार्य पूर्णांक से कम है, तो सब कुछ ठीक है।

int64 का उपयोग स्वीकार्य दायरे को बहुत बढ़ाता है। इस मामले में, 6 लेवल 1624 के लिए बच्चे पहले से ही उपलब्ध हैं। ऐसी चाबियों के साथ काम करने की गति बहुत धीमी नहीं होगी (कभी-कभी यह बिल्कुल भी धीमा नहीं होगा)।

दस्ते ने एक लड़ाकू के नुकसान की सूचना नहीं दी

एक चौकस पाठक यह देखेगा कि सबसे "लेफ्ट" रेंज उपयोग के लिए गायब हो जाती है।
उदाहरण के लिए, पेड़ में, चित्र 2 में, 0 से 16 तक की संख्या शामिल नहीं है। आप निश्चित रूप से, प्रारंभिक तत्व के साथ स्मार्ट हो सकते हैं (हम बाद में इसके बारे में बात करेंगे)। लेकिन मैंने नहीं - पर्याप्त था।

प्रारंभिक तत्व

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

तो, ऊपर दिए गए सभी चित्रों के लिए, प्रारंभिक तत्व इस तरह होगा:
ID = 0
PARENT = 0
LEVEL = 0
COUNT_CHILDS = 0

हां, वह शीर्ष पर नहीं है, जैसा कि इसे चित्रित करने के लिए प्रथागत है। वह "बाएं" जैसा है। लेकिन यह दृष्टिकोण काम करता है, और यह मुख्य बात है।

संकेत कुछ भी नहीं बदलता है

सभी डेटाबेस आपको एक अहस्ताक्षरित पूर्णांक को संग्रहीत करने की अनुमति नहीं देते हैं। लेकिन यह एल्गोरिदम को बिल्कुल प्रभावित नहीं करता है। दोनों एक नए तत्व की गणना के लिए, और नेस्टेड लोगों के चयन के लिए।
यहां हमारा उदाहरण है जहां पेड़ को "नकारात्मक सीमा में स्थानांतरित" किया गया है:


अंजीर। 6

इस उदाहरण के लिए, प्रारंभिक तत्व इस तरह बनाया जाना चाहिए:
ID = -32
PARENT = -32
LEVEL = 0
COUNT_CHILDS = 0

32-बिट पूर्णांक आपको -2,147,483,647 से 2,147,483,648 स्टोर करने की अनुमति देता है

हम प्रत्येक तत्व के लिए "अधिकतम", 39 बच्चों के साथ 6 स्तर चाहते हैं।
फिर हमें आरंभिक id=-((39+1)^6)/2 , और मैन्युअल रूप से डेटाबेस में (या जो भी आप चाहते हैं) हम निम्न मानों के साथ समूह में दर्ज करते हैं:
ID = -2,048,000,000
PARENT = -2,048,000,000
LEVEL = 0
COUNT_CHILDS = 0

सब कुछ ठीक वैसे ही चलेगा।

एल्गोरिदम कार्यान्वयन

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

निम्नलिखित एल्गोरिदम में प्रमुख बिंदुओं का वर्णन है।

एक नया आइटम डालें

वृक्ष का आयाम

CH - प्रति तत्व बच्चों की अनुमत संख्या
LV - एक पेड़ में स्तरों की अनुमति है

मैं दोहराता हूं, यह पहले से तय किया जाना चाहिए।

हमारे पास माता-पिता का रिकॉर्ड है

ID - पूर्णांक
PARENT - पूर्णांक - आईडी का संदर्भ
LEVEL - पूर्णांक
COUNT_CHILDS - पूर्णांक

तब आप सूत्र द्वारा एक नया बच्चा प्राप्त कर सकते हैं:

id = ((CH+1)^(LV-LEVEL-1)) * (COUNT_CHILDS+1) + ID

यदि माता-पिता के पास अधिक बच्चे नहीं हैं तो हम सम्मिलित नहीं करते हैं।

सभी बच्चों के साथ एक अभिभावक को दूसरे माता-पिता में स्थानांतरित करना

वास्तव में, सब कुछ सरल है।
स्थानांतरण करते समय, हम रिकॉर्ड फ़ील्ड में परिवर्तन करते हैं: आईडी, माता-पिता, स्तर, तत्व के लिए और सभी संभव बच्चों के लिए। सब कुछ एक अनुरोध बन जाता है।

हमें चाहिए:
1. पोर्टेबल तत्व - K , बेशक हमारे पास है
2. जनक - P , इसी तरह
3. द न्यू पेरेंट - NP , हमारे पास यह भी है
4. एक समय में बच्चों की स्वीकार्य संख्या CH , हमारे पास हमेशा यह है - निरंतर
5. स्तरों में अंतर - dL , मौजूदा डेटा से गणना की जाती है

उपरोक्त होने के बाद, हम बस तत्व और उसके सभी संभावित बच्चों के लिए अद्यतन करते हैं, सूत्र के अनुसार नई आईडी की गणना करते हैं:

Id = (KP)*(CH+1)^dL+NP

PARENT फ़ील्ड की गणना उसी तरह की जाती है, LEVEL फ़ील्ड को dL के अनुसार बदल दिया जाता है।

यहाँ django कोड से मुख्य टुकड़ा है:

 x_tmp = Group.objects.filter(id__gte=oldElement.id) .filter(id__lt = limit_right) .update( id=((F('id')-id_departure)*((CH+1)**delta_level) + id_destination), parent = ((F('parent')-id_departure)*((CH+1)**delta_level) + id_destination), level = (F('level')-delta_level) ) 

हम स्थानांतरण नहीं करते हैं:
1. नए माता-पिता के पास [अधिक] बच्चे नहीं हो सकते ...
2. या ... पोर्टेबल तत्व में वे बच्चे हैं जो ट्री में स्वीकार्य स्तर "नीचे" हैं। यह स्थिति केवल नीचे जाने पर घटित होगी। आप इसे कैसे संसाधित करते हैं, बस इस तरह के एक तत्व के हस्तांतरण पर रोक लगाते हैं, या स्वीकार्य स्तर पर बच्चों को "कट" करते हैं - यह आपके ऊपर है। मैं ऐसे एलिमेंट को ट्रांसफर नहीं करता।

निष्कासन

मैं केवल उस एलिमेंट को डिलीट करता हूं जिसमें कोई बच्चे नहीं हैं
किसी आइटम को हटाते समय - माता-पिता पर बच्चों की संख्या कम करें
लिखने के लिए और कुछ नहीं है।

एक छेद खोदो - सो जाओ

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

यहाँ एल्गोरिथ्म उपरोक्त स्थानांतरण का एक विशेष मामला है। केवल आसान है।

आवेदन का क्षेत्र

हर जगह जहां अंतहीन पदानुक्रम की जरूरत नहीं है।
और रोजमर्रा के रोजमर्रा के कार्यों में इसकी आवश्यकता कब होती है?

विपक्ष:
- प्रति समूह बच्चों की संख्या पर सीमा
- ट्री में स्तरों की संख्या पर सीमा

Int32 और int64 के लिए बच्चों और समूहों के संयोजन के लिए कुछ विकल्प:


चित्र 7

हो सकता है, इन नंबरों को स्ट्रोक करते हुए, कोई यह तय करेगा कि सब कुछ इतना बुरा नहीं है ...

पेशेवरों:
- काम की गति
- छोटी मात्रा में डेटा
- आप लगभग हमेशा एक प्रमुख सीमा अनुरोध के साथ प्राप्त कर सकते हैं
- कार्यान्वयन में आसानी



आपका ध्यान देने के लिए धन्यवाद।
मैं किसी भी त्रुटि या टाइपोस के लिए माफी माँगता हूँ।
मैं किसी भी टिप्पणी के लिए आभारी रहूंगा।

UPD 10/09/2015
Django (django-treensl) के लिए एक treensl ऐप लिखा।
सूत्र github.com/EvgeniyBurdin/django_treensl
डेटाबेस में प्राथमिक कुंजी के साथ काम करने का तर्क दिया जाता है।
वर्तमान में केवल PostgreSQL 9.1 और उच्चतर के लिए लागू किया गया है।