Hey Xabr! E'tiboringizga maqolaning tarjimasini taqdim etaman
"Relyatsion ma'lumotlar bazasi qanday ishlaydi".

Relyatsion ma'lumotlar bazalari haqida gap ketganda, men yordam bera olmayman, lekin biror narsa etishmayotgan deb o'ylayman. Ular hamma joyda qo'llaniladi. Kichik va foydali SQLite dan kuchli Teradatagacha bo'lgan turli xil ma'lumotlar bazalari mavjud. Ammo ma'lumotlar bazasi qanday ishlashini tushuntiradigan bir nechta maqolalar mavjud. Natijalar qanchalik kamligini ko'rish uchun "howdoesarelationaldatabasework" yordamida o'zingizni qidirishingiz mumkin. Bundan tashqari, bu maqolalar qisqa. Agar siz eng so'nggi shovqinli texnologiyalarni (BigData, NoSQL yoki JavaScript) izlayotgan bo'lsangiz, ular qanday ishlashini tushuntiruvchi batafsil maqolalarni topasiz.

Relyatsion ma'lumotlar bazalari juda eski va universitet kurslari, ilmiy maqolalar va kitoblardan tashqari tushuntirish uchun juda zerikarlimi?

Ishlab chiquvchi sifatida men tushunmaydigan narsadan foydalanishni yomon ko'raman. Va agar ma'lumotlar bazalari 40 yildan ortiq foydalanilgan bo'lsa, buning sababi bo'lishi kerak. Yillar davomida men har kuni foydalanadigan ushbu g'alati qora qutilarni tushunish uchun yuzlab soatlar sarfladim. Relyatsion ma'lumotlar bazalari juda qiziq, chunki ular foydali va qayta foydalanish mumkin bo'lgan tushunchalarga asoslanadi. Agar siz ma'lumotlar bazasini tushunishga qiziqsangiz, lekin bu keng mavzuni o'rganishga hech qachon vaqtingiz yoki moyilligingiz bo'lmasa, ushbu maqoladan bahramand bo'lishingiz kerak.

Ushbu maqolaning sarlavhasi aniq bo'lsa-da, ushbu maqolaning maqsadi ma'lumotlar bazasidan qanday foydalanishni tushunish emas. Demak, oddiy ulanish so'rovini va asosiy so'rovlarni qanday yozishni allaqachon bilishingiz kerak RAW; aks holda siz ushbu maqolani tushunmasligingiz mumkin. Bu siz bilishingiz kerak bo'lgan yagona narsa, qolganini tushuntiraman.

Men kompyuter fanining ba'zi asoslaridan boshlayman, masalan, algoritmlarning vaqt murakkabligi (BigO). Bilaman, sizlardan ba'zilaringiz bu kontseptsiyadan nafratlanadi, ammo busiz siz ma'lumotlar bazasi ichidagi nozik narsalarni tushuna olmaysiz. Bu juda katta mavzu bo'lgani uchun, Men diqqatimni qarataman muhim deb hisoblagan narsa: ma'lumotlar bazasi qanday ishlaydi SQL so'rovnoma. Men shunchaki tanishtiraman asosiy ma'lumotlar bazasi tushunchalariShunday qilib, maqolaning oxirida siz kaput ostida nima bo'layotgani haqida tasavvurga ega bo'lasiz.

Bu juda ko'p algoritmlar va ma'lumotlar tuzilmalarini o'z ichiga olgan uzoq va texnik maqola bo'lgani uchun uni o'qishga vaqt ajrating. Ba'zi tushunchalarni tushunish qiyin bo'lishi mumkin; siz ularni o'tkazib yuborishingiz va umumiy fikrni olishingiz mumkin.

Sizning orangizdagi bilimdonlar uchun ushbu maqola 3 qismga bo'lingan:

Past va yuqori darajadagi ma'lumotlar bazasi komponentlariga umumiy nuqtai
So'rovlarni optimallashtirish jarayonining umumiy ko'rinishi
Tranzaksiya va bufer pulini boshqarishga umumiy nuqtai

Asoslarga qaytish

