ഹേ ഹബർ! ലേഖനത്തിന്റെ വിവർത്തനം ഞാൻ നിങ്ങളുടെ ശ്രദ്ധയിൽപ്പെടുത്തുന്നു
"ഒരു റിലേഷണൽ ഡാറ്റാബേസ് എങ്ങനെയാണ് പ്രവർത്തിക്കുന്നത്".

റിലേഷണൽ ഡാറ്റാബേസുകളുടെ കാര്യം വരുമ്പോൾ, എന്തോ നഷ്‌ടമായതായി എനിക്ക് ചിന്തിക്കാൻ കഴിയില്ല. അവ എല്ലായിടത്തും ഉപയോഗിക്കുന്നു. ചെറുതും ഉപയോഗപ്രദവുമായ SQLite മുതൽ ശക്തമായ ടെറാഡാറ്റ വരെ നിരവധി വ്യത്യസ്ത ഡാറ്റാബേസുകൾ ലഭ്യമാണ്. എന്നാൽ ഡാറ്റാബേസ് എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് വിശദീകരിക്കുന്ന ചില ലേഖനങ്ങൾ മാത്രമേയുള്ളൂ. എത്ര കുറച്ച് ഫലങ്ങളുണ്ടെന്ന് കാണാൻ "howdoesarelationaldatabasework" ഉപയോഗിച്ച് നിങ്ങൾക്ക് സ്വയം തിരയാവുന്നതാണ്. മാത്രമല്ല, ഈ ലേഖനങ്ങൾ ചെറുതാണ്. നിങ്ങൾ ഏറ്റവും പുതിയ ബസി സാങ്കേതികവിദ്യകൾക്കായി തിരയുകയാണെങ്കിൽ (BigData, NoSQL അല്ലെങ്കിൽ JavaScript), അവ എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് വിശദീകരിക്കുന്ന കൂടുതൽ ആഴത്തിലുള്ള ലേഖനങ്ങൾ നിങ്ങൾ കണ്ടെത്തും.

സർവ്വകലാശാല കോഴ്‌സുകൾ, ഗവേഷണ പ്രബന്ധങ്ങൾ, പുസ്‌തകങ്ങൾ എന്നിവയ്‌ക്ക് പുറത്ത് വിശദീകരിക്കാൻ കഴിയാത്തവിധം റിലേഷണൽ ഡാറ്റാബേസുകൾ വളരെ പഴയതും വിരസവുമാണോ?

ഒരു ഡെവലപ്പർ എന്ന നിലയിൽ, എനിക്ക് മനസ്സിലാകാത്ത എന്തെങ്കിലും ഉപയോഗിക്കുന്നത് ഞാൻ വെറുക്കുന്നു. ഡാറ്റാബേസുകൾ 40 വർഷത്തിലേറെയായി ഉപയോഗിച്ചിട്ടുണ്ടെങ്കിൽ, അതിന് ഒരു കാരണമുണ്ടായിരിക്കണം. വർഷങ്ങളായി, ഞാൻ ദിവസവും ഉപയോഗിക്കുന്ന ഈ വിചിത്രമായ ബ്ലാക്ക് ബോക്സുകൾ ശരിക്കും മനസ്സിലാക്കാൻ നൂറുകണക്കിന് മണിക്കൂറുകൾ ചെലവഴിച്ചു. റിലേഷണൽ ഡാറ്റാബേസുകൾ അവർ കാരണം വളരെ രസകരമാണ് ഉപയോഗപ്രദവും പുനരുപയോഗിക്കാവുന്നതുമായ ആശയങ്ങളെ അടിസ്ഥാനമാക്കിയുള്ളതാണ്. നിങ്ങൾക്ക് ഒരു ഡാറ്റാബേസ് മനസ്സിലാക്കാൻ താൽപ്പര്യമുണ്ടെങ്കിൽ, എന്നാൽ ഈ വിശാലമായ വിഷയത്തിലേക്ക് ആഴ്ന്നിറങ്ങാൻ ഒരിക്കലും സമയമോ ചായ്വോ ഇല്ലെങ്കിൽ, നിങ്ങൾ ഈ ലേഖനം ആസ്വദിക്കണം.

