Hey Habr! Məqalənin tərcüməsini diqqətinizə təqdim edirəm
"Relational verilənlər bazası necə işləyir".

Əlaqəli verilənlər bazalarına gəldikdə, nəyinsə çatışmadığını düşünməyə kömək edə bilmirəm. Onlar hər yerdə istifadə olunur. Kiçik və faydalı SQLite-dən güclü Teradata-ya qədər çoxlu müxtəlif verilənlər bazaları mövcuddur. Lakin verilənlər bazasının necə işlədiyini izah edən bir neçə məqalə var. Nə qədər az nəticə olduğunu görmək üçün "howdoesarelationaldatabasework" istifadə edərək özünüz üçün axtarış edə bilərsiniz. Üstəlik, bu məqalələr qısadır. Ən son səs-küylü texnologiyalar (BigData, NoSQL və ya JavaScript) axtarırsınızsa, onların necə işlədiyini izah edən daha ətraflı məqalələr tapa bilərsiniz.

Əlaqəli verilənlər bazaları universitet kurslarından, tədqiqat məqalələrindən və kitablardan kənarda izah etmək üçün çox köhnə və çox darıxdırıcıdırmı?

Bir tərtibatçı olaraq başa düşmədiyim bir şeydən istifadə etməyə nifrət edirəm. Və əgər verilənlər bazaları 40 ildən çox istifadə olunubsa, bunun səbəbi olmalıdır. İllər ərzində mən hər gün istifadə etdiyim bu qəribə qara qutuları həqiqətən dərk etmək üçün yüzlərlə saat sərf etmişəm. Əlaqəli verilənlər bazaları çox maraqlıdır, çünki onlar faydalı və təkrar istifadə edilə bilən konsepsiyalara əsaslanır. Əgər siz verilənlər bazasını anlamaqda maraqlısınızsa, lakin bu geniş mövzunu araşdırmaq üçün heç vaxt vaxtınız və ya meyliniz yoxdursa, bu məqalədən zövq almalısınız.

Bu məqalənin başlığı açıq olsa da, bu məqalənin məqsədi verilənlər bazasından necə istifadə edəcəyinizi anlamaq deyil. Beləliklə, siz artıq sadə əlaqə sorğusunu və əsas sorğuları necə yazacağınızı bilməlisiniz RAW; əks halda bu məqaləni başa düşməyə bilərsiniz. Bilməli olduğunuz yeganə şey budur, qalanını izah edəcəyəm.

Alqoritmlərin vaxt mürəkkəbliyi (BigO) kimi bəzi kompüter elminin əsasları ilə başlayacağam. Bilirəm ki, sizlərdən bəziləri bu anlayışa nifrət edir, lakin onsuz verilənlər bazası daxilindəki incəlikləri başa düşə bilməyəcəksiniz. Bu, böyük bir mövzu olduğundan, diqqət yetirəcəyəm vacib hesab etdiyim şey: verilənlər bazası necə işləyir SQL sorğu. Mən sadəcə təqdim edəcəyəm baza verilənlər bazası anlayışlarıBeləliklə, məqalənin sonunda başlıq altında baş verənlər haqqında bir fikrə sahibsiniz.

Bu, çoxlu alqoritmlər və məlumat strukturlarını əhatə edən uzun və texniki məqalə olduğundan, onu oxumağa vaxt ayırın. Bəzi anlayışları başa düşmək çətin ola bilər; onları atlaya və yenə də ümumi fikir əldə edə bilərsiniz.

Aranızda daha çox məlumatlı olanlar üçün bu məqalə 3 hissəyə bölünür:

Aşağı səviyyəli və yüksək səviyyəli verilənlər bazası komponentlərinə ümumi baxış
Sorğunun optimallaşdırılması prosesinin icmalı
Tranzaksiya və Bufer Hövzəsinin İdarə edilməsinə İcmal

Əsaslara qayıt