Yillar oldin (uzoq, uzoq galaktikada...) ishlab chiquvchilar kodlashayotgan operatsiyalar sonini aniq bilishlari kerak edi. Ular o'zlarining algoritmlari va ma'lumotlar tuzilmalarini yoddan bilishgan, chunki ular sekin kompyuterlarining CPU va xotirasini behuda sarflashga qodir emas edilar.

Ushbu qismda men sizga ushbu tushunchalarning ba'zilarini eslatib o'taman, chunki ular ma'lumotlar bazasini tushunish uchun zarurdir. Men ham tushuncha bilan tanishtiraman ma'lumotlar bazasi indeksi.

O(1) va O(n2)

Hozirgi kunda ko'plab ishlab chiquvchilar algoritmlarning vaqt murakkabligi haqida qayg'urmaydilar ... va ular to'g'ri!

Ammo siz juda ko'p ma'lumotlar bilan ishlayotganingizda (men minglab gapirmayapman) yoki millisekundlarda kurashayotgan bo'lsangiz, bu kontseptsiyani tushunish juda muhim bo'ladi. Va siz tasavvur qilganingizdek, ma'lumotlar bazalari ikkala vaziyatni ham hal qilishlari kerak! Men sizni fikrni tushunish uchun kerak bo'lgandan ko'proq vaqt sarflashingizga majbur qilmayman. Bu keyinchalik xarajatlarga asoslangan optimallashtirish tushunchasini tushunishimizga yordam beradi (qiymati asoslangan optimallashtirish).

tushuncha

Algoritmning vaqt murakkabligi ma'lum miqdordagi ma'lumotlar uchun algoritmni bajarish uchun qancha vaqt ketishini ko'rish uchun foydalaniladi. Bu murakkablikni tasvirlash uchun biz katta O matematik belgilaridan foydalanamiz.Bu belgi algoritmga ma’lum miqdordagi kirishlar uchun qancha amal qilish kerakligini tavsiflovchi funksiya bilan ishlatiladi.

Masalan, “bu algoritm O(some_function()) murakkabligi bor” desam, algoritm ma’lum miqdordagi ma’lumotlarni qayta ishlash uchun some_function(a_aniq_ma’lumotlarning_miqdori) amallarini talab qiladi.

Shunday qilib Muhimi maʼlumotlar miqdori emas**, aks holda ** ma'lumotlar hajmining oshishi bilan operatsiyalar soni qanday oshadi. Vaqtning murakkabligi operatsiyalarning aniq sonini ta'minlamaydi, lekin bajarilish vaqtini hisoblashning yaxshi usuli hisoblanadi.

Ushbu grafikda siz turli xil algoritm vaqtlari murakkabligi uchun kiritilgan ma'lumotlar miqdoriga nisbatan operatsiyalar sonini ko'rishingiz mumkin. Men ularni ko'rsatish uchun logarifmik shkaladan foydalandim. Boshqacha qilib aytganda, ma'lumotlar miqdori tezda 1 milliarddan 1 milliardgacha oshadi.Biz buni ko'rishimiz mumkin:

O (1) yoki doimiy murakkablik doimiy bo'lib qoladi (aks holda u doimiy murakkablik deb nomlanmaydi).
O(log(n)) milliardlab ma'lumotlar bilan ham pastligicha qolmoqda.
Eng yomon qiyinchilik - O(n2), bu erda operatsiyalar soni tez o'sadi.
Qolgan ikkita asorat ham xuddi shunday tez ortadi.

misollar

Kichik miqdordagi ma'lumotlar bilan O (1) va O (n2) o'rtasidagi farq ahamiyatsiz. Misol uchun, sizda 2000 ta elementni qayta ishlash kerak bo'lgan algoritm bor deylik.

O(1) algoritmi sizga 1 ta operatsiyani talab qiladi
O(log(n)) algoritmi sizga 7 ta amalni sarflaydi
O(n) algoritmi sizga 2 operatsiyani talab qiladi
O(n*log(n)) algoritmi sizga 14 ta amalni sarflaydi
O(n2) algoritmi sizga 4 000 000 operatsiyani talab qiladi

O(1) va O(n2) o'rtasidagi farq katta ko'rinadi (4 million operatsiya), lekin siz maksimal 2 milodiy vaqtni yo'qotasiz, shunchaki ko'zingizni miltillash vaqti. Haqiqatan ham, zamonaviy protsessorlar ishlov berishi mumkin soniyada yuz millionlab operatsiyalar. Shuning uchun ko'plab IT loyihalarida ishlash va optimallashtirish muammo emas.