ഈ ലേഖനത്തിന്റെ തലക്കെട്ട് വ്യക്തമാണെങ്കിലും, ഈ ലേഖനത്തിന്റെ ഉദ്ദേശ്യം ഡാറ്റാബേസ് എങ്ങനെ ഉപയോഗിക്കണമെന്ന് മനസ്സിലാക്കുക എന്നതല്ല. അതിനാൽ, ഒരു ലളിതമായ കണക്ഷൻ അഭ്യർത്ഥനയും അടിസ്ഥാന ചോദ്യങ്ങളും എങ്ങനെ എഴുതണമെന്ന് നിങ്ങൾ ഇതിനകം അറിഞ്ഞിരിക്കണം ക്രൂഡ്; അല്ലെങ്കിൽ നിങ്ങൾക്ക് ഈ ലേഖനം മനസ്സിലാകണമെന്നില്ല. നിങ്ങൾ അറിയേണ്ട ഒരേയൊരു കാര്യം അത് മാത്രമാണ്, ബാക്കി ഞാൻ വിശദീകരിക്കാം.

അൽഗോരിതങ്ങളുടെ സമയ സങ്കീർണ്ണത (BigO) പോലെയുള്ള ചില കമ്പ്യൂട്ടർ സയൻസ് അടിസ്ഥാനകാര്യങ്ങളിൽ നിന്ന് ഞാൻ ആരംഭിക്കും. നിങ്ങളിൽ ചിലർ ഈ ആശയത്തെ വെറുക്കുന്നുവെന്ന് എനിക്കറിയാം, എന്നാൽ ഇതില്ലാതെ നിങ്ങൾക്ക് ഡാറ്റാബേസിനുള്ളിലെ സങ്കീർണതകൾ മനസ്സിലാക്കാൻ കഴിയില്ല. ഇതൊരു വലിയ വിഷയമായതിനാൽ, ഞാൻ ശ്രദ്ധ കേന്ദ്രീകരിക്കും ഞാൻ കരുതുന്നത് പ്രധാനമാണ്: ഡാറ്റാബേസ് എങ്ങനെ പ്രോസസ്സ് ചെയ്യുന്നു SQL അന്വേഷണം. ഞാൻ വെറുതെ പരിചയപ്പെടുത്താം അടിസ്ഥാന ഡാറ്റാബേസ് ആശയങ്ങൾഅതിനാൽ ലേഖനത്തിന്റെ അവസാനം നിങ്ങൾക്ക് എന്താണ് സംഭവിക്കുന്നതെന്ന് ഒരു ആശയം ലഭിക്കും.

ധാരാളം അൽഗോരിതങ്ങളും ഡാറ്റാ ഘടനകളും ഉൾപ്പെടുന്ന ദീർഘവും സാങ്കേതികവുമായ ലേഖനമായതിനാൽ, ഇത് വായിക്കാൻ നിങ്ങളുടെ സമയമെടുക്കുക. ചില ആശയങ്ങൾ മനസ്സിലാക്കാൻ ബുദ്ധിമുട്ടായിരിക്കാം; നിങ്ങൾക്ക് അവ ഒഴിവാക്കാനും പൊതുവായ ആശയം നേടാനും കഴിയും.

നിങ്ങളിൽ കൂടുതൽ അറിവുള്ളവർക്കായി, ഈ ലേഖനം 3 ഭാഗങ്ങളായി തിരിച്ചിരിക്കുന്നു:

• ലോ-ലെവൽ, ഹൈ-ലെവൽ ഡാറ്റാബേസ് ഘടകങ്ങളുടെ അവലോകനം
• അന്വേഷണ ഒപ്റ്റിമൈസേഷൻ പ്രക്രിയയുടെ അവലോകനം
• ഇടപാടിന്റെയും ബഫർ പൂൾ മാനേജ്മെന്റിന്റെയും അവലോകനം

