ሃይ ሀብር! የጽሁፉን ትርጉም ለእርስዎ ትኩረት አቀርባለሁ።
"ተዛማጅ የውሂብ ጎታ እንዴት እንደሚሰራ".

ወደ ተዛማጅ የውሂብ ጎታዎች ስንመጣ የሆነ ነገር ይጎድላል ​​ብዬ ከማሰብ አልችልም። በሁሉም ቦታ ጥቅም ላይ ይውላሉ. ከትንሽ እና ጠቃሚ SQLite እስከ ኃይለኛ ቴራዳታ ድረስ ብዙ የተለያዩ የመረጃ ቋቶች አሉ። ግን የመረጃ ቋቱ እንዴት እንደሚሰራ የሚያብራሩ ጥቂት ጽሑፎች ብቻ አሉ። ምን ያህል ጥቂት ውጤቶች እንዳሉ ለማየት "howdoesarelationaldatabasework" በመጠቀም እራስዎን መፈለግ ይችላሉ። ከዚህም በላይ እነዚህ ጽሑፎች አጭር ናቸው. የቅርብ ጊዜዎቹ በዝቅ ቴክኖሎጂዎች (BigData፣ NoSQL ወይም JavaScript) እየፈለጉ ከሆነ እንዴት እንደሚሠሩ የሚገልጹ ተጨማሪ ጥልቅ ጽሑፎችን ያገኛሉ።

ተዛማጅ የመረጃ ቋቶች በጣም ያረጁ እና በጣም አሰልቺ ናቸው ከዩኒቨርሲቲ ኮርሶች፣ የምርምር ወረቀቶች እና መጽሃፎች ውጭ ለመብራራት?

እንደ ገንቢ፣ ያልገባኝን ነገር መጠቀም እጠላለሁ። እና የውሂብ ጎታዎች ከ 40 ዓመታት በላይ ጥቅም ላይ ከዋሉ, ምክንያት ሊኖር ይገባል. በየእለቱ የምጠቀምባቸውን እነዚህን እንግዳ ጥቁር ሳጥኖች በትክክል ለመረዳት ባለፉት አመታት በመቶዎች የሚቆጠሩ ሰዓታት አሳልፌያለሁ። ተዛማጅ የውሂብ ጎታዎች እነሱ ምክንያቱም በጣም አስደሳች ጠቃሚ እና እንደገና ጥቅም ላይ በሚውሉ ጽንሰ-ሐሳቦች ላይ የተመሰረተ. የውሂብ ጎታውን ለመረዳት ፍላጎት ካሎት፣ ነገር ግን ወደዚህ ሰፊ ርዕስ ውስጥ ለመግባት ጊዜ ወይም ዝንባሌ ከሌለዎት፣ በዚህ ጽሑፍ መደሰት አለብዎት።

የዚህ ጽሑፍ ርዕስ ግልጽ ቢሆንም፣ የዚህ ጽሑፍ ዓላማ የውሂብ ጎታውን እንዴት እንደሚጠቀሙ መረዳት አይደለም. ስለዚህም እ.ኤ.አ. ቀላል የግንኙነት ጥያቄ እና መሰረታዊ ጥያቄዎችን እንዴት እንደሚጽፉ አስቀድመው ማወቅ አለብዎት ክሩድ; አለበለዚያ ይህን ጽሑፍ ላይረዱት ይችላሉ. ማወቅ ያለብዎት ብቸኛው ነገር ይህ ነው, የቀረውን እገልጻለሁ.