İllər əvvəl (uzaq, uzaq bir qalaktikada...) tərtibatçılar kodlaşdırdıqları əməliyyatların sayını dəqiq bilməli idilər. Onlar öz alqoritmlərini və məlumat strukturlarını əzbər bilirdilər, çünki yavaş kompüterlərinin CPU və yaddaşını boş yerə sərf edə bilmirdilər.

Bu hissədə mən sizə bu anlayışlardan bəzilərini xatırladacağam, çünki onlar verilənlər bazasını başa düşmək üçün vacibdir. Mən də konsepsiyanı təqdim edəcəyəm verilənlər bazası indeksi.

O(1) və O(n2)

İndiki vaxtda bir çox tərtibatçı alqoritmlərin vaxt mürəkkəbliyinə əhəmiyyət vermir... və onlar haqlıdırlar!

Ancaq bir çox məlumatla məşğul olduğunuz zaman (minlərlə danışmıram) və ya millisaniyələrlə mübarizə aparırsınızsa, bu konsepsiyanı başa düşmək kritik hala gəlir. Təsəvvür edə bildiyiniz kimi, verilənlər bazası hər iki vəziyyətlə məşğul olmalıdır! Mən sizə lazım olandan daha çox vaxt sərf etməyə məcbur etməyəcəyəm. Bu, daha sonra xərclərə əsaslanan optimallaşdırma anlayışını anlamağa kömək edəcək (qiymət əsasında optimallaşdırma).

Anlayış

Alqoritmin vaxt mürəkkəbliyi bir alqoritmin müəyyən miqdarda məlumat üçün nə qədər vaxt aparacağını görmək üçün istifadə olunur. Bu mürəkkəbliyi təsvir etmək üçün biz böyük O riyazi qeydindən istifadə edirik.Bu qeyd alqoritmin müəyyən sayda giriş üçün neçə əməliyyata ehtiyacı olduğunu təsvir edən funksiya ilə istifadə olunur.

Məsələn, mən "bu alqoritmin mürəkkəbliyi O(bəzi_funksiya())" dedikdə, bu o deməkdir ki, alqoritm müəyyən miqdarda verilənləri emal etmək üçün bəzi_funksiya (a_müəyyən_məlumat_miqdarı) əməliyyatları tələb edir.

Bu halda, Önəmli olan məlumatların miqdarı deyil**, əks halda ** artan məlumat həcmi ilə əməliyyatların sayı necə artır. Vaxtın mürəkkəbliyi əməliyyatların dəqiq sayını təmin etmir, lakin icra müddətini qiymətləndirmək üçün yaxşı bir üsuldur.

Bu qrafikdə müxtəlif növ alqoritm vaxt mürəkkəbliyi üçün daxil edilən məlumatların miqdarına qarşı əməliyyatların sayını görə bilərsiniz. Onları göstərmək üçün loqarifmik miqyasdan istifadə etdim. Başqa sözlə desək, məlumatların həcmi sürətlə 1 milyarddan 1 milyarda yüksəlir.Biz bunu görə bilərik:

O(1) və ya sabit mürəkkəblik sabit qalır (əks halda ona daimi mürəkkəblik deyilməzdi).
O(daxil ol(n)) milyardlarla məlumatla belə aşağı olaraq qalır.
Ən pis çətinlik - O(n2), burada əməliyyatların sayı sürətlə artır.
Digər iki ağırlaşma da eyni sürətlə artır.

Nümunələr

Kiçik bir məlumat miqdarı ilə O(1) və O(n2) arasındakı fərq əhəmiyyətsizdir. Məsələn, tutaq ki, sizin 2000 elementi emal etməli olan alqoritminiz var.

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 əməliyyata başa gələcək
O(n*log(n)) alqoritmi sizə 14 əməliyyata başa gələcək
O(n2) alqoritmi sizə 4 əməliyyata başa gələcək

O(1) və O(n2) arasındakı fərq böyük görünür (4 milyon əməliyyat), lakin siz maksimum 2 ms itirəcəksiniz, sadəcə gözlərinizi qırpmaq üçün vaxt itirəcəksiniz. Həqiqətən, müasir prosessorlar emal edə bilər saniyədə yüz milyonlarla əməliyyat. Buna görə də bir çox İT layihələrində performans və optimallaşdırma problem deyil.

