اي حبر! مان توهان جي ڌيان ۾ مضمون جو ترجمو پيش ڪريان ٿو
"هڪ تعلقي ڊيٽابيس ڪيئن ڪم ڪندو آهي".

جڏهن اهو تعلق رکندڙ ڊيٽابيسس تي اچي ٿو ته آئون مدد نه ٿو ڪري سگهان پر سوچيو ته ڪجهه غائب آهي. اهي هر هنڌ استعمال ٿيندا آهن. هتي ڪيترائي مختلف ڊيٽابيس موجود آهن، ننڍي ۽ مفيد SQLite کان طاقتور Teradata تائين. پر هتي صرف چند آرٽيڪل آهن جيڪي وضاحت ڪن ٿا ته ڊيٽابيس ڪيئن ڪم ڪندو آهي. توھان ڳولي سگھوٿا "howdoesarelationaldatabasework" استعمال ڪندي ڏسڻ لاءِ ته ڪيترا نتيجا آھن. ان کان علاوه، اهي مضمون مختصر آهن. جيڪڏھن توھان ڳولي رھيا آھيو جديد Buzzy ٽيڪنالاجيون (BigData، NoSQL يا JavaScript)، توھان کي وڌيڪ تفصيلي مضمون ملندا جيڪي بيان ڪن ٿا ته اھي ڪيئن ڪم ڪن ٿيون.

ڇا لاڳاپا ڊيٽابيس تمام پراڻا ۽ تمام بورنگ آھن جيڪي يونيورسٽي ڪورسز، تحقيقي مقالا ۽ ڪتابن کان ٻاهر بيان ڪيا وڃن؟

هڪ ڊولپر جي طور تي، مون کي ڪجهه استعمال ڪرڻ کان نفرت آهي جيڪا مون کي سمجھ ۾ نه اچي. ۽ جيڪڏهن ڊيٽابيس 40 سالن کان وڌيڪ استعمال ڪيو ويو آهي، اتي هڪ سبب هجڻ گهرجي. ڪيترن سالن کان، مون انهن عجيب بليڪ باڪس کي سمجهڻ لاءِ سوين ڪلاڪ گذاريا آهن جيڪي آئون هر روز استعمال ڪريان ٿو. تعلقي ڊيٽابيس تمام دلچسپ ڇاڪاڻ ته اهي مفيد ۽ ٻيهر قابل استعمال تصورن جي بنياد تي. جيڪڏهن توهان هڪ ڊيٽابيس کي سمجهڻ ۾ دلچسپي رکو ٿا، پر توهان وٽ هن وسيع موضوع تي ڌيان ڏيڻ جو وقت يا مائل نه آهي، توهان کي هن مضمون مان لطف اندوز ٿيڻ گهرجي.

جيتوڻيڪ هن مضمون جو عنوان واضح آهي، هن آرٽيڪل جو مقصد اهو سمجهڻ نه آهي ته ڊيٽابيس کي ڪيئن استعمال ڪجي. ان ڪري، توهان کي اڳ ۾ ئي ڄاڻڻ گهرجي ته هڪ سادي ڪنيڪشن جي درخواست ۽ بنيادي سوالن کي ڪيئن لکجي ٻڌ؛ ٻي صورت ۾ توهان هن مضمون کي سمجهي نه سگهندا. اهو صرف توهان کي ڄاڻڻ جي ضرورت آهي، باقي مان وضاحت ڪندس.

آئون ڪمپيوٽر سائنس جي ڪجهه بنيادي ڳالهين سان شروع ڪندس، جهڙوڪ وقت جي پيچيدگي جي الگورتھم (BigO). مون کي خبر آهي ته توهان مان ڪجهه هن تصور کان نفرت ڪندا آهن، پر ان جي بغير توهان ڊيٽابيس جي اندر جي پيچيدگين کي سمجهي نه سگهندا. ڇاڪاڻ ته هي هڪ وڏو موضوع آهي، مان ڌيان ڏيندس جيڪو مان سمجهان ٿو اهو اهم آهي: ڪيئن ڊيٽابيس پروسيس وارو SQL ايس پڇا ڳاڇا. مان صرف تعارف ڪندس بنيادي ڊيٽابيس تصوراتانهي ڪري ته مضمون جي آخر ۾ توهان کي هڪ خيال آهي ته هود هيٺ ڇا ٿي رهيو آهي.