እንደ ስልተ ቀመሮች የጊዜ ውስብስብነት (BigO) ባሉ አንዳንድ የኮምፒውተር ሳይንስ መሰረታዊ መርሆች እጀምራለሁ። አንዳንዶቻችሁ ይህንን ፅንሰ-ሃሳብ እንደምትጠሉ አውቃለሁ ነገር ግን ያለ እሱ በመረጃ ቋቱ ውስጥ ያሉትን ውስብስብ ነገሮች መረዳት አይችሉም። ይህ ትልቅ ርዕስ ስለሆነ ላይ አተኩራለሁ አስፈላጊ ነው ብዬ የማስበው: የውሂብ ጎታ እንዴት እንደሚሰራ SQL መጠይቅ. በቃ አስተዋውቃለሁ። መሠረታዊ የውሂብ ጎታ ጽንሰ-ሐሳቦችስለዚህ በአንቀጹ መጨረሻ ላይ ከሽፋኑ ስር ምን እየተደረገ እንዳለ ሀሳብ አለዎት ።

ይህ ብዙ ስልተ ቀመሮችን እና የውሂብ አወቃቀሮችን የሚያካትት ረጅም እና ቴክኒካል ጽሑፍ ስለሆነ እሱን ለማንበብ ጊዜዎን ይውሰዱ። አንዳንድ ጽንሰ-ሐሳቦች ለመረዳት አስቸጋሪ ሊሆን ይችላል; እነሱን መዝለል እና አሁንም አጠቃላይ ሀሳቡን ማግኘት ይችላሉ።

በመካከላችሁ የበለጠ እውቀት ላለው ፣ ይህ ጽሑፍ በ 3 ክፍሎች ተከፍሏል ።

• ዝቅተኛ-ደረጃ እና ከፍተኛ-ደረጃ የውሂብ ጎታ ክፍሎች አጠቃላይ እይታ
• የጥያቄ ማሻሻያ ሂደት አጠቃላይ እይታ
• የግብይት እና የቋት ገንዳ አስተዳደር አጠቃላይ እይታ

ወደ መሰረታዊ ነገሮች ተመለስ

ከዓመታት በፊት (በጋላክሲ በሩቅ፣ በሩቅ...)፣ ገንቢዎች ኮድ የሚያደርጉባቸውን የክወናዎች ብዛት በትክክል ማወቅ ነበረባቸው። የዘገየ ኮምፒውተሮቻቸውን ሲፒዩ እና ሚሞሪ ማባከን ስለማይችሉ ስልተ ቀመራቸውን እና ዳታ አወቃቀራቸውን ያውቁ ነበር።

በዚህ ክፍል ውስጥ፣ የውሂብ ጎታውን ለመረዳት አስፈላጊ ስለሆኑ ከእነዚህ ጽንሰ-ሀሳቦች ውስጥ አንዳንዶቹን አስታውሳችኋለሁ። ፅንሰ-ሀሳቡንም አስተዋውቃለሁ። የውሂብ ጎታ መረጃ ጠቋሚ.

ኦ(1) vs O(n2)

በአሁኑ ጊዜ፣ ብዙ ገንቢዎች ስለ ስልተ ቀመሮች የጊዜ ውስብስብነት ግድ የላቸውም... እና ትክክል ናቸው!

ነገር ግን ከብዙ ዳታ ጋር ስትገናኝ (ሺህ አላወራም) ወይም በሚሊሰከንዶች እየታገልክ ከሆነ ይህን ጽንሰ ሃሳብ መረዳት በጣም አስፈላጊ ይሆናል። እና እርስዎ እንደሚገምቱት, የውሂብ ጎታዎች ሁለቱንም ሁኔታዎች መቋቋም አለባቸው! ነጥቡን ለመረዳት ከሚያስፈልገው በላይ ጊዜ እንዲያሳልፉ አላደርግም። ይህ በኋላ ላይ ወጪን መሰረት ያደረገ የማመቻቸት ጽንሰ-ሀሳብ እንድንረዳ ይረዳናል (ዋጋ ላይ የተመሠረተ ማመቻቸት).

ጽንሰ-ሐሳብ