Dediyim kimi, böyük həcmli məlumatlarla işləyərkən bu konsepsiyanı bilmək hələ də vacibdir. Əgər bu dəfə alqoritm 1 elementi emal etməlidirsə (bu verilənlər bazası üçün o qədər də çox deyil):

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

Mən riyaziyyatı etməmişəm, amma deyərdim ki, O(n2) alqoritmi ilə bir qəhvə (hətta iki!) içməyə vaxtınız var. Məlumat həcminə başqa 0 əlavə etsəniz, yuxuya getməyə vaxtınız olacaq.

Gəlin daha dərinə gedək

Məlumat üçün:

Yaxşı hash cədvəli axtarışı O(1)-də element tapır.
Yaxşı balanslaşdırılmış ağac axtarışı O(log(n)) ilə nəticə verir.
Massiv axtarışı O(n) ilə nəticə verir.
Ən yaxşı çeşidləmə alqoritmləri mürəkkəbliyə malikdir O(n*log(n)).
Pis çeşidləmə alqoritmi O(n2) mürəkkəbliyinə malikdir.

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

Alqoritm vaxtının mürəkkəbliyinin bir neçə növü var:

orta vəziyyət ssenarisi
ən yaxşı ssenari
və ən pis vəziyyət ssenarisi

Zamanın mürəkkəbliyi çox vaxt ən pis vəziyyət ssenarisidir.

Mən yalnız alqoritmin zaman mürəkkəbliyindən danışırdım, lakin mürəkkəblik aşağıdakılara da aiddir:

alqoritmin yaddaş istehlakı
diskin I/O istehlak alqoritmi

Əlbəttə ki, n2-dən daha pis fəsadlar var, məsələn:

n4: bu dəhşətlidir! Qeyd olunan alqoritmlərdən bəziləri bu mürəkkəbliyə malikdir.
3n: bu daha da pisdir! Bu məqalənin ortasında görəcəyimiz alqoritmlərdən biri bu mürəkkəbliyə malikdir (və əslində bir çox verilənlər bazasında istifadə olunur).
faktorial n: hətta az miqdarda məlumatla da heç vaxt nəticə əldə etməyəcəksiniz.
nn: Əgər bu mürəkkəbliklə qarşılaşsanız, özünüzdən soruşmalısınız ki, bu həqiqətən sizin fəaliyyət sahənizdir...

Qeyd: Mən sizə böyük O işarəsinin həqiqi tərifini vermədim, sadəcə bir fikir. Bu məqaləni burada oxuya bilərsiniz Vikipediya real (asimptotik) tərif üçün.

MergeSort

Kolleksiyanı çeşidləmək lazım olduqda nə edirsiniz? Nə? Siz sort() funksiyasını çağırırsınız... Yaxşı, yaxşı cavab... Amma verilənlər bazası üçün bu sort() funksiyasının necə işlədiyini başa düşməlisiniz.

Bir neçə yaxşı çeşidləmə alqoritmi var, ona görə də ən vaciblərinə diqqət yetirəcəyəm: birləşmə çeşidi. Məlumatların çeşidlənməsinin niyə faydalı olduğunu başa düşməyə bilərsiniz, lakin sorğunun optimallaşdırılması hissəsindən sonra bunu etməlisiniz. Üstəlik, birləşmə növünü başa düşmək bizə daha sonra ümumi verilənlər bazası birləşmə əməliyyatını başa düşməyə kömək edəcək qatışmaq qoşulmaq (birləşmə birliyi).

Birləşdirin

Bir çox faydalı alqoritmlər kimi, birləşmənin çeşidlənməsi də hiyləyə əsaslanır: N/2 ölçülü 2 çeşidlənmiş massivləri N elementli çeşidlənmiş massivdə birləşdirmək yalnız N əməliyyata başa gəlir. Bu əməliyyat birləşmə adlanır.