ബേസിക്സിലേക്ക് മടങ്ങുക

വർഷങ്ങൾക്ക് മുമ്പ് (ഒരു ഗാലക്സിയിൽ, വളരെ അകലെ...), ഡെവലപ്പർമാർക്ക് അവർ കോഡിംഗ് ചെയ്യുന്ന പ്രവർത്തനങ്ങളുടെ എണ്ണം കൃത്യമായി അറിയേണ്ടതുണ്ട്. അവരുടെ സ്ലോ കമ്പ്യൂട്ടറുകളുടെ സിപിയുവും മെമ്മറിയും പാഴാക്കാൻ അവർക്ക് കഴിയാത്തതിനാൽ അവർക്ക് അവരുടെ അൽഗോരിതങ്ങളും ഡാറ്റാ ഘടനകളും ഹൃദ്യമായി അറിയാമായിരുന്നു.

ഈ ഭാഗത്ത്, ഈ ആശയങ്ങളിൽ ചിലത് ഞാൻ നിങ്ങളെ ഓർമ്മിപ്പിക്കും, കാരണം അവ ഡാറ്റാബേസ് മനസ്സിലാക്കുന്നതിന് അത്യാവശ്യമാണ്. ഞാൻ ആശയവും അവതരിപ്പിക്കും ഡാറ്റാബേസ് സൂചിക.

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 പദവിയുടെ യഥാർത്ഥ നിർവചനം നൽകിയില്ല, ഒരു ആശയം മാത്രം. നിങ്ങൾക്ക് ഈ ലേഖനം ഇവിടെ വായിക്കാം വിക്കിപീഡിയ യഥാർത്ഥ (അസിംപ്റ്റോട്ടിക്) നിർവചനത്തിന്.

ലയിപ്പിക്കുക

നിങ്ങൾക്ക് ഒരു ശേഖരം അടുക്കേണ്ടിവരുമ്പോൾ നിങ്ങൾ എന്തുചെയ്യും? എന്ത്? നിങ്ങൾ സോർട്ട്() ഫംഗ്‌ഷനെ വിളിക്കുന്നു... ശരി, നല്ല ഉത്തരം... എന്നാൽ ഒരു ഡാറ്റാബേസിനായി, ഈ സോർട്ട്() ഫംഗ്‌ഷൻ എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് നിങ്ങൾ മനസ്സിലാക്കണം.

നിരവധി നല്ല സോർട്ടിംഗ് അൽഗോരിതങ്ങൾ ഉണ്ട്, അതിനാൽ ഞാൻ ഏറ്റവും പ്രധാനപ്പെട്ടതിൽ ശ്രദ്ധ കേന്ദ്രീകരിക്കും: ലയിപ്പിക്കുക. ഡാറ്റ സോർട്ടിംഗ് ഇപ്പോൾ ഉപയോഗപ്രദമായിരിക്കുന്നത് എന്തുകൊണ്ടാണെന്ന് നിങ്ങൾക്ക് മനസ്സിലായില്ലായിരിക്കാം, എന്നാൽ നിങ്ങൾ അന്വേഷണ ഒപ്റ്റിമൈസേഷൻ ഭാഗത്തിന് ശേഷം വേണം. മാത്രമല്ല, ലയന ക്രമം മനസ്സിലാക്കുന്നത് പിന്നീട് വിളിക്കപ്പെടുന്ന പൊതുവായ ഡാറ്റാബേസ് ജോയിൻ ഓപ്പറേഷൻ മനസ്സിലാക്കാൻ ഞങ്ങളെ സഹായിക്കും ലയിപ്പിക്കുക ചേരുക (ലയന അസോസിയേഷൻ).

ലയിപ്പിക്കുക

പല ഉപയോഗപ്രദമായ അൽഗോരിതങ്ങൾ പോലെ, ലയന അടുക്കലും ഒരു തന്ത്രത്തെ ആശ്രയിച്ചിരിക്കുന്നു: 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;

