मैं बी पेड़ पर पढ़ रहा हूं और ऐसा लगता है कि वे ओ (एलजी एन) समय में गतिशील सेट ऑपरेशंस प्राप्त करते हैं। रेड ब्लैक ट्री (जावा में ट्रीमैप) भी उसी ऑपरेशन को उसी समय फ्रेम में समान ऑपरेशन में प्राप्त करता है। तो मैं जानना चाहता हूं कि बी पेड़ डेटाबेस और फाइल सिस्टम के लिए अधिक उपयोगी बनाता हैहमें डेटाबेस और फ़ाइल सिस्टम के लिए बी-ट्री जैसे अलग डेटास्ट्रक्चर की आवश्यकता क्यों है?
उत्तर
बी-पेड़ के अस्तित्व का मुख्य कारण डेटा के बड़े हिस्से को पढ़ने और लिखने वाले उपकरणों के व्यवहार का बेहतर उपयोग करना है। दो गुण बी ट्री द्विआधारी पेड़ की तुलना में बेहतर बनाने के लिए महत्वपूर्ण हैं जब डेटा डिस्क पर संग्रहीत करने के लिए किया गया है:
- डिस्क तक पहुंच वास्तव में धीमी है (स्मृति या कैश, आंकड़ों के यादृच्छिक अभिगम की तुलना में डिस्क आदेश है परिमाण धीमा); और
- प्रत्येक एकल पढ़ने से पूरे क्षेत्र को ड्राइव से लोड किया जा सकता है - 4K का क्षेत्रफल मानते हुए, इसका मतलब है 1000 पूर्णांक, या कुछ बड़ी ऑब्जेक्ट्स जो आप संग्रहीत कर रहे हैं।
इसलिए, हम दूसरे तथ्य के पेशेवरों का उपयोग कर सकते हैं, जबकि विपक्ष को कम करने के दौरान - डिस्क एक्सेस की संख्या भी कम कर सकते हैं।
तो, प्रत्येक नोड में केवल एक ही संख्या को संग्रहीत करने के बजाय हमें बताता है कि हमें बाएं या दाएं को जारी रखना चाहिए, तो हम एक बड़ी अनुक्रमणिका बना सकते हैं जो हमें बताता है कि हमें पहले 1/100 , दूसरे या 99-वें (अपनी पहली पत्र द्वारा क्रमबद्ध लाइब्रेरी में पुस्तकों की कल्पना करें, फिर दूसरे द्वारा, और इसी तरह)। जब तक यह सभी डेटा एक ही क्षेत्र पर फिट बैठता है, तब तक इसे लोड किया जाएगा, इसलिए हम इसे पूरी तरह से उपयोग कर सकते हैं।
परिणामस्वरूप यह लगभग बी एन लुकअप लॉग इन करता है, जहां एन रिकॉर्ड की संख्या है। यह संख्या, जबकि एन के रूप में asymptotically समान है, वास्तव में पर्याप्त पर्याप्त एन और बी के साथ कुछ गुना छोटा है - और चूंकि हम डेटाबेस में उपयोग के लिए डिस्क को डेटा संग्रहीत करने के बारे में बात कर रहे हैं, डेटा की मात्रा आम तौर पर इसे उचित ठहराने के लिए काफी बड़ा होता है।
शेष डिजाइन निर्णय मुख्य रूप से इस काम को कुशलतापूर्वक बनाने के लिए किया जाता है, क्योंकि एन-आरी पेड़ को संशोधित करना बाइनरी से अधिक कठिन होता है।
धन्यवाद! मैंने कम से कम बी पेड़ के उपयोग के बारे में कुछ 50 लेख पढ़े हैं, लेकिन किसी ने डिस्क एक्सेस के दूसरे कंस का उल्लेख नहीं किया है, जिसे बी पेड़ प्रो में बदल जाता है। – ernesto
आरबी पेड़ द्विआधारी खोज पेड़ हैं। बी पेड़ों में दो से अधिक बच्चे नोड्स हो सकते हैं। वास्तव में, बाल नोड्स की संख्या परिवर्तनीय है।
तो, आप बच्चे नोड्स की संख्या बदल सकते हैं जैसे कि नोड का आकार हमेशा फाइल सिस्टम ब्लॉक आकार का एक बहु होता है। यह पढ़ने के दौरान अपशिष्ट को कम करता है: आप किसी एक से भी कम ब्लॉक को नहीं पढ़ सकते हैं, आपको हमेशा पूर्ण ब्लॉक पढ़ना होगा, ताकि आप इसे उपयोगी डेटा के साथ भर सकें। बाल नोड्स की संख्या में वृद्धि पेड़ की गहराई घट जाती है, इस प्रकार "होप्स" (यानी डिस्क पढ़ने) की औसत संख्या घट जाती है, जो फिर से प्रदर्शन को बढ़ाती है।
याद रखें: बी पेड़ होती है जबकि आरबी पेड़ आम तौर पर दुकान डेटा संरचनाओं जो परिमाण छोटे स्मृति से के आदेश हैं करने के लिए इस्तेमाल कर रहे हैं, दुकान डेटा संरचनाओं जो परिमाण बड़ा स्मृति से के आदेश हैं करने के लिए इस्तेमाल कर रहे हैं। वास्तव में, बी पेड़ विशेष रूप से ऑन-डिस्क डेटा संरचना के रूप में डिज़ाइन किए गए हैं, क्योंकि इन-मेमोरी डेटा स्ट्रक्चर के विपरीत।
यह Wikipedia article (जोर मेरा) से कुंजी वाक्य है:
बी पेड़ प्रणाली है कि पढ़ सकते हैं और डेटा का बड़े ब्लॉकों लिखने के लिए अनुकूलित है
हम विभिन्न एल्गोरिदम की आवश्यकता है क्योंकि स्मृति में एक्सेस गति डिस्क की तुलना में बहुत तेज है। एक लाल/काला पेड़ कई मेमोरी एक्सेस बनाता है, इसलिए यह स्मृति की तेज पहुंच गति के साथ अच्छी तरह से काम करता है। एक बी-पेड़ कम, बड़ी पहुंच बनाता है क्योंकि डिस्क की पहुंच धीमी है।
- 1. हमें Nuget जैसे पैकेज प्रबंधक की आवश्यकता क्यों है?
- 2. हमें डेटाबेस टेबल्स में ऑडिट कॉलम की आवश्यकता क्यों है?
- 3. हमें एक अस्थायी डेटाबेस की आवश्यकता क्यों है?
- 4. हमें डिज़ाइन पैटर्न की आवश्यकता क्यों है
- 5. हमें लक्ष्य नामस्थान की आवश्यकता क्यों है?
- 6. हमें फ़ील्ड टैग की आवश्यकता क्यों है?
- 7. हमें संरचना की आवश्यकता क्यों है? (सी #)
- 8. हमें "हटाएं []" ऑपरेटर की आवश्यकता क्यों है?
- 9. हमें वेब-सॉकेट की आवश्यकता क्यों है?
- 10. हमें strdup() की आवश्यकता क्यों है?
- 11. हमें "आउट" पैरामीटर की आवश्यकता क्यों है?
- 12. हमें सी # प्रतिनिधियों की आवश्यकता क्यों है
- 13. हमें यहां टाइपनाम की आवश्यकता क्यों है?
- 14. हमें तीसरे पक्ष के निर्माण उपकरण की आवश्यकता क्यों है?
- 15. अलग आईशैच और डीसीएके की आवश्यकता क्यों है
- 16. हमें ढांचे के ढांचे की आवश्यकता क्यों है?
- 17. हमें ब्लॉक मैक्रो के आसपास कोष्ठक की आवश्यकता क्यों है?
- 18. हमें गतिशील भाषाओं में इंटरफेस की आवश्यकता क्यों नहीं है?
- 19. हमें मॉलोक रिटर्न डालने की आवश्यकता क्यों है?
- 20. हमें अभी भी जेनरेट कोड की आवश्यकता क्यों है?
- 21. हमें क्यों जारी रखने की विधि की आवश्यकता है?
- 22. हमें Easymock, JMock या Mockito जैसे मॉकिंग फ्रेमवर्क की आवश्यकता क्यों है?
- 23. हमें सजावटी डिजाइन पैटर्न में सजावट की आवश्यकता क्यों है?
- 24. हमें मूल क्वेरी बनाने की आवश्यकता क्यों है?
- 25. मार्शलिंग - यह क्या है और हमें इसकी आवश्यकता क्यों है?
- 26. हमें एक निजी निर्माता की आवश्यकता क्यों है?
- 27. PHP: हमें स्ट्रिंग तुलना फ़ंक्शन की आवश्यकता क्यों है?
- 28. हमें इस विशेष === ऑपरेटर की आवश्यकता क्यों है?
- 29. हमें हडोप स्टैक में ज़ूकीपर की आवश्यकता क्यों है?
- 30. हमें जावा में इंटरफेस की आवश्यकता क्यों है?
विकिपीडिया में बी-ट्री हल होने वाली समस्याओं का एक बहुत अच्छा विवरण है - http://en.wikipedia.org/wiki/B-tree#The_database_problem। –
@IvanVergiliev क्या आप विकी से संबंधित उत्तर को उत्तर के रूप में जोड़ना चाहते हैं ताकि मैं इसे स्वीकार कर सकूं। – Geek