የአልጎሪዝም የጊዜ ውስብስብነት ለተወሰነ የውሂብ መጠን አልጎሪዝምን ለመተግበር ምን ያህል ጊዜ እንደሚወስድ ለማየት ይጠቅማል. ይህንን ውስብስብነት ለመግለፅ ትልቅ O የሂሳብ ኖት እንጠቀማለን ይህ ምልክት ጥቅም ላይ የዋለው ለአንድ የተወሰነ የግብአት ብዛት ምን ያህል ኦፕሬሽኖች እንደሚያስፈልገው ከሚገልጽ ተግባር ጋር ነው።

ለምሳሌ "ይህ አልጎሪዝም ውስብስብነት O(አንዳንድ_ተግባር()) አለው" ብዬ ስናገር ስልተ ቀመር የተወሰነ መጠን ያለው ውሂብ ለመስራት አንዳንድ_ተግባር(a_certain_amount_of_data) ስራዎችን ይፈልጋል ማለት ነው።

ስለዚህ ወሳኙ የውሂብ መጠን አይደለም**አለበለዚያ ** የውሂብ መጠን በመጨመር የክወናዎች ብዛት እንዴት እንደሚጨምር. የጊዜ ውስብስብነት ትክክለኛ የክዋኔዎች ብዛት አይሰጥም, ነገር ግን የማስፈጸሚያ ጊዜን ለመገመት ጥሩ መንገድ ነው.

በዚህ ግራፍ ውስጥ ለተለያዩ የአልጎሪዝም የጊዜ ውስብስብ ዓይነቶች የግብአት ውሂብ መጠን ጋር ሲነፃፀር የክዋኔዎችን ብዛት ማየት ይችላሉ። እነሱን ለማሳየት ሎጋሪዝም ሚዛን ተጠቀምኩ። በሌላ አነጋገር የውሂብ መጠን በፍጥነት ከ 1 ወደ 1 ቢሊዮን ይጨምራል. እኛ ማየት እንችላለን:

• ኦ(1) ወይም የማያቋርጥ ውስብስብነት ቋሚ ሆኖ ይቆያል (አለበለዚያ ቋሚ ውስብስብነት ተብሎ አይጠራም)።
• O(መዝገብ(n)) በቢሊዮኖች በሚቆጠር መረጃም ቢሆን ዝቅተኛ ነው።.
• በጣም አስቸጋሪው ችግር - ኦ(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 ሚሴ ታጣለህ፣ ይህም ጊዜ ብቻ ነው አይንህን ብልጭ ድርግም የሚለው። በእርግጥ, ዘመናዊ ማቀነባበሪያዎች ማቀነባበር ይችላሉ በሰከንድ በመቶ ሚሊዮኖች የሚቆጠሩ ስራዎች. ለዚህም ነው በብዙ የአይቲ ፕሮጄክቶች ውስጥ አፈጻጸም እና ማመቻቸት ጉዳይ አይደሉም።

እንደተናገርኩት፣ ከፍተኛ መጠን ካለው መረጃ ጋር ሲሰራ ይህን ጽንሰ ሃሳብ ማወቅ አሁንም አስፈላጊ ነው። በዚህ ጊዜ አልጎሪዝም 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: ይህ ደግሞ የከፋ ነው! በዚህ ጽሑፍ መካከል ከምናያቸው ስልተ ቀመሮች አንዱ ይህ ውስብስብነት አለው (እና በእውነቱ በብዙ የውሂብ ጎታዎች ውስጥ ጥቅም ላይ ይውላል)።
• factorial n: በትንሽ መጠን ውሂብ እንኳን ውጤትዎን በጭራሽ አያገኙም።
• nn: ይህ ውስብስብ ነገር ካጋጠመዎት, ይህ የእርስዎ የተግባር መስክ መሆኑን እራስዎን ይጠይቁ ...

ማሳሰቢያ፡ የትልቅ ኦ ስያሜ ትክክለኛ ፍቺን አልሰጠሁህም ሀሳብ ብቻ። ይህንን ጽሑፍ በ ላይ ማንበብ ይችላሉ ዊኪፔዲያ ለትክክለኛው (asymptotic) ፍቺ.

አዋህድ ደርድር

ስብስብን መደርደር ሲያስፈልግ ምን ታደርጋለህ? ምንድን? እርስዎ ዓይነት() ተግባር ብለው ይጠሩታል... እሺ ጥሩ መልስ... ለዳታቤዝ ግን ይህ አይነት() ተግባር እንዴት እንደሚሰራ መረዳት አለቦት።

ብዙ ጥሩ የመደርደር ስልተ ቀመሮች አሉ፣ ስለዚህ በጣም አስፈላጊ በሆኑት ላይ አተኩራለሁ፡- መደርደር አዋህድ. አሁን ውሂብ መደርደር ለምን ጠቃሚ እንደሆነ ላይረዱ ይችላሉ ነገርግን ከጥያቄው ማሻሻያ ክፍል በኋላ ማድረግ አለብዎት። በተጨማሪም፣ የውህደት ዓይነትን መረዳታችን የተጠራውን የጋራ ዳታቤዝ መቀላቀል ተግባር በኋላ እንድንረዳ ይረዳናል። ሁለቱን ድርጅቶች ተዋሐደ መቀላቀል (ውህደት ማህበር).

አዋህድ

ልክ እንደ ብዙ ጠቃሚ ስልተ ቀመሮች፣ መደርደር መቀላቀል በብልሃት ላይ የተመሰረተ ነው፡ 2 የተደረደሩ መጠናቸው N/2 ን ወደ N-element የተደረደሩ ድርድር ወጪዎች N ኦፕሬሽኖችን ብቻ ነው። ይህ ክዋኔ ውህደት ይባላል።

በቀላል ምሳሌ ይህ ምን ማለት እንደሆነ እንይ፡-

ይህ አኃዝ የሚያሳየው የመጨረሻውን የተደረደሩ ባለ 8-ኤለመንት ድርድር ለመገንባት በ2 ባለ 4-ኤለመንት ድርድሮች ላይ አንድ ጊዜ ብቻ መደጋገም ያስፈልግዎታል። ሁለቱም ባለ 4-አባል ድርድሮች አስቀድመው የተደረደሩ ስለሆኑ፡-

• 1) ሁለቱንም የአሁኑን አካላት በሁለት ድርድሮች (በመጀመሪያው የአሁኑ = መጀመሪያ) ያወዳድራሉ
• 2) ከዚያም ወደ 8 ኤለመንቶች ድርድር ለማስገባት ትንሹን ይውሰዱ
• 3) እና ትንሹን ንጥረ ነገር ወደ ወሰዱበት ድርድር ውስጥ ወደሚቀጥለው አካል ይሂዱ
• እና የአንዱ ድርድሮች የመጨረሻውን አካል እስኪደርሱ ድረስ 1,2,3፣XNUMX፣XNUMX ይድገሙት።
• ከዚያም ወደ 8 ኤለመንቶች ድርድር ለማስገባት የሌላኛውን ድርድር ቀሪ አካላት ወስደዋቸዋል።

ይህ የሚሰራው ሁለቱም ባለ 4-ኤለመንት ድርድሮች ስለተደረደሩ እና በእነዚያ ድርድሮች ውስጥ "መመለስ" የለብዎትም።

አሁን ዘዴውን ስለተረዳን የውህደት የእኔ pseudocode እነሆ፡-

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 ፣ log(N) = 3)።

ይህንን እንዴት አውቃለሁ?

ጎበዝ ነኝ! በአንድ ቃል - ሂሳብ. ሀሳቡ እያንዳንዱ እርምጃ የዋናውን ድርድር መጠን በ 2 ይከፍላል. የእርምጃዎች ብዛት ዋናውን ድርድር ለሁለት መከፋፈል የሚችሉበት ጊዜ ብዛት ነው. ይህ የሎጋሪዝም ትክክለኛ ፍቺ ነው (ቤዝ 2)።

