मेरे पास 70 मिलियन रिकॉर्ड के साथ एक टेबल है और एक सूचकांक गायब है। मैं तालिका का बैक अप लेने और बैक अप तालिका पर इंडेक्स किए बिना इंडेक्स जोड़ने के लिए समय की गणना करना चाहता हूं।2 मिलियन रिकॉर्ड की एक तालिका पर एक इंडेक्स जोड़ना एक ही टेबल के रूप में दो लाख रिकॉर्ड के साथ धीमा होगा?
मैं बस सोच रहा हूं कि यह धीमा (रैखिक) से दोगुना होगा या यदि यह घातीय हो।
डेटाबेस: mysql 5.0
धन्यवाद एक बहुत
(अस्वीकरण: मैं MySQL पर कम से कम अनुभव है)
यह कहीं के बीच होना चाहिए।
पूरे ऑपरेशन की बिल्कुल कम जटिलता वह होगी जो केवल सभी रिकॉर्ड पढ़ने के दौरान दिखाई देगी, जो एक रैखिक प्रक्रिया है - O(n)। यह एक I/O बाध्य संचालन है और इसके बारे में बहुत कुछ नहीं किया जा सकता है - अधिकांश ओएस में आधुनिक कैशिंग सिस्टम मदद कर सकते हैं, लेकिन केवल एक डीबी में जो उपयोग में है और उपलब्ध स्मृति में फिट बैठता है।
अधिकांश एसक्यूएल इंजनों में, इंडेक्स बी-पेड़ की कुछ भिन्नता है। ऐसे पेड़ में एक रिकॉर्ड डालने की सीपीयू जटिलता लगभग O(log(n)) है, जहां n इसका आकार है। n रिकॉर्ड के लिए हमें O(n log(n)) की जटिलता मिलती है। ऑपरेशन की कुल जटिलता O(n log(n)) होना चाहिए।
बेशक, यह इतना आसान नहीं है। इंडेक्स पेड़ की कंप्यूटिंग वास्तव में सीपीयू-भारी नहीं है और चूंकि इंडेक्स पेज किसी भी आधुनिक सिस्टम पर रैम में फिट होना चाहिए, जब पेड़ को रीबैलेंस्ड नहीं किया जाता है तो एक नोड डालने का ऑपरेशनO(1) समय-समय पर होगा: एकल सूचकांक के एक पत्ता पृष्ठ को अद्यतन करने के लिए डिस्क ऑपरेशन।
चूंकि पेड़ को पुन: संतुलित किया जाता है, हालांकि, चीजें शायद थोड़ा अधिक जटिल होती हैं। एकाधिक इंडेक्स पृष्ठों को डिस्क पर ले जाना पड़ सकता है, इस प्रकार आवश्यक समय बढ़ाना। एक अनुमान के मुताबिक, मैं कहूंगा कि O(n log(n)) एक अच्छी शुरुआत है ...
हालांकि, यह कभी भी घातीय जटिलता के करीब कहीं नहीं आना चाहिए।
संपादित करें:
यह सिर्फ मेरे लिए हुआ है कि 70,000,000 बी पेड़ प्रविष्टियों नहीं हो सकता, वास्तव में, इन-मेमोरी कैश में फिट। यह पर भारी निर्भर करेगा अनुक्रमित किया जा रहा है। INTEGER कॉलम शायद ठीक होंगे, लेकिन TEXT कॉलम एक और कहानी पूरी तरह से हैं। यदि औसत फ़ील्ड लंबाई 100 बाइट्स है (उदा। HTTP लिंक या गैर-अंग्रेज़ी यूटीएफ -8 टेक्स्ट के 30 वर्ण) तो आपको इंडेक्स को स्टोर करने के लिए 7 जीबी से अधिक मेमोरी की आवश्यकता होगी।
निष्कर्ष: किसी
सूचकांक कैश में फिट बैठता है, तो सूचकांक के निर्माण के लिए एक एकल डीबी लेन-देन होना चाहिए, क्योंकि, यह मैं/हे बाध्य होगा और मोटे तौर पर सभी रिकॉर्ड है रैखिक पार्स किए जाने के लिए और फिर इंडेक्स इटेलसे को स्थायी भंडारण के लिए लिखा जाना चाहिए।
यदि सूचकांक कैश में फिट नहीं होता है, तो जटिलता बढ़ जाती है, क्योंकि इंडेक्स पर I/O प्रतीक्षा-समय प्रत्येक ऑपरेशन में स्वयं शामिल हो जाता है।
thkala अलग-अलग पंक्तियों डालने के लिए सच है क्या का वर्णन करता है, लेकिन जब एक नया सूचकांक बनाने, कोई उचित आरडीबीएमएस सिर्फ n आवेषण करना होगा, बल्कि यह सीधे पत्र-गांठ के साथ शुरू सूचकांक का निर्माण करेगी। यह प्रक्रिया लगभग निश्चित रूप से आईओ-बाउंड होगी।
तो, व्यावहारिक रूप से, पुनः अनुक्रमणित समय रैखिक होना चाहिए: कई बार रिकॉर्ड के लिए दोगुना होना चाहिए।
सच है, इंडेक्स का निर्माण एक ही लेनदेन होना चाहिए। समय जटिलता, हालांकि, इस बात पर निर्भर करेगी कि इंडेक्स पेड़ रैम में फिट होगा या नहीं। टेक्स्ट कॉलम पर 70,000,000 इंडेक्स प्रविष्टियां आसानी से कई जीबी इन-मेमोरी कैश भर सकती हैं ... – thkala
आपके उत्तर के लिए धन्यवाद! यह अब बहुत स्पष्ट है –