Bunun nə demək olduğunu sadə bir nümunə ilə görək:

Bu rəqəm göstərir ki, son çeşidlənmiş 8 elementli massiv qurmaq üçün 2 4 elementli massiv üzərində yalnız bir dəfə təkrarlamaq lazımdır. Hər iki 4 elementli massiv artıq çeşidləndiyi üçün:

1) hər iki cari elementi iki massivdə müqayisə edirsiniz (əvvəlində cari = birinci)
2) sonra 8 elementli massivdə yerləşdirmək üçün ən kiçiyini götürün
3) və ən kiçik elementi götürdüyünüz massivdə növbəti elementə keçin
və massivlərdən birinin sonuncu elementinə çatana qədər 1,2,3-ü təkrarlayın.
Sonra digər massivin qalan elementlərini götürərək onları 8 elementli massivdə yerləşdirin.

Bu, ona görə işləyir ki, hər iki 4 elementli massiv çeşidlənir və siz həmin massivlərdə "geri qayıtmaq" məcburiyyətində deyilsiniz.

İndi hiyləni başa düşdükdən sonra birləşmə üçün mənim psevdokodum budur:

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;

Birləşdirmə çeşidi problemi daha kiçik problemlərə ayırır və sonra orijinal məsələnin nəticəsini əldə etmək üçün kiçik məsələlərin nəticələrini tapır (qeyd: bu növ alqoritm böl və fəth adlanır). Bu alqoritmi başa düşmürsənsə, narahat olmayın; İlk dəfə görəndə başa düşmədim. Əgər bu sizə kömək edə bilərsə, mən bu alqoritmi iki fazalı alqoritm kimi görürəm:

Bölmə mərhələsi, burada massiv daha kiçik massivlərə bölünür
Çeşidləmə mərhələsi kiçik massivlərin daha böyük massiv yaratmaq üçün birləşdirildiyi yerdir (birlikdən istifadə etməklə).

Bölmə mərhələsi

Bölmə mərhələsində massiv 3 addımda unitar massivlərə bölünür. Addımların formal sayı log(N)-dir (çünki N=8, log(N) = 3).

Bunu hardan bilerem?

Mən dahiyəm! Bir sözlə - riyaziyyat. İdeya ondan ibarətdir ki, hər bir addım orijinal massivin ölçüsünü 2-yə bölür. Addımların sayı orijinal massivi neçə dəfə ikiyə bölmək olar. Bu, loqarifmin dəqiq tərifidir (əsas 2).

Çeşidləmə mərhələsi

Çeşidləmə mərhələsində siz unitar (tək elementli) massivlərdən başlayırsınız. Hər bir addımda birdən çox birləşmə əməliyyatı tətbiq edirsiniz və ümumi xərc N = 8 əməliyyatdır:

Birinci mərhələdə hər biri 4 əməliyyata başa gələn 2 birləşməniz var
İkinci addımda hər biri 2 əməliyyata başa gələn 4 birləşməniz var
Üçüncü addımda 1 əməliyyata başa gələn 8 birləşməniz var

log(N) addımları olduğundan, ümumi xərc N * log(N) əməliyyatları.

Birləşmə növünün üstünlükləri

Bu alqoritm niyə bu qədər güclüdür?

Çünki:

Yaddaşın izini azaltmaq üçün onu dəyişə bilərsiniz ki, yeni massivlər yaratmayasınız, ancaq giriş massivini birbaşa dəyişdirəsiniz.

Qeyd: bu tip alqoritm adlanır in-yer (əlavə yaddaş olmadan çeşidləmə).

Siz onu disk sahəsini və az miqdarda yaddaşdan istifadə etmək üçün eyni vaxtda əhəmiyyətli disk giriş/çıxış xərclərini ödəmədən dəyişə bilərsiniz. İdeya yaddaşa yalnız hazırda emal olunan hissələri yükləməkdir. Yalnız 100 meqabaytlıq yaddaş buferi ilə çox giqabaytlıq cədvəli çeşidləmək lazım olduqda bu vacibdir.