جيئن ته هي هڪ ڊگهو ۽ ٽيڪنيڪل آرٽيڪل آهي جنهن ۾ ڪيترائي الگورتھم ۽ ڊيٽا جي جوڙجڪ شامل آهن، ان جي ذريعي پڙهڻ لاء پنهنجو وقت وٺو. ڪجھ تصورن کي سمجھڻ ڏکيو ٿي سگھي ٿو. توھان انھن کي ڇڏي سگھو ٿا ۽ اڃا تائين عام خيال حاصل ڪري سگھو ٿا.

توهان جي وچ ۾ وڌيڪ ڄاڻ رکندڙ لاء، هي مضمون 3 حصن ۾ ورهايل آهي:

گھٽ-سطح ۽ اعلي-سطح ڊيٽابيس حصن جو جائزو
سوال جي اصلاح جي عمل جو جائزو
ٽرانزيڪشن ۽ بفر پول مينيجمينٽ جو جائزو

بنيادي ڳالهين ڏانهن واپس

سال اڳ (هڪ ڪهڪشان ۾ پري، پري...)، ڊولپرز کي اهو ڄاڻڻو پوندو هو ته انهن آپريشنن جو تعداد انهن کي ڪوڊ ڪري رهيا هئا. اھي پنھنجي الگورتھم ۽ ڊيٽا جي جوڙجڪ کي دل سان ڄاڻندا ھئا ڇو ته اھي پنھنجي سست ڪمپيوٽرن جي سي پي يو ۽ ياداشت کي ضايع ڪرڻ جي متحمل نه ٿي سگھيا.

هن حصي ۾، مان توهان کي انهن مان ڪجهه تصورن جي ياد ڏياريندس جيئن اهي ڊيٽابيس کي سمجهڻ لاء ضروري آهن. مان به تصور متعارف ڪرايو ڊيٽابيس انڊيڪس.

O(1) بمقابلہ 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 عناصر کي پروسيس ڪرڻ جي ضرورت آھي.

