डाटाबेस इंडेक्स और उनके बिग-ओ नोटेशन

Question

मैं बिग-ओ नोटेशन के संदर्भ में डेटाबेस इंडेक्स के प्रदर्शन को समझने की कोशिश कर रहा हूं। इसके बारे में ज्यादा जानने के बिना, मुझे लगता है कि होगा:

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

क्या यह आम तौर पर सही है? प्राथमिक कुंजी पर पूछताछ कभी ओ (1) से खराब प्रदर्शन देगी? मेरी विशिष्ट चिंता SQLite के लिए है, लेकिन मुझे यह जानने में दिलचस्पी होगी कि यह अलग-अलग डेटाबेस के बीच कितनी सीमा भिन्न है।

Answer 1

अधिकांश रिलेशनल डेटाबेस बी-पेड़ के रूप में सूचकांक संरचनाओं को ढंकते हैं।

यदि किसी तालिका में क्लस्टरिंग इंडेक्स है, तो डेटा पेज बी-पेड़ के पत्ती नोड्स के रूप में संग्रहीत किए जाते हैं। अनिवार्य रूप से, क्लस्टरिंग सूचकांक तालिका बन जाता है।

टेबल क्लस्टरिंग इंडेक्स के लिए टेबल के लिए, तालिका के डेटा पेज एक ढेर में संग्रहीत होते हैं। कोई भी गैर-क्लस्टर सूचकांक बी-पेड़ हैं जहां बी-पेड़ का पत्ता नोड ढेर में एक विशेष पृष्ठ की पहचान करता है।

एक बी पेड़ के सबसे ज्यादा मामले ऊंचाई है हे (लॉग एन), और के बाद से एक खोज ऊंचाई पर निर्भर है, बी पेड़ लुकअप (औसतन) की तरह कुछ में चला

ओ ( _{लॉग इन करें टी} एन)

जहां टी न्यूनतम कारक है (प्रत्येक नोड में कम से कम टी -1 कुंजी और अधिक से अधिक 2 * टी होना आवश्यक है * -1 कुंजी (जैसे, 2 * टी * बच्चों)।

जिस तरह से मैं इसे समझता हूं।

और अलग-अलग डेटाबेस सिस्टम, हूड के तहत विभिन्न डेटा संरचनाओं का अच्छी तरह से उपयोग कर सकते हैं।

और यदि क्वेरी इंडेक्स का उपयोग नहीं करती है, तो खोज डेटा पृष्ठों वाले ढेर या बी-पेड़ पर एक पुनरावृत्ति है।

यदि सूचकांक प्रयुक्त क्वेरी को संतुष्ट कर सकता है तो खोज थोड़ा सस्ता है; अन्यथा, स्मृति में संबंधित डेटापेज लाने के लिए एक लुकसाइड आवश्यक है।

Answer 2

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

यदि कोई अनुक्रमणिका नहीं है, तो, हाँ, यह ओ (एन) है।

Answer 3

आप एक ही कॉलम का चयन करते हैं आप तो

• प्राथमिक या unqiue हो जाएगा हे (लॉग एन) के लिए खोज: यह एक बी-वृक्ष खोज
• गैर-अद्वितीय सूचकांक भी हे (लॉग n है) + एक सा: यह एक बी-वृक्ष खोज
• कोई सूचकांक = हे (एन)

आप एक और "स्रोत" से जानकारी की आवश्यकता होती है (सूचकांक चौराहे, बुकमार्क/कुंजी देखने आदि) है सूचकांक है, क्योंकि गैर कवरिंग, तो आप ओ (एन + लॉग हो सकता है एन) या ओ (लॉग एन + लॉग एन + लॉग एन) एकाधिक इंडेक्स हिट + इंटरमीडिएट सॉर्टिंग के कारण।

तो आंकड़े बताते हैं कि आप पंक्तियों का एक उच्च% की आवश्यकता होती है (उदाहरण के लिए बहुत चयनात्मक नहीं इंडेक्स) तो सूचकांक नजरअंदाज किया जा सकता है और एक स्कैन बन = हे (एन)

Answer 4

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

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

Answer 5

यह आपकी क्वेरी पर निर्भर करता है।

• रूप Column = Value की एक शर्त एक हैश आधारित सूचकांक है, जो हे (1) देखने का समय है के उपयोग की अनुमति देता है। हालांकि, many databases, including SQLite, do not support them।
• एक शर्त संबंधपरक ऑपरेटर का उपयोग कर (<, >, <=, >=) एक आदेश दिया सूचकांक, आम तौर पर एक द्विआधारी पेड़ के साथ लागू किया है, जो हे (लॉग एन) समय देखने है का उपयोग कर सकते हैं।
• अधिक जटिल अभिव्यक्तियां जो इंडेक्स का उपयोग नहीं कर सकती हैं, ओ (एन) समय की आवश्यकता होती है।

के बाद से आप मुख्य रूप से SQLite में रुचि रखते हैं, तो आप अपने Query Optimizer Overview जो और अधिक विस्तार कैसे अनुक्रमित चयन किया जाता है में बताते हैं पढ़ने के लिए चाहते हो सकता है।