Salam, Habr! Sizi məqalənin tərcüməsi ilə tanış edirəm
"Relational databazası necə işləyir".

Relational databazalara gəldikdə, nəyinsə çatmadığını düşünmədən danışa bilmirəm. Onlar hər yerdə istifadə olunur. Kiçik və faydalı SQLite-dan tutmuş, güclü Teradata-dək bir çox fərqli databaza var. Lakin, bu databazanın necə işlədiyini izah edən yalnız bir neçə məqalə mövcuddur. Özünüz "howdoesarelationaldatabasework" axtarışını edin («relational databazalar necə işləyir») və nə qədər az nəticə olduğunu görün. Daha çox, bu məqalələr qısadır. Əgər müasir texnologiyaları (BigData, NoSQL və ya JavaScript) axtarırsınızsa, necə işlədiklərini izah edən daha çox dərin məqalə tapacaqsınız.

Relational databazaları universitet dərsləri, tədqiqat işləri və kitablar xaricində izah etmək üçün çox köhnə və darıxdırıcıdırmı?

Tərtibçi olaraq, başa düşmədiyim şeyləri istifadə etməyi sevmirəm. Və əgər databazalar 40 ildən çoxdur istifadə olunursa, bunun bir səbəbi olmalıdır. Bu illər ərzində, hər gün istifadə etdiyim bu qəribə qara qutuları həqiqətən başa düşmək üçün yüzlərlə saat sərf etmişəm. Relational databazalar çox maraqlıdır, çünki onlar faydalandırıcı və bir çox dəfə istifadə oluna bilən anlayışlara əsaslanır. Əgər databazanı başa düşmək ilə maraqlanırsınızsa, lakin bu geniş mövzuda dərinləşmək üçün heç vaxt vaxtınız və ya arzuladığınız olmuyorsa, bu məqaləni bəyəndiyinizi düşünürəm.

Bu məqalənin adı açıq olsa da, bu məqalənin məqsədi databazanı necə istifadə etməyi başa düşmək deyil. Buna görə də, artıq sadə bir birləşmə sorğusu yazmağı və əsas sorğuları bilməlisiniz CRUD; əks halda bu məqaləni başa düşməyə bilərsiniz. Biləcəyiniz tək şey budur, qalanını izah edəcəyəm.

Müəyyən bir kompyuter elminin əsasları ilə başlayacağam, məsələn, algoritmların zaman çətinliyi (BigO). Bəzi insanlar bu anlayışdan nifrət edir, amma onun olmadan databazanın incəliklərini başa düşmək mümkün deyil. Bu mövzu geniş olduğu üçün, önəmli olduğunu düşündüyüm şeylərə diqqət yetirəcəyəm databaza necə işləyir: sorğu SQL . Sadəcədatabaza anlayışlarını təqdim edəcəyəm , belə ki, bu məqalənin sonunda nə baş verdiyini anlamaq imkanınız olsun.Bu uzun və texniki bir məqalə olduğu üçün, bir çox algoritm və məlumat strukturlarını əhatə edir, onu oxumaq üçün tələsməyin. Bəzi anlayışlar başa düşmək çətin ola bilər; onları keçə bilərsiniz və yenə də ümumi bir şəkil əldə edərsiniz.

Daha məlumatlı olanlarınız üçün, bu məqalə 3 hissəyə bölünmüşdür:

Databazanın aşağı səviyyəli və yüksək səviyyəli komponentləri haqqında ümumi məlumat

Sorğuların optimallaşdırma prosesi haqqında ümumi məlumat
Transaksiyaların və tampon hovuzunun idarə edilməsi haqqında ümumi məlumat
Əsaslara qayıtmışıq

Возвращаясь к основам

Çox illər əvvəl (uzaq, uzaq bir qalaktikada...), proqramçılar kodladıqları əməliyyatların sayını dəqiq bilmək məcburiyyətində idilər. Onlar alqoritmlərini və məlumat strukturlarını əzbər bilirdilər, çünki yavaş kompüterlərinin CPU və yaddaşından istifadə etməyə icazə verə bilmirdilər.