Aytganimdek, katta hajmdagi ma'lumotlar bilan ishlashda ushbu kontseptsiyani bilish hali ham muhimdir. Agar bu safar algoritm 1 000 000 elementni qayta ishlashi kerak bo'lsa (bu ma'lumotlar bazasi uchun unchalik ko'p emas):

O(1) algoritmi sizga 1 ta operatsiyani talab qiladi
O(log(n)) algoritmi sizga 14 ta amalni sarflaydi
O(n) algoritmi sizga 1 000 000 operatsiyani talab qiladi
O(n*log(n)) algoritmi sizga 14 000 000 operatsiyani sarflaydi
O(n2) algoritmi sizga 1 000 000 000 000 operatsiyani talab qiladi

Men matematikani bajarmadim, lekin aytmoqchimanki, O(n2) algoritmi bilan sizda qahva ichishga vaqtingiz bor (hatto ikkita!). Agar siz ma'lumotlar hajmiga yana 0 qo'shsangiz, uxlash uchun vaqtingiz bo'ladi.

Keling, chuqurroq boraylik

ma'lumot olish uchun:

Yaxshi xesh-jadval qidiruvi O(1) da elementni topadi.
Yaxshi muvozanatli daraxtni izlash O(log(n)) da natijalar beradi.
Massivni izlash O(n) da natijalar beradi.
Eng yaxshi saralash algoritmlari O(n*log(n)) murakkabligiga ega.
Yomon tartiblash algoritmi O(n2) murakkabligiga ega.

Eslatma: Keyingi qismlarda biz ushbu algoritmlar va ma'lumotlar tuzilmalarini ko'rib chiqamiz.

Algoritm vaqtini murakkablashtirishning bir necha turlari mavjud:

o'rtacha vaziyat stsenariysi
eng yaxshi stsenariy
va eng yomon stsenariy

Vaqtning murakkabligi ko'pincha eng yomon stsenariydir.

Men faqat algoritmning vaqt murakkabligi haqida gapirgan edim, ammo murakkablik quyidagilarga ham tegishli:

algoritmning xotira iste'moli
disk kiritish-chiqarishni iste'mol qilish algoritmi

Albatta, n2 dan ham yomonroq asoratlar mavjud, masalan:

n4: bu dahshatli! Yuqorida aytib o'tilgan algoritmlarning ba'zilari bunday murakkablikka ega.
3n: bu bundan ham battar! Ushbu maqolaning o'rtasida ko'rib chiqiladigan algoritmlardan biri bu murakkablikka ega (va u aslida ko'plab ma'lumotlar bazalarida qo'llaniladi).
faktorial n: oz miqdordagi ma'lumotlar bilan ham natijalaringizni hech qachon olmaysiz.
nn: Agar siz bunday murakkablikka duch kelsangiz, o'zingizdan so'rang: bu haqiqatan ham sizning faoliyat sohangizmi?

Eslatma: Men sizga katta O belgisining haqiqiy ta'rifini bermadim, shunchaki fikr. Siz ushbu maqolani o'qishingiz mumkin Vikipediya haqiqiy (asimptotik) ta'rif uchun.

MergeSort

To'plamni saralash kerak bo'lganda nima qilasiz? Nima? Siz sort() funksiyasini chaqirasiz... Yaxshi javob... Lekin ma'lumotlar bazasi uchun bu sort() funksiyasi qanday ishlashini tushunishingiz kerak.

Bir nechta yaxshi tartiblash algoritmlari mavjud, shuning uchun men eng muhimlariga e'tibor qarataman: birlashtirish tartibi. Ma'lumotlarni saralash nima uchun hozir foydali ekanligini tushunmasligingiz mumkin, ammo so'rovni optimallashtirish qismidan keyin kerak. Bundan tashqari, birlashtirish tartibini tushunish bizga keyinchalik umumiy ma'lumotlar bazasini birlashtirish operatsiyasini tushunishga yordam beradi yushmoq Qo'shiling (birlashish uyushmasi).

Birlashtirish

Ko'pgina foydali algoritmlar singari, birlashtirish tartiblash ham hiylaga tayanadi: N/2 o'lchamdagi 2 ta tartiblangan massivni N elementli tartiblangan massivga birlashtirish faqat N ta operatsiyani talab qiladi. Ushbu operatsiyani birlashtirish deyiladi.

Keling, bu nimani anglatishini oddiy misol bilan ko'rib chiqaylik:

Bu rasm shuni ko'rsatadiki, yakuniy tartiblangan 8 elementli massivni yaratish uchun siz 2 ta 4 elementli massivni faqat bir marta takrorlashingiz kerak. Ikkala 4 elementli massivlar allaqachon tartiblanganligi sababli:

1) ikkala joriy elementni ikkita massivda solishtirasiz (boshida joriy = birinchi)
2) keyin 8 elementli massivga joylashtirish uchun eng kichigini oling
3) va eng kichik elementni olgan massivdagi keyingi elementga o'ting
va massivlardan birining oxirgi elementiga yetguncha 1,2,3 ni takrorlang.
Keyin boshqa massivning qolgan elementlarini 8 elementli massivga joylashtirish uchun olasiz.

