ஹே ஹப்ர்! கட்டுரையின் மொழிபெயர்ப்பை உங்கள் கவனத்திற்கு முன்வைக்கிறேன்
தொடர்புடைய தரவுத்தளங்களுக்கு வரும்போது, ஏதோ காணவில்லை என்று என்னால் நினைக்க முடியாது. அவை எல்லா இடங்களிலும் பயன்படுத்தப்படுகின்றன. சிறிய மற்றும் பயனுள்ள SQLite முதல் சக்திவாய்ந்த டெராடேட்டா வரை பல்வேறு தரவுத்தளங்கள் உள்ளன. ஆனால் தரவுத்தளம் எவ்வாறு செயல்படுகிறது என்பதை விளக்கும் சில கட்டுரைகள் மட்டுமே உள்ளன. "howdoesarelationaldatabasework" ஐப் பயன்படுத்தி நீங்களே தேடலாம், எவ்வளவு சில முடிவுகள் உள்ளன என்பதைப் பார்க்கலாம். மேலும், இந்த கட்டுரைகள் குறுகியவை. நீங்கள் சமீபத்திய பரபரப்பான தொழில்நுட்பங்களை (BigData, NoSQL அல்லது JavaScript) தேடுகிறீர்களானால், அவை எவ்வாறு செயல்படுகின்றன என்பதை விளக்கும் ஆழமான கட்டுரைகளைக் காணலாம்.
பல்கலைக்கழகப் படிப்புகள், ஆய்வுக் கட்டுரைகள் மற்றும் புத்தகங்களுக்கு வெளியே விவரிக்க முடியாத வகையில் தொடர்புடைய தரவுத்தளங்கள் மிகவும் பழமையானவை மற்றும் மிகவும் சலிப்பை ஏற்படுத்துகின்றனவா?
டெவலப்பராக, எனக்குப் புரியாத ஒன்றைப் பயன்படுத்துவதை நான் வெறுக்கிறேன். தரவுத்தளங்கள் 40 ஆண்டுகளுக்கும் மேலாக பயன்படுத்தப்பட்டிருந்தால், அதற்கு ஒரு காரணம் இருக்க வேண்டும். பல ஆண்டுகளாக, நான் ஒவ்வொரு நாளும் பயன்படுத்தும் இந்த விசித்திரமான கருப்பு பெட்டிகளை உண்மையாக புரிந்து கொள்ள நூற்றுக்கணக்கான மணிநேரங்களை செலவிட்டுள்ளேன். தொடர்புடைய தரவுத்தளங்கள் மிகவும் சுவாரஸ்யமானது, ஏனென்றால் அவை பயனுள்ள மற்றும் மீண்டும் பயன்படுத்தக்கூடிய கருத்துகளின் அடிப்படையில். நீங்கள் ஒரு தரவுத்தளத்தைப் புரிந்துகொள்வதில் ஆர்வமாக இருந்தால், ஆனால் இந்த பரந்த தலைப்பை ஆராய்வதற்கான நேரமோ அல்லது விருப்பமோ உங்களுக்கு இல்லை என்றால், இந்த கட்டுரையை நீங்கள் அனுபவிக்க வேண்டும்.
இந்தக் கட்டுரையின் தலைப்பு வெளிப்படையாக இருந்தாலும், இந்த கட்டுரையின் நோக்கம் தரவுத்தளத்தை எவ்வாறு பயன்படுத்துவது என்பதைப் புரிந்துகொள்வது அல்ல. எனவே, எளிய இணைப்பு கோரிக்கை மற்றும் அடிப்படை வினவல்களை எழுதுவது எப்படி என்பதை நீங்கள் ஏற்கனவே அறிந்திருக்க வேண்டும் ரா; இல்லையெனில் இந்தக் கட்டுரை உங்களுக்குப் புரியாமல் போகலாம். நீங்கள் தெரிந்து கொள்ள வேண்டிய ஒரே விஷயம், மற்றவற்றை நான் விளக்குகிறேன்.
அல்காரிதம்களின் நேர சிக்கலானது (BigO) போன்ற சில கணினி அறிவியல் அடிப்படைகளுடன் தொடங்குவேன். உங்களில் சிலர் இந்த கருத்தை வெறுக்கிறீர்கள் என்று எனக்குத் தெரியும், ஆனால் அது இல்லாமல் தரவுத்தளத்தில் உள்ள நுணுக்கங்களை உங்களால் புரிந்து கொள்ள முடியாது. இது ஒரு பெரிய தலைப்பு என்பதால், நான் கவனம் செலுத்துகிறேன் நான் நினைப்பது முக்கியமானது: தரவுத்தளம் எவ்வாறு செயல்படுகிறது எஸ்கியூஎல் விசாரணை. நான் தான் அறிமுகம் செய்கிறேன் அடிப்படை தரவுத்தள கருத்துக்கள்அதனால் கட்டுரையின் முடிவில் என்ன நடக்கிறது என்பது பற்றிய யோசனை உங்களுக்கு இருக்கும்.
இது நிறைய வழிமுறைகள் மற்றும் தரவு கட்டமைப்புகளை உள்ளடக்கிய நீண்ட மற்றும் தொழில்நுட்பக் கட்டுரை என்பதால், அதைப் படிக்க உங்கள் நேரத்தை ஒதுக்குங்கள். சில கருத்துக்கள் புரிந்து கொள்ள கடினமாக இருக்கலாம்; நீங்கள் அவற்றைத் தவிர்த்து, பொதுவான யோசனையைப் பெறலாம்.
உங்களில் அதிக அறிவுள்ளவர்களுக்கு, இந்த கட்டுரை 3 பகுதிகளாக பிரிக்கப்பட்டுள்ளது:
- குறைந்த-நிலை மற்றும் உயர்-நிலை தரவுத்தள கூறுகளின் கண்ணோட்டம்
- வினவல் மேம்படுத்தல் செயல்முறையின் கண்ணோட்டம்
- பரிவர்த்தனை மற்றும் பஃபர் பூல் மேலாண்மை பற்றிய கண்ணோட்டம்
அடிப்படைகளுக்குத் திரும்பு
பல ஆண்டுகளுக்கு முன்பு (ஒரு விண்மீன் மண்டலத்தில், வெகு தொலைவில்...), டெவலப்பர்கள் தாங்கள் குறியிடும் செயல்பாடுகளின் எண்ணிக்கையை சரியாக அறிந்து கொள்ள வேண்டும். அவர்கள் தங்கள் மெதுவான கணினிகளின் CPU மற்றும் நினைவகத்தை வீணடிக்க முடியாததால், அவர்களின் அல்காரிதம்கள் மற்றும் தரவு கட்டமைப்புகளை இதயப்பூர்வமாக அறிந்திருந்தனர்.
இந்த பகுதியில், தரவுத்தளத்தைப் புரிந்துகொள்வதற்கு அவசியமான சில கருத்துகளை நான் உங்களுக்கு நினைவூட்டுகிறேன். கருத்தையும் அறிமுகப்படுத்துகிறேன் தரவுத்தள அட்டவணை.
O(1) vs O(n2)
இப்போதெல்லாம், பல டெவலப்பர்கள் அல்காரிதம்களின் நேர சிக்கலைப் பற்றி கவலைப்படுவதில்லை... அவர்கள் சொல்வது சரிதான்!
ஆனால் நீங்கள் நிறைய தரவுகளைக் கையாளும் போது (நான் ஆயிரக்கணக்கில் பேசவில்லை) அல்லது மில்லி விநாடிகளில் நீங்கள் சிரமப்படுகிறீர்கள் என்றால், இந்தக் கருத்தைப் புரிந்துகொள்வது முக்கியமானதாகிறது. நீங்கள் கற்பனை செய்வது போல், தரவுத்தளங்கள் இரண்டு சூழ்நிலைகளையும் சமாளிக்க வேண்டும்! புள்ளியைப் பெறுவதற்குத் தேவையான நேரத்தை விட நான் உங்களைச் செலவிட மாட்டேன். இது செலவு அடிப்படையிலான தேர்வுமுறையின் கருத்தை பின்னர் புரிந்துகொள்ள உதவும் (கட்டண சார்ந்த தேர்வுமுறை).
கருத்து
அல்காரிதத்தின் நேர சிக்கலானது கொடுக்கப்பட்ட தரவுத் தொகைக்கு ஒரு அல்காரிதம் முடிக்க எவ்வளவு நேரம் ஆகும் என்பதைப் பார்க்கப் பயன்படுகிறது. இந்த சிக்கலை விவரிக்க, நாம் பெரிய O கணிதக் குறியீட்டைப் பயன்படுத்துகிறோம். கொடுக்கப்பட்ட எண்ணிக்கையிலான உள்ளீடுகளுக்கு ஒரு அல்காரிதத்திற்கு எத்தனை செயல்பாடுகள் தேவை என்பதை விவரிக்கும் செயல்பாட்டுடன் இந்த குறியீடு பயன்படுத்தப்படுகிறது.
எடுத்துக்காட்டாக, "இந்த அல்காரிதம் சிக்கலான O(some_function())" என்று நான் கூறும்போது, குறிப்பிட்ட அளவு தரவைச் செயலாக்க அல்காரிதத்திற்கு சில_function(a_certain_amount_of_data) செயல்பாடுகள் தேவை என்று அர்த்தம்.
இவ்வாறு இது முக்கியமான தரவுகளின் அளவு அல்ல **, இல்லையெனில் ** தரவு அளவை அதிகரிப்பதன் மூலம் செயல்பாடுகளின் எண்ணிக்கை எவ்வாறு அதிகரிக்கிறது. நேர சிக்கலானது சரியான எண்ணிக்கையிலான செயல்பாடுகளை வழங்காது, ஆனால் செயல்படுத்தும் நேரத்தை மதிப்பிடுவதற்கான சிறந்த வழியாகும்.
இந்த வரைபடத்தில், பல்வேறு வகையான அல்காரிதம் நேரச் சிக்கல்களுக்கான உள்ளீட்டுத் தரவின் எண்ணிக்கை மற்றும் செயல்பாடுகளின் எண்ணிக்கையைக் காணலாம். அவற்றைக் காட்ட மடக்கை அளவைப் பயன்படுத்தினேன். வேறு வார்த்தைகளில் கூறுவதானால், தரவுகளின் அளவு விரைவாக 1 முதல் 1 பில்லியனாக அதிகரிக்கிறது. அதை நாம் பார்க்கலாம்:
- O(1) அல்லது நிலையான சிக்கலான தன்மை மாறாமல் இருக்கும் (இல்லையெனில் அது நிலையான சிக்கலானது என்று அழைக்கப்படாது).
- O(பதிவு(n)) பில்லியன் கணக்கான தரவுகளுடன் கூட குறைவாகவே உள்ளது.
- மிக மோசமான சிரமம் - O(n2), செயல்பாடுகளின் எண்ணிக்கை வேகமாக வளரும்.
- மற்ற இரண்டு சிக்கல்களும் விரைவாக அதிகரிக்கின்றன.
உதாரணங்கள்
சிறிய அளவிலான தரவுகளுடன், O(1) மற்றும் O(n2) ஆகியவற்றுக்கு இடையேயான வேறுபாடு மிகக் குறைவு. எடுத்துக்காட்டாக, உங்களிடம் 2000 உறுப்புகளைச் செயலாக்க வேண்டிய அல்காரிதம் இருப்பதாக வைத்துக்கொள்வோம்.
- O(1) அல்காரிதம் உங்களுக்கு 1 செயல்பாட்டிற்கு செலவாகும்
- O(log(n)) அல்காரிதம் உங்களுக்கு 7 செயல்பாடுகளைச் செலவழிக்கும்
- O(n) அல்காரிதம் உங்களுக்கு 2 செயல்பாடுகளைச் செய்யும்
- O(n*log(n)) அல்காரிதம் உங்களுக்கு 14 செயல்பாடுகளைச் செலவழிக்கும்
- O(n2) அல்காரிதம் உங்களுக்கு 4 செயல்பாடுகளைச் செய்யும்
O(1) மற்றும் O(n2) ஆகியவற்றுக்கு இடையேயான வித்தியாசம் பெரியதாகத் தெரிகிறது (4 மில்லியன் செயல்பாடுகள்) ஆனால் நீங்கள் அதிகபட்சமாக 2 ms வரை இழப்பீர்கள், உங்கள் கண்களை இமைக்கும் நேரம். உண்மையில், நவீன செயலிகள் செயலாக்க முடியும்
நான் சொன்னது போல், பெரிய அளவிலான தரவுகளுடன் பணிபுரியும் போது இந்த கருத்தை அறிந்து கொள்வது இன்னும் முக்கியம். இந்த முறை அல்காரிதம் 1 உறுப்புகளை செயலாக்க வேண்டும் என்றால் (இது தரவுத்தளத்திற்கு அதிகம் இல்லை):
- O(1) அல்காரிதம் உங்களுக்கு 1 செயல்பாட்டிற்கு செலவாகும்
- O(log(n)) அல்காரிதம் உங்களுக்கு 14 செயல்பாடுகளைச் செலவழிக்கும்
- O(n) அல்காரிதம் உங்களுக்கு 1 செயல்பாடுகளைச் செய்யும்
- O(n*log(n)) அல்காரிதம் உங்களுக்கு 14 செயல்பாடுகளைச் செலவழிக்கும்
- O(n2) அல்காரிதம் உங்களுக்கு 1 செயல்பாடுகளைச் செலவழிக்கும்
நான் கணிதத்தைச் செய்யவில்லை, ஆனால் O(n2) அல்காரிதம் மூலம் உங்களுக்கு ஒரு காபி (இரண்டு கூட!) குடிக்க நேரம் இருக்கிறது என்று கூறுவேன். டேட்டா வால்யூமில் மற்றொரு 0ஐச் சேர்த்தால், சிறிது நேரம் தூங்குவதற்கு உங்களுக்கு நேரம் கிடைக்கும்.
இன்னும் ஆழமாக செல்வோம்
குறிப்பு:
- ஒரு நல்ல ஹாஷ் டேபிள் தேடுதல் O(1) இல் ஒரு உறுப்பைக் கண்டறியும்.
- நன்கு சமநிலையான மரத்தைத் தேடுவது O(log(n)) இல் முடிவுகளை உருவாக்குகிறது.
- வரிசையைத் தேடுவது O(n) இல் முடிவுகளை உருவாக்குகிறது.
- சிறந்த வரிசையாக்க வழிமுறைகள் O(n*log(n)) சிக்கலான தன்மையைக் கொண்டுள்ளன.
- மோசமான வரிசையாக்க அல்காரிதம் O(n2) சிக்கலைக் கொண்டுள்ளது.
குறிப்பு: பின்வரும் பகுதிகளில் இந்த அல்காரிதம்கள் மற்றும் தரவு கட்டமைப்புகளைப் பார்ப்போம்.
அல்காரிதம் நேர சிக்கலில் பல வகைகள் உள்ளன:
- சராசரி வழக்கு காட்சி
- சிறந்த சூழ்நிலை
- மற்றும் மோசமான சூழ்நிலை
நேர சிக்கலானது பெரும்பாலும் மோசமான சூழ்நிலையாகும்.
நான் அல்காரிதத்தின் நேர சிக்கலைப் பற்றி மட்டுமே பேசினேன், ஆனால் சிக்கலானது இதற்கும் பொருந்தும்:
- அல்காரிதம் நினைவக நுகர்வு
- வட்டு I/O நுகர்வு அல்காரிதம்
நிச்சயமாக, n2 ஐ விட மோசமான சிக்கல்கள் உள்ளன, எடுத்துக்காட்டாக:
- n4: இது பயங்கரமானது! குறிப்பிடப்பட்ட சில அல்காரிதம்கள் இந்த சிக்கலைக் கொண்டுள்ளன.
- 3n: இது இன்னும் மோசமானது! இந்த கட்டுரையின் நடுவில் நாம் காணும் வழிமுறைகளில் ஒன்று இந்த சிக்கலான தன்மையைக் கொண்டுள்ளது (இது உண்மையில் பல தரவுத்தளங்களில் பயன்படுத்தப்படுகிறது).
- காரணியாலான n: சிறிய அளவிலான தரவுகளுடன் கூட உங்கள் முடிவுகளைப் பெற முடியாது.
- nn: இந்த சிக்கலை நீங்கள் சந்தித்தால், இது உண்மையில் உங்கள் செயல்பாட்டுத் துறைதானா என்று நீங்களே கேட்டுக்கொள்ளுங்கள்...
குறிப்பு: பெரிய O பதவிக்கான உண்மையான வரையறையை நான் உங்களுக்கு வழங்கவில்லை, ஒரு யோசனை. இந்த கட்டுரையை நீங்கள் படிக்கலாம்
MergeSort
சேகரிப்பை வரிசைப்படுத்த வேண்டியிருக்கும் போது நீங்கள் என்ன செய்வீர்கள்? என்ன? நீங்கள் sort() செயல்பாட்டை அழைக்கிறீர்கள்... சரி, நல்ல பதில்... ஆனால் ஒரு தரவுத்தளத்திற்கு, இந்த sort() செயல்பாடு எவ்வாறு செயல்படுகிறது என்பதை நீங்கள் புரிந்து கொள்ள வேண்டும்.
பல நல்ல வரிசையாக்க வழிமுறைகள் உள்ளன, எனவே நான் மிக முக்கியமானவற்றில் கவனம் செலுத்துகிறேன்: ஒன்றிணைக்கும் வகை. இப்போது தரவை வரிசைப்படுத்துவது ஏன் பயனுள்ளதாக இருக்கும் என்பதை நீங்கள் புரிந்து கொள்ளாமல் இருக்கலாம், ஆனால் வினவல் தேர்வுமுறை பகுதிக்குப் பிறகு நீங்கள் புரிந்து கொள்ள வேண்டும். மேலும், ஒன்றிணைக்கும் வரிசையைப் புரிந்துகொள்வது, பின்னர் அழைக்கப்படும் பொதுவான தரவுத்தள இணைப்பின் செயல்பாட்டைப் புரிந்துகொள்ள உதவும் ஒன்றாக்க சேர (இணைப்பு சங்கம்).
ஒன்றிணைக்கவும்
பல பயனுள்ள வழிமுறைகளைப் போலவே, ஒன்றிணைக்கும் வரிசையும் ஒரு தந்திரத்தை சார்ந்துள்ளது: N/2 அளவுள்ள 2 வரிசைப்படுத்தப்பட்ட வரிசைகளை ஒரு N-உறுப்பு வரிசைப்படுத்தப்பட்ட வரிசையாக இணைப்பது N செயல்பாடுகளுக்கு மட்டுமே செலவாகும். இந்த செயல்பாடு ஒன்றிணைத்தல் என்று அழைக்கப்படுகிறது.
ஒரு எளிய உதாரணத்துடன் இதன் பொருள் என்ன என்று பார்ப்போம்:
இறுதி வரிசைப்படுத்தப்பட்ட 8-உறுப்பு வரிசையை உருவாக்க, நீங்கள் 2 4-உறுப்பு வரிசைகளை ஒருமுறை மட்டுமே மீண்டும் செய்ய வேண்டும் என்பதை இந்த எண்ணிக்கை காட்டுகிறது. இரண்டு 4-உறுப்பு அணிவரிசைகளும் ஏற்கனவே வரிசைப்படுத்தப்பட்டதால்:
- 1) நீங்கள் இரண்டு தற்போதைய கூறுகளை இரண்டு அணிகளில் ஒப்பிடுகிறீர்கள் (ஆரம்பத்தில் தற்போதைய = முதலில்)
- 2) பின்னர் அதை 8 உறுப்பு வரிசையில் வைக்க சிறிய ஒன்றை எடுக்கவும்
- 3) நீங்கள் சிறிய உறுப்பை எடுத்த வரிசையில் அடுத்த உறுப்புக்குச் செல்லவும்
- வரிசைகளில் ஒன்றின் கடைசி உறுப்பை அடையும் வரை 1,2,3 ஐ மீண்டும் செய்யவும்.
- மற்ற வரிசையின் மீதமுள்ள கூறுகளை 8 உறுப்பு வரிசையில் வைக்க அவற்றை எடுத்துக் கொள்ளுங்கள்.
4-உறுப்பு வரிசைகள் இரண்டும் வரிசைப்படுத்தப்பட்டிருப்பதால் இது வேலை செய்கிறது, எனவே நீங்கள் அந்த அணிகளில் "திரும்பிச் செல்ல" வேண்டியதில்லை.
இப்போது நாம் தந்திரத்தைப் புரிந்துகொண்டோம், இணைப்பிற்கான எனது சூடோகோட் இதோ:
array mergeSort(array a)
if(length(a)==1)
return a[0];
end if
//recursive calls
[left_array right_array] := split_into_2_equally_sized_arrays(a);
array new_left_array := mergeSort(left_array);
array new_right_array := mergeSort(right_array);
//merging the 2 small ordered arrays into a big one
array result := merge(new_left_array,new_right_array);
return result;
Merge sort ஆனது ஒரு சிக்கலைச் சிறிய சிக்கல்களாக உடைத்து, அதன் பிறகு அசல் சிக்கலின் முடிவைப் பெற சிறிய சிக்கல்களின் முடிவுகளைக் கண்டறியும் (குறிப்பு: இந்த வகை அல்காரிதம் பிரித்து வெற்றி என்று அழைக்கப்படுகிறது). இந்த அல்காரிதம் உங்களுக்கு புரியவில்லை என்றால், கவலைப்பட வேண்டாம்; முதல் முறை பார்த்தபோது எனக்குப் புரியவில்லை. இது உங்களுக்கு உதவுமானால், இந்த அல்காரிதத்தை இரண்டு-கட்ட வழிமுறையாக நான் பார்க்கிறேன்:
- பிரிவு கட்டம், வரிசை சிறிய அணிகளாக பிரிக்கப்பட்டுள்ளது
- வரிசையாக்க கட்டம் என்பது சிறிய வரிசைகளை ஒன்றிணைத்து (யூனியனைப் பயன்படுத்தி) ஒரு பெரிய வரிசையை உருவாக்குகிறது.
பிரிவு கட்டம்
பிரிவு கட்டத்தில், வரிசை 3 படிகளில் ஒற்றை அணிகளாக பிரிக்கப்பட்டுள்ளது. படிகளின் முறையான எண்ணிக்கை log(N) (N=8, log(N) = 3 என்பதால்).
எனக்கு இது எப்படி தெரியும்?
நான் மேதை! ஒரு வார்த்தையில் - கணிதம். யோசனை என்னவென்றால், ஒவ்வொரு அடியும் அசல் வரிசையின் அளவை 2 ஆல் வகுக்கிறது. படிகளின் எண்ணிக்கை என்பது அசல் வரிசையை இரண்டாகப் பிரிக்கக்கூடிய எண்ணிக்கையாகும். இது மடக்கையின் சரியான வரையறை (அடிப்படை 2).
வரிசைப்படுத்தும் கட்டம்
வரிசையாக்க கட்டத்தில், நீங்கள் ஒற்றை (ஒற்றை உறுப்பு) வரிசைகளுடன் தொடங்குகிறீர்கள். ஒவ்வொரு அடியிலும் நீங்கள் பல இணைப்புச் செயல்பாடுகளைப் பயன்படுத்துகிறீர்கள் மற்றும் மொத்தச் செலவு N = 8 செயல்பாடுகள்:
- முதல் கட்டத்தில், உங்களிடம் 4 இணைப்புகள் உள்ளன, அவை ஒவ்வொன்றும் 2 செயல்பாடுகள் ஆகும்
- இரண்டாவது கட்டத்தில், 2 இணைப்புகள் உள்ளன, அவை ஒவ்வொன்றும் 4 செயல்பாடுகளைச் செய்ய வேண்டும்
- மூன்றாவது கட்டத்தில், 1 செயல்பாடுகளைச் செய்ய வேண்டிய 8 இணைப்பு உள்ளது
பதிவு(N) படிகள் இருப்பதால், மொத்த செலவு என் * log(N) செயல்பாடுகள்.
ஒன்றிணைக்கும் வகையின் நன்மைகள்
இந்த அல்காரிதம் ஏன் மிகவும் சக்தி வாய்ந்தது?
ஏனெனில்:
- புதிய வரிசைகளை உருவாக்காமல், உள்ளீட்டு வரிசையை நேரடியாக மாற்றியமைக்க நினைவக தடத்தை குறைக்க அதை மாற்றலாம்.
குறிப்பு: இந்த வகை அல்காரிதம் அழைக்கப்படுகிறது
- குறிப்பிடத்தக்க வட்டு I/O மேல்நிலை இல்லாமல் ஒரே நேரத்தில் வட்டு இடத்தையும் சிறிய அளவிலான நினைவகத்தையும் பயன்படுத்த அதை மாற்றலாம். தற்போது செயலாக்கப்படும் பகுதிகளை மட்டுமே நினைவகத்தில் ஏற்றுவது என்பது யோசனை. 100 மெகாபைட் நினைவக இடையகத்துடன் பல ஜிகாபைட் அட்டவணையை நீங்கள் வரிசைப்படுத்த வேண்டியிருக்கும் போது இது முக்கியமானது.
குறிப்பு: இந்த வகை அல்காரிதம் அழைக்கப்படுகிறது
- பல செயல்முறைகள்/த்ரெட்கள்/சேவையகங்களில் இயங்குவதற்கு நீங்கள் அதை மாற்றலாம்.
எடுத்துக்காட்டாக, விநியோகிக்கப்பட்ட ஒன்றிணைப்பு வரிசை முக்கிய கூறுகளில் ஒன்றாகும்
- இந்த அல்காரிதம் ஈயத்தை தங்கமாக மாற்றும் (உண்மையில்!).
இந்த வரிசையாக்க அல்காரிதம் பெரும்பாலான (அனைத்தும் இல்லை என்றால்) தரவுத்தளங்களில் பயன்படுத்தப்படுகிறது, ஆனால் அது மட்டும் இல்லை. நீங்கள் மேலும் அறிய விரும்பினால், இதைப் படிக்கலாம்
வரிசை, மரம் மற்றும் ஹாஷ் அட்டவணை
நேரம் சிக்கலானது மற்றும் வரிசைப்படுத்துதல் பற்றிய யோசனையை இப்போது நாங்கள் புரிந்துகொள்கிறோம், 3 தரவு கட்டமைப்புகளைப் பற்றி நான் உங்களுக்குச் சொல்ல வேண்டும். அவர்கள் ஏனெனில் இது முக்கியமானது நவீன தரவுத்தளங்களின் அடிப்படையாகும். கருத்தையும் அறிமுகப்படுத்துகிறேன் தரவுத்தள அட்டவணை.
வரிசை
இரு பரிமாண வரிசை என்பது எளிமையான தரவு கட்டமைப்பாகும். ஒரு அட்டவணையை ஒரு வரிசையாகக் கருதலாம். உதாரணத்திற்கு:
இந்த 2 பரிமாண வரிசையானது வரிசைகள் மற்றும் நெடுவரிசைகளைக் கொண்ட அட்டவணையாகும்:
- ஒவ்வொரு வரியும் ஒரு பொருளைக் குறிக்கிறது
- நிறுவனத்தை விவரிக்கும் பண்புகளை நெடுவரிசைகள் சேமிக்கின்றன.
- ஒவ்வொரு நெடுவரிசையும் ஒரு குறிப்பிட்ட வகையின் தரவைச் சேமிக்கிறது (முழு எண், சரம், தேதி...).
தரவைச் சேமிப்பதற்கும் காட்சிப்படுத்துவதற்கும் இது வசதியானது, இருப்பினும், நீங்கள் ஒரு குறிப்பிட்ட மதிப்பைக் கண்டுபிடிக்க வேண்டியிருக்கும் போது, இது பொருத்தமானது அல்ல.
எடுத்துக்காட்டாக, இங்கிலாந்தில் பணிபுரியும் அனைத்து தோழர்களையும் நீங்கள் கண்டுபிடிக்க விரும்பினால், அந்த வரிசை இங்கிலாந்தைச் சேர்ந்ததா என்பதைத் தீர்மானிக்க ஒவ்வொரு வரிசையையும் பார்க்க வேண்டும். இது உங்களுக்கு N நடவடிக்கைகளுக்கு செலவாகும்அங்கு N - கோடுகளின் எண்ணிக்கை, இது மோசமாக இல்லை, ஆனால் வேகமான வழி இருக்க முடியுமா? இப்போது நாம் மரங்களைப் பற்றி தெரிந்துகொள்ள வேண்டிய நேரம் இது.
குறிப்பு: பெரும்பாலான நவீன தரவுத்தளங்கள் அட்டவணைகளை திறம்பட சேமிப்பதற்காக நீட்டிக்கப்பட்ட வரிசைகளை வழங்குகின்றன: குவியல்-ஒழுங்கமைக்கப்பட்ட அட்டவணைகள் மற்றும் குறியீட்டு-ஒழுங்கமைக்கப்பட்ட அட்டவணைகள். ஆனால் இது நெடுவரிசைகளின் குழுவில் ஒரு குறிப்பிட்ட நிலையை விரைவாகக் கண்டுபிடிப்பதில் சிக்கலை மாற்றாது.
தரவுத்தள மரம் மற்றும் அட்டவணை
பைனரி தேடல் மரம் என்பது ஒரு சிறப்புப் பண்பு கொண்ட பைனரி மரமாகும், ஒவ்வொரு முனையிலும் விசை இருக்க வேண்டும்:
- இடது சப்ட்ரீயில் சேமிக்கப்பட்ட அனைத்து விசைகளையும் விட பெரியது
- வலது சப்ட்ரீயில் சேமிக்கப்பட்ட அனைத்து விசைகளையும் விட குறைவாக
இதன் பொருள் என்ன என்பதை பார்வைக்கு பார்ப்போம்
யோசனை
இந்த மரத்தில் N = 15 தனிமங்கள் உள்ளன. நான் 208ஐத் தேடுகிறேன் என்று வைத்துக்கொள்வோம்:
- நான் 136 விசையை உள்ள மூலத்தில் தொடங்குகிறேன். 136<208 முதல், நான் முனை 136 இன் வலது துணைப் பிரிவைப் பார்க்கிறேன்.
- 398>208 எனவே நான் முனை 398 இன் இடது சப்ட்ரீயைப் பார்க்கிறேன்
- 250>208 எனவே நான் முனை 250 இன் இடது சப்ட்ரீயைப் பார்க்கிறேன்
- 200<208, எனவே நான் முனை 200 இன் வலது துணை மரத்தைப் பார்க்கிறேன். ஆனால் 200 க்கு சரியான சப்ட்ரீ இல்லை, மதிப்பு இல்லை (ஏனென்றால் அது இருந்தால், அது சரியான சப்ட்ரீ 200ல் இருக்கும்).
இப்போது நான் 40ஐத் தேடுகிறேன் என்று வைத்துக்கொள்வோம்
- நான் 136 விசையை உள்ள மூலத்தில் தொடங்குகிறேன். 136 > 40 முதல், நான் முனை 136 இன் இடது சப்ட்ரீயைப் பார்க்கிறேன்.
- 80 > 40, எனவே நான் முனை 80 இன் இடது சப்ட்ரீயைப் பார்க்கிறேன்
- 40= 40, முனை உள்ளது. நான் முனையின் உள்ளே உள்ள வரிசை ஐடியை மீட்டெடுக்கிறேன் (படத்தில் காட்டப்படவில்லை) மற்றும் கொடுக்கப்பட்ட வரிசை ஐடியை அட்டவணையில் பார்க்கிறேன்.
- வரிசை ஐடியை அறிந்துகொள்வதால், டேபிளில் உள்ள தரவு எங்குள்ளது என்பதைத் தெரிந்துகொள்ள எனக்கு உதவுகிறது, அதனால் என்னால் உடனடியாக அதை மீட்டெடுக்க முடியும்.
இறுதியில், இரண்டு தேடல்களும் மரத்தின் உள்ளே உள்ள நிலைகளின் எண்ணிக்கையை எனக்கு செலவழிக்கும். ஒன்றிணைப்பு வரிசை பற்றிய பகுதியை நீங்கள் கவனமாகப் படித்தால், log(N) நிலைகள் இருப்பதைப் பார்க்க வேண்டும். அது மாறிவிடும், தேடல் செலவு பதிவு(N), மோசமாக இல்லை!
நமது பிரச்சனைக்கு திரும்புவோம்
ஆனால் இது மிகவும் சுருக்கமானது, எனவே நமது பிரச்சனைக்கு வருவோம். ஒரு எளிய முழு எண்ணுக்குப் பதிலாக, முந்தைய அட்டவணையில் உள்ள ஒருவரின் நாட்டைக் குறிக்கும் ஒரு சரத்தை கற்பனை செய்து பாருங்கள். அட்டவணையின் "நாடு" புலத்தை (நெடுவரிசை 3) கொண்ட ஒரு மரம் உங்களிடம் உள்ளது என்று வைத்துக்கொள்வோம்:
- இங்கிலாந்தில் யார் வேலை செய்கிறார்கள் என்பதை நீங்கள் அறிய விரும்பினால்
- கிரேட் பிரிட்டனைக் குறிக்கும் முனையைப் பெற நீங்கள் மரத்தைப் பார்க்கிறீர்கள்
- "UKnode" க்குள் நீங்கள் UK பணியாளர் பதிவுகளின் இருப்பிடத்தைக் காண்பீர்கள்.
நீங்கள் வரிசையை நேரடியாகப் பயன்படுத்தினால், இந்தத் தேடலுக்கு N செயல்பாடுகளுக்குப் பதிலாக log(N) செயல்பாடுகள் செலவாகும். நீங்கள் இப்போது வழங்கியது தரவுத்தள அட்டவணை.
விசைகளை (அதாவது புலக் குழுக்கள்) ஒப்பிடுவதற்கான செயல்பாடு இருக்கும் வரை, எந்தப் புலங்களின் குழுவிற்கும் (சரம், எண், 2 கோடுகள், எண் மற்றும் சரம், தேதி...) ஒரு குறியீட்டு மரத்தை நீங்கள் உருவாக்கலாம். விசைகள் மத்தியில் ஒழுங்கு (இது தரவுத்தளத்தில் உள்ள எந்த அடிப்படை வகைகளுக்கும் பொருந்தும்).
B+TreeIndex
இந்த மரம் ஒரு குறிப்பிட்ட மதிப்பைப் பெறுவதற்கு நன்றாக வேலை செய்யும் போது, உங்களுக்குத் தேவைப்படும்போது ஒரு பெரிய சிக்கல் உள்ளது இரண்டு மதிப்புகளுக்கு இடையில் பல கூறுகளைப் பெறுங்கள். இதற்கு O(N) செலவாகும், ஏனெனில் நீங்கள் மரத்தில் உள்ள ஒவ்வொரு முனையையும் பார்த்து அது இந்த இரண்டு மதிப்புகளுக்கு இடையில் உள்ளதா எனச் சரிபார்க்க வேண்டும் (எ.கா. மரத்தின் வரிசைப்படுத்தப்பட்ட பயணத்துடன்). மேலும், நீங்கள் முழு மரத்தையும் படிக்க வேண்டியிருப்பதால், இந்த செயல்பாடு வட்டு I/O நட்பு அல்ல. திறம்பட செயல்படுத்துவதற்கான வழியை நாம் கண்டுபிடிக்க வேண்டும் வரம்பு கோரிக்கை. இந்தச் சிக்கலைத் தீர்க்க, நவீன தரவுத்தளங்கள் B+Tree எனப்படும் முந்தைய மரத்தின் மாற்றியமைக்கப்பட்ட பதிப்பைப் பயன்படுத்துகின்றன. B+Tree மரத்தில்:
- மிகக் குறைந்த முனைகள் (இலைகள்) தகவலைச் பதிவு செய் (தொடர்புடைய அட்டவணையில் உள்ள வரிசைகளின் இடம்)
- மீதமுள்ள முனைகள் இங்கே உள்ளன வழித்தடத்திற்கு சரியான முனைக்கு தேடலின் போது.
நீங்கள் பார்க்க முடியும் என, இங்கே அதிக முனைகள் உள்ளன (இரண்டு முறை). உண்மையில், உங்களிடம் கூடுதல் முனைகள் உள்ளன, "முடிவு முனைகள்", அவை சரியான முனையைக் கண்டறிய உதவும் (இது தொடர்புடைய அட்டவணையில் வரிசைகளின் இருப்பிடத்தை சேமிக்கிறது). ஆனால் தேடல் சிக்கலானது இன்னும் O(log(N)) தான் (இன்னும் ஒரே ஒரு நிலை உள்ளது). பெரிய வித்தியாசம் அதுதான் கீழ் மட்டத்தில் உள்ள முனைகள் அவற்றின் வாரிசுகளுடன் இணைக்கப்பட்டுள்ளன.
இந்த B+Tree மூலம், நீங்கள் 40 மற்றும் 100 க்கு இடையில் மதிப்புகளைத் தேடுகிறீர்கள் என்றால்:
- முந்தைய மரத்தைப் போலவே நீங்கள் 40ஐப் பார்க்க வேண்டும் (அல்லது 40 இல்லை என்றால் 40க்குப் பிறகு மிக நெருக்கமான மதிப்பு).
- நீங்கள் 40 ஐ அடையும் வரை நேரடி வாரிசு இணைப்புகளைப் பயன்படுத்தி 100 வாரிசுகளை சேகரிக்கவும்.
M வாரிசுகளை நீங்கள் கண்டுபிடித்துவிட்டீர்கள் மற்றும் மரத்தில் N முனைகள் உள்ளன என்று வைத்துக்கொள்வோம். ஒரு குறிப்பிட்ட முனையைக் கண்டறிவது முந்தைய மரத்தைப் போலவே பதிவு(N) செலவாகும். ஆனால் நீங்கள் இந்த முனையைப் பெற்றவுடன், M நடவடிக்கைகளில் M வாரிசுகளை அவர்களின் வாரிசுகளைப் பற்றிய குறிப்புகளுடன் பெறுவீர்கள். இந்தத் தேடலுக்கு M+log(N) மட்டுமே செலவாகும் முந்தைய மரத்தின் N செயல்பாடுகளுடன் ஒப்பிடும்போது செயல்பாடுகள். மேலும், நீங்கள் முழு மரத்தையும் (M+log(N) nodes மட்டும்) படிக்க வேண்டியதில்லை, அதாவது குறைந்த வட்டு பயன்பாடு. M சிறியதாக இருந்தால் (எ.கா. 200 வரிசைகள்) மற்றும் N பெரியதாக இருந்தால் (1 வரிசைகள்), பெரிய வித்தியாசம் இருக்கும்.
ஆனால் இங்கே புதிய சிக்கல்கள் உள்ளன (மீண்டும்!). தரவுத்தளத்தில் ஒரு வரிசையைச் சேர்த்தால் அல்லது நீக்கினால் (அதனால் தொடர்புடைய B+Tree குறியீட்டில்):
- B+Treeயின் உள்ளே உள்ள முனைகளுக்கு இடையில் நீங்கள் ஒழுங்கை பராமரிக்க வேண்டும், இல்லையெனில் வரிசைப்படுத்தப்படாத மரத்தில் உள்ள முனைகளை உங்களால் கண்டுபிடிக்க முடியாது.
- நீங்கள் B+Tree இல் குறைந்தபட்ச சாத்தியமான நிலைகளை வைத்திருக்க வேண்டும், இல்லையெனில் O(log(N)) நேர சிக்கலானது O(N) ஆக மாறும்.
வேறு வார்த்தைகளில் கூறுவதானால், B+Tree தானாக ஒழுங்குபடுத்தும் மற்றும் சமநிலையானதாக இருக்க வேண்டும். அதிர்ஷ்டவசமாக, ஸ்மார்ட் டெலிட் மற்றும் இன்செர்ட் செயல்பாடுகள் மூலம் இது சாத்தியமாகும். ஆனால் இது ஒரு செலவில் வருகிறது: ஒரு B+ மரத்தில் உள்ள செருகல்கள் மற்றும் நீக்குதல்களுக்கு O(log(N)) செலவாகும். அதனால்தான் உங்களில் சிலர் அதைக் கேட்டிருப்பீர்கள் பல குறியீடுகளைப் பயன்படுத்துவது நல்ல யோசனையல்ல. உண்மையில், அட்டவணையில் ஒரு வரிசையை வேகமாக செருகுவதை/புதுப்பிப்பதை/நீக்குவதை மெதுவாக்குகிறீர்கள்ஏனெனில் தரவுத்தளமானது ஒவ்வொரு குறியீட்டிற்கும் விலையுயர்ந்த O(log(N)) செயல்பாட்டைப் பயன்படுத்தி அட்டவணையின் குறியீடுகளைப் புதுப்பிக்க வேண்டும். மேலும், குறியீடுகளைச் சேர்ப்பது என்பது கூடுதல் பணிச்சுமையைக் குறிக்கிறது பரிவர்த்தனை மேலாளர் (கட்டுரையின் முடிவில் விவரிக்கப்படும்).
மேலும் விவரங்களுக்கு, நீங்கள் விக்கிபீடியா கட்டுரையைப் பார்க்கலாம்
குறிப்பு: குறைந்த அளவிலான மேம்படுத்தல்கள் காரணமாக, B+ மரம் முழுமையாக சமநிலையில் இருக்க வேண்டும் என்று ஒரு வாசகர் என்னிடம் கூறினார்.
ஹேஷ்டபிள்
எங்களின் கடைசி முக்கியமான தரவு அமைப்பு ஹாஷ் அட்டவணை. நீங்கள் விரைவாக மதிப்புகளைத் தேட விரும்பும் போது இது மிகவும் பயனுள்ளதாக இருக்கும். மேலும், ஹாஷ் அட்டவணையைப் புரிந்துகொள்வது, ஹாஷ் ஜாயின் எனப்படும் பொதுவான தரவுத்தள இணைப்பின் செயல்பாட்டைப் பின்னர் புரிந்து கொள்ள உதவும் ( ஹாஷ் சேர) இந்தத் தரவுக் கட்டமைப்பானது சில உள் விஷயங்களைச் சேமிக்க தரவுத்தளத்தால் பயன்படுத்தப்படுகிறது (எ.கா. பூட்டு மேஜை அல்லது தாங்கல் குளம், இந்த இரண்டு கருத்துகளையும் பின்னர் பார்ப்போம்).
ஹாஷ் டேபிள் என்பது ஒரு உறுப்பை அதன் விசையால் விரைவாகக் கண்டுபிடிக்கும் தரவுக் கட்டமைப்பாகும். ஹாஷ் அட்டவணையை உருவாக்க, நீங்கள் வரையறுக்க வேண்டும்:
- முக்கிய உங்கள் உறுப்புகளுக்கு
- ஹாஷ் செயல்பாடு விசைகளுக்கு. கணக்கிடப்பட்ட விசை ஹாஷ்கள் உறுப்புகளின் இருப்பிடத்தைக் கொடுக்கின்றன (அழைப்பு பிரிவுகள் ).
- விசைகளை ஒப்பிடுவதற்கான செயல்பாடு. சரியான பிரிவை நீங்கள் கண்டறிந்ததும், இந்த ஒப்பீட்டைப் பயன்படுத்தி பிரிவில் நீங்கள் தேடும் உறுப்பைக் கண்டறிய வேண்டும்.
எளிய உதாரணம்
ஒரு தெளிவான உதாரணத்தை எடுத்துக் கொள்வோம்:
இந்த ஹாஷ் அட்டவணை 10 பிரிவுகளைக் கொண்டுள்ளது. நான் சோம்பேறியாக இருப்பதால், நான் 5 பகுதிகளை மட்டுமே படம்பிடித்தேன், ஆனால் நீங்கள் புத்திசாலி என்று எனக்குத் தெரியும், எனவே மற்ற 5 பகுதிகளை நீங்களே படம்பிடிக்க அனுமதிக்கிறேன். நான் ஒரு ஹாஷ் செயல்பாடு மாடுலோ 10 விசையைப் பயன்படுத்தினேன். வேறு வார்த்தைகளில் கூறுவதானால், தனிமத்தின் விசையின் கடைசி இலக்கத்தை மட்டுமே அதன் பிரிவைக் கண்டறிகிறேன்:
- கடைசி இலக்கம் 0 என்றால், உறுப்பு 0 பிரிவில் விழும்,
- கடைசி இலக்கம் 1 என்றால், உறுப்பு 1 பிரிவில் விழும்,
- கடைசி இலக்கம் 2 ஆக இருந்தால், உறுப்பு 2 பகுதிக்குள் விழும்.
- ...
நான் பயன்படுத்திய ஒப்பீட்டு செயல்பாடு இரண்டு முழு எண்களுக்கு இடையிலான சமத்துவம்.
நீங்கள் உறுப்பு 78 ஐப் பெற விரும்புகிறீர்கள் என்று வைத்துக்கொள்வோம்:
- ஹாஷ் அட்டவணை 78க்கான ஹாஷ் குறியீட்டைக் கணக்கிடுகிறது, இது 8 ஆகும்.
- ஹாஷ் அட்டவணை பிரிவு 8 ஐப் பார்க்கிறது, மேலும் அது கண்டுபிடிக்கும் முதல் உறுப்பு 78 ஆகும்.
- அவள் 78 ஐ உங்களுக்குத் திருப்பித் தருகிறாள்
- தேடலுக்கு 2 செயல்பாடுகள் மட்டுமே செலவாகும் (ஒன்று ஹாஷ் மதிப்பைக் கணக்கிடவும் மற்றொன்று பிரிவில் உள்ள உறுப்பைப் பார்க்கவும்).
இப்போது நீங்கள் உறுப்பு 59 ஐப் பெற விரும்புகிறீர்கள் என்று வைத்துக்கொள்வோம்:
- ஹாஷ் அட்டவணை 59க்கான ஹாஷ் குறியீட்டைக் கணக்கிடுகிறது, இது 9 ஆகும்.
- ஹாஷ் அட்டவணை பிரிவு 9 இல் தேடுகிறது, முதல் உறுப்பு 99 ஆகும். 99!=59 முதல், உறுப்பு 99 சரியான உறுப்பு அல்ல.
- அதே தர்க்கத்தைப் பயன்படுத்தி, இரண்டாவது உறுப்பு (9), மூன்றாவது (79), ..., கடைசி (29) ஆகியவை எடுக்கப்படுகின்றன.
- உறுப்பு காணப்படவில்லை.
- தேடல் செலவு 7 செயல்பாடுகள்.
நல்ல ஹாஷ் செயல்பாடு
நீங்கள் பார்க்கிறபடி, நீங்கள் தேடும் மதிப்பைப் பொறுத்து, செலவு ஒரே மாதிரியாக இருக்காது!
நான் இப்போது விசையின் மாடுலோ 1 என்ற ஹாஷ் செயல்பாட்டை மாற்றினால் (அதாவது, கடைசி 000 இலக்கங்களை எடுத்துக் கொண்டால்), 000 பிரிவில் எந்த கூறுகளும் இல்லாததால், இரண்டாவது தேடல் 6 செயல்பாட்டிற்கு மட்டுமே செலவாகும். ஒரு நல்ல ஹாஷ் செயல்பாட்டைக் கண்டுபிடிப்பதே உண்மையான சவாலாகும், இது மிகச் சிறிய எண்ணிக்கையிலான உறுப்புகளைக் கொண்ட வாளிகளை உருவாக்கும்.
எனது எடுத்துக்காட்டில், ஒரு நல்ல ஹாஷ் செயல்பாட்டைக் கண்டுபிடிப்பது எளிது. ஆனால் இது ஒரு எளிய உதாரணம், விசை இருக்கும் போது ஒரு நல்ல ஹாஷ் செயல்பாட்டைக் கண்டுபிடிப்பது மிகவும் கடினம்:
- சரம் (உதாரணமாக - கடைசி பெயர்)
- 2 வரிகள் (உதாரணமாக - கடைசி பெயர் மற்றும் முதல் பெயர்)
- 2 கோடுகள் மற்றும் தேதி (உதாரணமாக - கடைசி பெயர், முதல் பெயர் மற்றும் பிறந்த தேதி)
- ...
ஒரு நல்ல ஹாஷ் செயல்பாட்டுடன், ஹாஷ் டேபிள் லுக்அப்களின் விலை O(1).
வரிசை vs ஹாஷ் அட்டவணை
வரிசையை ஏன் பயன்படுத்தக்கூடாது?
ம்ம், நல்ல கேள்வி.
- ஹாஷ் அட்டவணை இருக்க முடியும் ஓரளவு நினைவகத்தில் ஏற்றப்பட்டது, மற்றும் மீதமுள்ள பிரிவுகள் வட்டில் இருக்கும்.
- ஒரு வரிசையுடன் நீங்கள் நினைவகத்தில் தொடர்ச்சியான இடத்தைப் பயன்படுத்த வேண்டும். நீங்கள் ஒரு பெரிய அட்டவணையை ஏற்றினால் போதுமான தொடர்ச்சியான இடத்தைக் கண்டுபிடிப்பது மிகவும் கடினம்.
- ஹாஷ் அட்டவணைக்கு, நீங்கள் விரும்பும் விசையைத் தேர்ந்தெடுக்கலாம் (எடுத்துக்காட்டாக, நாடு மற்றும் நபரின் கடைசி பெயர்).
மேலும் தகவலுக்கு, நீங்கள் பற்றிய கட்டுரையைப் படிக்கலாம்
ஆதாரம்: www.habr.com