Bu hissədə bəzi konsepsiyaları xatırlatmaq istəyirəm, çünki onlar verilənlər bazasını başa düşmək üçün vacibdir. Mən həmçinin anlayışını təqdim edəcəyəm verilənlər bazasının indeksi.

O(1) vs O(n2)

Hazırda bir çox proqramçı alqoritmlərin vaxt mürəkkəbliyi ilə maraqlanmır... və haqlıdırlar!

Amma siz böyük miqdarda məlumatla (minlərlə deyil) işlədiyinizdə və ya milisaniyələr uğrunda mübarizə apardığınızda, bu konsepsiyanı anlamaq kritik əhəmiyyət kəsb edir. Və bildiyiniz kimi, verilənlər bazaları hər iki vəziyyətlə məşğul olmalıdır! İcazə verin, əsas anlayışı başa düşmək üçün lazım olandan daha çox vaxt sərf etməyin. Bu, gələcəkdə xərclərə əsaslanan optimizasiya anlayışını anlamağa kömək edəcəkxərc əsaslı optimizasiya).

Konsepsiya

Alqoritmin vaxt mürəkkəbliyi belli bir məlumat həcmi üçün alqoritmin işləmə müddətini görmək üçün istifadə olunur.. Bu mürəkkəbliyi təsvir etmək üçün böyük O matematik göstəricilərindən istifadə olunur. Bu notasiya, alqoritmin verilən giriş məlumatları üçün nə qədər əməliyyat tələb etdiyini təsvir edən funksiya ilə birlikdə istifadə olunur.

Məsələn, mən "bu alqoritmin mürəkkəbliyi O (some_function())" dedikdə, müəyyən bir məlumat həcmini emal etmək üçün alqoritmin some_function(a_certain_amount_of_data) əməliyyatı tələb etdiyini bildirir.

Bu halda vacib olan məlumatların sayı deyil,işləmə sayının məlumat həcmi artdıqca necə artdığıdır. . Vaxt mürəkkəbliyi dəqiq əməliyyat sayını vermir, amma işləmə vaxtını qiymətləndirmək üçün yaxşı bir yoldur.Bu qrafikdə siz müxtəlif vaxt mürəkkəblik növləri üçün əməliyyatların sayının giriş məlumatlarının həcminə bağlılığını görə bilərsiniz. Onları göstərmək üçün loqaritmik bir miqyas istifadə etdim. Başqa sözlə, verilənlərin sayı 1-dən 1 milyardadək sürətlə artır. Biz görə bilərik ki:

O(1) və ya sabit mürəkkəblik sabit qalır (əks halda buna sabit mürəkkəblik deyilər).

1 milyard verilənlərlə belə aşağı qalır.
N(log(n)) Ən pis mürəkkəblik —.
O(n2), burada əməliyyatların sayı sürətlə artır. İki digər mürəkkəblik də sürətlə artır..
Kiçik miqdarda verilən olduqda, O(1) və O(n2) arasında fərq əhəmiyyətsizdir. Məsələn, gəlin düşünək ki, sizdə 2000 elementi emal etməli olan bir alqoritm var.

Nümunələr

O (1) alqoritmi sizə 1 əməliyyata başa gələcək.

O (log (n)) alqoritmi sizə 7 əməliyyata başa gələcək.
O (n) alqoritmi sizə 2 000 əməliyyata başa gələcək.
O (n * log (n)) alqoritmi sizə 14 000 əməliyyata başa gələcək.
O (n2) alqoritmi sizə 4 000 000 əməliyyata başa gələcək.
Алгоритм O (n2) обойдется вам в 4 000 000 операций

O(1) və O(n2) arasındakı fərq çox böyük görünür (4 milyon əməliyyat), amma maksimum 2 ms itirirsiniz, bu da gözlərinizi qıxmaq üçün kifayətdir. Həqiqətən, müasir prosessorlar bir saniyədə yüz milyonlarla əməliyyatı həyata keçirə bilər. Buna görə də, performans və optimizasiya bir çox İT layihələrində problem deyil.

