ဟေး ဟာဘ! ဆောင်းပါးရဲ့ ဘာသာပြန်ချက်ကို မင်းရဲ့အာရုံကို ငါတင်ပြတယ်။
"ဆက်စပ်ဒေတာဘေ့စ်ဘယ်လိုအလုပ်လုပ်သလဲ".

ဆက်စပ်ဒေတာဘေ့စ်များနှင့် ပတ်သက်လာလျှင် တစ်စုံတစ်ခု လွဲမှားနေပြီဟု တွေး၍မရပါ။ နေရာတိုင်းတွင် အသုံးပြုကြသည်။ သေးငယ်ပြီး အသုံးဝင်သော SQLite မှ အစွမ်းထက် Teradata အထိ မတူညီသောဒေတာဘေ့စ်များစွာရှိပါသည်။ ဒါပေမယ့် ဒေတာဘေ့စ် ဘယ်လိုအလုပ်လုပ်တယ်ဆိုတာကို ရှင်းပြတဲ့ ဆောင်းပါးအနည်းငယ်ပဲရှိပါတယ်။ ရလဒ်မည်မျှရှိသည်ကိုကြည့်ရှုရန် "howdoesarelationaldatabasework" ကိုအသုံးပြု၍ သင်ကိုယ်တိုင်ရှာဖွေနိုင်ပါသည်။ ထို့အပြင် ဤဆောင်းပါးများသည် တိုတောင်းပါသည်။ အကယ်၍ သင်သည် နောက်ဆုံးပေါ် အမိုက်စား နည်းပညာများ (BigData၊ NoSQL သို့မဟုတ် JavaScript) ကို ရှာဖွေနေပါက ၎င်းတို့ အလုပ်လုပ်ပုံကို ရှင်းပြသည့် ပိုမိုနက်ရှိုင်းသော ဆောင်းပါးများကို သင်တွေ့လိမ့်မည်။

ဆက်စပ်ဒေတာဘေ့စ်များသည် တက္ကသိုလ်သင်တန်းများ၊ သုတေသနစာတမ်းများနှင့် စာအုပ်များအပြင်တွင် ရှင်းပြရန် အလွန်ဟောင်းနွမ်းပြီး ပျင်းစရာကောင်းနေပါသလား။

ဆော့ဖ်ဝဲရေးသားသူအနေဖြင့် ကျွန်ုပ်နားမလည်သောအရာကို အသုံးပြုခြင်းကို မုန်းတီးပါသည်။ ဒေတာဘေ့စ်များကို အနှစ် ၄၀ ကျော် အသုံးပြုခဲ့မည်ဆိုပါက အကြောင်းပြချက်ရှိရပါမည်။ နှစ်တွေကြာလာတာနဲ့အမျှ၊ ကျွန်တော်နေ့စဥ်သုံးနေတဲ့ ဒီထူးဆန်းတဲ့သေတ္တာနက်တွေကို အမှန်တကယ်နားလည်ဖို့ နာရီရာနဲ့ချီပြီး အချိန်ကုန်ခဲ့တယ်။ ဆက်စပ်ဒေတာဘေ့စ်များ သူတို့ကြောင့် အရမ်းစိတ်ဝင်စားတယ်။ အသုံးဝင်ပြီး ပြန်သုံးနိုင်သော သဘောတရားများကို အခြေခံထားသည်။. အကယ်၍ သင်သည် ဒေတာဘေ့စ်တစ်ခုကို နားလည်ရန် စိတ်ပါဝင်စားသော်လည်း ဤကျယ်ပြန့်သောအကြောင်းအရာကို စေ့စေ့စပ်စပ်လေ့လာရန် အချိန် သို့မဟုတ် စိတ်ဆန္ဒမရှိပါက ဤဆောင်းပါးကို သင်နှစ်သက်သင့်သည်။

ဤဆောင်းပါး၏ ခေါင်းစဉ်သည် ရှင်းလင်းပြတ်သားသော်လည်း၊ ဤဆောင်းပါး၏ ရည်ရွယ်ချက်မှာ ဒေတာဘေ့စ်ကို မည်သို့အသုံးပြုရမည်ကို နားလည်ရန်မဟုတ်ပါ။. ထို့ကြောင့်၊ ရိုးရှင်းသောချိတ်ဆက်မှုတောင်းဆိုမှုနှင့် အခြေခံမေးမြန်းချက်များကို သင်မည်သို့ရေးသားရမည်ကို သင်သိသင့်သည်။ ရေနံချောင်း; မဟုတ်ရင် ဒီဆောင်းပါးကို နားမလည်နိုင်ပါ။ အဲဒါ မင်းသိဖို့ တစ်ခုတည်းပဲ ကျန်တာ ငါရှင်းပြမယ်။

အချိန်ရှုပ်ထွေးမှု algorithms (BigO) ကဲ့သို့သော ကွန်ပျူတာသိပ္ပံအခြေခံများနှင့် စတင်ပါမည်။ တစ်ချို့က ဒီသဘောတရားကို မုန်းတီးတာ သိပါတယ်၊ ဒါပေမယ့် အဲဒါမပါဘဲ ဒေတာဘေ့စ်အတွင်းက ရှုပ်ထွေးမှုတွေကို နားလည်နိုင်မှာ မဟုတ်ပါဘူး။ ဒီအကြောင်းအရာက ကြီးမားတဲ့အကြောင်းအရာမို့ အာရုံစိုက်ပါ့မယ် ဘာအရေးကြီးတယ်ထင်လဲ။: ဒေတာဘေ့စ်ဘယ်လိုလုပ်ဆောင်တယ်။ SQL စုံစမ်းရေး. ခုပဲ မိတ်ဆက်ပေးမယ်။ အခြေခံဒေတာဘေ့စ်သဘောတရားများဒါမှ ဆောင်းပါးရဲ့ အဆုံးမှာ မင်းခေါင်းအုံးအောက်မှာ ဘာတွေဖြစ်နေလဲ ဆိုတာကို မင်း အကြံဥာဏ်တစ်ခု ရသွားလိမ့်မယ်။

ဤသည်မှာ ရှည်လျားပြီး နည်းပညာဆိုင်ရာ ဆောင်းပါးတစ်ပုဒ်ဖြစ်ပြီး အယ်လဂိုရီသမ်များနှင့် ဒေတာဖွဲ့စည်းပုံများစွာပါ၀င်သောကြောင့်၊ ၎င်းကိုဖတ်ရန် အချိန်ယူပါ။ အချို့သော အယူအဆများသည် နားလည်ရန် ခက်ခဲနိုင်သည်။ သူတို့ကို ကျော်သွားနိုင်ပြီး ယေဘုယျ အကြံဥာဏ်ကို ရနိုင်ပါသေးတယ်။

သင်တို့ကြားတွင် ဗဟုသုတပိုရှိစေရန် ဤဆောင်းပါးကို အပိုင်း ၃ ပိုင်းခွဲထားသည်။

• အဆင့်နိမ့်နှင့် အဆင့်မြင့် ဒေတာဘေ့စ် အစိတ်အပိုင်းများ၏ ခြုံငုံသုံးသပ်ချက်
• Query Optimization လုပ်ငန်းစဉ်၏ ခြုံငုံသုံးသပ်ချက်
• ငွေပေးငွေယူနှင့် Buffer Pool Management ၏ ခြုံငုံသုံးသပ်ချက်

အခြေခံများ သို့ ပြန်သွားရန်