Bu ishlaydi, chunki ikkala 4 elementli massiv ham tartiblangan va shuning uchun siz ushbu massivlarga "orqaga qaytishingiz" shart emas.

Endi biz hiyla-nayrangni tushunganimizdan so'ng, birlashish uchun mening psevdokodim:

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;

Birlashtirish tartiblash muammoni kichikroq masalalarga ajratadi va keyin asl muammoning natijasini olish uchun kichikroq masalalarning natijalarini topadi (eslatma: bu turdagi algoritmga bo'linish va zabt etish deyiladi). Agar siz ushbu algoritmni tushunmasangiz, tashvishlanmang; Men buni birinchi marta ko'rganimda tushunmadim. Agar u sizga yordam bera olsa, men ushbu algoritmni ikki fazali algoritm sifatida ko'raman:

Bo'linish bosqichi, bu erda massiv kichikroq massivlarga bo'linadi
Saralash bosqichi - kichik massivlar kattaroq massiv hosil qilish uchun birlashtiriladi (birlashma yordamida).

Bo'linish bosqichi

Bo'linish bosqichida massiv 3 bosqichda unitar massivlarga bo'linadi. Qadamlarning rasmiy soni log(N) dir (chunki N=8, log(N) = 3).

Buni qanday bilaman?

Men dahoman! Bir so'z bilan aytganda - matematika. G'oya shundan iboratki, har bir qadam asl massiv hajmini 2 ga bo'ladi. Qadamlar soni asl massivni ikkiga bo'lish soni. Bu logarifmning aniq ta'rifi (2-asos).

Saralash bosqichi

Saralash bosqichida siz unitar (bir elementli) massivlardan boshlaysiz. Har bir bosqichda siz bir nechta birlashma operatsiyalarini qo'llaysiz va umumiy xarajat N = 8 operatsiyani tashkil qiladi:

Birinchi bosqichda sizda har biri 4 ta operatsiyani talab qiladigan 2 ta birlashma mavjud
Ikkinchi bosqichda har biri 2 ta operatsiyani talab qiladigan 4 ta birlashma mavjud
Uchinchi bosqichda sizda 1 ta operatsiya turadigan 8 ta birlashma mavjud

Log (N) qadamlar mavjud bo'lgani uchun, umumiy xarajat N * log(N) operatsiyalari.

Birlashtirishning afzalliklari

Nima uchun bu algoritm juda kuchli?

Chunki:

Siz uni yangi massivlar yaratmaslik, balki kirish massivini to'g'ridan-to'g'ri o'zgartirish uchun xotira maydonini kamaytirish uchun o'zgartirishingiz mumkin.

Eslatma: bu turdagi algoritm deyiladi in-joy (qo'shimcha xotirasiz saralash).

Siz uni bir vaqtning o'zida disk maydoni va kichik hajmdagi xotiradan foydalanish uchun diskdagi kiritish-chiqarish uchun katta xarajatlarni talab qilmasdan o'zgartirishingiz mumkin. Maqsad xotiraga faqat hozirda qayta ishlanayotgan qismlarni yuklashdir. Bu faqat 100 megabayt xotira buferi bilan ko'p gigabaytli jadvalni saralash kerak bo'lganda muhimdir.

Eslatma: bu turdagi algoritm deyiladi tashqi tur.

Siz uni bir nechta jarayonlar/mavzular/serverlarda ishlash uchun o'zgartirishingiz mumkin.

Masalan, taqsimlangan birlashma tartiblash asosiy komponentlardan biridir Hadoop (bu katta ma'lumotlardagi tuzilma).

Ushbu algoritm qo'rg'oshinni oltinga aylantirishi mumkin (haqiqatan ham!).

Ushbu tartiblash algoritmi ko'pchilik (agar hammasi bo'lmasa) ma'lumotlar bazalarida qo'llaniladi, ammo bu yagona emas. Agar siz ko'proq bilmoqchi bo'lsangiz, buni o'qishingiz mumkin tadqiqot ishi, unda umumiy ma'lumotlar bazasini saralash algoritmlarining ijobiy va salbiy tomonlari muhokama qilinadi.

Massiv, daraxt va xesh jadvali

Endi biz vaqtning murakkabligi va saralash g'oyasini tushunganimizdan so'ng, men sizga 3 ta ma'lumotlar tuzilmasi haqida aytib berishim kerak. Bu juda muhim, chunki ular zamonaviy ma’lumotlar bazalarining asosi hisoblanadi. Men ham tushuncha bilan tanishtiraman ma'lumotlar bazasi indeksi.

Array

Ikki o'lchovli massiv eng oddiy ma'lumotlar strukturasidir. Jadvalni massiv sifatida tasavvur qilish mumkin. Masalan:

Ushbu 2 o'lchovli massiv qatorlar va ustunlardan iborat jadvaldir:

Har bir satr ob'ektni ifodalaydi
Ustunlar ob'ektni tavsiflovchi xususiyatlarni saqlaydi.
Har bir ustun ma'lum turdagi ma'lumotlarni saqlaydi (butun son, satr, sana...).

Bu ma'lumotlarni saqlash va vizualizatsiya qilish uchun qulay, ammo ma'lum bir qiymatni topish kerak bo'lganda, bu mos kelmaydi.

Misol uchun, agar siz Buyuk Britaniyada ishlaydigan barcha yigitlarni topmoqchi bo'lsangiz, bu qator Buyuk Britaniyaga tegishli yoki yo'qligini aniqlash uchun har bir qatorni ko'rib chiqishingiz kerak bo'ladi. Bu sizga N tranzaksiyaga tushadiqayerda N - qatorlar soni, bu yomon emas, lekin tezroq yo'l bo'lishi mumkinmi? Endi daraxtlar bilan tanishish vaqti keldi.

Eslatma: Ko'pgina zamonaviy ma'lumotlar bazalari jadvallarni samarali saqlash uchun kengaytirilgan massivlarni taqdim etadi: yig'ilgan jadvallar va indeks bilan tashkil etilgan jadvallar. Ammo bu ustunlar guruhida ma'lum bir shartni tezda topish muammosini o'zgartirmaydi.

Ma'lumotlar bazasi daraxti va indeksi

Ikkilik qidiruv daraxti maxsus xususiyatga ega ikkilik daraxt bo'lib, har bir tugundagi kalit bo'lishi kerak:

chap pastki daraxtda saqlangan barcha kalitlardan kattaroq
o'ng pastki daraxtda saqlangan barcha kalitlardan kamroq

Keling, bu vizual tarzda nimani anglatishini ko'rib chiqaylik

Fikr

Bu daraxtda N = 15 element mavjud. Aytaylik, men 208 ni qidiryapman:

Men kaliti 136 bo'lgan ildizdan boshlayman. 136<208 dan boshlab, 136-tugunning o'ng pastki daraxtiga qarayman.
398>208 shuning uchun men 398-tugunning chap pastki daraxtiga qarayman
250>208 shuning uchun men 250-tugunning chap pastki daraxtiga qarayman
200<208, shuning uchun men 200-tugunning o'ng pastki daraxtiga qarayman. Lekin 200-ning o'ng pastki daraxti yo'q, qiymat mavjud emas (chunki u mavjud bo'lsa, u o'ng pastki daraxtda 200 bo'ladi).

Endi men 40 ni qidiryapman deylik

Men kaliti 136 bo'lgan ildizdan boshlayman. 136 > 40 dan boshlab, 136 tugunning chap pastki daraxtiga qarayman.
80 > 40, shuning uchun men 80-tugunning chap pastki daraxtiga qarayman
40= 40, tugun mavjud. Men tugun ichidagi satr identifikatorini olaman (rasmda emas) va berilgan qator identifikatorini jadvalga qarayman.
Qator identifikatorini bilish menga ma'lumotlarning jadvalning qayerda ekanligini aniq bilish imkonini beradi, shuning uchun uni bir zumda olishim mumkin.

Oxir-oqibat, ikkala qidiruv menga daraxt ichidagi darajalar soniga tushadi. Birlashtirish tartibi haqidagi qismni diqqat bilan o'qib chiqsangiz, log (N) darajalari borligini ko'rishingiz kerak. Ma'lum bo'lishicha, Qidiruv xarajatlari jurnali (N), yomon emas!

Keling, muammomizga qaytaylik

Ammo bu juda mavhum, shuning uchun muammomizga qaytaylik. Oddiy butun son o'rniga oldingi jadvalda kimningdir mamlakatini ifodalovchi qatorni tasavvur qiling. Aytaylik, sizda jadvalning "mamlakat" maydonini (3-ustun) o'z ichiga olgan daraxtingiz bor:

Agar siz Buyuk Britaniyada kim ishlayotganini bilmoqchi bo'lsangiz
Buyuk Britaniyani ifodalovchi tugunni olish uchun daraxtga qaraysiz
"UKnode" ichida siz Buyuk Britaniyadagi ishchi yozuvlari joylashgan joyni topasiz.

Agar siz toʻgʻridan-toʻgʻri massivdan foydalansangiz, bu qidiruv N ta amal oʻrniga log(N) operatsiyalarini talab qiladi. Siz hozirgina taqdim etgan narsa edi ma'lumotlar bazasi indeksi.

Siz kalitlarni (ya'ni maydon guruhlarini) solishtirish funksiyasiga ega bo'lsangiz, istalgan maydonlar guruhi uchun indeks daraxtini yaratishingiz mumkin (satr, raqam, 2 qator, raqam va qator, sana...) kalitlar orasida tartib (bu ma'lumotlar bazasidagi har qanday asosiy turlarga tegishli).

B + TreeIndex

Bu daraxt ma'lum bir qiymatni olish uchun yaxshi ishlayotgan bo'lsa-da, kerak bo'lganda KATTA muammo mavjud ikkita qiymat o'rtasida bir nechta elementlarni oling. Bu O(N) ga tushadi, chunki siz daraxtdagi har bir tugunni ko'rib chiqishingiz va bu ikki qiymat o'rtasida ekanligini tekshirishingiz kerak bo'ladi (masalan, daraxtning tartibli o'tishi bilan). Bundan tashqari, bu operatsiya diskni kiritish-chiqarish uchun mos emas, chunki siz butun daraxtni o'qishingiz kerak. Biz samarali amalga oshirish yo'lini topishimiz kerak diapazon so'rovi. Ushbu muammoni hal qilish uchun zamonaviy ma'lumotlar bazalari B + Tree deb nomlangan oldingi daraxtning o'zgartirilgan versiyasidan foydalanadi. B + daraxt daraxtida:

faqat eng pastki tugunlar (barglar) ma'lumotlarni saqlash (tegishli jadvaldagi qatorlarning joylashuvi)
qolgan tugunlar shu yerda marshrutlash uchun to'g'ri tugunga qidiruv paytida.

Ko'rib turganingizdek, bu erda tugunlar ko'proq (ikki marta). Haqiqatan ham, sizda to'g'ri tugunni topishga yordam beradigan qo'shimcha tugunlar, "qaror tugunlari" mavjud (u bog'langan jadvaldagi satrlarning joylashishini saqlaydi). Ammo qidiruvning murakkabligi hali ham O (log (N)) (faqat bitta daraja mavjud). Katta farq shundaki pastki darajadagi tugunlar ularning vorislari bilan bog'langan.

Ushbu B + Tree bilan, agar siz 40 dan 100 gacha qiymatlarni qidirsangiz:

Oldingi daraxtda bo'lgani kabi 40 ni (yoki 40 bo'lmasa, 40 dan keyingi eng yaqin qiymatni) qidirishingiz kerak.
Keyin 40 ga etguningizcha to'g'ridan-to'g'ri merosxo'r havolalari yordamida 100 merosxo'rni to'plang.

