હે હબર! હું તમારા ધ્યાન પર લેખનો અનુવાદ રજૂ કરું છું
"રિલેશનલ ડેટાબેઝ કેવી રીતે કામ કરે છે".

જ્યારે રિલેશનલ ડેટાબેઝની વાત આવે છે ત્યારે હું મદદ કરી શકતો નથી પરંતુ લાગે છે કે કંઈક ખૂટે છે. તેઓ દરેક જગ્યાએ વપરાય છે. નાના અને ઉપયોગી SQLite થી લઈને શક્તિશાળી ટેરાડેટા સુધી ઘણા વિવિધ ડેટાબેસેસ ઉપલબ્ધ છે. પરંતુ ડેટાબેઝ કેવી રીતે કાર્ય કરે છે તે સમજાવતા માત્ર થોડા જ લેખો છે. કેટલા ઓછા પરિણામો છે તે જોવા માટે તમે "howdoesarelationaldatabasework" નો ઉપયોગ કરીને તમારા માટે શોધી શકો છો. વધુમાં, આ લેખો ટૂંકા છે. જો તમે નવીનતમ બઝી ટેક્નોલોજીઓ (BigData, NoSQL અથવા JavaScript) શોધી રહ્યાં છો, તો તમને તેઓ કેવી રીતે કાર્ય કરે છે તે સમજાવતા વધુ ગહન લેખો મળશે.

શું રિલેશનલ ડેટાબેઝ યુનિવર્સિટીના અભ્યાસક્રમો, સંશોધન પત્રો અને પુસ્તકોની બહાર સમજાવવા માટે ખૂબ જૂના અને ખૂબ કંટાળાજનક છે?

એક વિકાસકર્તા તરીકે, મને ન સમજાય તેવી કોઈ વસ્તુનો ઉપયોગ કરવાથી મને ધિક્કાર છે. અને જો ડેટાબેઝ 40 વર્ષથી વધુ સમયથી ઉપયોગમાં લેવાય છે, તો તેનું કારણ હોવું જોઈએ. વર્ષોથી, મેં આ વિચિત્ર બ્લેક બોક્સને સમજવા માટે સેંકડો કલાકો વિતાવ્યા છે જેનો હું દરરોજ ઉપયોગ કરું છું. રિલેશનલ ડેટાબેસેસ ખૂબ જ રસપ્રદ કારણ કે તેઓ ઉપયોગી અને ફરીથી વાપરી શકાય તેવા ખ્યાલો પર આધારિત. જો તમે ડેટાબેઝને સમજવામાં રસ ધરાવો છો, પરંતુ આ વ્યાપક વિષયને સમજવા માટે તમારી પાસે ક્યારેય સમય અથવા ઝોક નથી, તો તમારે આ લેખનો આનંદ માણવો જોઈએ.

આ લેખનું શીર્ષક સ્પષ્ટ હોવા છતાં, આ લેખનો હેતુ ડેટાબેઝનો ઉપયોગ કેવી રીતે કરવો તે સમજવાનો નથી. આથી, તમને પહેલાથી જ ખબર હોવી જોઈએ કે કેવી રીતે સરળ કનેક્શન વિનંતી અને મૂળભૂત પ્રશ્નો લખવા સીઆરયુડી; અન્યથા તમે આ લેખ સમજી શકશો નહીં. તમારે ફક્ત આ જ વસ્તુ જાણવાની જરૂર છે, હું બાકીનું સમજાવીશ.

હું અમુક કોમ્પ્યુટર સાયન્સ બેઝિક્સ સાથે શરૂ કરીશ, જેમ કે એલ્ગોરિધમ્સની સમય જટિલતા (BigO). હું જાણું છું કે તમારામાંથી કેટલાક આ ખ્યાલને નફરત કરે છે, પરંતુ તેના વિના તમે ડેટાબેઝની અંદરની જટિલતાઓને સમજી શકશો નહીં. આ એક વિશાળ વિષય હોવાથી, હું ધ્યાન કેન્દ્રિત કરીશ મને જે લાગે છે તે મહત્વનું છે: ડેટાબેઝ કેવી રીતે પ્રક્રિયા કરે છે એસક્યુએલ તપાસ. હું હમણાં જ પરિચય આપીશ મૂળભૂત ડેટાબેઝ ખ્યાલોજેથી લેખના અંતે તમને ખ્યાલ આવે કે હૂડ હેઠળ શું ચાલી રહ્યું છે.