လွန်ခဲ့သောနှစ်များ (ဝေးကွာသော၊ ဝေးကွာသော နဂါးငွေ့တန်း) တွင် developer များသည် ၎င်းတို့ coding လုပ်သည့် လုပ်ဆောင်မှုအရေအတွက်ကို အတိအကျ သိခဲ့ရသည်။ သူတို့ရဲ့ နှေးကွေးတဲ့ ကွန်ပျူတာတွေရဲ့ CPU နဲ့ Memory ကို မဖြုန်းတီးနိုင်လို့ သူတို့ရဲ့ algorithms နဲ့ ဒေတာတည်ဆောက်ပုံတွေကို နှလုံးသားနဲ့ သိတယ်။

ဤအပိုင်းတွင်၊ ၎င်းတို့သည် ဒေတာဘေ့စ်ကို နားလည်ရန် မရှိမဖြစ်လိုအပ်သောကြောင့် ဤသဘောတရားအချို့ကို ကျွန်ုပ်သတိပေးပါမည်။ သဘောတရားကိုလည်း မိတ်ဆက်ပေးပါမယ်။ ဒေတာဘေ့စ်အညွှန်း.

O(1) vs O(n2)

ယခုအချိန်တွင်၊ developer အများအပြားသည် algorithms ၏အချိန်ရှုပ်ထွေးမှုကို ဂရုမစိုက်ကြဘဲ... မှန်ပါသည်။

ဒါပေမယ့် ဒေတာအများကြီးနဲ့ ဆက်ဆံတဲ့အခါ (ထောင်ပေါင်းများစွာ မပြောပါဘူး) ဒါမှမဟုတ် မီလီစက္ကန့်တွေနဲ့ ရုန်းကန်နေရရင် ဒီသဘောတရားကို နားလည်ဖို့ အရေးကြီးလာပါတယ်။ သင်စိတ်ကူးနိုင်သည်အတိုင်း၊ ဒေတာဘေ့စ်များသည် အခြေအနေနှစ်ခုလုံးကို ကိုင်တွယ်ဖြေရှင်းရမည်ဖြစ်သည်။ အမှတ်ရဖို့အတွက် မင်းကို လိုအပ်တာထက်ပိုပြီး အချိန်ကုန်စေမှာ မဟုတ်ဘူး။ ၎င်းသည် နောက်ပိုင်းတွင် ကုန်ကျစရိတ်အခြေခံ ပိုမိုကောင်းမွန်အောင်ပြုလုပ်ခြင်း၏ သဘောတရားကို နားလည်ရန် ကူညီပေးလိမ့်မည် (ပေးရ based optimization).

ခံယူချက်

algorithm ၏အချိန်ရှုပ်ထွေးမှု ပေးထားသောဒေတာပမာဏအတွက် ပြီးမြောက်ရန် algorithm တစ်ခုသည် မည်မျှကြာမည်ကို ကြည့်ရှုရန် အသုံးပြုသည်။. ဤရှုပ်ထွေးမှုကိုဖော်ပြရန်၊ ကျွန်ုပ်တို့သည် ကြီးမားသော O သင်္ချာအမှတ်အသားကို အသုံးပြုပါသည်။ ပေးထားသောထည့်သွင်းမှုအရေအတွက်အတွက် algorithm တစ်ခုအတွက် လုပ်ဆောင်မှုမည်မျှလိုအပ်ကြောင်း ဖော်ပြသည့် လုပ်ဆောင်ချက်ဖြင့် ဤအမှတ်အသားကို အသုံးပြုထားသည်။

ဥပမာအားဖြင့်၊ "ဤ algorithm တွင် ရှုပ်ထွေးမှု O(some_function()))" ဟုပြောသောအခါ၊ algorithm သည် ဒေတာပမာဏအချို့ကို လုပ်ဆောင်ရန် some_function(a_certain_amount_of_data) လိုအပ်သည်ဟု ဆိုလိုသည်။

ထိုသို့ ဒေတာပမာဏက အရေးမကြီးပါဘူး **မဟုတ်ရင် ** ဒေတာပမာဏတိုးလာသည်နှင့်အမျှ လည်ပတ်မှုအရေအတွက် မည်မျှတိုးလာသည်. အချိန်ရှုပ်ထွေးမှုသည် တိကျသောလုပ်ဆောင်မှုအရေအတွက်ကို မပေးနိုင်သော်လည်း အကောင်အထည်ဖော်ချိန်ကို ခန့်မှန်းရန် နည်းလမ်းကောင်းတစ်ခုဖြစ်သည်။

ဤဂရပ်တွင် သင်သည် မတူညီသော algorithm time complexities အမျိုးအစားများအတွက် ထည့်သွင်းဒေတာပမာဏနှင့် လုပ်ဆောင်ချက်အရေအတွက်ကို သင်တွေ့မြင်နိုင်ပါသည်။ ၎င်းတို့ကိုပြသရန် လော့ဂရစ်သမ်စကေးကို အသုံးပြုခဲ့သည်။ တစ်နည်းဆိုရသော် ဒေတာပမာဏသည် 1 မှ 1 ဘီလီယံအထိ လျင်မြန်စွာ တိုးလာပါသည်။ ၎င်းကို ကျွန်ုပ်တို့ မြင်နိုင်သည်-

• O(1) သို့မဟုတ် စဉ်ဆက်မပြတ် ရှုပ်ထွေးမှုသည် ကိန်းသေတည်ရှိနေသည် (မဟုတ်ပါက ကိန်းသေရှုပ်ထွေးမှုဟု ခေါ်ဆိုမည်မဟုတ်ပါ)။
• O(တုံး(n)) ဒေတာ ဘီလီယံပေါင်းများစွာနဲ့တောင် နိမ့်နေပါသေးတယ်။.
• အဆိုးရွားဆုံးအခက်အခဲ - O(n2)၊ လည်ပတ်မှုအရေအတွက် လျင်မြန်စွာ တိုးလာပါသည်။.
• အခြားသော ရှုပ်ထွေးမှု နှစ်ခုသည် လျင်မြန်စွာ တိုးလာသည်။

ဥပမာ

ဒေတာပမာဏ အနည်းငယ်ဖြင့် O(1) နှင့် O(n2) အကြား ကွာခြားချက်မှာ နည်းပါးပါသည်။ ဥပမာအားဖြင့်၊ သင့်တွင် ဒြပ်စင် 2000 ကို လုပ်ဆောင်ရန် လိုအပ်သော algorithm တစ်ခုရှိသည် ဆိုကြပါစို့။

• O(1) algorithm သည် သင့်အား လည်ပတ်မှု 1 ခု ကုန်ကျမည်ဖြစ်သည်။
• O(log(n)) algorithm သည် သင့်အား လုပ်ဆောင်မှု 7 ခု ကုန်ကျမည်ဖြစ်သည်။
• O(n) algorithm သည် သင့်အား လည်ပတ်မှု 2 ကုန်ကျမည်ဖြစ်သည်။
• O(n*log(n)) algorithm သည် သင့်အား လည်ပတ်မှု 14 ကုန်ကျမည်ဖြစ်သည်။
• O(n2) algorithm သည် သင့်အား လုပ်ဆောင်ချက်ပေါင်း 4 ကုန်ကျမည်ဖြစ်သည်။

O(1) နှင့် O(n2) အကြား ကွာခြားချက်သည် ကြီးမားပုံရသည် (4 million operations) ဖြစ်သော်လည်း၊ သင့်မျက်လုံးမှိတ်ရန် အချိန်သာ 2 ms အများဆုံး ဆုံးရှုံးမည်ဖြစ်သည်။ အမှန်ကတော့ ခေတ်မီပရိုဆက်ဆာတွေက လုပ်ဆောင်နိုင်ပါတယ်။ တစ်စက္ကန့်လျှင် ရာနှင့်ချီသော လည်ပတ်မှု. ထို့ကြောင့် အိုင်တီပရောဂျက်များစွာတွင် စွမ်းဆောင်ရည်နှင့် ပိုမိုကောင်းမွန်အောင်ပြုလုပ်ခြင်းသည် ပြဿနာမဟုတ်ပါ။

