اې حبره! زه ستاسو پام ته د مقالې ژباړه وړاندې کوم
"د اړیکو ډیټابیس څنګه کار کوي".

کله چې د اړونده ډیټابیسونو خبره راځي زه نشم کولی مرسته وکړم مګر فکر کوم چې یو څه ورک دی. دوی هرچیرې کارول کیږي. دلته ډیری مختلف ډیټابیسونه شتون لري، د کوچني او ګټور SQLite څخه پیاوړي Teradata ته. مګر یوازې یو څو مقالې شتون لري چې تشریح کوي چې ډیټابیس څنګه کار کوي. تاسو کولی شئ د "howdoesarelationaldatabasework" په کارولو سره خپل ځان وپلټئ ترڅو وګورئ چې څومره لږې پایلې شتون لري. سربیره پردې، دا مقالې لنډې دي. که تاسو د وروستي Buzzy ټیکنالوژیو په لټه کې یاست (BigData، NoSQL یا JavaScript)، تاسو به ډیر ژور مقالې ومومئ چې تشریح کوي چې دوی څنګه کار کوي.

ایا اړونده ډیټابیسونه ډیر زاړه او ډیر ستړي دي چې د پوهنتون کورسونو، څیړنیزو مقالو او کتابونو څخه بهر تشریح شي؟

د یو پراختیا کونکي په توګه، زه د هغه څه کارولو څخه نفرت کوم چې زه یې نه پوهیږم. او که ډیټابیسونه د 40 کلونو څخه ډیر وخت لپاره کارول شوي وي، باید یو دلیل وي. د کلونو په اوږدو کې، ما د دې عجيب تور بکسونو په ریښتیا پوهیدو لپاره سلګونه ساعته تیر کړي چې زه هره ورځ کاروم. د اړیکو ډیټابیسونه ډیر په زړه پوری ځکه چې دوی د ګټورو او بیا کارولو وړ مفکورو پر بنسټ. که تاسو د ډیټابیس په پوهیدو کې لیوالتیا لرئ، مګر هیڅکله وخت یا لیوالتیا نه لرئ چې دې پراخې موضوع ته پام وکړئ، تاسو باید د دې مقالې څخه خوند واخلئ.

که څه هم د دې مقالې سرلیک څرګند دی، د دې مقالې موخه دا نه ده چې د ډیټابیس کارولو څرنګوالی پوه شي. له همدې امله، تاسو باید دمخه پوه شئ چې څنګه د ساده اړیکې غوښتنه او لومړني پوښتنې ولیکئ RAW; که نه نو تاسو ممکن پدې مقاله پوه نه شئ. دا یوازینی شی دی چې تاسو اړتیا لرئ پوه شئ، زه به پاتې نور تشریح کړم.

زه به د کمپیوټر ساینس ځینې اساساتو سره پیل وکړم ، لکه د الګوریتم وخت پیچلتیا (BigO). زه پوهیږم چې ستاسو څخه ځینې له دې مفکورې څخه نفرت کوي، مګر پرته له دې تاسو به د ډیټابیس دننه پیچلتیاو باندې پوه نشي. ځکه چې دا یوه لویه موضوع ده، زه به تمرکز وکړم هغه څه چې زه فکر کوم مهم دی: ډیټابیس څنګه پروسس کوي د ايس کيو ايل پوښتنه. زه به یوازې معرفي کړم د ډیټابیس بنسټیز مفهومنو د مقالې په پای کې تاسو د دې په اړه نظر لرئ چې د هود لاندې څه پیښیږي.

څرنګه چې دا یوه اوږده او تخنیکي مقاله ده چې ډیری الګوریتمونه او د ډیټا جوړښتونه پکې شامل دي، د دې له لارې لوستلو لپاره خپل وخت ونیسئ. د ځینو مفاهیمو پوهیدل ممکن ستونزمن وي؛ تاسو کولی شئ دوی پریږدئ او بیا هم عمومي نظر ترلاسه کړئ.

ستاسو په منځ کې د لا زیاتو پوهانو لپاره، دا مقاله په 3 برخو ویشل شوې ده:

د ټیټې کچې او لوړې کچې ډیټابیس اجزاوو عمومي کتنه
د پوښتنو د اصلاح کولو پروسې عمومي کتنه
د لیږد او بفر پول مدیریت عمومي کتنه

بیرته اساساتو ته

کلونه وړاندې (په یوه کهکشان کې، لیرې لرې ...)، پراختیا کونکي باید دقیقا د هغو عملیاتو شمیره معلومه کړي چې دوی یې کوډ کوي. دوی خپل الګوریتمونه او ډیټا جوړښتونه د زړه له لارې پوهیدل ځکه چې دوی نشي کولی د خپلو ورو کمپیوټرونو CPU او حافظې ضایع کړي.

