डेटाबेस में क्वेरी खोज के लिए एल्गोरिदम क्या है?

Question

शुभ दिन हर कोई, मैं वर्तमान में खोज एल्गोरिदम अनुकूलन पर शोध कर रहा हूं।

अभी तक, मैं डेटाबेस पर शोध कर रहा हूं।

डेटाबेस डब्ल्यू/एसक्यूएल समर्थन में।

मैं एक विशिष्ट तालिका के लिए क्वेरी लिख सकता हूं।

1. तालिका 1 से संख्या का चयन करें जहां नाम = "परीक्षण";
2. * तालिका 1 से चुनें जहां नाम = "परीक्षण";

1 तालिका 1 से संख्या की खोज करता है जहां से नाम परीक्षण है और 2 नाम टेस्ट के लिए सभी कॉलम खोजता है।

मैं समारोह की अवधारणा को समझता हूं हालांकि मुझे सीखने में क्या दिलचस्पी है कि खोज का दृष्टिकोण क्या है?

क्या यह केवल सादा रैखिक खोज है, जहां पहली इंडेक्स से एनएच इंडेक्स तक यह तब तक पकड़ लेगा जब तक यह स्थिति सच है क्योंकि इस स्थिति में ओ (एन) गति है या क्या इसका अनूठा एल्गोरिदम है जो इसकी प्रक्रिया को गति देता है?

Answer 1

बहुत अच्छा प्रश्न है, लेकिन यह अपने तालिका की संरचना के आधार पर कई जवाब हो सकता है और कैसे सामान्यीकृत है ...

आम तौर पर एक SELECT क्वेरी डीबीएमएस तालिका प्रकार के एक seacrh प्रदर्शन करने के लिए (यह mergesort का उपयोग करता है क्योंकि यह एल्गोरिदम डिस्क में I/O के लिए अच्छा है, क्विकॉर्ट नहीं) तो इंडेक्स (यदि तालिका में है) के आधार पर यह सिर्फ संख्याओं से मेल खाता है, लेकिन यदि संरचना अधिक जटिल है तो डीबीएमएस एक पेड़ में खोज कर सकता है, लेकिन यह बहुत गहरा है, मुझे अपने नोट्स में फिर से शोध करने दो।

मैं एसक्यूएल सर्वर 2008 में ऐसा करने के तरीके में क्वेरी निष्पादन योजना, here is an example को सक्रिय करने की अनुशंसा करता हूं। और फिर WHERE क्लॉज के साथ अपना चयन कथन निष्पादित करें और आप डीबीएमएस के अंदर क्या हो रहा है उसे समझने में सक्षम होंगे।

Answer 2

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

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

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

अन्य प्रकार के इंडेक्स हैं, लेकिन मुझे लगता है कि आपको विचार मिलता है - डुप्लिकेट डेटा और इसे व्यवस्थित करने के लिए तेज़ी से व्यवस्थित करें।

एक बड़े डेटाबेस पर, इंडेक्स एक जटिल क्वेरी के लिए संभवतः दिनों के एक सेकंड के एक अंश का इंतजार करने के बीच अंतर बनाते हैं।

बीटीडब्ल्यू- बी पेड़ डेटा संरचना को समझने में आसान और आसान नहीं है, और ट्रैवर्सल एल्गोरिदम भी जटिल है। इसके अलावा, ट्रैवर्सल आपके द्वारा प्राप्त किए जाने वाले अधिकांश कोड की तुलना में भी अधिक है, क्योंकि डेटाबेस में वे डिस्क से डेटा के हिस्सों को लगातार लोड/अनलोड कर रहे हैं और इसे स्मृति में प्रबंधित करते हैं, और यह कोड को काफी महत्व देता है। लेकिन, अगर आप binary search trees से परिचित हैं, तो मुझे लगता है कि आप अवधारणा को पर्याप्त रूप से समझते हैं।

Answer 3

अच्छा, यह इस बात पर निर्भर करता है कि डेटा कैसे संग्रहीत किया जाता है और आप क्या करने की कोशिश कर रहे हैं।

• जैसा कि पहले ही संकेत दिया गया है, प्रविष्टियों को बनाए रखने के लिए एक सामान्य संरचना B+ tree है। पेड़ डिस्क के लिए अच्छी तरह अनुकूलित है क्योंकि वास्तविक डेटा केवल पत्तियों में संग्रहीत होता है - और चाबियाँ आंतरिक नोड्स में संग्रहीत होती हैं। यह आमतौर पर डिस्क की बहुत छोटी संख्या की अनुमति देता है क्योंकि पेड़ के शीर्ष k स्तर रैम में संग्रहीत किए जा सकते हैं, और केवल कुछ नीचे के स्तर डिस्क पर संग्रहीत किए जाएंगे और प्रत्येक के लिए डिस्क पढ़ने की आवश्यकता होगी।
• अन्य विकल्प hash table है। आप स्मृति (रैम) में "पॉइंटर्स" की एक सरणी में बनाए रखते हैं - ये पॉइंटर्स डिस्क पता इंगित करते हैं, जिसमें एक बाल्टी होती है जिसमें संबंधित हैश मान वाले सभी प्रविष्टियां शामिल होती हैं। इस विधि का उपयोग करके, आपको केवल O(1) डिस्क एक्सेस (जो आमतौर पर डेटा बेस से निपटने पर बाधा होती है) की आवश्यकता होती है, इसलिए यह अपेक्षाकृत तेज़ होना चाहिए।
  हालांकि, एक हैश तालिका कुशल सीमा प्रश्नों की अनुमति नहीं देती है (जिसे बी + पेड़ में कुशलता से किया जा सकता है)।

ऊपर के सभी का नुकसान यह एक एकल कुंजी की आवश्यकता है कि है - यानी अगर हैश तालिका या B + ट्री संबंध के क्षेत्र "आईडी" के अनुसार बनाया गया है, और फिर आप "कुंजी के अनुसार खोज "- यह बेकार हो जाता है।
यदि आप संबंध के सभी क्षेत्रों के लिए तेज़ खोज की गारंटी देना चाहते हैं - आपको कई संरचनाओं की आवश्यकता होगी, प्रत्येक एक अलग कुंजी के अनुसार - जो बहुत मेमोरी कुशल नहीं है।

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