Qeyd: bu tip alqoritm adlanır xarici növ.

Siz onu birdən çox proses/mevz/serverdə işləmək üçün dəyişə bilərsiniz.

Məsələn, paylanmış birləşmə çeşidi əsas komponentlərdən biridir Hadoop (bu, böyük verilənlərdə strukturdur).

Bu alqoritm qurğuşunu qızıla çevirə bilər (həqiqətən!).

Bu çeşidləmə alqoritmi əksər (hamısı olmasa da) verilənlər bazasında istifadə olunur, lakin bu, yeganə deyil. Daha çox bilmək istəyirsinizsə, bunu oxuya bilərsiniz tədqiqat işi, ümumi verilənlər bazası çeşidləmə alqoritmlərinin müsbət və mənfi cəhətlərini müzakirə edir.

Massiv, Ağac və Hash Cədvəli

İndi zamanın mürəkkəbliyi və çeşidlənməsi ideyasını başa düşdüyümüz üçün sizə 3 məlumat strukturu haqqında məlumat verməliyəm. Bu vacibdir, çünki onlar müasir verilənlər bazalarının əsasını təşkil edir. Mən də konsepsiyanı təqdim edəcəyəm verilənlər bazası indeksi.

Maşiv

İki ölçülü massiv ən sadə verilənlər strukturudur. Cədvəl bir massiv kimi düşünülə bilər. Misal üçün:

Bu 2 ölçülü massiv sətir və sütunlardan ibarət cədvəldir:

Hər bir sətir bir varlığı təmsil edir
Sütunlar obyekti təsvir edən xassələri saxlayır.
Hər bir sütun müəyyən tipli məlumatları (tam ədəd, sətir, tarix...) saxlayır.

Bu, məlumatların saxlanması və vizuallaşdırılması üçün əlverişlidir, lakin müəyyən bir dəyər tapmaq lazım olduqda bu uyğun deyil.

Məsələn, əgər siz Böyük Britaniyada işləyən bütün oğlanları tapmaq istəyirsinizsə, həmin sıranın Böyük Britaniyaya aid olub-olmadığını müəyyən etmək üçün hər cərgəyə baxmaq lazımdır. Bu sizə N əməliyyata başa gələcəkHara N - xətlərin sayı, pis deyil, amma daha sürətli bir yol ola bilərmi? İndi ağaclarla tanış olmağın vaxtı gəldi.

Qeyd: Müasir verilənlər bazalarının əksəriyyəti cədvəlləri səmərəli saxlamaq üçün genişləndirilmiş massivləri təmin edir: yığın-organizedtables və index-organized tables. Ancaq bu, bir qrup sütunda müəyyən bir şərti tez tapmaq problemini dəyişdirmir.

Verilənlər bazası ağacı və indeksi

İkili axtarış ağacı xüsusi xüsusiyyətə malik ikili ağacdır, hər bir qovşaqda açar aşağıdakı olmalıdır:

sol alt ağacda saxlanılan bütün düymələrdən böyükdür
sağ alt ağacda saxlanılan bütün açarlardan azdır

Bunun vizual olaraq nə demək olduğunu görək

Fikir

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

Açarı 136 olan kökdən başlayıram. 136<208 olduğundan, 136 node-un sağ alt ağacına baxıram.
398>208 buna görə də 398 node-un sol alt ağacına baxıram
250>208 buna görə də 250 node-un sol alt ağacına baxıram
200<208, ona görə də mən 200 node-un sağ alt ağacına baxıram. Amma 200-ün sağ alt ağacı yoxdur, dəyəri yoxdur (çünki əgər varsa, o, sağ alt ağac 200-də olacaq).

İndi deyək ki, mən 40 axtarıram

Mən açarı 136 olan kökdən başlayıram. 136 > 40 olduğundan, 136 node-un sol alt ağacına baxıram.
80 > 40, buna görə də 80 node-un sol alt ağacına baxıram
40= 40, node mövcuddur. Mən qovşaq daxilində (şəkildə göstərilməyib) cərgə identifikatorunu alıram və verilmiş sətir ID-si üçün cədvələ baxıram.
Sətir identifikatorunu bilmək mənə verilənlərin cədvəlin harada olduğunu dəqiq bilməyə imkan verir, ona görə də mən onu dərhal geri ala bilərəm.