اي (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 عناصر کي پروسيس ڪرڻو پوندو (جيڪو ڊيٽابيس لاءِ ايترو گهڻو ناهي):

اي (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: هي اڃا به بدتر آهي! هڪ الگورٿم جنهن کي اسين هن مضمون جي وچ ۾ ڏسندا هي پيچيدگي آهي (۽ اهو اصل ۾ ڪيترن ئي ڊيٽابيس ۾ استعمال ٿيندو آهي).
فڪري ن: توهان ڪڏهن به حاصل نه ڪندا توهان جا نتيجا جيتوڻيڪ ڊيٽا جي هڪ ننڍڙي مقدار سان.
nn: جيڪڏهن توهان هن پيچيدگي کي منهن ڏيو ٿا، توهان کي پنهنجي پاڻ کان پڇڻ گهرجي ته ڇا اهو واقعي توهان جي سرگرمي جو ميدان آهي ...

نوٽ: مون توهان کي وڏي O عهدي جي اصل تعريف نه ڏني، صرف هڪ خيال. توهان هن مضمون تي پڙهي سگهو ٿا وڪيپيڊيا حقيقي (asymptotic) تعريف لاءِ.

ملائي ترتيب

توهان ڇا ڪندا آهيو جڏهن توهان کي مجموعو ترتيب ڏيڻ جي ضرورت آهي؟ ڇا؟ توهان سڏين ٿا ترتيب () فنڪشن... ٺيڪ، سٺو جواب... پر هڪ ڊيٽابيس لاءِ، توهان کي اهو سمجهڻ گهرجي ته هي ترتيب () فنڪشن ڪيئن ڪم ڪري ٿو.

اتي ڪيترائي سٺا ترتيب ڏيڻ وارا الگورتھم آھن، تنھنڪري مان سڀ کان اھم تي ڌيان ڏيندس: ضم ڪرڻ جو قسم. توھان سمجھي نه سگھندا آھيو ڇو ڊيٽا کي ترتيب ڏيڻ ھاڻي ڪارائتو آھي، پر توھان کي سوال جي اصلاح واري حصي کان پوءِ ڪرڻ گھرجي. ان کان علاوه، ضم ڪرڻ جي ترتيب کي سمجهڻ بعد ۾ اسان کي عام ڊيٽابيس جوائن آپريشن کي سمجهڻ ۾ مدد ملندي ملن شامل ٿيو (ملڪي اتحاد).

ملائڻ

ڪيترن ئي ڪارآمد الورورٿمز وانگر، ضم ڪرڻ جو دارومدار هڪ چال تي آهي: 2 ترتيب ڏنل صفن کي N/2 جي N-عنصر سان ترتيب ڏنل صف ۾ گڏ ڪرڻ صرف N آپريشنن جي قيمت آهي. هن آپريشن کي ملائي سڏيو ويندو آهي.

اچو ته ڏسو ته ان جو مطلب ڇا آهي هڪ سادي مثال سان:

هي انگ اکر ڏيکاري ٿو ته حتمي ترتيب ڏنل 8-عنصر صف کي تعمير ڪرڻ لاء، توهان کي صرف 2 4-عنصر صفن تي هڪ ڀيرو ٻيهر ڪرڻ جي ضرورت آهي. ڇاڪاڻ ته ٻئي 4-عنصر صفون اڳ ۾ ئي ترتيب ڏنل آهن:

1) توهان ٻنهي موجوده عناصر کي ٻن صفن ۾ موازنہ ڪريو (شروعات ۾ موجوده = پهريون)
2) پوءِ ان کي 8 عنصرن جي صف ۾ رکڻ لاءِ سڀ کان ننڍو کڻي
3) ۽ صف ۾ ايندڙ عنصر ڏانهن وڃو جتي توهان ننڍڙو عنصر ورتو
۽ 1,2,3 کي ورجايو جيستائين توهان هڪ صف جي آخري عنصر تائين پهچي وڃو.
ان کان پوء توهان ٻين سرن جي باقي عناصر کي 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 مرحلن ۾ يونٽي صفن ۾ ورهايو ويو آهي. قدمن جو رسمي نمبر log(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 ڊيٽا جي جوڙجڪ بابت ٻڌائڻ گهرجي. هي اهم آهي ڇاڪاڻ ته اهي جديد ڊيٽابيس جو بنياد آهن. مان به تصور متعارف ڪرايو ڊيٽابيس انڊيڪس.

قطار

هڪ ٻه-dimensional صف آسان ڊيٽا جي جوڙجڪ آهي. هڪ ٽيبل کي هڪ صف طور سمجهي سگهجي ٿو. مثال طور:

هي 2-dimensional صف قطار ۽ ڪالمن سان گڏ ٽيبل آهي:

هر لڪير هڪ وجود جي نمائندگي ڪري ٿو
ڪالمن جا خاصيتون ذخيرو ڪن ٿيون جيڪي بيان ڪن ٿيون.
هر ڪالم هڪ مخصوص قسم جي ڊيٽا کي ذخيرو ڪري ٿو (انٽيجر، اسٽرنگ، تاريخ ...).

اهو ڊيٽا کي محفوظ ڪرڻ ۽ ڏسڻ لاءِ آسان آهي، جڏهن ته، جڏهن توهان کي هڪ خاص قدر ڳولڻ جي ضرورت آهي، اهو مناسب ناهي.

مثال طور، جيڪڏهن توهان چاهيو ٿا ته اهي سڀئي ماڻهو جيڪي برطانيه ۾ ڪم ڪن ٿا، توهان کي هر قطار کي ڏسڻ جي ضرورت پوندي اهو طئي ڪرڻ لاءِ ته ڇا اها قطار برطانيه سان تعلق رکي ٿي. اهو توهان کي N ٽرانزيڪشن جي قيمت ڏيندوڪٿي N - لائينن جو تعداد، جيڪو خراب نه آھي، پر ھڪڙو تيز رستو ٿي سگھي ٿو؟ هاڻي وقت اچي ويو آهي ته اسان وڻن سان واقف ٿي وڃون.

نوٽ: گھڻا جديد ڊيٽابيس مهيا ڪن ٿا وڌايل صفن کي محفوظ ڪرڻ لاءِ جدولن کي موثر طريقي سان: heap-organized tables and index-organized tables. پر هي ڪالمن جي گروپ ۾ هڪ خاص حالت کي جلدي ڳولڻ جي مسئلي کي تبديل نٿو ڪري.

ڊيٽابيس وڻ ۽ انڊيڪس

هڪ بائنري ڳولا وڻ هڪ بائنري وڻ آهي هڪ خاص ملڪيت سان، هر نوڊ تي ڪنجي هجڻ گهرجي:

کاٻي ذيلي تري ۾ محفوظ ڪيل سڀني ڪنجين کان وڌيڪ
ساڄي ذيلي وڻ ۾ محفوظ ڪيل سڀني ڪنجين کان گھٽ

اچو ته ڏسو ته ان جو مطلب ڇا آهي بصري

نظريه

ھن وڻ ۾ 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 لاءِ ٽيبل ۾ ڏسو.
قطار جي سڃاڻپ کي ڄاڻڻ جي اجازت ڏئي ٿي ته مون کي اهو معلوم ٿئي ٿو ته ڊيٽا ڪٿي آهي جدول ۾، تنهنڪري مان ان کي فوري طور تي حاصل ڪري سگهان ٿو.

آخر ۾، ٻنهي ڳولها مون کي وڻ جي اندر جي سطحن جو تعداد خرچ ڪندو. جيڪڏهن توهان ضم جي ترتيب بابت حصو احتياط سان پڙهو ٿا، توهان کي ڏسڻ گهرجي ته اتي لاگ (N) سطحون آهن. معلوم ٿئي ٿو، ڳولا جي قيمت لاگ (N)، برو ناهي!

اچو ته اسان جي مسئلي ڏانهن واپس وڃو

پر اهو تمام خلاصو آهي، تنهنڪري اچو ته اسان جي مسئلي ڏانهن واپس وڃو. هڪ سادي عدد جي بدران، هڪ اسٽرنگ جو تصور ڪريو جيڪو اڳوڻي جدول ۾ ڪنهن جي ملڪ جي نمائندگي ڪري ٿو. اچو ته چئو ته توهان وٽ هڪ وڻ آهي جنهن ۾ ٽيبل جي "ملڪ" فيلڊ (ڪالمن 3) شامل آهي:

جيڪڏھن توھان ڄاڻڻ چاھيو ٿا جيڪو برطانيه ۾ ڪم ڪري ٿو
توھان وڻ کي ڏسو نوڊ حاصل ڪرڻ لاءِ جيڪو برطانيه جي نمائندگي ڪري ٿو
"UKnode" جي اندر توهان برطانيه جي ڪارڪنن جي رڪارڊ جو مقام ڳوليندا.

هي ڳولا خرچ ڪندو لاگ(N) آپريشنن بدران N آپريشنز جي جيڪڏھن توھان سڌو سنئون استعمال ڪريو ٿا. جيڪو توهان صرف پيش ڪيو هو ڊيٽابيس انڊيڪس.

توهان فيلڊ جي ڪنهن به گروهه لاءِ هڪ انڊيڪس ٽري ٺاهي سگهو ٿا (اسٽرنگ، نمبر، 2 لائينون، نمبر ۽ اسٽرنگ، تاريخ...) جيستائين توهان وٽ ڪيز (يعني فيلڊ گروپس) جي مقابلي لاءِ فنڪشن آهي، تنهنڪري توهان سيٽ ڪري سگهو ٿا. ڪنجين جي وچ ۾ ترتيب ڏيو (جيڪو ڊيٽابيس ۾ ڪنهن به بنيادي قسم جي صورت ۾ آهي).

B+TreeIndex

جڏهن ته هي وڻ هڪ خاص قيمت حاصل ڪرڻ لاء سٺو ڪم ڪري ٿو، اتي هڪ وڏو مسئلو آهي جڏهن توهان کي ضرورت آهي ٻن قدرن جي وچ ۾ ڪيترائي عنصر حاصل ڪريو. اهو خرچ ٿيندو O (N) ڇو ته توهان کي وڻ ۾ هر نوڊ کي ڏسڻو پوندو ۽ چيڪ ڪرڻو پوندو ته ڇا اهو انهن ٻن قدرن جي وچ ۾ آهي (مثال طور وڻ جي آرڊر ٿيل ٽرورسل سان). ان کان علاوه، هي آپريشن ڊسڪ I/O دوستانه نه آهي ڇو ته توهان کي سڄو وڻ پڙهڻو پوندو. اسان کي موثر طريقي سان عمل ڪرڻ جو طريقو ڳولڻ جي ضرورت آهي حد جي درخواست. ھن مسئلي کي حل ڪرڻ لاءِ، جديد ڊيٽابيس استعمال ڪن ٿا اڳئين وڻ جو تبديل ٿيل ورجن B+Tree. بي + وڻ جي وڻ ۾:

صرف هيٺيون نوڊس (پتي) ذخيرو جي معلومات (لاڳاپيل جدول ۾ قطارن جي جڳھ)
باقي نوڊس هتي آهن رستي لاءِ صحيح نوڊ ڏانهن ڳولا دوران.

جئين توهان ڏسي سگهو ٿا، هتي وڌيڪ نوڊس آهن (ٻه ڀيرا). درحقيقت، توهان وٽ اضافي نوڊس آهن، "فيصلو نوڊس"، جيڪو توهان کي درست نوڊ ڳولڻ ۾ مدد ڪندو (جيڪو لاڳاپيل جدول ۾ قطار جي جڳهه کي محفوظ ڪري ٿو). پر ڳولا جي پيچيدگي اڃا تائين 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+Tree انڊيڪس ۾):