Daha əvvəl qeyd etdiyim kimi, bu konsepsiyanı böyük məlumatlarla işlədiyiniz zaman bilmək hələ də vacibdir. Əgər bu dəfə alqoritm 1 000 000 element emal etməlidirsə (bu, verilənlər bazası üçün o qədər də çox deyil):

O (log (n)) alqoritmi sizə 7 əməliyyata başa gələcək.
O(log(n)) alqoritmi 14 əməliyyata başa gələcək
O(n) alqoritmi 1 000 000 əməliyyata başa gələcək
O(n * log(n)) alqoritmi 14 000 000 əməliyyata başa gələcək
O(n2) alqoritmi 1 000 000 000 000 əməliyyata başa gələcək

Mən hesablamalar etməmişəm, amma deyərdim ki, O(n2) alqoritmi ilə qəhvə içmək üçün vaxtınız var (hətta iki dəfə!). Əgər verilənlərin həcminə 0 əlavə etsəniz, bir az yatmağa vaxtınız olacaq.

Dərinliyə enək

Qeyd üçün:

Yaxşı bir hash cədvəlində axtarma O(1) başa gəlir.
Yaxşı balanslaşdırılmış ağacda axtarma O(log(n)) nəticə verir.
Massivdə axtarma O(n) başa gəlir.
Ən yaxşı sıralama alqoritmləri O(n * log(n)) çətinliyə malikdir.
Pis sıralama alqoritmi O(n2) çətinliyə malikdir.

Qeyd: Növbəti hissələrdə bu alqoritmləri və məlumat strukturlarını göreceyik.

Alqoritmin bir neçə növ zaman çətinliyi vardır:

ortalama hal senarisi
ən yaxşı hal senarisi
və ən pis senari

Zaman çətinliyi çox vaxt ən pis senariyə uyğun gəlir.

Yalnız alqoritmin zaman çətinliyindən danışdım, amma çətinliklər həm də:

alqoritmin yaddaş istehlakı
alqoritmin disk giriş/çıxış istehlakı

Təbii ki, n2-dən daha pis çətinliklər var, məsələn:

n4: bu dəhşətlidir! Bəzi qeyd etdiyimiz alqoritmlərin belə çətinliyi var.
3n: bu daha da pisdir! Bu məqalənin ortalarında görücəyimiz alqoritmlərdən biri belə çətinliyə malikdir (və bu, bir çox verilənlər bazalarında həqiqətən istifadə olunur).
n faktoriyal: kiçik məlumatlarla belə nəticələri əldə edə bilməzsiniz.
nn: əgər belə bir çətinliklə qarşılaşsanız, özünüzdən soruşmalısınız ki, bu, sizin sahənizdirmi …

Qeyd: Mən sizə "böyük O" işarələməsinin real tərifini vermədim, sadəcə bir fikir verdim. Bu yaxınlarda oxuduğunuz məqalədə Vikipediya real (asimptotik) tərifini oxuya bilərsiniz.

MergeSort (Birlikdə Sıralama)

Kolleksiyanı sıralamaq lazım gəldikdə nə edirsiniz? Nə? sort() funksiyasını çağırırsınız... Yaxşı, gözəl cavab... Amma verilənlər bazası üçün bu sort() funksiyasının necə işlədiyini anlamaq vacibdir.

Bir neçə yaxşı sıralama alqoritmi vardır, ona görə də mən ən önəmlisi ilə dayanıram: birlikdə sıralamaBəlkə indi verilənlərin sıralanmasının niyə faydalı olduğunu başa düşmürsünüz, amma bu anlayışa sorğuların optimallaşdırılmasına həsr olunmuş hissədən sonra sahib olacaqsınız. Üstəlik, birləşmiş sıralamanın başa düşülməsi, daha sonra verilənlər bazalarındakı ümumi join əməliyyatını anlamağa kömək edəcək. merge join (birləşmək).

Merge (birləşmək)

Faydalı algoritmlardan biri olan sıralama birləşməsi bir fəndə əsaslanır: N / 2 ölçülü 2 sıralanmış massivlərin N-elementli sıralanmış massivə birləşdirilməsi yalnız N əməliyyatı tələb edir. Bu əməliyyata birləşmə deyilir.