કારણ કે આ એક લાંબો અને તકનીકી લેખ છે જેમાં ઘણા બધા અલ્ગોરિધમ્સ અને ડેટા સ્ટ્રક્ચર્સનો સમાવેશ થાય છે, તે વાંચવા માટે તમારો સમય કાઢો. કેટલીક વિભાવનાઓ સમજવી મુશ્કેલ હોઈ શકે છે; તમે તેમને છોડી શકો છો અને હજુ પણ સામાન્ય વિચાર મેળવી શકો છો.

તમારામાંથી વધુ જાણકાર લોકો માટે, આ લેખ 3 ભાગોમાં વહેંચાયેલો છે:

• નિમ્ન-સ્તર અને ઉચ્ચ-સ્તરના ડેટાબેઝ ઘટકોની ઝાંખી
• ક્વેરી ઑપ્ટિમાઇઝેશન પ્રક્રિયાની ઝાંખી
• ટ્રાન્ઝેક્શન અને બફર પૂલ મેનેજમેન્ટની ઝાંખી

મૂળભૂત પર પાછા

વર્ષો પહેલા (એક આકાશગંગામાં, ખૂબ દૂર...), વિકાસકર્તાઓને તેઓ કોડિંગ કરી રહ્યા હતા તે ઑપરેશનની સંખ્યા બરાબર જાણવી હતી. તેઓ તેમના અલ્ગોરિધમ્સ અને ડેટા સ્ટ્રક્ચર્સને હૃદયથી જાણતા હતા કારણ કે તેઓ તેમના ધીમા કમ્પ્યુટર્સની CPU અને મેમરીને બગાડવાનું પરવડે નહીં.

આ ભાગમાં, હું તમને આમાંના કેટલાક ખ્યાલોની યાદ અપાવીશ કારણ કે તે ડેટાબેઝને સમજવા માટે જરૂરી છે. હું ખ્યાલ પણ રજૂ કરીશ ડેટાબેઝ ઇન્ડેક્સ.

O(1) વિ O(n2)

આજકાલ, ઘણા વિકાસકર્તાઓ એલ્ગોરિધમ્સની સમય જટિલતા વિશે ધ્યાન આપતા નથી... અને તેઓ સાચા છે!

પરંતુ જ્યારે તમે ઘણા બધા ડેટા સાથે કામ કરી રહ્યાં હોવ (હું હજારો વાત નથી કરતો) અથવા જો તમે મિલિસેકન્ડ્સમાં સંઘર્ષ કરી રહ્યાં હોવ, તો આ ખ્યાલને સમજવો મહત્વપૂર્ણ બની જાય છે. અને જેમ તમે કલ્પના કરી શકો છો, ડેટાબેસેસને બંને પરિસ્થિતિઓનો સામનો કરવો પડશે! હું તમને મુદ્દાને પાર પાડવા માટે જરૂરી કરતાં વધુ સમય ફાળવીશ નહીં. આ અમને ખર્ચ-આધારિત ઑપ્ટિમાઇઝેશનના ખ્યાલને પછીથી સમજવામાં મદદ કરશે (ખર્ચ આધારિત ઑપ્ટિમાઇઝેશન).

કન્સેપ્ટ

અલ્ગોરિધમનો સમય જટિલતા ડેટાની આપેલ રકમ માટે અલ્ગોરિધમનો અમલ કરવામાં કેટલો સમય લાગશે તે જોવા માટે વપરાય છે. આ જટિલતાને વર્ણવવા માટે, અમે મોટા O ગાણિતિક સંકેતનો ઉપયોગ કરીએ છીએ. આ સંકેતનો ઉપયોગ ફંક્શન સાથે કરવામાં આવે છે જે દર્શાવે છે કે આપેલ સંખ્યાના ઇનપુટ્સ માટે અલ્ગોરિધમને કેટલી કામગીરીની જરૂર છે.

ઉદાહરણ તરીકે, જ્યારે હું કહું છું કે "આ અલ્ગોરિધમમાં જટિલતા O(some_function()) છે", તો તેનો અર્થ એ છે કે અલ્ગોરિધમને અમુક ચોક્કસ માત્રામાં ડેટાની પ્રક્રિયા કરવા માટે some_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 હોદ્દાની વાસ્તવિક વ્યાખ્યા આપી નથી, માત્ર એક વિચાર. તમે આ લેખ પર વાંચી શકો છો વિકિપીડિયા વાસ્તવિક (અસિમ્પ્ટોટિક) વ્યાખ્યા માટે.