توهان کي بي + وڻ جي اندر نوڊس جي وچ ۾ ترتيب برقرار رکڻ گهرجي، ٻي صورت ۾ توهان اڻ ترتيب ڏنل وڻ جي اندر نوڊس کي ڳولي نه سگهندا.
توھان کي لازمي طور تي گھٽ ۾ گھٽ ممڪن سطحن جو تعداد B+ Tree ۾ رکڻ گھرجي، ٻي صورت ۾ O(log(N)) وقت جي پيچيدگي O(N) ٿي ويندي.

ٻين لفظن ۾، B+ وڻ پاڻ کي ترتيب ڏيڻ ۽ متوازن هجڻ گهرجي. خوش قسمت، اهو سمارٽ حذف ڪرڻ ۽ داخل ڪرڻ جي عملن سان ممڪن آهي. پر اهو هڪ قيمت تي اچي ٿو: B+ وڻ جي قيمت O(log(N)) ۾ داخل ۽ حذف. ان ڪري اوهان مان ڪجهه ٻڌو آهي تمام گھڻا انڊيڪس استعمال ڪرڻ سٺو خيال نه آھي. واقعي، توھان سست ڪري رھيا آھيو تيز رفتار داخل ڪريو / تازه ڪاري / ھڪڙي قطار کي ختم ڪريو ھڪڙي ٽيبل ۾ڇاڪاڻ ته ڊيٽابيس کي هر انڊيڪس لاءِ قيمتي O(log(N)) آپريشن استعمال ڪندي ٽيبل جي انڊيڪس کي اپڊيٽ ڪرڻ جي ضرورت آهي. ان کان علاوه، انڊيڪس شامل ڪرڻ جو مطلب آهي وڌيڪ ڪم لوڊ لاء ٽرانزيڪشن مينيجر (مضمون جي آخر ۾ بيان ڪيو ويندو).