ደረጃ መደርደር

በመደርደር ደረጃ፣ በአንድ ነጠላ (ነጠላ ክፍል) ድርድሮች ይጀምራሉ። በእያንዳንዱ እርምጃ ብዙ የማዋሃድ ስራዎችን ይተገብራሉ እና አጠቃላይ ወጪ N = 8 ክወናዎች ነው:

• በመጀመሪያ ደረጃ እያንዳንዳቸው 4 ስራዎችን የሚከፍሉ 2 ውህዶች አሉዎት
• በሁለተኛው ደረጃ እያንዳንዳቸው 2 ክዋኔዎች የሚያወጡ 4 ውህዶች አሉዎት
• በሦስተኛው ደረጃ 1 ክዋኔዎች የሚያስከፍል 8 ውህደት አለዎት

የምዝግብ ማስታወሻ (N) ደረጃዎች ስላሉ፣ ጠቅላላ ወጪ N * log (N) ክወናዎች.

የማዋሃድ ዓይነቶች ጥቅሞች

ይህ አልጎሪዝም በጣም ኃይለኛ የሆነው ለምንድነው?

ምክንያቱም፡-

• አዲስ ድርድሮች እንዳይፈጥሩ ነገር ግን የግቤት ድርድርን በቀጥታ እንዲቀይሩ የማስታወሻውን አሻራ ለመቀነስ መቀየር ይችላሉ።

ማሳሰቢያ፡ የዚህ አይነት ስልተ ቀመር ይባላል in-ቦታ (ያለ ተጨማሪ ማህደረ ትውስታ መደርደር).

• ጉልህ የሆነ የዲስክ I/O በላይ ሳያደርጉ የዲስክ ቦታን እና ትንሽ ማህደረ ትውስታን በተመሳሳይ ጊዜ ለመጠቀም መለወጥ ይችላሉ። ሃሳቡ አሁን እየተሰሩ ያሉትን ክፍሎች ብቻ ወደ ማህደረ ትውስታ መጫን ነው። ባለብዙ ጊጋባይት ሠንጠረዥ ባለ 100 ሜጋባይት ማህደረ ትውስታ ቋት ብቻ መደርደር ሲያስፈልግ ይህ አስፈላጊ ነው።

ማሳሰቢያ፡ የዚህ አይነት ስልተ ቀመር ይባላል ውጫዊ ዓይነት.

• በበርካታ ሂደቶች/ክሮች/ሰርቨሮች ላይ እንዲሰራ መቀየር ትችላለህ።

ለምሳሌ፣ የተከፋፈለ የውህደት አይነት ከዋና ዋና አካላት አንዱ ነው። Hadoop (ይህም በትልቅ ውሂብ ውስጥ መዋቅር ነው).

• ይህ አልጎሪዝም እርሳስን ወደ ወርቅ (በእርግጥ!) ሊለውጠው ይችላል.

ይህ የመደርደር ስልተ-ቀመር በአብዛኛዎቹ (ሁሉም ካልሆነ) የውሂብ ጎታዎች ውስጥ ጥቅም ላይ ይውላል, ግን እሱ ብቻ አይደለም. የበለጠ ለማወቅ ከፈለጉ ይህንን ማንበብ ይችላሉ። የምርምር ሥራየጋራ የመረጃ ቋት መደርደር ስልተ ቀመሮችን ጥቅሙን እና ጉዳቱን የሚያብራራ።

ድርድር ፣ የዛፍ እና የሃሽ ጠረጴዛ

አሁን የጊዜ ውስብስብነት እና የመደርደር ሀሳቡን ከተረዳን, ስለ 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) ስራዎችን ያስከፍላል። አሁን ያቀረብከው ነው። የውሂብ ጎታ መረጃ ጠቋሚ.