پدې برخه کې، زه به تاسو ته د دې مفکورو څخه ځینې یادونه وکړم ځکه چې دوی د ډیټابیس د پوهیدو لپاره اړین دي. زه به مفهوم هم معرفي کړم د ډیټابیس شاخص.

O(1) vs O(n2)

نن ورځ، ډیری پراختیا کونکي د الګوریتم د وخت پیچلتیا پروا نه کوي ... او دوی سم دي!

مګر کله چې تاسو د ډیری ډیټا سره معامله کوئ (زه په زرګونو خبرې نه کوم) یا که تاسو په ملی ثانیو کې مبارزه کوئ ، نو د دې مفهوم پوهیدل خورا مهم کیږي. او لکه څنګه چې تاسو تصور کولی شئ، ډیټابیس باید د دواړو حالتونو سره معامله وکړي! زه به تاسو ته د اړتیا په پرتله ډیر وخت ونه لګوم ترڅو د هغې لنډیز ترلاسه کړم. دا به موږ سره د لګښت پر بنسټ د اصلاح کولو مفهوم په پوهیدو کې مرسته وکړي وروسته (لګښت پر بنسټ اصلاح کول).

مفهوم

د الګوریتم وخت پیچلتیا د دې لپاره کارول کیږي چې د ورکړل شوي ډیټا لپاره د الګوریتم اجرا کولو لپاره څومره وخت ونیسي. د دې پیچلتیا د تشریح کولو لپاره، موږ د لوی O ریاضیاتي یادښت څخه کار اخلو. دا نوټیشن د یو فنکشن سره کارول کیږي چې دا تشریح کوي چې یو الګوریتم د ورکړل شوي شمیرو لپاره څومره عملیاتو ته اړتیا لري.

د مثال په توګه، کله چې زه ووایم چې "دا الګوریتم پیچلتیا لري O(some_function())"، دا پدې مانا ده چې الګوریتم د ځینې_function(a_certain_amount_of_data) عملیاتو ته اړتیا لري ترڅو د یو ټاکلي مقدار ډیټا پروسس کړي.

نو دا د ډیټا مقدار ندی چې مهم دی **بل ډول ** د ډیټا حجم زیاتوالي سره د عملیاتو شمیر څنګه وده کوي. د وخت پیچلتیا د عملیاتو دقیق شمیر نه وړاندې کوي، مګر د اجرا کولو وخت اټکل کولو لپاره یوه ښه لار ده.

په دې ګراف کې تاسو کولی شئ د مختلف الګوریتم وخت پیچلتیاو لپاره د ان پټ ډیټا مقدار په پرتله د عملیاتو شمیر وګورئ. ما د دوی د ښودلو لپاره لوګاریتمیک پیمانه کارولې. په بل عبارت، د معلوماتو مقدار په چټکۍ سره له 1 څخه تر 1 ملیارد پورې لوړیږي. موږ لیدلی شو چې:

O(1) یا ثابت پیچلتیا ثابت پاتې کیږي (که نه نو دا به ثابت پیچلتیا ونه بلل شي).
O(log(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 له لاسه ورکړئ، یوازې د سترګو د پټولو لپاره وخت. په حقیقت کې، عصري پروسیسر کولی شي پروسس کړي په هره ثانیه کې سلګونه ملیونه عملیات. له همدې امله فعالیت او اصلاح کول په ډیری IT پروژو کې مسله نده.

لکه څنګه چې ما وویل، دا لاهم مهمه ده چې دا مفهوم پوه شي کله چې د ډیرو معلوماتو سره کار کوي. که دا ځل الګوریتم باید 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 ډیزاین ریښتیني تعریف نه دی ورکړی، یوازې یو نظر دی. تاسو کولی شئ دا مقاله ولولئ ويکيپېډيا د اصلي (asymptotic) تعریف لپاره.

ضم کړئ

تاسو څه کوئ کله چې تاسو د راټولولو ترتیب کولو ته اړتیا لرئ؟ څه؟ تاسو د 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) مرحلې شتون لري، ټول لګښت N * log(N) عملیات.

د ادغام ډول ګټې

ولې دا الګوریتم دومره پیاوړی دی؟

ځکه:

تاسو کولی شئ دا د حافظې فوټپرنټ کمولو لپاره بدل کړئ ترڅو تاسو نوي صفونه رامینځته نه کړئ مګر په مستقیم ډول د ان پټ سرې بدل کړئ.

یادونه: دې ډول الګوریتم ته ویل کیږي in-ځای (د اضافي حافظې پرته ترتیب کول).

تاسو کولی شئ دا په ورته وخت کې د ډیسک ځای او لږ مقدار حافظې کارولو لپاره بدل کړئ پرته لدې چې د پام وړ ډیسک I/O سر پورته کړي. نظر دا دی چې په حافظه کې یوازې هغه برخې بار کړئ چې اوس مهال پروسس کیږي. دا مهم دی کله چې تاسو اړتیا لرئ د څو ګیګابایټ میز ترتیب کړئ یوازې د 100 میګابایټ حافظې بفر سره.

یادونه: دې ډول الګوریتم ته ویل کیږي بهرنۍ ترتیب.

تاسو کولی شئ دا په ډیری پروسو / تارونو / سرورونو چلولو لپاره بدل کړئ.

د مثال په توګه، د توزیع شوي انضمام ترتیب یو له مهمو برخو څخه دی Hadoop (کوم چې په لویو معلوماتو کې جوړښت دی).

دا الګوریتم کولی شي مشر په سرو زرو بدل کړي (واقعی!).

دا ترتیبول الګوریتم په ډیری (که ټول نه) ډیټابیسونو کې کارول کیږي، مګر دا یوازینی ندی. که تاسو غواړئ نور پوه شئ، تاسو کولی شئ دا ولولئ څیړنیز کار، کوم چې د عام ډیټابیس ترتیب کولو الګوریتمونو ګټې او زیانونه بحث کوي.

صف، ونې او هش میز

اوس چې موږ د وخت پیچلتیا او ترتیب کولو نظر پوهیږو، زه باید تاسو ته د 3 ډیټا جوړښتونو په اړه ووایم. دا مهمه ده ځکه چې دوی د عصري ډیټابیس اساس دی. زه به مفهوم هم معرفي کړم د ډیټابیس شاخص.

صف

دوه اړخیزه لړۍ د ډیټا ترټولو ساده جوړښت دی. یو جدول د سرې په توګه فکر کیدی شي. د مثال په ډول:

دا دوه اړخیز سرې د قطارونو او کالمونو سره یو جدول دی:

هره کرښه د یو وجود استازیتوب کوي
کالم د ملکیتونو ذخیره کوي چې د وجود تشریح کوي.
هر کالم د یو ځانګړي ډول ډیټا ذخیره کوي (انټیجر، تار، نیټه ...).

دا د معلوماتو ذخیره کولو او لیدو لپاره مناسب دی ، په هرصورت ، کله چې تاسو اړتیا لرئ یو ځانګړي ارزښت ومومئ ، دا مناسب ندي.

د مثال په توګه، که تاسو غواړئ ټول هغه هلکان ومومئ چې په انګلستان کې کار کوي، تاسو اړتیا لرئ چې هر قطار وګورئ ترڅو معلومه کړئ چې آیا دا قطار په انګلستان پورې اړه لري. دا به تاسو د 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 کیڼ فرعي بڼ ته ګورم
۴۰= ۴۰، نوډ شتون لري. زه د نوډ دننه د قطار ID ترلاسه کوم (په عکس کې نه) او د ورکړل شوي قطار ID لپاره جدول کې ګورم.
د قطار ID پیژندل ما ته اجازه راکوي چې دقیقا پوه شم چې ډاټا په جدول کې چیرې ده، نو زه کولی شم سمدستي بیرته ترلاسه کړم.

په پاى کې، دواړه لټونونه به ما د ونې دننه د کچو شمېره مصرف کړي. که تاسو د ادغام ترتیب په اړه برخه په احتیاط سره ولولئ، نو تاسو باید وګورئ چې د log(N) کچه شتون لري. دا معلومه شوه، د لټون لګښت log(N)، بد نه دی!

راځم خپلې ستونزې ته

مګر دا خورا خلاص دی ، نو راځئ چې بیرته خپلې ستونزې ته راشو. د ساده عدد پر ځای، یو تار تصور کړئ چې په تیر جدول کې د یو چا هیواد استازیتوب کوي. راځئ چې ووایو تاسو یوه ونه لرئ چې د میز د "هیواد" ساحه (کالم 3) لري:

که تاسو غواړئ پوه شئ چې څوک په انګلستان کې کار کوي
تاسو ونې ته ګورئ ترڅو نوډ ترلاسه کړئ چې د لوی انګلستان استازیتوب کوي
د "UKnode" دننه تاسو به د انګلستان د کارګر ریکارډونو موقعیت ومومئ.

دا لټون به د N عملیاتو پرځای د log(N) عملیاتو لګښت وکړي که تاسو مستقیم صف وکاروئ. هغه څه چې تاسو یې وړاندې کړي وو د ډیټابیس شاخص.

تاسو کولی شئ د ساحو د هرې ډلې لپاره د شاخص ونې جوړ کړئ (سټرینګ ، شمیره ، 2 لینونه ، شمیره او تار ، نیټه ...) تر هغه چې تاسو د کیلي پرتله کولو لپاره فعالیت لرئ (د بیلګې په توګه د ساحې ګروپونه) نو تاسو کولی شئ تنظیم کړئ د کیلي په مینځ کې ترتیب (کوم چې په ډیټابیس کې د هر ډول لومړني ډولونو لپاره قضیه ده).

B+ TreeIndex

پداسې حال کې چې دا ونه د ځانګړي ارزښت ترلاسه کولو لپاره ښه کار کوي، کله چې تاسو اړتیا لرئ یوه لویه ستونزه شتون لري د دوه ارزښتونو تر مینځ ډیری عناصر ترلاسه کړئ. دا به د O (N) لګښت ولري ځکه چې تاسو باید په ونه کې هر نوډ وګورئ او وګورئ چې ایا دا د دې دوه ارزښتونو تر مینځ دی (د مثال په توګه د ونې د ترتیب شوي لیږد سره). سربیره پردې، دا عملیات د ډیسک I/O دوستانه ندي ځکه چې تاسو باید ټوله ونې ولولئ. موږ اړتیا لرو چې په اغیزمنه توګه د اجرا کولو لپاره لاره پیدا کړو د حد غوښتنه. د دې ستونزې د حل لپاره، عصري ډیټابیسونه د پخوانۍ ونې بدله شوې نسخه کاروي چې B+Tree نومیږي. د B+ ونې په ونې کې:

یوازې ټیټ نوډونه (پاڼې) معلومات ذخیره کول (په اړوند جدول کې د قطارونو موقعیت)
پاتې نوډونه دلته دي د تګ لپاره سم نوډ ته د لټون پر مهال.

لکه څنګه چې تاسو لیدلی شئ، دلته نور نوډونه شتون لري (دوه ځله). په حقیقت کې، تاسو اضافي نوډونه لرئ، "پریکړه نوډ"، دا به تاسو سره د سم نوډ په موندلو کې مرسته وکړي (کوم چې په اړونده جدول کې د قطارونو موقعیت ذخیره کوي). مګر د لټون پیچلتیا لاهم O(log(N)) ده (یوازې یوه بله کچه شتون لري). لوی توپیر دا دی په ټیټه کچه نوډونه د دوی د جانشین سره تړلي دي.

د دې B+ ونې سره، که تاسو د 40 او 100 ترمنځ ارزښتونو په لټه کې یاست:

تاسو اړتیا لرئ د 40 په لټه کې شئ (یا د 40 وروسته نږدې ارزښت که 40 شتون نلري) لکه څنګه چې تاسو د تیرې ونې سره کړی و.
بیا د مستقیم وارث لینکونو په کارولو سره 40 وارثان راټول کړئ تر هغه چې تاسو 100 ته ورسیږئ.

راځئ چې ووایو تاسو د M جانشینان ومومئ او ونه د N نوډونه لري. د ځانګړي نوډ موندل د پخوانۍ ونې په څیر د لاګ (N) لګښت کوي. مګر یوځل چې تاسو دا نوډ ترلاسه کړئ، تاسو به د M عملیاتو کې د دوی د جانشینانو حوالې سره د M جانشینان ترلاسه کړئ. دا لټون یوازې د M+log(N) لګښت لري عملیات په تیرو ونې کې د N عملیاتو په پرتله. سربیره پردې ، تاسو اړتیا نلرئ بشپړ ونې ولولئ (یوازې M + log (N) نوډونه) ، کوم چې د ډیسک کم کارول معنی لري. که M کوچنی وي (د مثال په توګه 200 قطارونه) او N لوی وي (1 قطارونه)، یو لوی توپیر به وي.

مګر دلته نوې ستونزې شتون لري (بیا!). که تاسو په ډیټابیس کې یو قطار اضافه یا حذف کړئ (او له همدې امله په اړوند B+ ونې شاخص کې):

تاسو باید د B+ ونې دننه د نوډونو تر مینځ نظم وساتئ، که نه نو تاسو به ونه توانیدئ چې په غیر ترتیب شوي ونې کې نوډونه ومومئ.
تاسو باید په B+ ونې کې د کچې لږترلږه ممکنه شمیره وساتئ، که نه نو د O(log(N)) وخت پیچلتیا O(N) کیږي.

په بل عبارت، B+ ونې باید پخپله ترتیب او متوازن وي. خوشبختانه ، دا د سمارټ حذف کولو او داخلولو عملیاتو سره امکان لري. مګر دا په لګښت راځي: د 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

د اړیکو ډیټابیس څنګه کار کوي (1 برخه)