Gəlin bunun sadə bir misalla nə demək olduğunu nəzərdən keçirək:

Bu şəkildə göstərilir ki, 8 elementdən ibarət son sıralanmış massivdə hər iki 4 elementli massivdən bir dəfə iterasiya etməklə yalnız bir dəfə aktivləşdirmək lazımdır. Hər iki 4 elementli massiv artıq sıralandığına görə:

1) siz hər iki massivdə cari elementləri (ilk vəziyyət) müqayisə edirsiniz
2) sonra ən kiçiyini seçərək 8 elementli massivə daxil edirsiniz
3) və ən kiçik elementi götürdüyünüz massivdə növbəti elementə keçirsiniz
və birinci, ikinci, üçüncü əməliyyatları təkrarlayırsınız, ta ki biri massivlərin sonuncu elementinə çatanadək.
Daha sonra digər massivdən qalan elementləri götürərək 8 elementli massivə daxil edirsiniz.

Bu, hər iki 4 elementli massiv sıralandığı üçün işləyir, beləliklə, bu massivlərdə "geri dönmək" lazım deyil.

İndi bu fəndi başa düşdükdən sonra, merge üçün mənim psixologiyam:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //təkrarlanan çağırışlar
   [sol_massiv sağ_massiv] := split_into_2_equally_sized_arrays(a);
   array yeni_sol_massiv := mergeSort(sol_massiv);
   array yeni_sağ_massiv := mergeSort(sağ_massiv);

   //iki kiçik sıralanmış massivlərin böyük olanına birləşdirilməsi
   array nəticə := merge(yeni_sol_massiv,yeni_sağ_massiv);
   return nəticə;

Sıralama birləşməsi problemi daha kiçik problemlərə parçalayır və daha kiçik problemlərin nəticələrini taparaq orijinal problemin nəticəsini əldə edir (Qeyd: bu cür algoritmlara "ayır və idarə et" deyilir). Əgər bu algoritmi başa düşmürsünüzsə, narahat olmayın; mən bunu ilk dəfə gördüyüm zaman başa düşmədim. Bu sizə kömək edə bilərsə, bu algoritmi iki mərhələli algoritm kimi görürəm:

Bölmə mərhələsi, burada massiv daha kiçik massivlərə ayrılır
Sıralama mərhələsi, burada kiçik massivlərin birləşmə (birləşmə istifadə edərək) nəticəsində daha böyük bir massiv meydana gəlir.

Division phase (bölmə mərhələsi)

Bölmə mərhələsində massiv 3 addımda birləşmiş massivlərə çevrilir. Rəsmi addım sayı — log(N) (çünki N=8, log(N) = 3).

Bunu haradan bilirəm?

Mən dahi! Qısacası — riyaziyyat. İdeya ondan ibarətdir ki, hər addım orijinal massiv ölçüsünü 2-yə bölür. Addım sayı, orijinal massivini iki hissəyə bölmək əvəzsiz edə biləcəyiniz addımların sayı ilə əlaqədardır. Bu, logaritm (2 əsaslı) dəqiq tərifidir.

Sorting phase (sıralama mərhələsi)

Sıralama mərhələsində siz unitar (bir-elementli) massivlərdən başlayırsınız. Hər mərhələdə bir neçə birləşmə əməliyyatları tətbiq edirsiniz və ümumi xərc N = 8 əməliyyatdır:

Birinci mərhələdə 2 əməliyyat dəyəri olan 4 birləşmə var.
İkinci mərhələdə 4 əməliyyat dəyəri olan 2 birləşmə var.
Üçüncü mərhələdə 8 əməliyyat dəyəri olan 1 birləşmə var.

Mövcud log (N) mərhələsi olduğu üçün, ümumi xərc N * log(N) əməliyyatıdır..

Merge sortun üstünlükləri

Niyə bu alqoritm bu qədər güclüdür?

realdır

Onu dəyişdirə bilərsiniz ki, yaddaş həcmini azaltsın ki, yeni massivlər yaratmayasınız, əksinə daxil olan massivə birbaşa müdaxilə edəsiniz.

Qeyd: Bu cür alqoritmlərə in—yer (əlavə yaddaş olmadan sıralama) deyilir.