ကျွန်တော်ပြောခဲ့သလိုပဲ ဒေတာပမာဏများစွာနဲ့ အလုပ်လုပ်တဲ့အခါ ဒီသဘောတရားကို သိဖို့က အရေးကြီးပါသေးတယ်။ အကယ်၍ ဤအချိန်တွင် algorithm သည် ဒြပ်စင် 1 (ဒေတာဘေ့စ်အတွက် ထိုမျှလောက်မဟုတ်ပါ)။

• O(1) algorithm သည် သင့်အား လည်ပတ်မှု 1 ခု ကုန်ကျမည်ဖြစ်သည်။
• O(log(n)) algorithm သည် သင့်အား လုပ်ဆောင်မှု 14 ခု ကုန်ကျမည်ဖြစ်သည်။
• O(n) algorithm သည် သင့်အား လည်ပတ်မှု 1 ကုန်ကျမည်ဖြစ်သည်။
• O(n*log(n)) algorithm သည် သင့်အား လည်ပတ်မှု 14 ကုန်ကျမည်
• O(n2) algorithm သည် သင့်အား လည်ပတ်မှု 1 ကုန်ကျမည်

သင်္ချာမဖြေရသေးပေမယ့် O(n2) algorithm နဲ့ ကော်ဖီသောက်ဖို့ အချိန်ရှိတယ် (နှစ်ခုတောင်မှ!)။ အကယ်၍ သင်သည် အခြား 0 ကို ဒေတာပမာဏသို့ ထည့်ပါက၊ သင် တစ်ရေးတစ်မော အိပ်ရန် အချိန်ရပါလိမ့်မည်။

ပိုနက်နဲသွားရအောင်

သတင်းအချက်အလက် for:

• ကောင်းသော hash table ကိုရှာဖွေခြင်းသည် O(1) တွင် အစိတ်အပိုင်းတစ်ခုကို တွေ့ရှိသည်။
• ဟန်ချက်ညီသော သစ်ပင်တစ်ပင်ကို ရှာဖွေခြင်းသည် O(log(n)) တွင် ရလဒ်များကို ထုတ်ပေးပါသည်။
• array တစ်ခုကို ရှာဖွေခြင်းသည် O(n) ဖြင့် ရလဒ်များ ထုတ်ပေးသည်။
• အကောင်းဆုံး စီခြင်း အယ်လဂိုရီသမ်များတွင် ရှုပ်ထွေးမှု O(n*log(n)) ရှိသည်။
• မကောင်းသော စီခြင်း အယ်လဂိုရီသမ်တွင် ရှုပ်ထွေးမှု O(n2) ရှိသည်။

မှတ်ချက်- အောက်ပါအပိုင်းများတွင် ကျွန်ုပ်တို့သည် ဤ algorithms နှင့် data structures ကိုတွေ့ရပါမည်။

အချိန်ရှုပ်ထွေးမှု algorithm အမျိုးအစားများစွာ ရှိပါသည်။

• ပျမ်းမျှဖြစ်ရပ်မှန်
• အကောင်းဆုံးဖြစ်ရပ်မှန်
• နှင့် အဆိုးဆုံးအခြေအနေ

အချိန်ရှုပ်ထွေးမှုသည် အဆိုးဆုံးအခြေအနေဖြစ်တတ်သည်။

ကျွန်ုပ်သည် အယ်လဂိုရီသမ်၏ အချိန်ရှုပ်ထွေးမှုအကြောင်းကိုသာ ပြောနေသော်လည်း ရှုပ်ထွေးမှုသည်-

• algorithm ၏မှတ်ဉာဏ်သုံးစွဲမှု
• disk I/O သုံးစွဲမှု algorithm

ဟုတ်ပါတယ်၊ ဥပမာ၊ n2 ထက် ပိုဆိုးတဲ့ နောက်ဆက်တွဲပြဿနာတွေ ရှိတယ်။

• n4: ဒါက ကြောက်စရာကောင်းတယ်။ ဖော်ပြထားသော အယ်လဂိုရီသမ်အချို့တွင် ဤရှုပ်ထွေးမှုများရှိသည်။
• 3n: ဒါက ပိုတောင်ဆိုးသေးတယ်။ ဤဆောင်းပါး၏အလယ်တွင်ကျွန်ုပ်တို့မြင်ရမည့် algorithms တစ်ခုမှာ ဤရှုပ်ထွေးမှုများရှိသည် (၎င်းကို databases များစွာတွင် အမှန်တကယ်အသုံးပြုသည်)။
• factorial n- ဒေတာပမာဏအနည်းငယ်ဖြင့်ပင် သင့်ရလဒ်များကို မည်သည့်အခါမျှ ရရှိမည်မဟုတ်ပါ။
• nn : ဒီလို ရှုပ်ထွေးမှုတွေ ကြုံလာရရင် ဒါက မင်းရဲ့ လှုပ်ရှားမှုနယ်ပယ်က တကယ်လားလို့ ကိုယ့်ကိုကိုယ် မေးသင့်တယ်...

မှတ်ချက်- O ကြီးကြီးမားမား သတ်မှတ်ခြင်း၏ အမှန်တကယ် အဓိပ္ပါယ်ဖွင့်ဆိုချက်ကို အကြံဥာဏ်တစ်ခုမျှ မပေးမိပါ။ ဒီဆောင်းပါးမှာ ဖတ်ရှုနိုင်ပါတယ်။ ဝီကီပီးဒီးယား အစစ်အမှန် (asymptotic) အဓိပ္ပါယ်။

MergeSort

စုစည်းမှုတစ်ခုကို စီရန် လိုအပ်သောအခါ သင်ဘာလုပ်မည်နည်း။ ဘာလဲ? sort() function ကို ခေါ်သည်... ကောင်းပြီ အဖြေ... ဒါပေမယ့် database တစ်ခုအတွက်၊ ဒီ sort() function အလုပ်လုပ်ပုံကို နားလည်ရပါမယ်။

ကောင်းမွန်သော စီခြင်းဆိုင်ရာ အယ်လဂိုရီသမ်များစွာ ရှိသည်၊ ထို့ကြောင့် အရေးကြီးဆုံးကို ကျွန်ုပ်အာရုံစိုက်ပါမည်- ပေါင်းစပ်အမျိုးအစား. ဒေတာအမျိုးအစားခွဲခြင်းသည် အဘယ်ကြောင့် အသုံးဝင်သည်ကို ယခုအချိန်တွင် သင်နားမလည်နိုင်သော်လည်း မေးမြန်းမှုအား ပိုမိုကောင်းမွန်အောင်ပြုလုပ်ခြင်းအပိုင်းကို အပြီးလုပ်ဆောင်သင့်ပါသည်။ ထို့အပြင်၊ ပေါင်းစည်းခြင်းအမျိုးအစားကို နားလည်ခြင်းသည် ဘုံဒေတာဘေ့စ်ပူးပေါင်းဆောင်ရွက်မှုဟုခေါ်သော ဘုံဒေတာဘေ့စ်ကို နောက်ပိုင်းတွင် နားလည်ရန် ကူညီပေးပါမည်။ အဖှဲ့ပေါငျး ပူးပေါင်း (ပေါင်းစည်းခြင်းအသင်း).

ပေါင်းစည်းပါ။