મર્જ સોર્ટ

જ્યારે તમારે સંગ્રહને સૉર્ટ કરવાની જરૂર હોય ત્યારે તમે શું કરો છો? શું? તમે 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;

મર્જ સૉર્ટ સમસ્યાને નાની સમસ્યાઓમાં તોડે છે અને પછી મૂળ સમસ્યાનું પરિણામ મેળવવા માટે નાની સમસ્યાઓના પરિણામો શોધે છે (નોંધ: આ પ્રકારના અલ્ગોરિધમને ડિવાઈડ એન્ડ કોન્કર કહેવામાં આવે છે). જો તમે આ અલ્ગોરિધમ સમજી શકતા નથી, તો ચિંતા કરશો નહીં; મેં તેને પહેલીવાર જોયું ત્યારે મને સમજાયું નહીં. જો તે તમને મદદ કરી શકે, તો હું આ અલ્ગોરિધમને બે તબક્કાના અલ્ગોરિધમ તરીકે જોઉં છું:

• વિભાગનો તબક્કો, જ્યાં એરે નાના એરેમાં વિભાજિત થાય છે
• સૉર્ટિંગનો તબક્કો એ છે જ્યાં નાના એરેને જોડવામાં આવે છે (યુનિયનનો ઉપયોગ કરીને) મોટી એરે બનાવવા માટે.

વિભાજન તબક્કો

વિભાજન તબક્કામાં, એરેને 3 પગલાંઓમાં એકાત્મક એરેમાં વિભાજિત કરવામાં આવે છે. પગલાંઓની ઔપચારિક સંખ્યા log(N) છે ( N=8 થી, log(N) = 3).

હું આ કેવી રીતે જાણી શકું?

હું પ્રતિભાશાળી છું! એક શબ્દમાં - ગણિત. વિચાર એ છે કે દરેક પગલું મૂળ એરેના કદને 2 વડે વિભાજિત કરે છે. પગલાંઓની સંખ્યા એ છે કે તમે મૂળ એરેને બે ભાગમાં કેટલી વખત વિભાજીત કરી શકો છો. આ લઘુગણક (આધાર 2) ની ચોક્કસ વ્યાખ્યા છે.

વર્ગીકરણ તબક્કો

સૉર્ટિંગ તબક્કામાં, તમે એકાત્મક (સિંગલ-એલિમેન્ટ) એરેથી પ્રારંભ કરો છો. દરેક પગલા દરમિયાન તમે બહુવિધ મર્જ ઑપરેશન્સ લાગુ કરો છો અને કુલ કિંમત N = 8 ઑપરેશન્સ છે:

• પ્રથમ તબક્કામાં તમારી પાસે 4 મર્જ છે જેની કિંમત 2 ઓપરેશન્સ છે
• બીજા પગલામાં તમારી પાસે 2 મર્જ છે જેની કિંમત 4 ઓપરેશન્સ છે
• ત્રીજા પગલામાં તમારી પાસે 1 મર્જ છે જેની કિંમત 8 ઓપરેશન્સ છે

લોગ(એન) સ્ટેપ્સ હોવાથી, કુલ ખર્ચ એન * log(N) કામગીરી.

મર્જ સૉર્ટના ફાયદા

આ અલ્ગોરિધમ શા માટે આટલું શક્તિશાળી છે?

કારણ કે:

• તમે મેમરી ફૂટપ્રિન્ટને ઘટાડવા માટે તેને બદલી શકો છો જેથી કરીને તમે નવા એરે ન બનાવો પરંતુ ઇનપુટ એરેમાં સીધા ફેરફાર કરો.

નોંધ: આ પ્રકારના અલ્ગોરિધમને કહેવામાં આવે છે in-સ્થળ (વધારાની મેમરી વિના વર્ગીકરણ).

• તમે નોંધપાત્ર ડિસ્ક I/O ઓવરહેડનો ખર્ચ કર્યા વિના એક જ સમયે ડિસ્ક જગ્યા અને થોડી માત્રામાં મેમરીનો ઉપયોગ કરવા માટે તેને બદલી શકો છો. મેમરીમાં ફક્ત તે જ ભાગો લોડ કરવાનો વિચાર છે જે હાલમાં પ્રક્રિયા કરવામાં આવી રહી છે. જ્યારે તમારે માત્ર 100-મેગાબાઇટ મેમરી બફર સાથે મલ્ટિ-ગીગાબાઇટ ટેબલને સૉર્ટ કરવાની જરૂર હોય ત્યારે આ મહત્વપૂર્ણ છે.