Onu disklə birlikdə kiçik yaddaş həcmi ilə istifadəyə dəyişdirə bilərsiniz, disk giriş/çıxarışı üçün əhəmiyyətli xərclər olmadan. İdeya, aşkar edilən hissələri yalnız həmin anda işlətmək üçün yaddaşa yükləməkdir. Bu, bir neçə gigabayt ölçüsündə bir cədvəli yalnız 100 megabaytlıq bir tampon yaddaşla sıralamağınız lazım olduqda, vacibdir.

Qeyd: Bu cür alqoritmlərə xarici sıralama.

Onu birdən çox prosesi / ipini / serverdə işə salmaq üçün dəyişdirə bilərsiniz.

Məsələn, paylanmış merge sort böyük verilənlərdə olan əsas komponentlərdən biridir. Hadoop (bunun böyük məlumatlar strukturu olduğunu göstərir).

Bu alqoritm tam dəyişkəni qızılda çevirə bilər (doğrudur!).

Bu sıralama alqoritmi əksər (həm də bütün) verilənlər bazalarında istifadə olunur, amma yeganə deyil. Daha çox məlumat əldə etmək istəyirsinizsə, bu araşdırma işini, verilənlər bazasında ümumi sıralama alqoritmlərinin plüsləri və mənfi cəhətləri haqqında müzakirə edir.

Massiv, Ağac və Həş Tablosu

İndi zaman mürəkkəbliyi və sıralama fikrini anladığımızda, sizə 3 məlumat strukturu haqqında məlumat verməliyəm. Bu, əhəmiyyətlidir, çünki onlar müasir verilənlər bazalarının əsasını təşkil edir.. Mən həmçinin verilənlər bazasının indeksi.

Massiv

İkiölçülü massiv ən sadə məlumat strukturudur. Cədvəl massiv olaraq qəbul edilə bilər. Məsələn:

Bu ikiölçülü massiv satırlar və sütunlarla bir cədvəl təqdim edir:

Hər sətir bir varlığı təmsil edir.
Sütunlar varlığın xüsusiyyətlərini saxlayır.
Hər sütun müəyyən tipdə (tam ədəd, mətn, tarix …) məlumat saxlayır.

Belə məlumatları saxlamaq və vizuallaşdırmaq çox rahatdır, lakin müəyyən bir dəyəri tapmaq lazım olduqda, bu uyğun deyil.

Məsələn, əgər siz Böyük Britaniyada çalışan bütün oğlanları tapmaq istəyirsinizsə, bu sətirin Böyük Britaniyaya aid olduğunu müəyyən etmək üçün hər bir sətri nəzərdən keçirməlisiniz. Bu sizə N əməliyyatına başa gələcək., burada N — sətirlər sayı yaxşıdır, amma daha sürətli bir yol ola bilərmi? İndi ağaclarla tanış olmağın vaxtıdır.

Qeyd: müasir verilənlər bazalarının əksəriyyəti effektli cədvəl saxlamaq üçün genişləndirilmiş massivlər təqdim edir: heap-təşkil olunmuş cədvəllər və index-təşkil olunmuş cədvəllər. Lakin bu, sütun qrupunda müəyyən bir şərti sürətlə tapmaq problemini dəyişdirmir.

Verilənlər bazası üçün ağac və indeks

İkili axtarış ağacı — xüsusi bir xassəyə sahib olan ikili ağacdır; hər düyündəki açar:

sol alt ağacda saxlanılan bütün açarlardan böyükdür
sağ alt ağacda saxlanılan bütün açarlardan kiçikdir

Gəlin bunun vizual olaraq nə demək olduğunu baxaq

Ideya

Bu ağacda N = 15 element var. Tutaq ki, mən 208-i axtarıram:

Mən 136 açarlı kökdən başlayıram. Çünki 136<208, mən 136-nın sağ alt ağacına baxıram.
398>208, buna görə 398-nin sol alt ağacına baxıram
250>208, buna görə 250-nin sol alt ağacına baxıram
200<208, buna görə 200-nin sağ alt ağacına baxıram. Amma 200-nün sağ alt ağacı yoxdur, dəyər mövcud deyil (çünki əgər o varsa, o, 200-ün sağ alt ağacında olacaqdır).