များစွာသော အသုံးဝင်သော အယ်လဂိုရီသမ်များကဲ့သို့ပင်၊ ပေါင်းစည်းခြင်းသည် လှည့်ကွက်တစ်ခုအပေါ် မူတည်သည်- အရွယ်အစား N/2 အမျိုးအစားခွဲထားသော ခင်းကျင်းမှု 2 ခုကို ပေါင်းစပ်ခြင်းသည် N-ဒြပ်စင်ခွဲထားသော ခင်းကျင်းမှုသို့ N လုပ်ဆောင်ချက်များကိုသာ ကုန်ကျပါသည်။ ဤလုပ်ဆောင်ချက်ကို ပေါင်းစည်းခြင်းဟုခေါ်သည်။

ရိုးရှင်းသော ဥပမာတစ်ခုဖြင့် ၎င်းသည် ဘာကိုဆိုလိုသည်ကို ကြည့်ကြပါစို့။

ဤပုံသည် နောက်ဆုံးခွဲထားသော 8-element array ကိုတည်ဆောက်ရန်၊ သင်သည် 2 4-element arrays ထက် တစ်ကြိမ်ထပ်လုပ်ရန် လိုအပ်ကြောင်း ပြသသည်။ ဒြပ်စင် 4 ခုစလုံးကို စီထားပြီးသားဖြစ်သောကြောင့်-

• 1) သင်သည် array နှစ်ခုတွင် လက်ရှိဒြပ်စင်နှစ်ခုလုံးကို နှိုင်းယှဉ်ပါ (အစတွင် လက်ရှိ = ပထမ)၊
• 2) ထို့နောက် အသေးဆုံးကို ယူ၍ 8 element array တွင်ထည့်ပါ။
• 3) အသေးဆုံးဒြပ်စင်ကို သင်ယူထားသည့် array ရှိ နောက်ဒြပ်စင်သို့ ရွှေ့ပါ။
• နှင့် 1,2,3 ကို array တစ်ခု၏ နောက်ဆုံးဒြပ်စင်သို့ ရောက်သည်အထိ ပြန်လုပ်ပါ။
• ထို့နောက် အခြား array ၏ ကျန်ဒြပ်စင်များကို ယူ၍ ၎င်းတို့ကို 8 element array တွင် ထည့်သွင်းပါ။

4-element array နှစ်ခုလုံးကို စီထားသောကြောင့် ၎င်းသည် အလုပ်လုပ်သောကြောင့် ထို array များတွင် "ပြန်သွား" ရန် မလိုအပ်ပါ။

ယခု ကျွန်ုပ်တို့သည် လှည့်ကွက်ကို နားလည်ပြီး၊ ဤနေရာတွင် ပေါင်းစည်းရန်အတွက် ကျွန်ုပ်၏ 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;

ပေါင်းစည်းခြင်းအမျိုးအစားသည် ပြဿနာကို သေးငယ်သောပြဿနာများအဖြစ် ခွဲထုတ်ပြီး မူလပြဿနာ၏ရလဒ်ကိုရရှိရန် သေးငယ်သောပြဿနာများ၏ရလဒ်များကို ရှာဖွေပါ ဤ algorithm ကို နားမလည်ပါက စိတ်မပူပါနှင့်။ ပထမဆုံးမြင်ဖူးတာတော့ နားမလည်ဘူး။ အဲဒါက မင်းကိုကူညီနိုင်ရင် ဒီ algorithm ကို two-phase algorithm အဖြစ် ငါမြင်တယ်-

• Division အဆင့်၊ array ကို သေးငယ်သော array များအဖြစ် ပိုင်းခြားပါသည်။
• စီစဥ်ခြင်းအဆင့်သည် ပိုကြီးသော array ကိုဖွဲ့စည်းရန် သေးငယ်သော array များကို ပေါင်းစပ်ထားသည် (ယူနီယံကို အသုံးပြု၍) ဖြစ်သည်။

တိုင်းအဆင့်

ပိုင်းခြားခြင်းအဆင့်တွင်၊ array ကို အဆင့် 3 ဆင့်ဖြင့် ယူနစ် array များအဖြစ် ပိုင်းခြားထားသည်။ တရားဝင်ခြေလှမ်းအရေအတွက်မှာ log(N) (N=8၊ log(N) = 3) ကတည်းက ဖြစ်သည်။

ဒါကို ငါဘယ်လိုသိလဲ။

ငါက ဉာဏ်ကြီးရှင်ပါ။ စကားလုံး - သင်္ချာ။ အယူအဆမှာ အဆင့်တစ်ခုစီသည် မူလ array ၏ အရွယ်အစားကို 2 ဖြင့် ပိုင်းခြားထားသည်။ အဆင့်အရေအတွက်သည် မူလ array ကို နှစ်ပိုင်းခွဲနိုင်သည့် အကြိမ်အရေအတွက်ဖြစ်သည်။ ဤသည်မှာ လော့ဂရစ်သမ် (base 2) ၏ တိကျသော အဓိပ္ပါယ်ဖွင့်ဆိုချက်ဖြစ်သည်။

စီခြင်းအဆင့်

စီခြင်းအဆင့်တွင်၊ သင်သည် တစ်ယူနစ် (ဒြပ်စင်) ခင်းကျင်းမှုများဖြင့် စတင်သည်။ အဆင့်တစ်ဆင့်စီတွင် သင်သည် ပေါင်းစည်းလုပ်ဆောင်မှုများစွာကို ကျင့်သုံးပြီး စုစုပေါင်းကုန်ကျစရိတ်မှာ N=8 လုပ်ဆောင်ချက်များဖြစ်သည်-

• ပထမအဆင့်တွင် သင့်တွင် လည်ပတ်မှု 4 ခုစီ ကုန်ကျသည့် ပေါင်းစည်းမှု 2 ခုရှိသည်။
• ဒုတိယအဆင့်တွင် လုပ်ငန်းတစ်ခုစီအတွက် 2 ခုကုန်ကျသော ပေါင်းစည်းမှု 4 ခုရှိသည်။
• တတိယအဆင့်တွင် လည်ပတ်မှု 1 ခု ကုန်ကျသည့် 8 ပေါင်းစည်းမှုရှိသည်။

log(N) အဆင့်များ ရှိသောကြောင့်၊ စုစုပေါင်းကုန်ကျစရိတ် N * log(N) လုပ်ဆောင်ချက်များ.

ပေါင်းစည်းခြင်း၏ အားသာချက်များ

ဤ algorithm သည် အဘယ်ကြောင့် အလွန်အစွမ်းထက်သနည်း။

ဘာဖြစ်လို့လဲဆိုတော့:

• array အသစ်များကို မဖန်တီးဘဲ ထည့်သွင်းသည့် array ကို တိုက်ရိုက်မွမ်းမံရန်အတွက် မမ်မိုရီခြေရာကို လျှော့ချရန် ၎င်းကို သင်ပြောင်းလဲနိုင်သည်။

မှတ်ချက်- ဤ algorithm အမျိုးအစားကို ခေါ်သည်။ in-နေရာ (အပိုဆောင်းမှတ်ဉာဏ်မပါဘဲစီခြင်း)။

• သိသာထင်ရှားသော ဒစ်စ့် I/O အပေါ်မှ မပါဝင်ဘဲ ဒစ်နေရာနှင့် မမ်မိုရီအနည်းငယ်ကို တစ်ချိန်တည်းတွင် အသုံးပြုရန် ၎င်းကို သင်ပြောင်းနိုင်သည်။ စိတ်ကူးမှာ လက်ရှိလုပ်ဆောင်နေသည့် အစိတ်အပိုင်းများကိုသာ မှတ်ဉာဏ်ထဲသို့ ထည့်သွင်းရန်ဖြစ်သည်။ 100-megabyte memory buffer ဖြင့် multi-gigabyte table ကို စီရန် လိုအပ်သောအခါတွင် ၎င်းသည် အရေးကြီးပါသည်။