ലയിപ്പിക്കൽ ഒരു പ്രശ്‌നത്തെ ചെറിയ പ്രശ്‌നങ്ങളാക്കി മാറ്റുകയും തുടർന്ന് യഥാർത്ഥ പ്രശ്‌നത്തിന്റെ ഫലം ലഭിക്കുന്നതിന് ചെറിയ പ്രശ്‌നങ്ങളുടെ ഫലങ്ങൾ കണ്ടെത്തുകയും ചെയ്യുന്നു (ശ്രദ്ധിക്കുക: ഇത്തരത്തിലുള്ള അൽഗോരിതത്തെ വിഭജിച്ച് കീഴടക്കുക എന്ന് വിളിക്കുന്നു). നിങ്ങൾക്ക് ഈ അൽഗോരിതം മനസ്സിലാകുന്നില്ലെങ്കിൽ, വിഷമിക്കേണ്ട; ആദ്യം കണ്ടപ്പോൾ മനസ്സിലായില്ല. ഇതിന് നിങ്ങളെ സഹായിക്കാൻ കഴിയുമെങ്കിൽ, ഞാൻ ഈ അൽഗോരിതം ഒരു രണ്ട്-ഘട്ട അൽഗോരിതം ആയി കാണുന്നു:

• ഡിവിഷൻ ഘട്ടം, ഇവിടെ അറേയെ ചെറിയ അറേകളായി തിരിച്ചിരിക്കുന്നു
• ചെറിയ അറേകൾ സംയോജിപ്പിച്ച് (യൂണിയൻ ഉപയോഗിച്ച്) ഒരു വലിയ അറേ രൂപപ്പെടുത്തുന്നതാണ് സോർട്ടിംഗ് ഘട്ടം.

വിഭജന ഘട്ടം

ഡിവിഷൻ ഘട്ടത്തിൽ, അറേയെ 3 ഘട്ടങ്ങളിലായി ഏകീകൃത ശ്രേണികളായി തിരിച്ചിരിക്കുന്നു. ഘട്ടങ്ങളുടെ ഔപചാരിക എണ്ണം ലോഗ്(N) ആണ് (N=8, ലോഗ്(N) = 3 മുതൽ).

ഇത് എനിക്ക് എങ്ങനെ അറിയാം?

ഞാൻ പ്രതിഭയാണ്! ഒരു വാക്കിൽ - ഗണിതശാസ്ത്രം. ഓരോ ഘട്ടവും ഒറിജിനൽ അറേയുടെ വലുപ്പത്തെ 2 കൊണ്ട് ഹരിക്കുന്നു എന്നതാണ് ആശയം. ഒറിജിനൽ അറേയെ നിങ്ങൾക്ക് എത്ര തവണ വിഭജിക്കാം എന്നതാണ് ഘട്ടങ്ങളുടെ എണ്ണം. ഇതാണ് ലോഗരിതം (അടിസ്ഥാനം 2) ന്റെ കൃത്യമായ നിർവചനം.

സോർട്ടിംഗ് ഘട്ടം

സോർട്ടിംഗ് ഘട്ടത്തിൽ, നിങ്ങൾ ഏകീകൃത (ഏക-ഘടകം) അറേകളിൽ നിന്ന് ആരംഭിക്കുന്നു. ഓരോ ഘട്ടത്തിലും നിങ്ങൾ ഒന്നിലധികം ലയന പ്രവർത്തനങ്ങൾ പ്രയോഗിക്കുന്നു, മൊത്തം ചെലവ് N = 8 പ്രവർത്തനങ്ങളാണ്:

• ആദ്യ ഘട്ടത്തിൽ നിങ്ങൾക്ക് 4 ലയനങ്ങൾ ഉണ്ട്, അത് ഓരോന്നിനും 2 പ്രവർത്തനങ്ങൾക്ക് ചിലവാകും
• രണ്ടാമത്തെ ഘട്ടത്തിൽ നിങ്ങൾക്ക് 2 ലയനങ്ങൾ ഉണ്ട്, അത് 4 ഓപ്പറേഷനുകൾ വീതം ചെലവാകും
• മൂന്നാം ഘട്ടത്തിൽ നിങ്ങൾക്ക് 1 ലയനമുണ്ട്, അതിന് 8 പ്രവർത്തനങ്ങൾ ചിലവാകും