ቁልፎችን (የመስክ ቡድኖችን) የማወዳደር ተግባር እስካልዎት ድረስ ለማንኛውም የመስኮች ቡድን (ሕብረቁምፊ፣ ቁጥር፣ 2 መስመሮች፣ ቁጥር እና ሕብረቁምፊ፣ ቀን...) ማውጫ ዛፍ መገንባት ይችላሉ። ከቁልፎቹ መካከል ማዘዝ (ይህም በመረጃ ቋቱ ውስጥ ለማንኛውም መሰረታዊ ዓይነቶች ነው).

B+TreeIndex

ይህ ዛፍ የተወሰነ እሴት ለማግኘት በደንብ ቢሰራም, በሚፈልጉበት ጊዜ ትልቅ ችግር አለ በሁለት እሴቶች መካከል ብዙ ንጥረ ነገሮችን ያግኙ. ይህ ዋጋ O(N) ያስከፍላል ምክንያቱም በዛፉ ውስጥ ያለውን እያንዳንዱን መስቀለኛ መንገድ መመልከት እና በእነዚህ ሁለት እሴቶች መካከል መሆኑን ያረጋግጡ (ለምሳሌ በታዘዘ የዛፍ ማቋረጥ)። ከዚህም በላይ ሙሉውን ዛፍ ማንበብ ስላለብዎት ይህ ክዋኔ የዲስክ I / O ተስማሚ አይደለም. በብቃት የምንሰራበትን መንገድ መፈለግ አለብን ክልል ጥያቄ. ይህንን ችግር ለመቅረፍ ዘመናዊ የመረጃ ቋቶች የተሻሻለው የቀድሞ ዛፍ ቢ+ ዛፍን ይጠቀማሉ። በ B+ ዛፍ ውስጥ;

• በጣም ዝቅተኛ አንጓዎች (ቅጠሎች) ብቻ መረጃን ማከማቸት (በተዛማጅ ሰንጠረዥ ውስጥ የረድፎች ቦታ)
• የተቀሩት አንጓዎች እዚህ አሉ። ለመዘዋወር ወደ ትክክለኛው መስቀለኛ መንገድ በፍለጋ ወቅት.

እንደሚመለከቱት, እዚህ ተጨማሪ አንጓዎች (ሁለት ጊዜ) አሉ. በእርግጥ, ተጨማሪ አንጓዎች, "የውሳኔ አንጓዎች" አሉዎት, ይህም ትክክለኛውን መስቀለኛ መንገድ (በተጓዳኝ ሠንጠረዥ ውስጥ ያሉትን የረድፎች ቦታ የሚያከማች) እንዲያገኙ ይረዳዎታል. ግን የፍለጋው ውስብስብነት አሁንም ኦ(ሎግ(N)) ነው (አንድ ተጨማሪ ደረጃ ብቻ ነው ያለው)። ትልቁ ልዩነቱ ይህ ነው። በዝቅተኛ ደረጃ ላይ ያሉ አንጓዎች ከተተኪዎቻቸው ጋር የተገናኙ ናቸው.

በዚህ B+Tree፣ በ40 እና 100 መካከል እሴቶችን እየፈለጉ ከሆነ፡-

• ልክ እንደ ቀድሞው ዛፍ 40 (ወይም ከ 40 በኋላ 40 ከሌለው በጣም ቅርብ የሆነ እሴት) መፈለግ ያስፈልግዎታል።
• ከዚያ 40 እስኪደርሱ ድረስ ቀጥታ ወራሾችን በመጠቀም 100 ወራሾችን ይሰብስቡ።