Sonda hər iki axtarış mənə ağacın içindəki səviyyələrin sayına başa gələcək. Birləşmənin çeşidlənməsi ilə bağlı hissəni diqqətlə oxusanız, log(N) səviyyələrinin olduğunu görəcəksiniz. Çıxır, axtarış xərcləri jurnalı(N), pis deyil!

Qayıdaq problemimizə

Amma bu çox mücərrəddir, ona görə də problemimizə qayıdaq. Sadə bir tam ədəd əvəzinə, əvvəlki cədvəldə kiminsə ölkəsini təmsil edən bir sətir təsəvvür edin. Deyək ki, cədvəlin "ölkə" sahəsini (sütun 3) ehtiva edən bir ağacınız var:

Böyük Britaniyada kimin işlədiyini bilmək istəyirsinizsə
Böyük Britaniyanı təmsil edən düyünü almaq üçün ağaca baxırsınız
"UKnode" daxilində siz Böyük Britaniya işçi qeydlərinin yerini tapa bilərsiniz.

Əgər massivdən birbaşa istifadə etsəniz, bu axtarış N əməliyyat yerinə log(N) əməliyyatlarına başa gələcək. Bayaq təqdim etdiyiniz şey idi verilənlər bazası indeksi.

Düymələri (yəni sahə qrupları) müqayisə etmək funksiyanız olduğu müddətcə istənilən sahələr qrupu (sətir, nömrə, 2 sətir, nömrə və sətir, tarix...) üçün indeks ağacı yarada bilərsiniz, beləliklə açarlar arasında sifariş verin (bu verilənlər bazasındakı hər hansı əsas növlər üçün belədir).

B+TreeIndex

Bu ağac müəyyən bir dəyər əldə etmək üçün yaxşı işləsə də, ehtiyac duyduğunuzda BÖYÜK problem var iki dəyər arasında çoxlu element əldə edin. Bunun O(N) bahasına başa gələcək, çünki siz ağacdakı hər bir düyünə baxmaq və onun bu iki dəyər arasında olub-olmadığını yoxlamaq məcburiyyətində qalacaqsınız (məsələn, ağacın sifarişli keçidi ilə). Üstəlik, bu əməliyyat diskə giriş/çıxış üçün uyğun deyil, çünki siz bütün ağacı oxumalısınız. Səmərəli icra etmək üçün bir yol tapmalıyıq diapazon tələbi. Bu problemi həll etmək üçün müasir verilənlər bazaları B+Tree adlı əvvəlki ağacın dəyişdirilmiş versiyasından istifadə edir. B+Ağac ağacında:

yalnız ən aşağı düyünlər (yarpaqlar) məlumat saxlamaq (müvafiq cədvəldə sətirlərin yeri)
qovşaqların qalan hissəsi buradadır marşrutlaşdırma üçün düzgün node üçün axtarış zamanı.

Gördüyünüz kimi, burada daha çox qovşaq var (iki dəfə). Həqiqətən, sizin düzgün qovşağı (əlaqəli cədvəldə cərgələrin yerini saxlayan) tapmağınıza kömək edəcək əlavə qovşaqlarınız, "qərar qovşaqları" var. Lakin axtarışın mürəkkəbliyi hələ də O(log(N)) (yalnız daha bir səviyyə var). Böyük fərq ondadır aşağı səviyyədə olan qovşaqlar onların davamçıları ilə əlaqələndirilir.

Bu B+Tree ilə 40 ilə 100 arasında dəyərlər axtarırsınızsa:

Siz sadəcə olaraq əvvəlki ağacda etdiyiniz kimi 40-ı (və ya 40 yoxdursa 40-dan sonrakı ən yaxın dəyəri) axtarmalısınız.
Sonra 40-ə çatana qədər birbaşa varis bağlantılarından istifadə edərək 100 varis toplayın.

