मैं डेटाबेस के लिए बहुत नया हूं, इसलिए मुझे माफ़ कर दो अगर यह एक मूर्ख सवाल है।डेटाबेस क्वेरी समय जटिलता
आधुनिक डेटाबेस में, यदि मैं पंक्ति तक पहुंचने के लिए एक इंडेक्स का उपयोग करता हूं, तो मेरा मानना है कि यह ओ (1) जटिलता होगी। लेकिन अगर मैं एक और कॉलम चुनने के लिए कोई प्रश्न करता हूं, तो क्या यह ओ (1) या ओ (एन) होगा? क्या डेटाबेस को सभी पंक्तियों के माध्यम से फिर से चलाना पड़ता है, या क्या यह प्रत्येक कॉलम के लिए एक क्रमबद्ध सूची बनाता है?
दरअसल, मुझे लगता है कि एक सूचकांक के आधार पर पहुंच ओ (लॉग (एन)) होगी, क्योंकि आप अभी भी अपने रिकॉर्ड प्राप्त करने के लिए बी-ट्री-एस्क्यू संगठन के माध्यम से खोज करेंगे।
आपके पास इंडेक्स हैं। क्लस्टर्ड इंडेक्स डिस्क पर भौतिक रूप से क्रमबद्ध होते हैं, आपके पास प्रति तालिका केवल एक हो सकती है। अव्यवस्थित सूचकांक तार्किक रूप से क्रमबद्ध होते हैं और आप उनमें से कई (सावधानीपूर्वक इसका दुरुपयोग न करने के लिए सावधान रह सकते हैं, यह लिखने के कार्यों को धीमा कर सकता है)। यदि आपके कॉलम पर कोई अनुक्रमणिका नहीं है तो मुझे विश्वास है कि यह पंक्ति विधि द्वारा अच्छी पुरानी पंक्ति है।
इंडेक्स प्रति कॉलम हैं, इसलिए यदि आप एक अनुक्रमित कॉलम पर एक क्लॉज का उपयोग करते हैं तो यह एक तथाकथित टेबलकेन करेगा जो ओ (एन) है।
अपने शाब्दिक प्रश्न का उत्तर देने के लिए, हाँ यदि कॉलम पर कोई अनुक्रमणिका नहीं है, तो डेटाबेस इंजन को सभी पंक्तियों को देखना होगा।
एकाधिक कॉलम द्वारा चयन किए जाने के अधिक दिलचस्प मामले में, इंडेक्स के साथ और बिना, स्थिति अधिक जटिल हो जाती है: यदि क्वेरी ऑप्टिमाइज़र इंडेक्स का उपयोग करना चुनता है, तो यह पहले इंडेक्स के आधार पर पंक्तियों का चयन करेगा और फिर शेष बाधाओं के साथ एक फ़िल्टर लागू करें। इस प्रकार ओ (पंक्तियों की संख्या) से दूसरे फ़िल्टरिंग ऑपरेशन को कम करने के लिए ओ (इंडेक्स द्वारा चयनित पंक्तियों की संख्या) को कम करना। इन दो संख्याओं के बीच अनुपात को चुनिंदाता कहा जाता है और यह चुनने के लिए कि कौन सी अनुक्रमणिका का उपयोग करना है, एक महत्वपूर्ण आंकड़ा कहा जाता है।
विभिन्न प्रकार के इंडेक्स, विभिन्न निष्पादन योजनाएं और विभिन्न डेटाबेस के लिए विभिन्न कार्यान्वयन हैं। संबंध डेटाबेस का अधिकांश कोड खोज-अनुकूलन एल्गोरिदम में है। आपके प्रश्न का कोई जवाब नहीं है। जब आप जानना चाहते हैं कि क्वेरी कैसे निष्पादित की जा रही है, तो आप निष्पादन योजना को देखने के लिए टूल का उपयोग कर सकते हैं।
सत्य है, लेकिन फिर भी एक अच्छा अनुमान (और वह क्या देख रहा है) है: ओ (लॉग (एन)) जब अनुक्रमित और ओ (एन) जब – Javier
यह सच नहीं है, लेकिन सूचकांक हमेशा प्रश्नों में सबसे सीमित कारक नहीं होते हैं।कुछ मामलों में आप किसी इंडेक्स का उपयोग करने के बीच अंतर नहीं देख सकते हैं या नहीं। – Paco
@Paco: निष्पादन योजना को देखने के लिए सबसे अच्छा टूल कौन सा है? – Miranda
मुझे जवाब नहीं पता है, लेकिन ध्यान रखें कि बड़े-ओ नोटेशन केवल आपको डेटा-सेट आकारों के प्रदर्शन का संकेत देता है जो मनमाने ढंग से बड़े होते हैं।
उदाहरण के लिए, डेटाबेस प्रदर्शन के लिए बाधा आमतौर पर डिस्क की तलाश करती है। इसलिए, कामकाजी डेटा-सेट स्मृति में रखा जा सकता है, तो प्रदर्शन में काफी वृद्धि हुई है। बिग-ओ नोटेशन आपको ऐसे अनुकूलन के बारे में कुछ नहीं बताएगा, क्योंकि वे केवल सीमित डेटा सेट के लिए प्रासंगिक हैं।
बी-पेड़ ओ (लॉगएन) उत्पन्न नहीं करते हैं, यह एक बाइनरी पेड़ की जटिलता है।
ए बी-ट्री का आयोजन किया जाता है जैसे कि इसमें प्रति नोड एक संपूर्ण ब्लॉक होता है, इस प्रकार एक नोड को एक बार आई/ओ ऑपरेशन मिलने पर एक संपूर्ण ब्लॉक पढ़ सकता है।
प्रति नोड मदों की संख्या = अवरुद्ध कारक (# रिकॉर्ड/ब्लॉक) {} BFR साथ, एक बी ट्री अनुकूलित खोज हे निकलेगा (लॉग BFR ÷ 2 +1 एन) मैं/हे आपरेशन के बजाय ओ (एन) I/O संचालन कुंजी द्वारा रिकॉर्ड की मांग।
क्षमा करें अगर मैं आपको नीले रंग से पूछता हूं, लेकिन क्या कोई ऐसी किताब है जहां आप मुझे सुझाव दे सकते हैं कि मुझे इस तरह की सूचनाएं मिल सकती हैं? – jackb
ध्यान रखें कि किसी भी निरंतर के लिए ओ (log_k n) = O (लॉग n/log k) = O (लॉग n), इसलिए तकनीकी रूप से, बी-ट्री लुकअप ओ (लॉग एन) समय लेते हैं। हालांकि, वे बाइनरी पेड़ों की तुलना में बहुत तेज हैं, लेकिन केवल स्थिर कारक से। – cfstras
हैश इंडेक्स के अलावा, जहां यह ओ (बाल्टी-चेन-लम्बाई) –