ലോഗ് (N) ഘട്ടങ്ങൾ ഉള്ളതിനാൽ, ആകെ ചെലവ് എൻ * ലോഗ്(എൻ) പ്രവർത്തനങ്ങൾ.

ലയന രീതിയുടെ പ്രയോജനങ്ങൾ

എന്തുകൊണ്ടാണ് ഈ അൽഗോരിതം ഇത്ര ശക്തിയുള്ളത്?

കാരണം:

• മെമ്മറി ഫൂട്ട്‌പ്രിന്റ് കുറയ്ക്കാൻ നിങ്ങൾക്കത് മാറ്റാം, അതുവഴി നിങ്ങൾ പുതിയ അറേകൾ സൃഷ്‌ടിക്കാതെ ഇൻപുട്ട് അറേ നേരിട്ട് പരിഷ്‌ക്കരിക്കുക.

ശ്രദ്ധിക്കുക: ഇത്തരത്തിലുള്ള അൽഗോരിതം വിളിക്കുന്നു in-സ്ഥലം (അധിക മെമ്മറി ഇല്ലാതെ അടുക്കുന്നു).

• കാര്യമായ ഡിസ്ക് 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, നോഡ് നിലവിലുണ്ട്. ഞാൻ നോഡിനുള്ളിലെ വരി ഐഡി വീണ്ടെടുക്കുന്നു (ചിത്രത്തിൽ കാണിച്ചിട്ടില്ല) കൂടാതെ നൽകിയിരിക്കുന്ന വരി ഐഡിക്കായി പട്ടികയിൽ നോക്കുക.
• വരി ഐഡി അറിയുന്നത്, പട്ടികയിൽ ഡാറ്റ എവിടെയാണെന്ന് കൃത്യമായി അറിയാൻ എന്നെ അനുവദിക്കുന്നു, അതിനാൽ എനിക്ക് അത് തൽക്ഷണം വീണ്ടെടുക്കാനാകും.

അവസാനം, രണ്ട് തിരയലുകൾക്കും എനിക്ക് മരത്തിനുള്ളിലെ ലെവലുകളുടെ എണ്ണം ചിലവാകും. ലയിപ്പിക്കൽ ക്രമത്തെക്കുറിച്ചുള്ള ഭാഗം നിങ്ങൾ ശ്രദ്ധാപൂർവ്വം വായിച്ചാൽ, ലോഗ് (N) ലെവലുകൾ ഉണ്ടെന്ന് നിങ്ങൾ കാണും. ഇത് മാറുന്നു, തിരയൽ ചെലവ് ലോഗ് (N), മോശമല്ല!

നമുക്ക് നമ്മുടെ പ്രശ്നത്തിലേക്ക് മടങ്ങാം

എന്നാൽ ഇത് വളരെ അമൂർത്തമാണ്, അതിനാൽ നമുക്ക് നമ്മുടെ പ്രശ്നത്തിലേക്ക് മടങ്ങാം. ലളിതമായ ഒരു പൂർണ്ണസംഖ്യയ്ക്ക് പകരം, മുമ്പത്തെ പട്ടികയിലെ ഒരാളുടെ രാജ്യത്തെ പ്രതിനിധീകരിക്കുന്ന ഒരു സ്ട്രിംഗ് സങ്കൽപ്പിക്കുക. പട്ടികയുടെ "രാജ്യം" ഫീൽഡ് (നിര 3) അടങ്ങുന്ന ഒരു വൃക്ഷം നിങ്ങൾക്കുണ്ടെന്ന് പറയാം:

• യുകെയിൽ ആരാണ് ജോലി ചെയ്യുന്നതെന്ന് അറിയണമെങ്കിൽ
• ഗ്രേറ്റ് ബ്രിട്ടനെ പ്രതിനിധീകരിക്കുന്ന നോഡ് ലഭിക്കാൻ നിങ്ങൾ മരത്തിലേക്ക് നോക്കുന്നു
• "UKnode" എന്നതിനുള്ളിൽ നിങ്ങൾ യുകെ വർക്കർ റെക്കോർഡുകളുടെ സ്ഥാനം കണ്ടെത്തും.

നിങ്ങൾ അറേ നേരിട്ട് ഉപയോഗിക്കുകയാണെങ്കിൽ ഈ തിരയലിന് N ഓപ്പറേഷനുകൾക്ക് പകരം ലോഗ്(N) പ്രവർത്തനങ്ങൾക്ക് ചിലവ് വരും. നിങ്ങൾ ഇപ്പോൾ അവതരിപ്പിച്ചത് ഡാറ്റാബേസ് സൂചിക.

നിങ്ങൾക്ക് കീകൾ (അതായത് ഫീൽഡ് ഗ്രൂപ്പുകൾ) താരതമ്യം ചെയ്യാനുള്ള ഒരു ഫംഗ്‌ഷൻ ഉള്ളിടത്തോളം കാലം, ഏത് ഗ്രൂപ്പിന്റെ ഫീൽഡുകൾക്കും (സ്ട്രിംഗ്, നമ്പർ, 2 ലൈനുകൾ, നമ്പർ, സ്ട്രിംഗ്, തീയതി...) ഒരു ഇൻഡക്സ് ട്രീ നിർമ്മിക്കാൻ കഴിയും. കീകൾക്കിടയിൽ ക്രമം (ഡാറ്റാബേസിലെ ഏതെങ്കിലും അടിസ്ഥാന തരങ്ങൾക്ക് ഇത് ബാധകമാണ്).

ബി+ട്രീ സൂചിക

ഒരു പ്രത്യേക മൂല്യം ലഭിക്കുന്നതിന് ഈ മരം നന്നായി പ്രവർത്തിക്കുമ്പോൾ, നിങ്ങൾക്ക് ആവശ്യമുള്ളപ്പോൾ ഒരു വലിയ പ്രശ്നമുണ്ട് രണ്ട് മൂല്യങ്ങൾക്കിടയിൽ ഒന്നിലധികം ഘടകങ്ങൾ നേടുക. ഇതിന് O (N) ചിലവാകും, കാരണം നിങ്ങൾ ട്രീയിലെ ഓരോ നോഡും നോക്കുകയും അത് ഈ രണ്ട് മൂല്യങ്ങൾക്കിടയിലാണോ എന്ന് പരിശോധിക്കുകയും വേണം (ഉദാ. ട്രീയുടെ ഒരു ഓർഡർ ട്രാവേസൽ ഉപയോഗിച്ച്). മാത്രമല്ല, നിങ്ങൾ മുഴുവൻ ട്രീയും വായിക്കേണ്ടതിനാൽ ഈ പ്രവർത്തനം ഡിസ്ക് I/O സൗഹൃദമല്ല. കാര്യക്ഷമമായി നിർവ്വഹിക്കുന്നതിനുള്ള മാർഗം നാം കണ്ടെത്തേണ്ടതുണ്ട് ശ്രേണി അഭ്യർത്ഥന. ഈ പ്രശ്നം പരിഹരിക്കാൻ, ആധുനിക ഡാറ്റാബേസുകൾ ബി+ട്രീ എന്ന മുൻ ട്രീയുടെ പരിഷ്കരിച്ച പതിപ്പ് ഉപയോഗിക്കുന്നു. ഒരു ബി+ട്രീ മരത്തിൽ:

• ഏറ്റവും താഴ്ന്ന നോഡുകൾ (ഇലകൾ) മാത്രം വിവരങ്ങൾ സംഭരിക്കുക (അനുബന്ധ പട്ടികയിലെ വരികളുടെ സ്ഥാനം)
• ബാക്കിയുള്ള നോഡുകൾ ഇവിടെയുണ്ട് റൂട്ടിംഗിനായി ശരിയായ നോഡിലേക്ക് തിരച്ചിൽ സമയത്ത്.

