डेटाबेस में एक पदानुक्रमित डेटा संरचना को कार्यान्वित करना

Question

मुझे पता है कि दो दृष्टिकोण हैं: आसन्नता सूची और नेस्टेड पेड़। ऐसा कहा जाता है कि कई प्रश्नों के कारण आस-पास की सूची ट्रैवर्सल पर उपयोग करने में धीमी हो सकती है। लेकिन मुझे इसके लिए कोई यथार्थवादी आंकड़ा नहीं पता है। जो साइट मैं बना रहा हूं वह 200 पृष्ठों के क्षेत्र में होगी। ट्रैवर्सल उत्पन्न करने के लिए है (उदाहरण के लिए) साइटमैप लगभग 0.3 सेकंड से अधिक समय ले रहा है?

एलएएमपी स्टैक के साथ MySQL (innoDB) पर चल रहा है।

अधिक सरल डिजाइन के कारण यदि संभव हो तो मैं आसन्नता को लागू करना पसंद करूंगा।

धन्यवाद।

Answer 1

यहाँ है कि आप मदद कर सकता है प्रश्नों की एक जोड़ी हैं:

SQL how to store and navigate hierarchies

Which is the best database schema for my navigation

Answer 2

अन्य दृष्टिकोण "नेस्टेड सेट", मुझे लगता है, नहीं "नेस्टेड पेड़" कहा जाता है।

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

0.3 सेकंड मुझे 200 पृष्ठों को समझने के लिए बहुत लंबे समय की तरह लगता है, तो शायद यह ठीक है।

भी एक साइट मानचित्र अक्सर अद्यतन नहीं किया जाता है; इसलिए यदि SQL से पुनर्प्राप्त करने में लंबा समय लगता है, तो आप शायद RAM में पुनर्प्राप्त/गणना किए गए पेड़ को कैश कर सकते हैं।

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

Answer 3

लेख Managing Hierarchical Data in MySQL इस बारे में विवरण में जाता है।

मैं "नेस्टेड सेट" तकनीक की अनुशंसा करता हूं, क्योंकि यह आपको एक प्रश्न में पूरे पेड़ (और उसके बच्चों) को प्राप्त करने की अनुमति देता है। मूल रूप से पढ़ना सस्ता है लेकिन लिखने महंगे हैं क्योंकि पूरे पेड़ को फिर से संतुलित किया जाना चाहिए। लेकिन जिन मामलों में आपके पास 99% पढ़ते हैं, तो यह पूरी तरह से न्यायसंगत है।

Answer 4

पूर्णता के लिए: ओरेकल में START_WITH और CONNECT_BY ऑपरेटर हैं: यह Hierarchical Queries दस्तावेज़ देखें।

Answer 5

आपके द्वारा उल्लेख किए गए दो विकल्पों की तुलना में अधिक विकल्प हैं।के होते हैं:

• संलग्नता सूची ("PARENT_ID" एक लगभग हर कोई उपयोग करता है)
• नेस्टेड सेट
• पथ गणन
• बंद तालिका (उर्फ संलग्नता रिलेशन)

देखें मेरा उत्तर "What is the most efficient/elegant way to parse a flat table into a tree?"

या कुछ किताबें:

• "Trees and Hierarchies in SQL for Smarties" जो सेल्को द्वारा।
• "SQL Design Patterns" वादिम Tropashko द्वारा।

Answer 6

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

मैंने 1 क्वेरी के साथ एक आसन्न सूची बनाने के लिए निम्न दृष्टिकोण का उपयोग किया है। सभी आइटम डेटाबेस का चयन करें। सभी वस्तुओं को उनकी कुंजी द्वारा अनुक्रमित सरणी में स्थानांतरित करें। सरणी को पार करें और पैरेंट ऑब्जेक्ट से अपने प्रत्येक बच्चे को संदर्भ दें। सरणी को दूसरी बार घुमाएं और केवल मूल स्तर की वस्तुओं के पीछे छोड़कर सभी बाल वस्तुओं को हटा दें।

जब से तुम दीप ढेर उल्लेख किया है, PHP कोड यह मोटे तौर पर इस प्रकार है क्या करने के लिए:

<?php 
// Assumes $src is the array if items from the database. 
$tmp = array(); 

// Traverse the array and index it by id, ensuing each item has an empty array of children. 
foreach ($src as $item) { 
    $item['children'] = array(); 
    $tmp[$item['id']] = $item; 
} 

// Now traverse the array a second time and link children to their parents. 
foreach ($tmp as $id => $item) { 
    if ($item['parent_id'] != 0 || $item['parent_id'] !== NULL) { 
    $tmp[$item['parent_id']]['children'][$id] = &$tmp[$id]; 
    } 
} 

// Finally create an array with just root level items. 
$tree = array(); 
foreach ($tmp as $id => $item) { 
    if ($item['parent_id'] == 0 || $item['parent_id'] === NULL) { 
    $tree[$id] = $item; 
    } 
} 

// $tree now contains our adjacency list in tree form. 
?> 

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

जिम,