Aytaylik, siz M voris topasiz va daraxtda N tugun bor. Muayyan tugunni topish oldingi daraxtga o'xshab log(N) turadi. Ammo siz ushbu tugunni olganingizdan so'ng, M operatsiyalarida M vorislarini ularning vorislariga havolalar bilan olasiz. Bu qidiruv faqat M+log(N) turadi oldingi daraxtdagi N amal bilan solishtirganda operatsiyalar. Bundan tashqari, siz to'liq daraxtni o'qishingiz shart emas (faqat M+log (N) tugunlari), bu esa kamroq diskdan foydalanishni anglatadi. Agar M kichik (masalan, 200 qator) va N katta (1 000 000 qator) bo'lsa, KATTA farq bo'ladi.

Ammo bu erda yangi muammolar bor (yana!). Agar siz ma'lumotlar bazasiga (va shuning uchun tegishli B + Tree indeksiga) qator qo'shsangiz yoki o'chirsangiz:

B+Tree ichidagi tugunlar orasidagi tartibni saqlashingiz kerak, aks holda siz tartiblanmagan daraxt ichida tugunlarni topa olmaysiz.
B+Tree-da minimal mumkin bo'lgan darajalar sonini saqlashingiz kerak, aks holda O(log(N)) vaqt murakkabligi O(N) ga aylanadi.

