मेरे पास एक प्रोजेक्ट है जिसमें मुझे मेगाबाइट्स से टेराबाइट तक के डेटा पर संचालन को तेज खोज, डालने और हटाने की आवश्यकता है। मैं देर से डेटा संरचनाओं का अध्ययन कर रहा था और उनका विश्लेषण कर रहा था। विशिष्ट होने के नाते, मैं उस पर 3 मामलों सवालों के लागू करने और पूछना चाहता हूँ:लाल पेड़ बनाम बी पेड़
डेटा क्या स्मृति एक बार में (10-15 टेराबाइट्स में नमूना पर्वतमाला) संभाल कर सकते हैं की तुलना में अधिक है। इस मामले में, मैं डेटा संरचना को डिस्क पर संग्रहीत करूंगा।
डेटा की स्मृति की तुलना में डेटा अपेक्षाकृत कम है और इस प्रकार इसे गति के लिए स्मृति में ही संग्रहीत और संचालित किया जा सकता है।
डेटा मुफ्त मेमोरी से अधिक है और मान लें कि यह पेजिंग फ़ाइल में डेटा के संभावित संगत खंड के आकार से कम है। इस प्रकार मैं डेटा संरचना को डिस्क पर एक फ़ाइल में संग्रहीत करता हूं और फ़ाइल का मेमोरी मैपिंग करता हूं।
निष्कर्ष मैं तैयार की है कर रहे हैं:
मामले 1 के लिए, मैं एक बी पेड़ तेजी से पहुँच के लिए के रूप में यह डिस्क रोटेशन द्वारा उत्पादित अंतराल पर बचाता है का उपयोग करना चाहिए
मामले 2 के लिए, मैं तेजी से पहुंच के लिए लाल ब्लैक ट्री का उपयोग करना चाहिए क्योंकि डेटा स्मृति पर है और नहीं। बदतर मामले में स्कैन किए जाने वाले तत्वों की तुलना में मुझे कम से कम एक करना होगा यदि मैं बी पेड़
मामले के लिए 3, मुझे इस पर संदेह है, पृष्ठ फ़ाइल डिस्क पर है मूल ओएस I/O का उपयोग करता है फ़ाइलों पर काम करने के लिए, तो बी ट्री एक बेहतर विकल्प या लाल काला पेड़ होना चाहिए?
मैं जानना चाहता हूं कि उपरोक्त तीन निष्कर्ष सही कहां जाते हैं और यह गलत कहां जाता है और मैं तीन अलग-अलग मामलों में प्रदर्शन पर कैसे सुधार कर सकता हूं।
मैं एक लाल काले पेड़ और एक बी पेड़ के साथ सी ++ भाषा का उपयोग कर रहा हूं, जिसे मैंने खरोंच से डिजाइन किया है। मैं फाइल मैपिंग के लिए बूस्ट लाइब्रेरी का उपयोग कर रहा हूं।
अद्यतन 1 :: this स्टैक ओवरफ्लो में पोस्ट के माध्यम से पढ़ रहा था। कुछ असली अच्छी अंतर्दृष्टि मिली, जो मुझे महसूस करती है कि मामलों में मैंने जो तुलना की है, वह दोषपूर्ण हो सकती है। सबसे अधिक वोट वाले उत्तर के लिए http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
आप किस तरह की खोज करने जा रहे हैं? कुंजी द्वारा सरल खोज? कुंजी कैसा दिखता है? – svick
आप कम या ज्यादा सही हैं। कार्यान्वयन के साथ आगे बढ़ें, अगर आप अटक जाते हैं तो यहां पूछें। – nikhil
@ एसविक हाँ, मैं सबसे सामान्य तरीके से कुंजी द्वारा सरल खोज कर रहा हूं, वे एक बुद्धिमान हो सकते हैं, या संख्यात्मक रूप से निरंतर क्रम में, 1 से शुरू होने वाली विशिष्ट प्राकृतिक संख्याओं का सेट (2^8) -1 – swanar