मैं बी पेड़ पर पढ़ रहा हूं और ऐसा लगता है कि वे ओ (एलजी एन) समय में गतिशील सेट ऑपरेशंस प्राप्त करते हैं। रेड ब्लैक ट्री (जावा में ट्रीमैप) भी उसी ऑपरेशन को उसी समय फ्रेम में समान ऑपरेशन में प्राप्त करता है। तो मैं जानना चाहता हूं कि बी पेड़ डेटाबेस और फाइल सिस्टम के लिए अधिक उपयोगी बनाता हैहमें डेटाबेस और फ़ाइल सिस्टम के लिए बी-ट्री जैसे अलग डेटास्ट्रक्चर की आवश्यकता क्यों है?
बी-पेड़ के अस्तित्व का मुख्य कारण डेटा के बड़े हिस्से को पढ़ने और लिखने वाले उपकरणों के व्यवहार का बेहतर उपयोग करना है। दो गुण बी ट्री द्विआधारी पेड़ की तुलना में बेहतर बनाने के लिए महत्वपूर्ण हैं जब डेटा डिस्क पर संग्रहीत करने के लिए किया गया है:
इसलिए, हम दूसरे तथ्य के पेशेवरों का उपयोग कर सकते हैं, जबकि विपक्ष को कम करने के दौरान - डिस्क एक्सेस की संख्या भी कम कर सकते हैं।
तो, प्रत्येक नोड में केवल एक ही संख्या को संग्रहीत करने के बजाय हमें बताता है कि हमें बाएं या दाएं को जारी रखना चाहिए, तो हम एक बड़ी अनुक्रमणिका बना सकते हैं जो हमें बताता है कि हमें पहले 1/100 , दूसरे या 99-वें (अपनी पहली पत्र द्वारा क्रमबद्ध लाइब्रेरी में पुस्तकों की कल्पना करें, फिर दूसरे द्वारा, और इसी तरह)। जब तक यह सभी डेटा एक ही क्षेत्र पर फिट बैठता है, तब तक इसे लोड किया जाएगा, इसलिए हम इसे पूरी तरह से उपयोग कर सकते हैं।
परिणामस्वरूप यह लगभग बी एन लुकअप लॉग इन करता है, जहां एन रिकॉर्ड की संख्या है। यह संख्या, जबकि एन के रूप में asymptotically समान है, वास्तव में पर्याप्त पर्याप्त एन और बी के साथ कुछ गुना छोटा है - और चूंकि हम डेटाबेस में उपयोग के लिए डिस्क को डेटा संग्रहीत करने के बारे में बात कर रहे हैं, डेटा की मात्रा आम तौर पर इसे उचित ठहराने के लिए काफी बड़ा होता है।
शेष डिजाइन निर्णय मुख्य रूप से इस काम को कुशलतापूर्वक बनाने के लिए किया जाता है, क्योंकि एन-आरी पेड़ को संशोधित करना बाइनरी से अधिक कठिन होता है।
धन्यवाद! मैंने कम से कम बी पेड़ के उपयोग के बारे में कुछ 50 लेख पढ़े हैं, लेकिन किसी ने डिस्क एक्सेस के दूसरे कंस का उल्लेख नहीं किया है, जिसे बी पेड़ प्रो में बदल जाता है। – ernesto
आरबी पेड़ द्विआधारी खोज पेड़ हैं। बी पेड़ों में दो से अधिक बच्चे नोड्स हो सकते हैं। वास्तव में, बाल नोड्स की संख्या परिवर्तनीय है।
तो, आप बच्चे नोड्स की संख्या बदल सकते हैं जैसे कि नोड का आकार हमेशा फाइल सिस्टम ब्लॉक आकार का एक बहु होता है। यह पढ़ने के दौरान अपशिष्ट को कम करता है: आप किसी एक से भी कम ब्लॉक को नहीं पढ़ सकते हैं, आपको हमेशा पूर्ण ब्लॉक पढ़ना होगा, ताकि आप इसे उपयोगी डेटा के साथ भर सकें। बाल नोड्स की संख्या में वृद्धि पेड़ की गहराई घट जाती है, इस प्रकार "होप्स" (यानी डिस्क पढ़ने) की औसत संख्या घट जाती है, जो फिर से प्रदर्शन को बढ़ाती है।
याद रखें: बी पेड़ होती है जबकि आरबी पेड़ आम तौर पर दुकान डेटा संरचनाओं जो परिमाण छोटे स्मृति से के आदेश हैं करने के लिए इस्तेमाल कर रहे हैं, दुकान डेटा संरचनाओं जो परिमाण बड़ा स्मृति से के आदेश हैं करने के लिए इस्तेमाल कर रहे हैं। वास्तव में, बी पेड़ विशेष रूप से ऑन-डिस्क डेटा संरचना के रूप में डिज़ाइन किए गए हैं, क्योंकि इन-मेमोरी डेटा स्ट्रक्चर के विपरीत।
यह Wikipedia article (जोर मेरा) से कुंजी वाक्य है:
बी पेड़ प्रणाली है कि पढ़ सकते हैं और डेटा का बड़े ब्लॉकों लिखने के लिए अनुकूलित है
हम विभिन्न एल्गोरिदम की आवश्यकता है क्योंकि स्मृति में एक्सेस गति डिस्क की तुलना में बहुत तेज है। एक लाल/काला पेड़ कई मेमोरी एक्सेस बनाता है, इसलिए यह स्मृति की तेज पहुंच गति के साथ अच्छी तरह से काम करता है। एक बी-पेड़ कम, बड़ी पहुंच बनाता है क्योंकि डिस्क की पहुंच धीमी है।
विकिपीडिया में बी-ट्री हल होने वाली समस्याओं का एक बहुत अच्छा विवरण है - http://en.wikipedia.org/wiki/B-tree#The_database_problem। –
@IvanVergiliev क्या आप विकी से संबंधित उत्तर को उत्तर के रूप में जोड़ना चाहते हैं ताकि मैं इसे स्वीकार कर सकूं। – Geek