မှတ်ချက်- ဤ algorithm အမျိုးအစားကို ခေါ်သည်။ ပြင်ပအမျိုးအစား.

• လုပ်ငန်းစဉ်များစွာ/ threads/servers များပေါ်တွင် လုပ်ဆောင်ရန် ၎င်းကို သင်ပြောင်းလဲနိုင်သည်။

ဥပမာအားဖြင့်၊ ဖြန့်ဝေသော ပေါင်းစည်းခြင်းအမျိုးအစားသည် အဓိကအစိတ်အပိုင်းများထဲမှ တစ်ခုဖြစ်သည်။ Hadoop (ဒါက big data မှာ တည်ဆောက်ပုံ)။

• ဤ algorithm သည် ခဲများကို ရွှေအဖြစ် ပြောင်းလဲနိုင်သည် (အမှန်ပင်။)

ဤအမျိုးအစားခွဲခြင်းဆိုင်ရာ အယ်လဂိုရီသမ်ကို ဒေတာဘေ့စ်အများစု (အားလုံးမဟုတ်ပါက) တွင်အသုံးပြုသော်လည်း ၎င်းသည်တစ်ခုတည်းမဟုတ်ပါ။ ပိုသိချင်ရင် ဒီလင့်မှာ ဖတ်နိုင်ပါတယ်။ သုတေသနအလုပ်ဘုံဒေတာဘေ့စ်အမျိုးအစားခွဲခြင်းဆိုင်ရာ အယ်လဂိုရီသမ်များ၏ အားသာချက်များနှင့် အားနည်းချက်များကို ဆွေးနွေးပေးသည်။

Array၊ Tree နှင့် Hash Table

ယခု ကျွန်ုပ်တို့သည် အချိန်ရှုပ်ထွေးမှုနှင့် အမျိုးအစားခွဲခြင်းဆိုင်ရာ အယူအဆကို နားလည်လာသောအခါ၊ ဒေတာဖွဲ့စည်းပုံ ၃ ခုအကြောင်း ပြောပြသင့်ပါသည်။ ဒါက သူတို့ကြောင့် အရေးကြီးတယ်။ ခေတ်မီဒေတာဘေ့စ်များ၏အခြေခံများဖြစ်ကြသည်။. သဘောတရားကိုလည်း မိတ်ဆက်ပေးပါမယ်။ ဒေတာဘေ့စ်အညွှန်း.

Array

နှစ်ဘက်မြင် array သည် အရိုးရှင်းဆုံး ဒေတာဖွဲ့စည်းပုံဖြစ်သည်။ ဇယားတစ်ခုအား array တစ်ခုအဖြစ် ယူဆနိုင်သည်။ ဥပမာအားဖြင့်:

ဤ 2 ဖက်မြင် array သည် အတန်းများနှင့် ကော်လံများပါရှိသော ဇယားဖြစ်သည်-

• စာကြောင်းတစ်ခုစီသည် အကြောင်းအရာတစ်ခုကို ကိုယ်စားပြုသည်။
• အကြောင်းအရာကို ဖော်ပြသော ကော်လံများသည် ဂုဏ်သတ္တိများကို သိမ်းဆည်းသည်။
• ကော်လံတစ်ခုစီသည် သီးခြားအမျိုးအစားတစ်ခု၏ အချက်အလက် (ကိန်းပြည့်၊ စာကြောင်း၊ ရက်စွဲ...) ကို သိမ်းဆည်းထားသည်။

ဒေတာကို သိမ်းဆည်းခြင်းနှင့် ပုံဖော်ခြင်းအတွက် ၎င်းသည် အဆင်ပြေသော်လည်း၊ တိကျသောတန်ဖိုးကို သင်ရှာဖွေသည့်အခါ ၎င်းသည် မသင့်လျော်ပါ။

ဥပမာအားဖြင့်၊ သင်သည် UK တွင်အလုပ်လုပ်သောယောက်ျားအားလုံးကိုရှာလိုပါက၊ ထိုအတန်းသည် UK မှဟုတ်မဟုတ်ဆုံးဖြတ်ရန်အတန်းတစ်ခုစီကိုကြည့်ရှုရန်လိုအပ်သည်။ ၎င်းသည် သင့်အား N အရောင်းအ၀ယ်ပြုလုပ်ရာတွင် ကုန်ကျမည်ဖြစ်သည်။ဘယ်မှာ N - လိုင်းအရေအတွက် မဆိုးပါဘူး၊ ဒါပေမယ့် ပိုမြန်တဲ့နည်းလမ်း ရှိနိုင်မလား။ အခုက သစ်ပင်တွေနဲ့ ရင်းနှီးဖို့ အချိန်ရောက်ပြီ။

မှတ်ချက်- ခေတ်မီဒေတာဘေ့စ်အများစုသည် ဇယားများကို ထိရောက်စွာသိမ်းဆည်းရန်အတွက် တိုးချဲ့ထားသော အခင်းအကျင်းများကို ပံ့ပိုးပေးသည်- heap-organizedtables နှင့် index-organizedtables။ သို့သော် ကော်လံအုပ်စုတစ်စုရှိ သီးခြားအခြေအနေတစ်ခုကို လျင်မြန်စွာရှာဖွေခြင်း၏ပြဿနာကို ယင်းက မပြောင်းလဲပါ။

ဒေတာဘေ့စ်သစ်ပင်နှင့် အညွှန်းကိန်း

ဒွိရှာဖွေမှုသစ်ပင်သည် အထူးပိုင်ဆိုင်မှုတစ်ခုပါရှိသော ဒွိစုံသစ်ပင်ဖြစ်ပြီး၊ node တစ်ခုစီရှိ သော့သည်-

• ဘယ်ဘက်ပင်ခွဲတွင် သိမ်းဆည်းထားသော သော့အားလုံးထက် ကြီးသည်။
• မှန်ကန်သောသစ်ပင်ခွဲတွင် သိမ်းဆည်းထားသော သော့အားလုံးထက်နည်းသည်။

အမြင်အာရုံမှာ ဘာကိုဆိုလိုလဲဆိုတာ ကြည့်ကြရအောင်

စိတ်ကူး

ဤသစ်ပင်တွင် N = 15 ဒြပ်စင်များရှိသည်။ 208 ကို ရှာနေတယ် ဆိုပါစို့။

• သော့သည် 136 ၏ root မှစတင်ပါသည်။ 136<208 မှစတင်၍ node 136 ၏ညာဘက်အခွဲကိုကြည့်ပါ။
• 398>208 ထို့ကြောင့် ကျွန်ုပ်သည် node 398 ၏ ဘယ်ဘက်အခြမ်းကို ကြည့်နေသည်။
• 250>208 ထို့ကြောင့် ကျွန်ုပ်သည် node 250 ၏ ဘယ်ဘက်အခြမ်းကို ကြည့်နေသည်။
• 200<208 ထို့ကြောင့် ကျွန်ုပ်သည် node 200 ၏ ညာဘက်အခြမ်းကို ကြည့်နေသည်။ သို့သော် 200 တွင် မှန်ကန်သောသစ်ပင်မရှိ၊ တန်ဖိုးမရှိပါ။ (ဘာလို့လဲဆိုတော့ အဲဒါရှိရင်၊ ညာဘက်က subtree 200 မှာရှိမယ်)။

အခု 40 ကို ရှာနေတယ် ဆိုပါစို့