Deyək ki, siz M varis tapdınız və ağacın N qovşağı var. Müəyyən bir node tapmaq əvvəlki ağac kimi log(N) xərcləyir. Ancaq bu nodu əldə etdikdən sonra, onların davamçılarına istinadla M əməliyyatlarında M varisləri əldə edəcəksiniz. Bu axtarış yalnız M+log(N) dəyərindədir əvvəlki ağacdakı N əməliyyatla müqayisədə əməliyyatlar. Üstəlik, tam ağacı oxumaq lazım deyil (yalnız M+log(N) qovşaqları), bu da daha az disk istifadəsi deməkdir. M kiçikdirsə (məsələn, 200 sıra) və N böyükdürsə (1 sıra), BÖYÜK fərq olacaq.

Ancaq burada yeni problemlər var (yenə də!). Verilənlər bazasında (və buna görə də əlaqəli B+Ağac indeksində) bir sıra əlavə etsəniz və ya silsəniz:

siz B+Ağac daxilində qovşaqlar arasında nizamı qorumalısınız, əks halda çeşidlənməmiş ağacın içərisində qovşaqları tapa bilməyəcəksiniz.
B+Tree-də minimum mümkün səviyyə sayını saxlamalısınız, əks halda O(log(N)) zaman mürəkkəbliyi O(N) olur.

Başqa sözlə, B+Tree öz-özünə nizamlı və balanslı olmalıdır. Xoşbəxtlikdən, bu, ağıllı silmə və daxiletmə əməliyyatları ilə mümkündür. Lakin bunun baha başa gəlir: B+ ağacında əlavələr və silmələr O(log(N)) dəyərinə malikdir. Buna görə də bəziləriniz bunu eşitmisiniz çoxlu indekslərdən istifadə etmək yaxşı fikir deyil. Həqiqətən, cədvəldə sıranın sürətli daxil edilməsini/yenilənməsini/silməsini ləngidirsinizçünki verilənlər bazası hər bir indeks üçün bahalı O(log(N)) əməliyyatından istifadə edərək cədvəlin indekslərini yeniləməlidir. Üstəlik, indekslərin əlavə edilməsi daha çox iş yükü deməkdir əməliyyat meneceri (məqalənin sonunda təsvir olunacaq).

Ətraflı məlumat üçün Vikipediya məqaləsinə baxa bilərsiniz B+Ağac. Əgər verilənlər bazasında B+Tree tətbiqi nümunəsi istəyirsinizsə, nəzər salın Bu məqalə и Bu məqalə aparıcı MySQL tərtibatçısından. Hər ikisi InnoDB (MySQL mühərriki) indeksləri necə idarə etdiyinə diqqət yetirir.

Qeyd: Bir oxucu mənə dedi ki, aşağı səviyyəli optimallaşdırmalara görə B+ ağacı tamamilə balanslaşdırılmalıdır.

Hashtable

Son vacib məlumat strukturumuz hash cədvəlidir. Tez dəyərlərə baxmaq istədiyiniz zaman bu çox faydalıdır. Bundan əlavə, hash cədvəlini başa düşmək bizə daha sonra hash qoşulma adlanan ümumi verilənlər bazası birləşmə əməliyyatını başa düşməyə kömək edəcək ( hash qoşulun). Bu məlumat strukturu bəzi daxili şeyləri saxlamaq üçün verilənlər bazası tərəfindən də istifadə olunur (məs. kilid masası və ya bufer hovuzu, bu anlayışların hər ikisini daha sonra görəcəyik).

Hash cədvəli elementi açarı ilə tez tapan məlumat strukturudur. Hash cədvəli yaratmaq üçün aşağıdakıları təyin etməlisiniz:

ipucu elementləriniz üçün
hash funksiyası açarlar üçün. Hesablanmış açar hashları elementlərin yerini verir (adlanır seqmentlər ).
düymələri müqayisə etmək funksiyası. Düzgün seqmenti tapdıqdan sonra bu müqayisədən istifadə edərək seqment daxilində axtardığınız elementi tapmalısınız.

