बीएसटी इंडेक्स बनाम माइस्क्लुएल बी + पेड़ बनाम

Question

हम माइस्क्लुएल से पीजीएसक्यूएल में माइग्रेट करने की प्रक्रिया में हैं और हमारे पास 100 मिलियन पंक्ति तालिका है।

जब मैं यह पता लगाने की कोशिश कर रहा था कि दोनों सिस्टम कितनी जगह का उपयोग करते हैं, तो मुझे टेबल के लिए बहुत कम अंतर मिला, लेकिन इंडेक्स के लिए भारी अंतर मिला।

MySQL अनुक्रमणिका तालिका डेटा से अधिक आकार पर कब्जा कर रहे थे और पोस्टग्रेज़ काफी कम आकार का उपयोग कर रहे थे।

• जब कारण के लिए के माध्यम से खुदाई, मैंने पाया कि MySQL बी + पेड़ का उपयोग करता है अनुक्रमित और postgres uses बी पेड़ स्टोर करने के लिए।

• इंडेक्स का MySQL उपयोग थोड़ा अलग था, यह इंडेक्स के साथ डेटा संग्रहीत करता है (जिसके कारण बढ़ी हुई आकार), लेकिन पोस्टग्रेज़ नहीं है।

अब सवाल:

• तुलना बी पेड़ और B + डेटाबेस पर पेड़ बात करते हैं, यह बी + पेड़ का उपयोग करने के बाद से वे सीमा के लिए बेहतर हैं बेहतर है प्रश्नों हे (एम) + O (लॉगएन) - जहां सीमा और लुक में एम बी + पेड़ों में लॉगरिदमिक है?

  अब बी-पेड़ों में लुकअप रेंज क्वेरी के लिए लॉगरिदमिक है जो इसे ओ (एन) तक शूट करता है क्योंकि इसमें डेटा नोड्स के लिए लिंक की गई सूची अंतर्निहित संरचना नहीं है। इसके साथ ही, पोस्टग्रेस बी-पेड़ का उपयोग क्यों करता है? क्या यह रेंज पूछताछ के लिए अच्छा प्रदर्शन करता है (यह करता है, लेकिन यह बी-पेड़ों के साथ आंतरिक रूप से कैसे संभालता है)?

• उपर्युक्त प्रश्न पोस्टग्रेस बिंदु से है, लेकिन एक MySQL परिप्रेक्ष्य से, यह पोस्टग्रेज़ से अधिक संग्रहण का उपयोग क्यों करता है, वास्तविकता में बी + पेड़ों का उपयोग करने का प्रदर्शन लाभ क्या है?

मैं कई चीजों को याद/गलत समझा सकता था, इसलिए कृपया मेरी समझ को सही करने के लिए स्वतंत्र महसूस करें।

का जवाब देने के लिए रिक जेम्स संपादित सवाल

• मैं MySQL
• के लिए InnoDB इंजन का उपयोग कर रहा मैं डेटा को आबाद करने के बाद सूचकांक बनाया - उसी तरह मैं postgres में किया था
• अनुक्रमित नहीं हैं अद्वितीय सूचकांक, केवल सामान्य अनुक्रमणिका
• कोई यादृच्छिक आवेषण नहीं था, मैंने दोनों पोस्टग्रेज़ और MySQL में सीएसवी लोडिंग का उपयोग किया और इसके बाद ही मैंने इंडेक्स बनाया।
• इंडेक्स और डेटा दोनों के लिए पोस्टग्रेस ब्लॉक आकार 8KB है, मुझे MySQL के लिए निश्चित नहीं है, लेकिन मैंने इसे नहीं बदला है, इसलिए यह डिफ़ॉल्ट होना चाहिए।
• मैं पंक्तियों को बड़ा नहीं कहूंगा, उनके पास 200 अक्षर लंबे, 4 दशमलव फ़ील्ड और 2 बिगिन फ़ील्ड के साथ लगभग 4 टेक्स्ट फ़ील्ड हैं - 1 9 नंबर लंबा।
• पीके 1 9 नंबरों के साथ एक बड़ा स्तंभ है, मुझे यकीन नहीं है कि यह भारी है या नहीं? भारी पैमाने पर गैर-भारी को किस पैमाने पर अलग किया जाना चाहिए?
• MySQL तालिका का आकार 600 एमबी था और पोस्टग्रेस इंडेक्स समेत लगभग 310 एमबी था - यह मेरा गणित सही होने पर 48% बड़ा आकार है। लेकिन क्या कोई तरीका है कि मैं माईएसक्यूएल में अकेले इंडेक्स आकार को माप सकता हूं टेबल आकार?इससे मुझे लगता है कि बेहतर संख्या का कारण बन सकता है।
• मशीन जानकारी: मेरे पास पर्याप्त तालिकाओं - 256GB सभी टेबल और इंडेक्स को फिट करने के लिए पर्याप्त था, लेकिन मुझे नहीं लगता कि हमें इस मार्ग को पार करने की आवश्यकता है, मुझे दोनों में कोई उल्लेखनीय प्रदर्शन अंतर नहीं दिखाई देता।