• သော့သည် 136 ၏ root မှ စတင်ပါသည်။ 136 > 40 မှစ၍၊ node 136 ၏ ဘယ်ဘက်အခြမ်းကို ကြည့်ပါသည်။
• 80 > 40၊ ထို့ကြောင့် ကျွန်ုပ်သည် node 80 ၏ ဘယ်ဘက်အခြမ်းကို ကြည့်နေသည်။
• ၄၀=၄၀၊ node ရှိတယ်။. ကျွန်ုပ်သည် node အတွင်းရှိ row ID ကိုရယူပြီး (ပုံတွင်မပြထား) နှင့်ပေးထားသော row ID အတွက်ဇယားကိုကြည့်ရှုပါ။
• အတန်း ID ကိုသိခြင်းက ဇယားရှိဒေတာဘယ်မှာရှိတယ်ဆိုတာကို အတိအကျသိနိုင်စေတဲ့အတွက် ချက်ချင်းပြန်ယူနိုင်ပါတယ်။

နောက်ဆုံးတွင်၊ ရှာဖွေမှုနှစ်ခုစလုံးသည် သစ်ပင်အတွင်းရှိ အဆင့်အရေအတွက်ကို ကုန်ကျစေမည်ဖြစ်သည်။ ပေါင်းစည်းခြင်းအကြောင်း အပိုင်းကို သေသေချာချာဖတ်ပါက၊ log(N) အဆင့်များရှိကြောင်း တွေ့ရပါမည်။ ထွက်လှည့်၊ ရှာဖွေမှုကုန်ကျစရိတ်မှတ်တမ်း(N), မဆိုးပါဘူး!

ငါတို့ပြဿနာကို ပြန်ကြည့်ရအောင်

ဒါပေမယ့် ဒါက သိပ်ကို စိတ်ကူးယဉ်ဆန်တယ်၊ ဒါကြောင့် ငါတို့ရဲ့ ပြဿနာကို ပြန်ကြည့်ရအောင်။ ရိုးရှင်းသော ကိန်းပြည့်အစား ယခင်ဇယားရှိ တစ်စုံတစ်ဦး၏နိုင်ငံကို ကိုယ်စားပြုသည့် စာကြောင်းတစ်ခုကို စိတ်ကူးကြည့်ပါ။ သင့်တွင် ဇယား၏ "နိုင်ငံ" အကွက် (ကော်လံ 3) ပါရှိသော သစ်ပင်တစ်ပင်ရှိသည် ဆိုကြပါစို့။

• UK မှာ အလုပ်လုပ်တဲ့ သူတွေ သိချင်ရင်
• ဂရိတ်ဗြိတိန်ကိုကိုယ်စားပြုတဲ့ node ကိုရဖို့အတွက် သစ်ပင်ကိုကြည့်ပါ။
• "UKnode" တွင် UK အလုပ်သမားမှတ်တမ်းများ၏တည်နေရာကိုသင်တွေ့လိမ့်မည်။

array ကို တိုက်ရိုက်အသုံးပြုပါက ဤရှာဖွေမှုသည် N လုပ်ဆောင်ချက်များအစား မှတ်တမ်း(N) လုပ်ဆောင်ချက်များကို ကုန်ကျမည်ဖြစ်သည်။ ခုနက တင်ပြခဲ့တာ ဒေတာဘေ့စ်အညွှန်း.

သင့်တွင် သော့များ (ဥပမာ အကွက်အုပ်စုများ) ကို နှိုင်းယှဉ်ရန် လုပ်ဆောင်ချက်တစ်ခုရှိသ၍ မည်သည့်နယ်ပယ်အုပ်စု (စာကြောင်း၊ နံပါတ်၊ 2 လိုင်း၊ နံပါတ်နှင့် စာကြောင်း၊ ရက်စွဲ...) အတွက် အညွှန်းသစ်ပင်ကို သင်တည်ဆောက်နိုင်သည်။ သော့များကြားတွင် အမိန့်ပေးသည်။ (၎င်းသည် ဒေတာဘေ့စ်ရှိ မည်သည့်အခြေခံအမျိုးအစားများအတွက်မဆို သက်ဆိုင်သည်)။

B+TreeIndex

ဤသစ်ပင်သည် တိကျသောတန်ဖိုးတစ်ခုရရှိရန်အတွက် ကောင်းမွန်စွာအလုပ်လုပ်သော်လည်း လိုအပ်သည့်အခါတွင် ပြဿနာကြီးတစ်ခုရှိသည်။ တန်ဖိုးနှစ်ခုကြားတွင် ဒြပ်စင်များစွာကို ရယူပါ။. သစ်ပင်ရှိ node တစ်ခုစီကို ကြည့်ရှုပြီး ဤတန်ဖိုးနှစ်ခုကြားရှိမရှိ စစ်ဆေးရမည်ဖြစ်ပြီး၊ အကြောင်းမှာ ၎င်းသည် O(N) ကုန်ကျမည်ဖြစ်သည်။ ထို့အပြင်၊ သင်သည် သစ်ပင်တစ်ခုလုံးကို ဖတ်ရသောကြောင့် ဤလုပ်ဆောင်ချက်သည် disk I/O အတွက် အဆင်ပြေမည်မဟုတ်ပါ။ ထိထိရောက်ရောက် အကောင်အထည်ဖော်ဖို့ နည်းလမ်းရှာဖို့ လိုပါတယ်။ အပိုင်းအခြားတောင်းဆိုချက်. ဤပြဿနာကိုဖြေရှင်းရန်၊ ခေတ်မီဒေတာဘေ့စ်များသည် B+Tree ဟုခေါ်သောယခင်သစ်ပင်၏မွမ်းမံထားသောဗားရှင်းကိုအသုံးပြုသည်။ B+Tree သစ်ပင်တွင်-

• အနိမ့်ဆုံးဆုံမှတ်များသာ (အရွက်များ)၊ အချက်အလက်သိမ်းဆည်းပါ။ (ဆက်စပ်ဇယားရှိအတန်းများ၏တည်နေရာ)
• ကျန်တဲ့ node တွေက ဒီမှာ လမ်းကြောင်းအတွက် မှန်ကန်သော node သို့ ရှာဖွေနေစဉ်.

သင်တွေ့မြင်ရသည့်အတိုင်း ဤနေရာတွင် နောက်ထပ် node များ (နှစ်ကြိမ်) ရှိပါသည်။ အမှန်မှာ၊ သင့်တွင် မှန်ကန်သော node (ဆက်စပ်ဇယားရှိ အတန်းများ၏တည်နေရာကို သိမ်းဆည်းထားသည့်) မှန်ကန်သော node ကိုရှာဖွေရန် ကူညီပေးမည့် "ဆုံးဖြတ်ချက် nodes" အပိုဆောင်း node များရှိသည်။ သို့သော် ရှာဖွေမှုရှုပ်ထွေးမှုသည် O(log(N)) (နောက်ထပ် အဆင့်တစ်ခုသာရှိသေးသည်)။ ကြီးမားတဲ့ ခြားနားချက်ကတော့ အဲဒါပါပဲ။ အောက်ခြေအဆင့်ရှိ node များသည် ၎င်းတို့၏ ဆက်ခံသူများနှင့် ချိတ်ဆက်ထားသည်။.

ဤ B+Tree ဖြင့်၊ သင်သည် 40 နှင့် 100 အကြားတန်ဖိုးများကိုရှာဖွေနေပါက-

• သင်သည် ယခင်သစ်ပင်နှင့်တူသော 40 (သို့မဟုတ် 40 မရှိလျှင် 40 ပြီးနောက် အနီးစပ်ဆုံးတန်ဖိုး) ကို ရှာရန်သာလိုသည်။
• ထို့နောက် သင် 40 ပြည့်သည်အထိ တိုက်ရိုက်အမွေဆက်ခံလင့်ခ်များကို အသုံးပြု၍ အမွေဆက်ခံသူ 100 ဦးကို စုဆောင်းပါ။