وڌيڪ تفصيل لاءِ، توھان ڏسي سگھو ٿا وڪيپيڊيا تي مضمون B+وڻن. جيڪڏھن توھان چاھيو ٿا ھڪڙو مثال لاڳو ڪرڻ جو ھڪڙو ڊيٽابيس ۾ B + Tree، ھڪڙو نظر وٺو اهو مضمون и اهو مضمون هڪ معروف MySQL ڊولپر کان. اهي ٻئي ڌيان ڏين ٿا ته ڪيئن InnoDB (The MySQL انجڻ) انڊيڪسس کي سنڀاليندو آهي.

نوٽ: هڪ پڙهندڙ مون کي ٻڌايو ته، گهٽ سطح جي اصلاحن جي ڪري، B+ وڻ مڪمل طور تي متوازن هجڻ گهرجي.

هيش ٽيبل

اسان جي آخري اهم ڊيٽا ڍانچي آهي hash ٽيبل. اهو تمام ڪارائتو آهي جڏهن توهان جلدي قدر ڳولڻ چاهيو ٿا. ان کان علاوه، هيش ٽيبل کي سمجهڻ اسان کي بعد ۾ هڪ عام ڊيٽابيس جوائن آپريشن کي سمجهڻ ۾ مدد ڏيندو جنهن کي هيش جوائن (Hash join) چيو ويندو آهي. hash شامل ٿيڻ). هي ڊيٽا ڍانچي پڻ استعمال ڪيو ويندو آهي ڊيٽابيس طرفان ڪجهه اندروني شين کي ذخيرو ڪرڻ لاء (مثال طور. تالا ٽيبل يا بفر پول، اسان انهن ٻنهي تصورن کي بعد ۾ ڏسنداسين).

