data structures लाल पेड़ बनाम बी पेड़ बनाम




data-structures b-tree (2)

इन दोनों के बीच अंतर को समझने के लिए, नीचे 2 अंक पढ़ें:

1) ए "रेड-ब्लैक ट्री" एक "स्व-संतुलन" "बाइनरी सर्च ट्री" है, जिसमें प्रत्येक नोड रंग (या तो लाल या काला) के साथ चिह्नित होता है और इसमें "संतुलन" बनाए रखने के लिए अतिरिक्त संचालन परिभाषित किया जाता है।

2) सभी "रेड-ब्लैक ट्री" "बाइनरी सर्च ट्री" हैं, लेकिन सभी "बाइनरी सर्च ट्री" नहीं हैं "रेड-ब्लैक ट्री"

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

  1. डेटा एक ही समय में मेमोरी संभाल सकता है (नमूना 10-15 टेराबाइट्स में है) से कहीं अधिक है। इस मामले में, मैं डेटा संरचना को डिस्क पर संग्रहीत करूंगा।

  2. डेटा प्रणाली की स्मृति की तुलना में अपेक्षाकृत कम है और इस प्रकार इसे गति के लिए स्मृति में संग्रहीत और संचालित किया जा सकता है।

  3. डेटा मुफ्त मेमोरी से अधिक है और मान लें कि यह पेजिंग फ़ाइल में डेटा के संभावित संगत खंड के आकार से कम है। इस प्रकार मैं डेटा संरचना को डिस्क पर एक फ़ाइल में संग्रहीत करता हूं और फ़ाइल का मेमोरी मैपिंग करता हूं।

मेरे द्वारा तैयार किए गए निष्कर्ष हैं:

1 मामले के लिए, मुझे तेजी से पहुंच के लिए बी-ट्री का उपयोग करना चाहिए क्योंकि यह डिस्क रोटेशन द्वारा उत्पादित अंतराल पर बचाता है

मामले 2 के लिए, मुझे तेजी से पहुंच के लिए लाल ब्लैक ट्री का उपयोग करना चाहिए क्योंकि डेटा स्मृति पर है और नहीं। बदतर मामले में स्कैन किए जाने वाले तत्वों में से एक से कम होगा यदि मैं बी पेड़ का उपयोग करता हूं तो मुझे करना होगा

3 मामले के लिए, मैं इस पर संदिग्ध हूं, फाइल फ़ाइल डिस्क पर है फ़ाइलों पर काम करने के लिए मूल ओएस I / O का उपयोग करता है, तो बी ट्री एक बेहतर विकल्प या लाल काला पेड़ होना चाहिए?

मैं जानना चाहता हूं कि उपरोक्त तीन निष्कर्ष सही कहां जाते हैं और जहां यह गलत हो जाता है और मैं तीन अलग-अलग मामलों में प्रदर्शन पर कैसे सुधार कर सकता हूं।

मैं सी ++ भाषा का उपयोग कर रहा हूं, एक लाल काले पेड़ और एक बी पेड़ के साथ, जिसे मैंने खरोंच से डिजाइन किया है। मैं फाइल मैपिंग के लिए बूस्ट लाइब्रेरी का उपयोग कर रहा हूं।

अद्यतन 1 :: this पोस्ट के माध्यम से stackoverflow में पढ़ रहा this । कुछ असली अच्छी अंतर्दृष्टि मिली, जो मुझे महसूस करती है कि मामलों में मैंने जो तुलना की है, वह दोषपूर्ण हो सकती है। सबसे अधिक वोट-इन-उत्तर में एक लिंक पोस्ट किया गया था http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html


एक लाल / काली पेड़ 2-3-4 पेड़ के बराबर बराबर होता है, जो कि बी-पेड़ का एक प्रकार है। सबसे खराब केस प्रदर्शन समान है, बशर्ते आप बी-पेड़ नोड मानों की बाइनरी खोज करें।

बी-पेड़ का स्पष्ट नुकसान अंतरिक्ष बर्बाद हो गया है, लेकिन भाषा / स्मृति आवंटक के आधार पर उपयोग किया जाता है, आप पाते हैं कि 2-3-4 पेड़ औसतन लाल-काले पेड़ की तुलना में कम जगह का उपयोग करता है। उदाहरण के लिए, 32-बिट जावा में, प्रति ऑब्जेक्ट लगभग 8-बाइट ओवरहेड होता है। (यह भी आवंटक पर बहुत निर्भर करता है; आईआईआरसी phkmalloc छोटे आवंटन को एक शक्ति के 2 आकार के लिए गोल करता है।)

अपने मामलों का जवाब देने के लिए,

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

सादगी के लिए, मैं बी-पेड़ के साथ जाऊंगा और विभिन्न नोड आकारों पर कुछ मानक चलाऊंगा।





large-data