M ကိုဆက်ခံသူတွေ့ပြီး သစ်ပင်တွင် N node များရှိသည်ဆိုကြပါစို့။ ယခင်သစ်ပင်ကဲ့သို့ သီးခြား node တစ်ခုကို ရှာဖွေရာတွင် ကုန်ကျစရိတ် မှတ်တမ်း(N)။ ဒါပေမယ့် ဒီ node ကို သင်ရပြီဆိုတာနဲ့၊ သူတို့ရဲ့ ဆက်ခံသူတွေကို ရည်ညွှန်းတဲ့ M လုပ်ငန်းတွေမှာ M ဆက်ခံသူတွေကို သင်ရလိမ့်မယ်။ ဤရှာဖွေမှုသည် M+log(N) သာ ကုန်ကျသည် ယခင်သစ်ပင်ရှိ N လုပ်ဆောင်ချက်များနှင့် နှိုင်းယှဉ်သည့် လုပ်ဆောင်ချက်များ။ ထို့အပြင်၊ သင်သည် အပြည့်အဝသစ်ပင် (M+log(N) node များသာ) ကိုဖတ်ရန် မလိုအပ်ပါ။ ဆိုလိုသည်မှာ ဒစ်ခ်အသုံးပြုမှုနည်းသည်။ M သည် သေးငယ်သည် (ဥပမာ အတန်း 200) နှင့် N သည် ကြီးမားသော (အတန်း 1) ဖြစ်ပါက ကြီးမားသော ခြားနားချက် ရှိလိမ့်မည်။

ဒါပေမယ့် ဒီမှာ ပြဿနာအသစ်တွေ ရှိတယ် (တဖန်!) အကယ်၍ သင်သည် ဒေတာဘေ့စ်တွင် အတန်းတစ်ခုကို ထည့်ပါ သို့မဟုတ် ဖျက်ပါက (ထို့ကြောင့် ဆက်စပ် B+Tree အညွှန်းတွင်)

• B+Tree အတွင်းရှိ node များကြား အစီအစဥ်ကို ထိန်းသိမ်းထားရမည်ဖြစ်ပြီး၊ မဟုတ်ပါက မခွဲခြားထားသောသစ်ပင်အတွင်းရှိ node များကို ရှာတွေ့နိုင်မည်မဟုတ်ပါ။
• B+Tree တွင် ဖြစ်နိုင်ချေရှိသော အဆင့်အနိမ့်ဆုံးအဆင့်ကို ထားရှိရမည်၊ မဟုတ်ပါက O(log(N)) အချိန်ရှုပ်ထွေးမှုသည် O(N) ဖြစ်လာမည်ဖြစ်သည်။

တစ်နည်းဆိုရသော် B+Tree သည် မိမိဘာသာ အော်ဒါမှာပြီး ဟန်ချက်ညီနေရပါမည်။ ကံကောင်းစွာဖြင့်၊ ၎င်းကို စမတ် ဖျက်ခြင်းနှင့် ထည့်သွင်းခြင်း လုပ်ဆောင်ချက်များဖြင့် ဖြစ်နိုင်သည်။ သို့သော် ၎င်းသည် ကုန်ကျစရိတ်ဖြင့် လာပါသည်- B+ သစ်ပင်တွင် ထည့်သွင်းခြင်းနှင့် ဖျက်ခြင်း O(log(N)) ကုန်ကျသည်။ အဲဒါကြောင့် တချို့က ကြားဖူးတယ်။ အညွှန်းကိန်းများ အလွန်အကျွံသုံးခြင်းသည် ကောင်းသောအကြံမဟုတ်ပါ။. တကယ်လား၊ သင်သည် ဇယားတစ်ခုရှိ အတန်းတစ်ခု၏ အမြန်ထည့်သွင်း/အပ်ဒိတ်/ဖျက်ခြင်းကို နှေးကွေးစေသည်။အဘယ်ကြောင့်ဆိုသော် ဒေတာဘေ့စ်သည် အညွှန်းတစ်ခုစီအတွက် စျေးကြီးသော O(log(N)) လုပ်ဆောင်ချက်ကို အသုံးပြု၍ ဇယား၏အညွှန်းကိန်းများကို အပ်ဒိတ်လုပ်ရန် လိုအပ်သောကြောင့်ဖြစ်သည်။ ထို့အပြင်၊ အညွှန်းကိန်းများထည့်ခြင်းသည် အလုပ်တာဝန်ပိုမိုရရှိစေသည်။ ငွေပေးငွေယူမန်နေဂျာ (ဆောင်းပါး၏အဆုံးတွင် ဖော်ပြပါမည်။)

အသေးစိတ်အချက်အလက်များအတွက် Wikipedia ဆောင်းပါးတွင် ကြည့်ရှုနိုင်ပါသည်။ B+သစ်ပင်. ဒေတာဘေ့စ်တစ်ခုတွင် B+Tree ကိုအကောင်အထည်ဖော်ခြင်း၏ဥပမာကိုရယူလိုပါက၊ ကြည့်ရှုပါ။ ဒီဆောင်းပါး и ဒီဆောင်းပါး ဦးဆောင် MySQL developer မှ။ ၎င်းတို့နှစ်ဦးစလုံးသည် InnoDB (MySQL အင်ဂျင်) သည် အညွှန်းကိန်းများကို ကိုင်တွယ်ပုံအပေါ် အာရုံစိုက်ကြသည်။

မှတ်ချက်- အဆင့်နိမ့်သော ပိုမိုကောင်းမွန်အောင်ပြုလုပ်မှုများကြောင့် B+ သစ်ပင်သည် လုံးလုံးမျှမျှတတဖြစ်သင့်သည်ဟု စာဖတ်သူတစ်ဦးက ပြောခဲ့သည်။

Hasshable

ကျွန်ုပ်တို့၏နောက်ဆုံးအရေးကြီးသောဒေတာဖွဲ့စည်းပုံမှာ hash table ဖြစ်သည်။ တန်ဖိုးများကို အမြန်ရှာဖွေလိုသည့်အခါ ၎င်းသည် အလွန်အသုံးဝင်ပါသည်။ ထို့အပြင်၊ hash table ကိုနားလည်ခြင်းသည် hash join ဟုခေါ်သော ဘုံဒေတာဘေ့စ်ပူးပေါင်းဆောင်ရွက်မှုကို နောက်ပိုင်းတွင် နားလည်ရန် ကူညီပေးပါမည်။ hash join) အချို့သော အတွင်းပိုင်းအရာများကို သိမ်းဆည်းရန်အတွက် ဤဒေတာဖွဲ့စည်းပုံကိုလည်း ဒေတာဘေ့စ်မှလည်း အသုံးပြုသည် (ဥပမာ။ သော့ခတ်စားပွဲ သို့မဟုတ် ကြားခံရေကန်ဒီသဘောတရားနှစ်ခုလုံးကို နောက်မှတွေ့မယ်။)

hash table သည် ၎င်း၏သော့ဖြင့် ဒြပ်စင်တစ်ခုကို လျင်မြန်စွာ ရှာဖွေနိုင်သည့် ဒေတာဖွဲ့စည်းပုံဖြစ်သည်။ hash table တစ်ခုတည်ဆောက်ရန်၊ သင်သတ်မှတ်ရန်လိုအပ်သည်-

• သော့ သင်၏ဒြပ်စင်များအတွက်
• hash လုပ်ဆောင်ချက် သော့များအတွက်။ တွက်ချက်ထားသော key hashe များသည် element များ၏တည်နေရာကိုပေးသည် (ဟုခေါ်သည်။ အပိုင်းများ ).
• သော့များကို နှိုင်းယှဉ်ရန် လုပ်ဆောင်ချက်. မှန်ကန်သော အပိုင်းကို သင်တွေ့ရှိပြီးသည်နှင့်၊ ဤနှိုင်းယှဉ်မှုကို အသုံးပြု၍ အပိုင်းအတွင်း သင်ရှာဖွေနေသည့် အစိတ်အပိုင်းကို ရှာဖွေရပါမည်။