अतिरिक्त प्रश्न

• जब हम कहते हैं विखंडन होता है? क्या डी-विखंडन करने का कोई तरीका है ताकि हम कह सकें कि इससे परे कुछ भी नहीं किया जा रहा है। मैं रास्ते में सेंट ओएस का उपयोग कर रहा हूं।
• क्या MySQL में इंडेक्स आकार को मापने का कोई तरीका है, प्राथमिक कुंजी को क्लस्टर करने के रूप में अनदेखा कर रहा है, ताकि हम वास्तव में देख सकें कि कोई भी आकार किस प्रकार अधिक आकार पर कब्जा कर रहा है।

Answer 1

डेटाबेस में आप अक्सर जो उद्धार आईडी 200
100 से की तरह कुछ डेटा पर्वतमाला इस मामले

• बी ट्री के लिए लीफ़्स को जड़ से मार्ग का अनुसरण करने की जरूरत में प्रश्न हैं डाटा-पॉइंटर प्राप्त करने के लिए प्रत्येक प्रविष्टि।
• बी + -Trees लीफ़्स के माध्यम से की पैदल दूरी पर 'कर सकते हैं और

यह वह जगह है (आईडी 100 के लिए यानी) केवल पहली बार लीफ़्स के लिए पथ का पालन किया है क्योंकि बी + -Trees भंडार केवल पत्ते और डेटा में डेटा (या डेटा-पॉइंटर) जुड़े होते हैं ताकि आप तेजी से इन-ऑर्डर-ट्रैवर्सल कर सकें।

बी + पेड़

एक और मुद्दा है:
बी + पेड़ आंतरिक नोड्स भंडार केवल किसी भी डेटा-सूचक के बिना अन्य नोड सूचक पर है, तो आप संकेत के लिए अधिक स्थान है और आप की जरूरत है कम आईओ-ऑपरेशंस और आप मेमोरी पेज पर अधिक नोड-पॉइंटर्स स्टोर कर सकते हैं।

तो सीमा-प्रश्नों के लिए बी + -ट्री इष्टतम डेटा-strucure हैं। एकल चयनों के लिए बी-पेड़ बेहतर हो सकते हैं (पेड़ की गहराई/आकार के कारण), क्योंकि डेटा-पॉइंटर पेड़ के अंदर भी स्थित है।

Answer 2

सबसे पहले, और सबसे महत्वपूर्ण, यदि आप इनो डीबी का उपयोग नहीं कर रहे हैं, तो इस सवाल को बंद करें, इनो डीबी के साथ पुनर्निर्माण करें, फिर देखें कि आपको प्रश्न को फिर से खोलने की आवश्यकता है या नहीं। MyISAM पसंदीदा नहीं है और चर्चा नहीं की जानी चाहिए।

आप कैसे इंडेक्स MySQL में बनाते हैं? स्पष्ट रूप से या स्पष्ट रूप से इंडेक्स बनाने के कई तरीके हैं; वे बेहतर या बदतर पैकिंग का नेतृत्व करते हैं।

MySQL: डेटा और इंडेक्स 16KB ब्लॉक से बना बी + पेड़ में संग्रहीत हैं।

MySQL: UNIQUE अनुक्रमित (सहित PRIMARY KEY) अद्यतन किया जाना चाहिए आप पंक्तियां सम्मिलित रूप में। तो, UNIQUE इंडेक्स में जरूरी ब्लॉक विभाजन आदि होंगे।

MySQL: PRIMARY KEY डेटा के साथ क्लस्टर किया गया है, इसलिए यह प्रभावी रूप से शून्य स्थान लेता है। यदि आप पीके ऑर्डर में डेटा लोड करते हैं, तो ब्लॉक विखंडन न्यूनतम है।

गैर- UNIQUE द्वितीयक कुंजी फ्लाई पर बनाया जा सकता है, जो कुछ विखंडन की ओर जाता है। या टेबल लोड होने के बाद उनका निर्माण किया जा सकता है; यह घनत्व पैकिंग की ओर जाता है।

माध्यमिक कुंजी (UNIQUE या नहीं) इसमें PRIMARY KEY शामिल हैं। यदि पीके "बड़ा" है तो माध्यमिक कुंजी भारी हैं। आपका पीके क्या है? क्या यह 'उत्तर' है?

सिद्धांत रूप में, बीटीआर में पूरी तरह से यादृच्छिक प्रविष्टियां 69% पूर्ण के ब्लॉक के लिए पूरी तरह से यादृच्छिक प्रविष्टियां होती हैं। शायद यह जवाब है। MySQL 45% बड़ा (1/69%) है?

100 एम पंक्तियों के साथ, शायद कई ऑपरेशन I/O-bound हैं क्योंकि आपके पास आवश्यक सभी डेटा और/या इंडेक्स ब्लॉक को कैश करने के लिए पर्याप्त RAM नहीं है। अगर सब कुछ कैश किया जाता है, तो बी-ट्री बनाम बी + ट्री बहुत अंतर नहीं करेगा। आइए विश्लेषण करें कि चीजें पूरी तरह से कैश नहीं होने पर सीमा सीमा के लिए क्या होने की आवश्यकता है।