M ተተኪዎችን አገኘህ እንበል እና ዛፉ N ኖዶች አሉት። አንድ የተወሰነ መስቀለኛ መንገድ መፈለግ ልክ እንደ ቀድሞው ዛፍ ሎግ (N) ያስከፍላል። ግን ይህን መስቀለኛ መንገድ አንዴ ካገኙ፣ ተተኪዎቻቸውን በማጣቀስ በ M ተተኪዎች ያገኛሉ። ይህ ፍለጋ M+log(N) ብቻ ያስከፍላል በቀድሞው ዛፍ ላይ ከኤን ኦፕሬሽኖች ጋር ሲነፃፀር ክዋኔዎች. ከዚህም በላይ ሙሉውን ዛፍ ማንበብ አይጠበቅብዎትም (M+log(N) nodes ብቻ) ይህ ማለት የዲስክ አጠቃቀምን ይቀንሳል ማለት ነው። M ትንሽ ከሆነ (ለምሳሌ 200 ረድፎች) እና N ትልቅ ከሆነ (1 ረድፎች) ትልቅ ልዩነት ይኖራል።

ግን እዚህ አዲስ ችግሮች አሉ (እንደገና!). በዳታቤዝ ውስጥ አንድ ረድፍ ካከሉ ወይም ከሰረዙ (እና ስለዚህ በተዛመደ B+Tree ኢንዴክስ)፡-

• በ B+Tree ውስጥ ባሉት አንጓዎች መካከል ሥርዓትን መጠበቅ አለቦት፣ ያለበለዚያ ባልተደረደረ ዛፍ ውስጥ ያሉትን አንጓዎች ማግኘት አይችሉም።
• በ B+Tree ውስጥ አነስተኛውን የደረጃዎች ብዛት መያዝ አለቦት፣ ይህ ካልሆነ ግን የ O(ሎግ(N)) የጊዜ ውስብስብነት O(N) ይሆናል።

በሌላ አነጋገር, B+Tree እራሱን ማዘዝ እና ሚዛናዊ መሆን አለበት. እንደ እድል ሆኖ, ይህ በስማርት ሰርዝ እና ኦፕሬሽኖች አስገባ ይቻላል. ነገር ግን ይህ በዋጋ ይመጣል፡ በ B+ ዛፍ ዋጋ O(ሎግ(N)) ውስጥ ማስገባት እና መሰረዝ። ለዚህም ነው አንዳንዶቻችሁ ያንን የሰማችሁት። በጣም ብዙ ኢንዴክሶችን መጠቀም ጥሩ ሀሳብ አይደለም. በእውነት፣ በሰንጠረዥ ውስጥ የረድፍ በፍጥነት ማስገባት/ማዘመን/መሰረዝ እያዘገምን ነው።ምክንያቱም ዳታቤዙ ለእያንዳንዱ ኢንዴክስ ውድ የሆነ ኦ(ሎግ(N)) አሠራር በመጠቀም የሠንጠረዡን ኢንዴክሶች ማዘመን ያስፈልገዋል። ከዚህም በላይ ኢንዴክሶችን መጨመር ለተጨማሪ የሥራ ጫና ማለት ነው የግብይት አስተዳዳሪ (በጽሁፉ መጨረሻ ላይ ይገለጻል).

ለበለጠ ዝርዝር የዊኪፔዲያ መጣጥፍ ማየት ትችላለህ B+ዛፍ. በመረጃ ቋት ውስጥ B+Treeን የመተግበር ምሳሌ ከፈለጉ ይመልከቱ ይህ ዓምድ и ይህ ዓምድ ከዋና MySQL ገንቢ. ሁለቱም ትኩረታቸው InnoDB (የ MySQL ሞተር) ኢንዴክሶችን እንዴት እንደሚይዝ ላይ ነው።

ማስታወሻ፡ አንድ አንባቢ በዝቅተኛ ደረጃ ማመቻቸት ምክንያት የ B+ ዛፉ ሙሉ በሙሉ ሚዛናዊ መሆን እንዳለበት ነግሮኛል።

Hashtable