İndi, tutalım ki, mən 40-ı axtarıram

Mən 136 açarlı kökdən başlayıram. Çünki 136 > 40, mən 136-nın sol alt ağacına baxıram.
80 > 40, buna görə 80-nin sol alt ağacına baxıram
40= 40, düyün mövcuddur. Düyün içindəki sətir identifikatorunu çıxarıram (bu, şəkildə yoxdur) və müvafiq sətir identifikatoru üçün cədvəldə baxıram.
Sətir identifikatorunu bilmək, məlumatların cədvəldə harada yerləşdiyini bilməyə imkan tanıyır və buna görə onları dərhal əldə edə bilirəm.

Nəticədə, iki axtarış mənim üçün ağacın içindəki səviyyə sayını ödəyəcək. Əgər birləşmə sıralaması barədəki hissəni diqqətlə oxuyursanız, burada log(N) səviyyəsi görməlisiniz. Beləliklə, axtarışın qiyməti log(N), yaxşıdır!

Problemi yenidən nəzərdən keçirək

Amma bu, çox abstrakt olduğu üçün, probleminə qayıdaq. Sadə bir tam ədəd yerinə, əvvəlki cədvəldə kiminsə ölkəsini təmsil edən bir sətiri təsəvvür edin. Gəlin, sizdə "ölkə" (sütun 3) sahəsini ehtiva edən bir ağac var olduğunu düşünək:

Böyük Britaniyada kimlərin işlədiyini bilmək istəyirsinizsə
ağaca baxaraq, Böyük Britaniyanı təmsil edən düyünü tapırsınız
"UKnode" içərisində, Böyük Britaniyada çalışanların qeydlərinin yerləşməsini tapacaqsınız.

Bu axtarış, birbaşa massiv istifadə etsəniz, N əməliyyat əvəzinə log(N) əməliyyatına başa gələcək. Təhqir etdiyiniz şey — bu bir verilənlər bazası indeksidir.

Hər hansı bir sahələr qrupuna (sətir, ədəd, 2 sətir, ədəd və sətir, tarix ...) indeks ağacı qura bilərsiniz, əgər açarları (yəni, sahələr qrupunu) müqayisə etmək üçün bir funksiya varsa, beləliklə açarlar arasında nizam qura bilərsiniz (məlumat bazasında əsas növlər üçün mövcuddur).

B+TreeIndex

Bu ağac müəyyən bir dəyəri əldə etmək üçün yaxşı işləsə də, iki dəyər arasında bir neçə elementi əldə etməyə ehtiyac olduqda BÖYÜK bir problem var. Bu O(N) başa gələcək, çünki ağacdakı hər bir düyünü yoxlamalı və onun bu iki dəyər arasında olub olmadığını müəyyən etməlisiniz (məsələn, ağacın sıralanmış gedişi ilə). Yuxarıda qeyd olunan əməliyyat disk I/O üçün rahat deyil, çünki tam ağacı oxumalısınız. Müxtəlif bir diapazon sorğusunu effektiv icra etmənin bir yolunu tapmalıyıq.sorğu . Bu problemin həlli üçün müasir məlumat bazaları əvvəlki ağacın dəyişdirilmiş versiyası olan B+Tree-dən istifadə edirlər. B+Tree-də:yalnız alt düyünlər (yarpaqlar)

məlumat saxlayır (əlaqəli cədvəldəki satırların yerləri) digər düyünlər burada
doğru düyünə yönləndirmək axtarış zamanı Gördüyünüz kimi, burada daha çox düyün var (iki dəfə). Həqiqətən, sizə doğru düyünü tapmağa kömək edəcək əlavə düyünlər, "qərar qəbul edən düyünlər" var (açılan cədvəldəki satırların yerləşdiyi düyün). Lakin axtarışın mürəkkəbliyi hələ də O(log(N))-dir (sadəcə başqa bir səviyyə var). Böyük fərq isə odur ki, aşağıdakı düyünlər öz varisləri ilə bağlıdır..