किसी भी प्रकार के पेड़ के साथ, ऑपरेशन पेड़ में एक ड्रिल-डाउन के साथ शुरू होता है। MySQL के लिए, 100 एम पंक्तियों में लगभग 4 स्तरों का गहराई वाला बी + वृक्ष होगा। 3 गैर-पत्ते नोड्स (फिर से 16 केबी ब्लॉक) कैश किए जाएंगे (यदि वे पहले से नहीं थे) और पुन: उपयोग किया जाएगा। पोस्टग्रेज़ के लिए भी, यह कैशिंग शायद होता है। (मुझे पोस्टग्रेज़ नहीं पता।) फिर रेंज स्कैन शुरू होता है। MySQL के साथ यह बाकी ब्लॉक के माध्यम से चलता है। (अंगूठे का नियम: एक ब्लॉक में 100 पंक्तियां।) पोस्टग्रेस के लिए डिट्टो?

ब्लॉक के अंत में कुछ अलग होना पड़ता है। MySQL के लिए, अगले ब्लॉक का एक लिंक है। वह ब्लॉक (100 और पंक्तियों के साथ) डिस्क से लाया जाता है (यदि कैश नहीं किया जाता है)। बी-ट्री के लिए गैर-पत्ती नोड्स को फिर से घुमाने की आवश्यकता होती है। 2, शायद 3 स्तर अभी भी कैश किए गए हैं। मैं उम्मीद करता हूं कि डिस्क से केवल 1/10 के पंक्तियों तक पहुंचने के लिए एक और गैर-पत्ता नोड की आवश्यकता होगी। (10 के = 100 * 100) यही है, पोस्टग्रेस डिस्क को "ठंड" प्रणाली पर भी MySQL से 1% अधिक बार मार सकता है।

दूसरी ओर, यदि पंक्तियां इतनी मोटी हैं कि केवल 1 या 2 16 के ब्लॉक में फिट हो सकती हैं, तो "100" मैंने उपयोग किया है "2" और 1% शायद 50% हो जाता है। यही है, यदि आपके पास बड़ी पंक्तियां हैं तो यह "उत्तर" हो सकती है। क्या यह?

पोस्टग्रेज़ में ब्लॉक आकार क्या है? ध्यान दें कि उपरोक्त कई गणना ब्लॉक और डेटा के बीच सापेक्ष आकार पर निर्भर करती हैं। क्या यह एक जवाब हो सकता है?

निष्कर्ष: मैंने आपको 4 संभावित उत्तर दिए हैं। क्या आप इनमें से प्रत्येक को लागू करने या पुष्टि करने के लिए प्रश्न को बढ़ाना चाहते हैं? (माध्यमिक अनुक्रमित, बड़े पीके, माध्यमिक अनुक्रमित, बड़े पंक्तियाँ, ब्लॉक आकार के अकुशल इमारत के अस्तित्व, ...)

के बारे में प्राथमिक कुंजी

InnoDB के लिए अनुशेष, एक और बात नोट करने के लिए ... यह डेटा लोड करने से पहले तालिका की परिभाषा में PRIMARY KEY होना सर्वोत्तम है। LOAD DATA से पहले पीके आदेश में डेटा को सॉर्ट करना भी सबसे अच्छा है। PRIMARY KEY या UNIQUE कुंजी निर्दिष्ट किए बिना, InnoDB एक छुपा 6-बाइट पीके बनाता है; यह आमतौर पर उप-इष्टतम है।

Answer 3

MySQL और PostgreSQL वास्तव में तुलनीय नहीं हैं यहां Innodb तालिका डेटा स्टोर करने के लिए एक अनुक्रमणिका का उपयोग करता है (और द्वितीयक अनुक्रमणिका बस पाकी पर इंगित करता है)। यह सिंगल पंक्ति पकी लुकअप के लिए बहुत अच्छा है और बी + पेड़ के साथ, पकी फ़ील्ड पर रेंज क्वेरी के साथ ठीक है, लेकिन बाकी सब कुछ के लिए प्रदर्शन कमियां हैं।

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

मुझे लगता है कि btree का उपयोग किया जाता है क्योंकि यह सरल उपयोग मामले में उत्कृष्ट होता है: निम्न डेटा में कौन से राउज़ होते हैं? यह उदाहरण के लिए जीआईएन का एक बिल्डिंग ब्लॉक बन जाता है।

लेकिन यह सच नहीं है कि PostgreSQL बी + पेड़ का उपयोग नहीं कर सकता है। जीआईएसटी एक सामान्यीकृत प्रारूप में बी + ट्री इंडेक्स पर बनाया गया है। तो PostgreSQL आपको बी + पेड़ों का उपयोग करने का विकल्प देता है जहां वे काम में आते हैं।