Sadə bir misal

Aydın bir nümunə götürək:

Bu hash cədvəlinin 10 seqmenti var. Tənbəl olduğum üçün cəmi 5 seqmenti təsvir etdim, amma bilirəm ki, sən ağıllısan, ona görə də qalan 5-ni özbaşına təsvir etməyə icazə verim. Açarın 10 modulu hash funksiyasından istifadə etdim. Başqa sözlə, onun seqmentini tapmaq üçün elementin açarının yalnız son rəqəmini saxlayıram:

sonuncu rəqəm 0 olarsa, element 0 seqmentinə düşür,
sonuncu rəqəm 1 olarsa, element 1 seqmentinə düşür,
sonuncu rəqəm 2 olarsa, element 2-ci sahəyə düşür,
...

İstifadə etdiyim müqayisə funksiyası sadəcə olaraq iki tam ədəd arasındakı bərabərlikdir.

Tutaq ki, siz 78 elementi əldə etmək istəyirsiniz:

Hash cədvəli 78 olan 8 üçün hash kodunu hesablayır.
Hash cədvəli 8-ci seqmentə baxır və ilk tapdığı element 78-dir.
78-ci maddəni sizə qaytarır
Axtarış yalnız 2 əməliyyata başa gəlir (biri hash dəyərini hesablamaq üçün, digəri isə seqment daxilində elementi axtarmaq üçün).

İndi deyək ki, siz 59-cu elementi əldə etmək istəyirsiniz:

Hash cədvəli 59 olan 9 üçün hash kodunu hesablayır.
Hash cədvəli 9-cu seqmentdə axtarış edir, ilk tapılan element 99-dur. 99!=59 olduğundan, element 99 etibarlı element deyil.
Eyni məntiqdən istifadə edərək ikinci element (9), üçüncü (79), ..., sonuncu (29) alınır.
Element tapılmadı.
Axtarış 7 əməliyyata başa gəlib.

Yaxşı hash funksiyası

Gördüyünüz kimi, axtardığınız dəyərdən asılı olaraq, xərc eyni deyil!

İndi açarın 1 hash funksiyasını dəyişdirsəm (yəni son 000 rəqəmi götürməklə), ikinci axtarış yalnız 000 əməliyyata başa gələcək, çünki 6 seqmentində heç bir element yoxdur. Əsl problem çox az sayda elementdən ibarət kovalar yaradacaq yaxşı hash funksiyası tapmaqdır.

Mənim nümunəmdə yaxşı hash funksiyası tapmaq asandır. Ancaq bu sadə bir nümunədir, yaxşı bir hash funksiyası tapmaq açar olduqda daha çətindir:

sətir (məsələn - soyad)
2 sətir (məsələn - soyad və ad)
2 sətir və tarix (məsələn - soyad, ad və doğum tarixi)
...

Yaxşı hash funksiyası ilə hash cədvəli axtarışları O(1) başa gəlir.

Massiv və hash cədvəli

Niyə massivdən istifadə etmirsiniz?

Hmm, yaxşı sual.

Hash cədvəli ola bilər yaddaşa qismən yüklənmişdir, qalan seqmentlər isə diskdə qala bilər.
Massivlə yaddaşda bitişik boşluqdan istifadə etməlisiniz. Böyük bir masa yükləyirsinizsə kifayət qədər davamlı yer tapmaq çox çətindir.
Hash cədvəli üçün istədiyiniz açarı seçə bilərsiniz (məsələn, ölkə və şəxsin soyadı).

Daha ətraflı məlumat üçün məqaləni oxuya bilərsiniz JavaHashMaphash cədvəlinin səmərəli tətbiqi olan ; bu məqalədə əhatə olunan anlayışları başa düşmək üçün Java-nı başa düşməyə ehtiyac yoxdur.

Mənbə: www.habr.com

Əlaqəli verilənlər bazaları necə işləyir (1-ci hissə)