നിങ്ങൾക്ക് കാണാനാകുന്നതുപോലെ, ഇവിടെ കൂടുതൽ നോഡുകൾ ഉണ്ട് (രണ്ട് തവണ). തീർച്ചയായും, നിങ്ങൾക്ക് "ഡിസിഷൻ നോഡുകൾ" എന്ന അധിക നോഡുകൾ ഉണ്ട്, അത് ശരിയായ നോഡ് കണ്ടെത്താൻ നിങ്ങളെ സഹായിക്കും (അത് അനുബന്ധ പട്ടികയിലെ വരികളുടെ സ്ഥാനം സംഭരിക്കുന്നു). എന്നാൽ തിരയൽ സങ്കീർണ്ണത ഇപ്പോഴും O(log(N)) ആണ് (ഒരു ലെവൽ കൂടി ഉണ്ട്). വലിയ വ്യത്യാസം അതാണ് താഴ്ന്ന നിലയിലുള്ള നോഡുകൾ അവയുടെ പിൻഗാമികളുമായി ബന്ധിപ്പിച്ചിരിക്കുന്നു.

ഈ B+Tree ഉപയോഗിച്ച്, നിങ്ങൾ 40 നും 100 നും ഇടയിലുള്ള മൂല്യങ്ങൾക്കായി തിരയുകയാണെങ്കിൽ:

• നിങ്ങൾ മുമ്പത്തെ ട്രീയിൽ ചെയ്തതുപോലെ 40 (അല്ലെങ്കിൽ 40 ഇല്ലെങ്കിൽ 40 ന് ശേഷമുള്ള ഏറ്റവും അടുത്ത മൂല്യം) നോക്കേണ്ടതുണ്ട്.
• നിങ്ങൾ 40 ൽ എത്തുന്നതുവരെ നേരിട്ടുള്ള അവകാശ ലിങ്കുകൾ ഉപയോഗിച്ച് 100 അവകാശികളെ ശേഖരിക്കുക.

നിങ്ങൾ M പിൻഗാമികളെ കണ്ടെത്തിയെന്നും വൃക്ഷത്തിന് N നോഡുകൾ ഉണ്ടെന്നും പറയാം. ഒരു നിർദ്ദിഷ്ട നോഡ് കണ്ടെത്തുന്നതിന് മുമ്പത്തെ ട്രീ പോലെ ലോഗ് (N) ചിലവാകും. എന്നാൽ നിങ്ങൾക്ക് ഈ നോഡ് ലഭിച്ചുകഴിഞ്ഞാൽ, M പ്രവർത്തനങ്ങളിൽ നിങ്ങൾക്ക് M പിൻഗാമികളെ അവരുടെ പിൻഗാമികളെക്കുറിച്ചുള്ള റഫറൻസുകൾ ലഭിക്കും. ഈ തിരയലിന് M+log(N) മാത്രമേ ചെലവാകൂ മുമ്പത്തെ ട്രീയിലെ N പ്രവർത്തനങ്ങളുമായി താരതമ്യം ചെയ്യുമ്പോൾ പ്രവർത്തനങ്ങൾ. മാത്രമല്ല, നിങ്ങൾ മുഴുവൻ ട്രീയും (M+log(N) നോഡുകൾ മാത്രം) വായിക്കേണ്ടതില്ല, അതായത് ഡിസ്ക് ഉപയോഗം കുറവാണ്. M ചെറുതാണെങ്കിൽ (ഉദാ. 200 വരികൾ), N വലുതാണെങ്കിൽ (1 വരികൾ), വലിയ വ്യത്യാസം ഉണ്ടാകും.