Bu B+Tree ilə, 40-dan 100-ə qədər dəyərləri axtardığınızda: Sadəcə 40-ı (40 yoxdursa, 40-dan sonrakı ən yaxın dəyəri) axtarmaq lazımdır, əvvəlki ağacda etdiyiniz kimi..

Sonra 40-dan varis olanları toplayın, varislərinə birbaşa müstəqil yolla çatana qədər 100-ə çatana qədər.

Tutaq ki, M varisini tapdınız və ağacın N düyünü var. Müəyyən bir düyünü axtarmaq O(log(N)) başa gəlir, əvvəlki ağacda olduğu kimi. Ancaq bu düyünə çatdıqda, M əməliyyatı ilə varislərini alacaqsınız.
Bu axtarış yalnız M+log(N) başa gəlir

əvvəlki ağacla müqayisədə N əməliyyatına qarşı. Üstəlik, tam ağacı oxumağa ehtiyac yoxdur (yalnız M + log(N) düyünü), bu da disk istifadəsinin azalmasını bildirir. Əgər M azdır (məsələn, 200 satır) və N böyükdür (1.000.000 satır), bu, BÖYÜK bir fərq olacaq. Amma burada yeni problemlər var (yenə də!). Məlumat bazasında (və buna görə də əlaqəli B+Tree indeksində) bir satırı əlavə etdiyinizdə və ya silərkən: B+Tree içindəki düyünlər arasındakı sıralamanı saxlamalısınız, əks təqdirdə sıralanmamış ağacda düyünləri tapa bilməzsiniz.

B+Tree-də mümkün olan ən az səviyyələri saxlamaq lazımdır, əks halda O(log(N)) zaman mürəkkəbliyi O(N)-ə çevriləcək.

вы должны поддерживать порядок между узлами внутри дерева B+Tree, иначе вы не сможете найти узлы внутри несортированного дерева.
вы должны сохранить минимально возможное количество уровней в B+Tree, иначе временная сложность в O (log (N)) станет O (N).

Başqa sözlə, B+Tree öz-özünə düzənlənmiş və balanslı olmalıdır. Şükür ki, bu, ağıllı silmə və əlavə etmə əməliyyatları ilə mümkündür. Lakin bu, baha başa gəlir: B+ ağacında əlavə etmə və silmə O (log (N)) vaxtını alır. Buna görə, bəziləriniz eşitmişsiniz ki, bir çox indekslərdən istifadə etmək çox yaxşı bir fikir deyil.Həqiqətən də, sizin cədvəldə sürətli əlavə etmə / yeniləmə / silmə prosesiniz yavaşlayır,çünki verilənlər bazası hər bir indeks üçün baha başa gələn O (log (N)) əməliyyatı ilə cədvəl indekslərini yeniləməlidir. Daha da əhəmiyyətlisi, indekslərin əlavə olunması transaksiya meneceri üçün daha çox yük deməkdir (bu, məqalənin sonunda izah ediləcək).

Daha ətraflı məlumat üçün, siz B+Ağacmövzusundakı Vikipediya məqaləsinə baxa bilərsiniz. B+Tree-nin verilənlər bazasında necə həyata keçirildiyini görmək istəyirsinizsə, bu məqaləni və bu məqaləni MySQL-in aparıcı inkişafçısından baxın. Onlar hər ikisi InnoDB-nin (MySQL mühərriki) indeksləri necə idarə etdiyinə fokuslanıblar.

Qeyd: oxucu mənə dedi ki, aşağı səviyyəli optimizasiyalar səbəbindən B+ ağacı tam balanslı olmalıdır.

HashTable (Hash cədvəli)

Sonuncu əhəmiyyətli məlumat strukturumuz hash cədvəlidir. Bu, dəyərləri sürətlə axtarmaq istədiyiniz zaman çox faydalıdır. Daha da əhəmiyyətlisi, hash cədvəlini başa düşmək bizə sonra verilənlər bazasıyla əlaqəli ümumi əməliyyatı başa düşməyə kömək edəcək, buna hash join ( hash join) deyilir. Bu məlumat strukturu verilənlər bazası tərəfindən bəzi daxili şeylərin (məsələn, loklama cədvəli və yaddaş yerləşdirmə) saxlanması üçün də istifadə olunur, bu iki anlayışı sonra görəcəyik.