Boshqacha qilib aytganda, B + Tree o'z-o'zidan tartibli va muvozanatli bo'lishi kerak. Yaxshiyamki, bu aqlli o'chirish va kiritish operatsiyalari bilan mumkin. Lekin bu qimmatga tushadi: B+ daraxtiga kiritish va oʻchirish O(log(N)) ga tushadi. Shuning uchun ba'zilaringiz buni eshitgansiz juda ko'p indekslardan foydalanish yaxshi fikr emas. Haqiqatan ham, jadvalga qatorni tez qo'shish/yangilash/o'chirishni sekinlashtirasizchunki ma'lumotlar bazasi har bir indeks uchun qimmat O(log(N)) operatsiyasidan foydalangan holda jadval indekslarini yangilashi kerak. Bundan tashqari, indekslarni qo'shish ko'proq ish yukini anglatadi tranzaksiya menejeri (maqolaning oxirida tavsiflanadi).

Batafsil ma'lumot uchun Vikipediyadagi maqolani ko'rishingiz mumkin B+Daraxt. Agar ma'lumotlar bazasida B + Tree ni qo'llash misolini olishni istasangiz, ko'rib chiqing Ushbu maqola и Ushbu maqola yetakchi MySQL dasturchisidan. Ikkalasi ham InnoDB (MySQL dvigateli) indekslarni qanday boshqarishiga e'tibor qaratadi.