ရိုးရှင်းသောဥပမာ

ရှင်းရှင်းလင်းလင်း ဥပမာတစ်ခုကို ကြည့်ကြပါစို့။

ဤ hash ဇယားတွင် အပိုင်း ၁၀ ပိုင်းရှိသည်။ ပျင်းနေလို့ အပိုင်း ၅ ပိုင်းပဲ ပုံဖော်ခဲ့တယ်၊ ဒါပေမယ့် မင်းက ဉာဏ်ကောင်းတယ်ဆိုတာ ငါသိတယ်၊ ဒါကြောင့် ကျန်တဲ့ ၅ ပုံကို မင်းကိုယ်တိုင် ပုံဖော်ခွင့်ပေးမယ်။ သော့၏ hash function modulo 10 ကို ကျွန်တော်အသုံးပြုခဲ့သည်။ တစ်နည်းဆိုရသော်၊ ကျွန်ုပ်သည် ၎င်း၏ အပိုင်းကိုရှာဖွေရန် ဒြပ်စင်၏သော့၏ နောက်ဆုံးဂဏန်းကိုသာ သိမ်းဆည်းထားသည်-

• နောက်ဆုံးဂဏန်းသည် 0 ဖြစ်ပါက ဒြပ်စင်သည် segment 0 သို့ ကျရောက်သည်၊
• နောက်ဆုံးဂဏန်းသည် 1 ဖြစ်ပါက ဒြပ်စင်သည် segment 1 သို့ ကျရောက်သည်၊
• နောက်ဆုံးဂဏန်းသည် 2 ဖြစ်ပါက ဒြပ်စင်သည် ဧရိယာ 2 သို့ ကျရောက်သည်။
• ...

ကျွန်တော်အသုံးပြုခဲ့သည့် နှိုင်းယှဉ်မှုလုပ်ဆောင်ချက်သည် ကိန်းပြည့်နှစ်ခုကြားတွင် ညီမျှခြင်းဖြစ်ပါသည်။

Element 78 ကို လိုချင်တယ် ဆိုကြပါစို့။

• hash table သည် 78 အတွက် hash code ကိုတွက်ချက်သည်၊ 8 ဖြစ်သည်။
• hash table သည် segment 8 ကိုကြည့်ပါ၊ ၎င်းတွေ့ရှိသည့်ပထမဒြပ်စင်မှာ 78 ဖြစ်သည်။
• 78 ကို မင်းဆီ ပြန်ပို့ပေးတယ်။
• ရှာဖွေခြင်းလုပ်ငန်း ၂ ခုသာ ကုန်ကျသည်။ (တစ်ခုသည် hash တန်ဖိုးကိုတွက်ချက်ရန်နှင့် segment အတွင်းရှိဒြပ်စင်ကိုရှာဖွေရန်နောက်တစ်ခု)။

အခု မင်း element 59 ကို ရချင်တယ် ဆိုကြပါစို့။

• hash table သည် 59 အတွက် hash code ကိုတွက်ချက်သည်၊ 9 ဖြစ်သည်။
• hash table သည် segment 9 တွင်ရှာဖွေသည်၊ ပထမဆုံးတွေ့ရသောဒြပ်စင်မှာ 99 ဖြစ်သည်။ 99!=59 မှစ၍၊ element 99 သည် မှန်ကန်သောဒြပ်စင်မဟုတ်ပါ။
• တူညီသောယုတ္တိကိုအသုံးပြု၍ ဒုတိယဒြပ်စင် (၉)၊ တတိယ (၇၉)၊ ...၊ နောက်ဆုံး (၂၉) ကို ယူသည်။
• ဒြပ်စင်မတွေ့ပါ။
• ရှာဖွေရေး လုပ်ငန်း ၇ ခု ကုန်ကျပါတယ်။.

ကောင်းသော hash လုပ်ဆောင်ချက်

သင်ရှာဖွေနေသည့်တန်ဖိုးပေါ်မူတည်၍ ကုန်ကျစရိတ်သည် တူညီမည်မဟုတ်ပါ။

အကယ်၍ ကျွန်ုပ်သည် သော့၏ hash function modulo 1 (၎င်းသည် နောက်ဆုံးဂဏန်း 000 လုံးကိုယူခြင်း) ကိုပြောင်းလဲပါက၊ ဒုတိယရှာဖွေမှုသည် segment 000 တွင်ဒြပ်စင်များမရှိသည့်အတွက် လုပ်ဆောင်ချက် 6 ခုသာကုန်ကျပါသည်။ တကယ့်စိန်ခေါ်မှုမှာ အလွန်သေးငယ်သော ဒြပ်စင်များပါရှိသော ပုံးများကို ဖန်တီးမည့် ကောင်းမွန်သော hash လုပ်ဆောင်ချက်ကို ရှာဖွေရန်ဖြစ်သည်။.

ကျွန်ုပ်၏ဥပမာတွင်၊ ကောင်းသော hash လုပ်ဆောင်ချက်ကိုရှာဖွေရန်လွယ်ကူသည်။ ဒါပေမယ့် ဒါက ရိုးရှင်းတဲ့ ဥပမာတစ်ခုပါ၊ သော့ချက်က ကောင်းတဲ့ hash function ကိုရှာရတာ ပိုခက်ပါတယ်။

• string (ဥပမာ - နောက်ဆုံးအမည်)
• စာကြောင်း ၂ ကြောင်း (ဥပမာ - အမည်နှင့် ပထမအမည်)
• စာကြောင်း 2 ကြောင်းနှင့် ရက်စွဲ (ဥပမာ - နောက်ဆုံးအမည်၊ ပထမအမည်နှင့် မွေးသက္ကရာဇ်)
• ...

ကောင်းသော hash လုပ်ဆောင်ချက်ဖြင့်၊ hash table lookups သည် O(1) ကုန်ကျသည်.

Array နှင့် hash ဇယား

ဘာကြောင့် array ကိုမသုံးတာလဲ။

ဟမ်၊ မေးခွန်းကောင်း။

• hash table လည်း ဖြစ်နိုင်ပါတယ်။ မှတ်ဉာဏ်ထဲသို့ တစ်စိတ်တစ်ပိုင်း တင်ထားသည်။၊ ကျန်အပိုင်းများသည် disk ပေါ်တွင်ရှိနေနိုင်သည်။
• array တစ်ခုဖြင့် သင်သည် မှတ်ဉာဏ်ထဲတွင် ဆက်တိုက်နေရာလွတ်ကို အသုံးပြုရပါမည်။ စားပွဲကြီးတစ်လုံးကို ဆွဲချနေရင်၊ အဆက်မပြတ်နေရာလွတ်ကို ရှာဖွေရန် အလွန်ခက်ခဲသည်။.
• hash table တစ်ခုအတွက်၊ သင်အလိုရှိသောသော့ (ဥပမာ၊ နိုင်ငံနှင့်လူ၏နောက်ဆုံးအမည်) ကို သင်ရွေးချယ်နိုင်ပါသည်။

ပိုမိုသိရှိလိုပါက, သင်အကြောင်းဆောင်းပါးကိုဖတ်ရှုနိုင်ပါတယ်။ ဂျာဗားHashMaphash table ကို ထိရောက်စွာ အကောင်အထည်ဖော်ခြင်း ၊ ဤဆောင်းပါးတွင်ပါရှိသော သဘောတရားများကို နားလည်ရန် Java ကို နားလည်ရန် မလိုအပ်ပါ။

source: www.habr.com