નોંધ: આ પ્રકારના અલ્ગોરિધમને કહેવામાં આવે છે બાહ્ય પ્રકાર.

• તમે તેને બહુવિધ પ્રક્રિયાઓ/થ્રેડો/સર્વર પર ચલાવવા માટે બદલી શકો છો.

ઉદાહરણ તરીકે, વિતરિત મર્જ સૉર્ટ એ મુખ્ય ઘટકોમાંનું એક છે Hadoop (જે મોટા ડેટામાં એક માળખું છે).

• આ અલ્ગોરિધમ લીડને સોનામાં ફેરવી શકે છે (ખરેખર!).

આ સોર્ટિંગ અલ્ગોરિધમનો ઉપયોગ મોટાભાગના (જો બધા નહીં) ડેટાબેસેસમાં થાય છે, પરંતુ તે એકમાત્ર નથી. જો તમે વધુ જાણવા માંગતા હો, તો તમે આ વાંચી શકો છો સંશોધન કાર્ય, જે સામાન્ય ડેટાબેઝ સોર્ટિંગ અલ્ગોરિધમ્સના ગુણદોષની ચર્ચા કરે છે.

અરે, વૃક્ષ અને હેશ ટેબલ

હવે જ્યારે આપણે સમયની જટિલતા અને વર્ગીકરણનો વિચાર સમજીએ છીએ, તો મારે તમને 3 ડેટા સ્ટ્રક્ચર્સ વિશે જણાવવું જોઈએ. આ મહત્વપૂર્ણ છે કારણ કે તેઓ આધુનિક ડેટાબેઝનો આધાર છે. હું ખ્યાલ પણ રજૂ કરીશ ડેટાબેઝ ઇન્ડેક્સ.

અરે

દ્વિ-પરિમાણીય એરે એ સૌથી સરળ ડેટા માળખું છે. કોષ્ટકને એરે તરીકે વિચારી શકાય છે. દાખ્લા તરીકે:

આ 2-પરિમાણીય એરે પંક્તિઓ અને કૉલમ્સ સાથેનું કોષ્ટક છે:

• દરેક રેખા એક એન્ટિટી દર્શાવે છે
• કૉલમ પ્રોપર્ટીઝ સ્ટોર કરે છે જે એન્ટિટીનું વર્ણન કરે છે.
• દરેક કૉલમ ચોક્કસ પ્રકારનો ડેટા સ્ટોર કરે છે (પૂર્ણાંક, શબ્દમાળા, તારીખ...).

ડેટા સ્ટોર કરવા અને વિઝ્યુઅલાઈઝ કરવા માટે આ અનુકૂળ છે, જો કે, જ્યારે તમારે કોઈ ચોક્કસ મૂલ્ય શોધવાની જરૂર હોય, ત્યારે આ યોગ્ય નથી.

ઉદાહરણ તરીકે, જો તમે યુકેમાં કામ કરતા તમામ લોકોને શોધવા માંગતા હો, તો તમારે તે પંક્તિ યુકેની છે કે કેમ તે નક્કી કરવા માટે દરેક પંક્તિ જોવાની જરૂર પડશે. તે તમને N વ્યવહારોનો ખર્ચ કરશેજ્યાં N - લીટીઓની સંખ્યા, જે ખરાબ નથી, પરંતુ શું કોઈ ઝડપી રીત હોઈ શકે છે? હવે આપણે વૃક્ષોથી પરિચિત થવાનો સમય છે.

નોંધ: મોટા ભાગના આધુનિક ડેટાબેઝ કોષ્ટકોને કાર્યક્ષમ રીતે સંગ્રહિત કરવા માટે વિસ્તૃત એરે પ્રદાન કરે છે: heap-organized કોષ્ટકો અને index-organized કોષ્ટકો. પરંતુ આ કૉલમના જૂથમાં ઝડપથી ચોક્કસ સ્થિતિ શોધવાની સમસ્યાને બદલતું નથી.

ડેટાબેઝ વૃક્ષ અને અનુક્રમણિકા

દ્વિસંગી શોધ વૃક્ષ એ વિશિષ્ટ ગુણધર્મ ધરાવતું દ્વિસંગી વૃક્ષ છે, દરેક નોડ પરની કી આ હોવી જોઈએ:

• ડાબી સબટ્રીમાં સંગ્રહિત બધી કીઓ કરતાં મોટી
• જમણી સબટ્રીમાં સંગ્રહિત બધી કી કરતાં ઓછી

ચાલો જોઈએ કે આનો અર્થ શું થાય છે

આઈડિયા

આ વૃક્ષમાં 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, નોડ અસ્તિત્વમાં છે. હું નોડની અંદરની પંક્તિ ID પુનઃપ્રાપ્ત કરું છું (ચિત્રમાં બતાવેલ નથી) અને આપેલ પંક્તિ ID માટે કોષ્ટકમાં જુઓ.
• પંક્તિ ID ને જાણવાથી મને ખબર પડે છે કે કોષ્ટકમાં ડેટા ક્યાં છે, જેથી હું તેને તરત જ પુનઃપ્રાપ્ત કરી શકું.

અંતે, બંને શોધો મને વૃક્ષની અંદરના સ્તરોની સંખ્યા ખર્ચ કરશે. જો તમે મર્જ સૉર્ટ વિશેનો ભાગ કાળજીપૂર્વક વાંચો, તો તમારે જોવું જોઈએ કે ત્યાં લોગ(એન) સ્તરો છે. તે તારણ આપે છે, શોધ ખર્ચ લોગ(N), ખરાબ નથી!

ચાલો આપણી સમસ્યા પર પાછા ફરીએ

પરંતુ આ ખૂબ જ અમૂર્ત છે, તો ચાલો આપણી સમસ્યા પર પાછા આવીએ. સાદા પૂર્ણાંકને બદલે, પાછલા કોષ્ટકમાં કોઈના દેશને રજૂ કરતી સ્ટ્રિંગની કલ્પના કરો. ધારો કે તમારી પાસે એક વૃક્ષ છે જેમાં કોષ્ટકનું "દેશ" ફીલ્ડ (કૉલમ 3) છે:

• જો તમારે જાણવું હોય કે યુકેમાં કોણ કામ કરે છે
• ગ્રેટ બ્રિટનનું પ્રતિનિધિત્વ કરતી નોડ મેળવવા માટે તમે વૃક્ષને જુઓ
• "UKnode" ની અંદર તમને UK વર્કર રેકોર્ડ્સનું સ્થાન મળશે.

જો તમે એરેનો સીધો ઉપયોગ કરો છો તો આ શોધમાં N ઑપરેશનને બદલે લૉગ(N) ઑપરેશનનો ખર્ચ થશે. તમે હમણાં જ રજૂ કર્યું હતું ડેટાબેઝ ઇન્ડેક્સ.

જ્યાં સુધી તમારી પાસે કી (એટલે ​​કે ફીલ્ડ જૂથો) ની સરખામણી કરવા માટેનું કાર્ય હોય ત્યાં સુધી તમે ફીલ્ડના કોઈપણ જૂથ (સ્ટ્રિંગ, નંબર, 2 લીટીઓ, નંબર અને સ્ટ્રિંગ, તારીખ...) માટે ઇન્ડેક્સ ટ્રી બનાવી શકો છો જેથી તમે સેટ કરી શકો. કીઓ વચ્ચે ઓર્ડર (જે ડેટાબેઝમાં કોઈપણ મૂળભૂત પ્રકારો માટેનો કેસ છે).

B+TreeIndex

જ્યારે આ વૃક્ષ ચોક્કસ મૂલ્ય મેળવવા માટે સારી રીતે કામ કરે છે, જ્યારે તમને જરૂર હોય ત્યારે એક મોટી સમસ્યા હોય છે બે મૂલ્યો વચ્ચે બહુવિધ ઘટકો મેળવો. આના માટે O(N) નો ખર્ચ થશે કારણ કે તમારે વૃક્ષના દરેક નોડને જોવું પડશે અને તે આ બે મૂલ્યો વચ્ચે છે કે કેમ તે તપાસવું પડશે (દા.ત. વૃક્ષના ઓર્ડર કરેલ ટ્રાવર્સલ સાથે). વધુમાં, આ ઑપરેશન ડિસ્ક I/O મૈત્રીપૂર્ણ નથી કારણ કે તમારે આખું વૃક્ષ વાંચવું પડશે. આપણે કાર્યક્ષમ રીતે એક્ઝિક્યુટ કરવાનો રસ્તો શોધવાની જરૂર છે શ્રેણી વિનંતી. આ સમસ્યાને ઉકેલવા માટે, આધુનિક ડેટાબેઝ B+Tree નામના અગાઉના વૃક્ષના સંશોધિત સંસ્કરણનો ઉપયોગ કરે છે. બી+ટ્રી વૃક્ષમાં:

• માત્ર સૌથી નીચલા ગાંઠો (પાંદડા) સ્ટોર માહિતી (સંબંધિત કોષ્ટકમાં પંક્તિઓનું સ્થાન)
• બાકીના ગાંઠો અહીં છે રૂટીંગ માટે યોગ્ય નોડ પર શોધ દરમિયાન.

જેમ તમે જોઈ શકો છો, અહીં વધુ ગાંઠો છે (બે વાર). ખરેખર, તમારી પાસે વધારાના નોડ્સ છે, "નિર્ણય ગાંઠો", જે તમને યોગ્ય નોડ (જે સંકળાયેલ કોષ્ટકમાં પંક્તિઓનું સ્થાન સંગ્રહિત કરે છે) શોધવામાં મદદ કરશે. પરંતુ શોધ જટિલતા હજુ પણ O(log(N)) છે (ત્યાં માત્ર એક વધુ સ્તર છે). મોટો તફાવત એ છે નીચલા સ્તરે ગાંઠો તેમના અનુગામીઓ સાથે જોડાયેલા છે.

આ B+Tree સાથે, જો તમે 40 અને 100 ની વચ્ચેના મૂલ્યો શોધી રહ્યા છો:

• તમારે ફક્ત 40 (અથવા 40 પછીનું સૌથી નજીકનું મૂલ્ય જો 40 અસ્તિત્વમાં ન હોય તો) શોધવાની જરૂર છે જેમ તમે અગાઉના વૃક્ષ સાથે કર્યું હતું.
• પછી તમે 40 સુધી પહોંચો ત્યાં સુધી સીધી વારસદાર લિંકનો ઉપયોગ કરીને 100 વારસદારો એકત્રિત કરો.

ચાલો કહીએ કે તમને M અનુગામીઓ મળે છે અને વૃક્ષમાં N નોડ્સ છે. ચોક્કસ નોડ શોધવામાં અગાઉના વૃક્ષની જેમ લોગ(એન) ખર્ચ થાય છે. પરંતુ એકવાર તમે આ નોડ મેળવી લો, પછી તમને M ઓપરેશન્સમાં તેમના અનુગામીઓના સંદર્ભો સાથે M અનુગામીઓ મળશે. આ શોધની કિંમત માત્ર M+log(N) છે અગાઉના વૃક્ષ પર N કામગીરીની સરખામણીમાં કામગીરી. તદુપરાંત, તમારે સંપૂર્ણ વૃક્ષ (ફક્ત M+log(N) નોડ્સ) વાંચવાની જરૂર નથી, જેનો અર્થ થાય છે ઓછી ડિસ્ક વપરાશ. જો 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+વૃક્ષ. જો તમને ડેટાબેઝમાં 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).

એરે વિ હેશ ટેબલ

શા માટે એરેનો ઉપયોગ કરશો નહીં?

હમ્મ, સારો પ્રશ્ન.

• હેશ ટેબલ હોઈ શકે છે આંશિક રીતે મેમરીમાં લોડ, અને બાકીના સેગમેન્ટ્સ ડિસ્ક પર રહી શકે છે.
• એરે સાથે તમારે મેમરીમાં સંલગ્ન જગ્યાનો ઉપયોગ કરવો આવશ્યક છે. જો તમે મોટું ટેબલ લોડ કરી રહ્યા છો પૂરતી સતત જગ્યા શોધવી ખૂબ જ મુશ્કેલ છે.
• હેશ ટેબલ માટે, તમે તમને જોઈતી કી પસંદ કરી શકો છો (ઉદાહરણ તરીકે, દેશ અને વ્યક્તિનું છેલ્લું નામ).

વધુ માહિતી માટે, તમે વિશે લેખ વાંચી શકો છો જાવાહેશમેપ, જે હેશ ટેબલનું કાર્યક્ષમ અમલીકરણ છે; આ લેખમાં આવરી લેવામાં આવેલ ખ્યાલોને સમજવા માટે તમારે જાવા સમજવાની જરૂર નથી.

સોર્સ: www.habr.com