Eslatma: O'quvchi menga past darajadagi optimallashtirishlar tufayli B + daraxti to'liq muvozanatli bo'lishi kerakligini aytdi.

Hashtable

Bizning oxirgi muhim ma'lumotlar tuzilmasi - bu xesh-jadval. Bu qiymatlarni tezda qidirmoqchi bo'lganingizda juda foydali. Bundan tashqari, xesh-jadvalni tushunish, keyinchalik hash birlashma deb ataladigan umumiy ma'lumotlar bazasini birlashtirish operatsiyasini tushunishga yordam beradi ( hash qo'shilish). Ushbu ma'lumotlar strukturasi ma'lumotlar bazasi tomonidan ba'zi ichki narsalarni saqlash uchun ham ishlatiladi (masalan, stolni qulflash yoki bufer hovuzi, bu ikkala tushunchani keyinroq ko'rib chiqamiz).

Xesh-jadval - bu kalitga asoslangan elementni tezda topadigan ma'lumotlar strukturasi. Xesh jadvalini yaratish uchun quyidagilarni aniqlashingiz kerak:

maslahat olish Sizning elementlaringiz uchun
hash funktsiyasi kalitlar uchun. Hisoblangan kalit xeshlari elementlarning joylashishini beradi (deb ataladi segmentlar ).
tugmachalarni taqqoslash funktsiyasi. To'g'ri segmentni topganingizdan so'ng, ushbu taqqoslash yordamida segment ichidan izlayotgan elementni topishingiz kerak.