എന്നാൽ ഇവിടെ പുതിയ പ്രശ്നങ്ങൾ ഉണ്ട് (വീണ്ടും!). നിങ്ങൾ ഡാറ്റാബേസിൽ ഒരു വരി ചേർക്കുകയോ ഇല്ലാതാക്കുകയോ ചെയ്യുകയാണെങ്കിൽ (അതിനാൽ ബന്ധപ്പെട്ട B+Tree സൂചികയിൽ):

• നിങ്ങൾ ഒരു B+Tree ഉള്ളിലെ നോഡുകൾക്കിടയിൽ ക്രമം പാലിക്കണം, അല്ലാത്തപക്ഷം തരംതിരിക്കാത്ത ഒരു മരത്തിനുള്ളിൽ നിങ്ങൾക്ക് നോഡുകൾ കണ്ടെത്താൻ കഴിയില്ല.
• B+Tree-ൽ സാധ്യമായ ഏറ്റവും കുറഞ്ഞ ലെവലുകൾ നിങ്ങൾ സൂക്ഷിക്കണം, അല്ലാത്തപക്ഷം O(ലോഗ്(N)) സമയ സങ്കീർണ്ണത O(N) ആയി മാറുന്നു.

മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, B+Tree സ്വയം ക്രമപ്പെടുത്തുന്നതും സന്തുലിതവുമായിരിക്കണം. ഭാഗ്യവശാൽ, സ്മാർട്ട് ഡിലീറ്റ്, ഇൻസേർട്ട് ഓപ്പറേഷനുകൾ ഉപയോഗിച്ച് ഇത് സാധ്യമാണ്. എന്നാൽ ഇതിന് ചിലവ് വരും: ഒരു B+ ട്രീയിലെ ഇൻസേർഷനുകളും ഇല്ലാതാക്കലുകളും വില O(ലോഗ്(N)) ആണ്. അതുകൊണ്ടാണ് നിങ്ങളിൽ ചിലർ അത് കേട്ടത് വളരെയധികം സൂചികകൾ ഉപയോഗിക്കുന്നത് നല്ല ആശയമല്ല. ശരിക്കും, ഒരു പട്ടികയിൽ ഒരു വരി വേഗത്തിൽ ചേർക്കൽ/അപ്‌ഡേറ്റ്/ഇല്ലാതാക്കൽ എന്നിവ നിങ്ങൾ മന്ദഗതിയിലാക്കുന്നുകാരണം ഡാറ്റാബേസിന് ഓരോ സൂചികയ്ക്കും വിലയേറിയ O(log(N)) ഓപ്പറേഷൻ ഉപയോഗിച്ച് പട്ടികയുടെ സൂചികകൾ അപ്ഡേറ്റ് ചെയ്യേണ്ടതുണ്ട്. മാത്രമല്ല, സൂചികകൾ ചേർക്കുന്നത് കൂടുതൽ ജോലിഭാരം എന്നാണ് അർത്ഥമാക്കുന്നത് ഇടപാട് മാനേജർ (ലേഖനത്തിന്റെ അവസാനം വിവരിക്കും).

കൂടുതൽ വിവരങ്ങൾക്ക്, നിങ്ങൾക്ക് വിക്കിപീഡിയയിലെ ലേഖനം കാണാം B+വൃക്ഷം. ഒരു ഡാറ്റാബേസിൽ B+Tree നടപ്പിലാക്കുന്നതിനുള്ള ഒരു ഉദാഹരണം നിങ്ങൾക്ക് വേണമെങ്കിൽ, നോക്കുക ഈ ലേഖനം и ഈ ലേഖനം ഒരു പ്രമുഖ MySQL ഡവലപ്പറിൽ നിന്ന്. InnoDB (MySQL എഞ്ചിൻ) സൂചികകൾ എങ്ങനെ കൈകാര്യം ചെയ്യുന്നു എന്നതിൽ ഇരുവരും ശ്രദ്ധ കേന്ദ്രീകരിക്കുന്നു.

കുറിപ്പ്: താഴ്ന്ന നിലയിലുള്ള ഒപ്റ്റിമൈസേഷനുകൾ കാരണം, 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