Hash cədvəli, bir elementi açarı ilə sürətlə tapmağa imkan verən məlumat strukturudur. Hash cədvəli qurmaq üçün sizə lazımdır:

elementləriniz üçün açar açarlar üçün hash funksiyası. Hesablanmış açarların hash-ləri elementlərin yerləşməsini (buna
seqmentlər deyilir) tapır. Açarların müqayisəsi funksiyası. Doğru seqmenti tapdıqdan sonra, həmin seqment daxilində axtardığınız elementi tapmalısınız. ).
Sadə bir misalGəlin bir nümunəyə baxaq:

Bu hash cədvəlinin 10 seqmenti var. Mən tənbəl olduğum üçün yalnız 5 seqment çəkməyi bacardım, amma bilirəm ki, siz ağıllısınız, ona görə də 5 digərini özünüz təsəvvür etməyə icazə verirəm. Mən açarın 10-a bölünməsi ilə hash funksiyasını istifadə etdim. Başqa sözlə, seqmentini tapmaq üçün yalnız elementin açarının sonuncu rəqəmini saxlayıram:

əgər sonuncu rəqəm 0-dırsa, element 0 seqmentinə düşür,

əgər sonuncu rəqəm 1-dirsə, element 1 seqmentinə düşür,

əgər sonuncu rəqəm 2-dirsə, element 2 seqmentinə düşür,
İstifadə etdiyim müqayisə funksiyası yalnız iki tam ədəd arasında bərabərlikdir.
Tutaq ki, siz 78 elementini əldə etmək istəyirsiniz:
…

Hash cədvəli 78 üçün hash kodunu hesablayır, bu da 8-dir.

Допустим, вы хотите получить элемент 78:

Хеш-таблица вычисляет хеш-код для 78, который равен 8.
Хеш-таблица смотрит в сегмент 8, и первый элемент, который она находит, это 78.
Она возвращает вам элемент 78
Поиск стоит только 2 операции (одна для вычисления значения хеш-функции, а другая для поиска элемента внутри сегмента).

Теперь, допустим, вы хотите получить элемент 59:

Хеш-таблица вычисляет хеш-код для 59, который равен 9.
Хеш-таблица ищет в 9 сегменте, первый найденный элемент — это 99. Поскольку 99!=59, элемент 99 не правильный элемент.
Используя эту же логику, берется второй элемент (9), третий (79), …, последний (29).
Элемент не найден.
Поиск стоил 7 операций.

Хорошая хеш-функция

Как видите, в зависимости от значения, которое вы ищете, стоимость не одинакова!

Если я теперь изменю хэш-функцию по модулю 1 000 000 от ключа (то есть, взяв последние 6 цифр), второй поиск будет стоить только 1 операцию, поскольку в сегменте 000059 нет элементов. Реальная задача — найти хорошую хэш-функцию, которая будет создавать сегменты, содержащие очень небольшое количество элементов.

В моем примере найти хорошую хеш-функцию легко. Но это простой пример, найти хорошую хеш-функцию сложнее, когда ключ:

строка (например — фамилия)
2 строки (например — фамилия и имя)
2 строки и дата (например — фамилия, имя и дата рождения)
…

С хорошей хеш-функцией поиск в хеш-таблице обходится в O(1).

Массив vs хеш-таблица

Почему бы не использовать массив?

Хм, хороший вопрос.

Хеш-таблица может быть частично загружена в память, а остальные сегменты могут оставаться на диске.
С массивом вы должны использовать непрерывное пространство в памяти. Если вы загружаете большую таблицу очень сложно найти достаточно непрерывного пространства.
Для хеш-таблицы вы можете выбрать нужный ключ (например, страну и фамилию человека).

Для дополнительной информации, вы можете прочитать статью о JavaHashMap, которая является эффективной реализацией хеш-таблицы; вам не нужно понимать Java, чтобы понять концепции, изложенные в этой статье.

Mənbə: habr.com