Oddiy misol

Keling, aniq bir misol keltiraylik:

Ushbu xesh-jadval 10 ta segmentga ega. Men dangasa bo'lganim uchun faqat 5 ta segmentni tasvirladim, lekin siz aqlli ekanligingizni bilaman, shuning uchun qolgan 5 tasini o'zingiz tasvirlashga ruxsat beraman. Men kalitning 10-moduli hash funktsiyasidan foydalandim. Boshqacha qilib aytganda, men uning segmentini topish uchun element kalitining faqat oxirgi raqamini saqlayman:

agar oxirgi raqam 0 bo'lsa, element 0 segmentiga tushadi,
agar oxirgi raqam 1 bo'lsa, element 1 segmentiga tushadi,
agar oxirgi raqam 2 bo'lsa, element 2 maydoniga tushadi,
...

Men ishlatgan taqqoslash funktsiyasi shunchaki ikkita butun son o'rtasidagi tenglikdir.

Aytaylik, siz 78 elementni olishni xohlaysiz:

Xesh jadvali 78 uchun xesh kodini hisoblab chiqadi, bu 8 ga teng.
Xesh jadvali 8-segmentga qaraydi va u topadigan birinchi element 78 ni tashkil qiladi.
U sizga 78-bandni qaytaradi
Qidiruv faqat 2 ta operatsiyani talab qiladi (biri xesh qiymatini hisoblash uchun, ikkinchisi esa segment ichidagi elementni qidirish uchun).

Aytaylik, siz 59-elementni olishni xohlaysiz:

Xesh jadvali 59 uchun xesh kodini hisoblab chiqadi, bu 9 ga teng.
Xesh-jadval 9-segmentda qidiradi, birinchi topilgan element 99. 99!=59 boʻlgani uchun 99-element haqiqiy emas.
Xuddi shu mantiqdan foydalanib, ikkinchi element (9), uchinchi (79), ..., oxirgi (29) olinadi.
Element topilmadi.
Qidiruv 7 ta operatsiyani talab qildi.

Yaxshi hash funktsiyasi

Ko'rib turganingizdek, siz izlayotgan qiymatga qarab, narx bir xil emas!

Agar men kalitning 1 000 000 xesh funktsiyasi modulini o'zgartirsam (ya'ni oxirgi 6 ta raqamni olgan holda), ikkinchi qidiruv faqat 1 operatsiyani talab qiladi, chunki 000059 segmentida hech qanday element yo'q. Haqiqiy qiyinchilik juda oz sonli elementlarni o'z ichiga olgan chelaklarni yaratadigan yaxshi xesh funktsiyasini topishdir.

Mening misolimda yaxshi hash funktsiyasini topish oson. Ammo bu oddiy misol, kalit bo'lganda yaxshi xesh funktsiyasini topish qiyinroq:

string (masalan - familiya)
2 qator (masalan - familiya va ism)
2 qator va sana (masalan - familiya, ism va tug'ilgan sana)
...

Yaxshi xesh funksiyasi bilan xesh jadvallarini qidirish O(1) turadi.

Massiv va xesh jadvali

Nima uchun massivdan foydalanmaslik kerak?

Hmm, yaxshi savol.

Xesh jadvali bo'lishi mumkin xotiraga qisman yuklangan, qolgan segmentlar esa diskda qolishi mumkin.
Massiv bilan siz xotirada qo'shni bo'sh joydan foydalanishingiz kerak. Agar siz katta stol yuklayotgan bo'lsangiz yetarlicha uzluksiz joyni topish juda qiyin.
Xesh-jadval uchun siz kerakli kalitni tanlashingiz mumkin (masalan, mamlakat va shaxsning familiyasi).

Qo'shimcha ma'lumot olish uchun siz maqolani o'qishingiz mumkin JavaHashMap, bu hash jadvalining samarali amalga oshirilishi; Ushbu maqolada keltirilgan tushunchalarni tushunish uchun Java tilini tushunishingiz shart emas.

Manba: www.habr.com

Relyatsion ma'lumotlar bazalari qanday ishlaydi (1-qism)