هيش ٽيبل هڪ ڊيٽا ڍانچي آهي جيڪو جلدي هڪ عنصر ڳولي ٿو ان جي ڪنجي ذريعي. هيش ٽيبل ٺاهڻ لاء توهان کي وضاحت ڪرڻ جي ضرورت آهي:

چاٻي توهان جي عناصر لاء
hash فنڪشن چاٻين لاءِ. ڪمپيوٽنگ ڪيل ڪي هيش عناصر جي جڳھ کي ڏيو (سڏيو ويو حصا ).
ڪنجي جي مقابلي لاءِ فنڪشن. هڪ دفعو توهان کي صحيح ڀاڱو مليو آهي، توهان کي اهو عنصر ڳولڻ گهرجي جيڪو توهان هن مقابلي کي استعمال ڪندي حصي ۾ ڳولي رهيا آهيو.

سادو مثال

اچو ته هڪ واضح مثال وٺون:

ھن ھيش ٽيبل ۾ 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).

ايري بمقابله هيش ٽيبل

ڇو نه هڪ صف استعمال ڪريو؟

ها، سٺو سوال.

هيش ٽيبل ٿي سگهي ٿو جزوي طور تي ياداشت ۾ لوڊ، ۽ باقي حصا ڊسڪ تي رهي سگهن ٿا.
هڪ صف سان توهان کي يادگيري ۾ متضاد جڳهه استعمال ڪرڻ گهرجي. جيڪڏهن توهان هڪ وڏي ٽيبل لوڊ ڪري رهيا آهيو ڪافي مسلسل خلا ڳولڻ تمام ڏکيو آهي.
هيش ٽيبل لاءِ، توھان چونڊي سگھوٿا چاٻي جيڪا توھان چاھيو (مثال طور، ملڪ ۽ شخص جو آخري نالو).

وڌيڪ معلومات لاء، توهان پڙهي سگهو ٿا مضمون بابت جاواهش ميپ, جيڪو هڪ hash ٽيبل جي هڪ موثر عملدرآمد آهي. توھان کي ھن مضمون ۾ ڏنل تصورن کي سمجھڻ لاءِ جاوا کي سمجھڻ جي ضرورت ناھي.

جو ذريعو: www.habr.com

ڪيئن لاڳاپو ڊيٽابيس ڪم (حصو 1)