የእኛ የመጨረሻው አስፈላጊ የውሂብ መዋቅር የሃሽ ሰንጠረዥ ነው. እሴቶችን በፍጥነት መፈለግ ሲፈልጉ ይህ በጣም ጠቃሚ ነው። በተጨማሪም፣ የሃሽ ሠንጠረዥን መረዳታችን ሀሽ መቀላቀል (ሀሽ መቀላቀል) የሚባል የጋራ ዳታቤዝ መቀላቀል ስራን በኋላ እንድንረዳ ይረዳናል። hash መቀላቀል). ይህ የውሂብ መዋቅር አንዳንድ ውስጣዊ ነገሮችን ለማከማቸት በመረጃ ቋቱ ጥቅም ላይ ይውላል (ለምሳሌ፦ የመቆለፊያ ጠረጴዛ ወይም ቋት ገንዳ, ሁለቱንም እነዚህን ጽንሰ-ሐሳቦች በኋላ ላይ እንመለከታለን).

ሃሽ ሠንጠረዥ አንድን ንጥረ ነገር በቁልፍ በፍጥነት የሚያገኝ የውሂብ መዋቅር ነው። የሃሽ ጠረጴዛን ለመገንባት የሚከተሉትን መግለፅ ያስፈልግዎታል

• ፍንጭ ለእርስዎ ንጥረ ነገሮች
• የሃሽ ተግባር ለቁልፍ. የተሰላው ቁልፍ hashes የንጥረ ነገሮች መገኛ ቦታ ይሰጣሉ (ይባላሉ ክፍሎች ).
• ቁልፎችን ለማነፃፀር ተግባር. ትክክለኛውን ክፍል ካገኙ በኋላ, ይህንን ንፅፅር በመጠቀም የሚፈልጉትን አካል በክፍል ውስጥ ማግኘት አለብዎት.

ቀላል ምሳሌ

አንድ ግልጽ ምሳሌ እንውሰድ፡-

ይህ የሃሽ ጠረጴዛ 10 ክፍሎች አሉት። ሰነፍ ስለሆንኩ 5 ክፍሎችን ብቻ ነው የሳልኩት ነገርግን ብልህ መሆንህን ስለማውቅ ሌላውን 5 በራስህ እንድትሳል እፈቅዳለሁ። እኔ አንድ hash ተግባር modulo ተጠቀምሁ 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 መስመር እና ቀን (ለምሳሌ - የአያት ስም, የመጀመሪያ ስም እና የትውልድ ቀን)
• ...

በጥሩ የሃሽ ተግባር፣ የሃሽ ሠንጠረዥ ፍለጋ ዋጋ ኦ(1).

ድርድር vs ሃሽ ጠረጴዛ

ለምን ድርድር አትጠቀምም?

ሆ ጥሩ ጥያቄ።

• የሃሽ ጠረጴዛው ሊሆን ይችላል በከፊል ወደ ማህደረ ትውስታ ተጭኗል, እና የተቀሩት ክፍሎች በዲስክ ላይ ሊቆዩ ይችላሉ.
• ከድርድር ጋር በማህደረ ትውስታ ውስጥ ተላላፊ ቦታን መጠቀም አለብዎት። ትልቅ ጠረጴዛ እየጫኑ ከሆነ በቂ ቀጣይነት ያለው ቦታ ማግኘት በጣም አስቸጋሪ ነው.
• ለሃሽ ሠንጠረዥ፣ የሚፈልጉትን ቁልፍ (ለምሳሌ የሀገር እና የሰው ስም) መምረጥ ይችላሉ።

ለበለጠ መረጃ ስለ ጽሑፉ ማንበብ ይችላሉ። ጃቫሃሽ ማፕየሃሽ ሠንጠረዥ ቀልጣፋ አተገባበር; በዚህ ጽሑፍ ውስጥ የተካተቱትን ጽንሰ-ሐሳቦች ለመረዳት ጃቫን መረዳት አያስፈልግዎትም.

ምንጭ: hab.com