ჰეი ჰაბრ! თქვენს ყურადღებას წარმოგიდგენთ სტატიის თარგმანს
"როგორ მუშაობს რელაციური მონაცემთა ბაზა".

რაც შეეხება რელაციურ მონაცემთა ბაზებს, არ შემიძლია არ ვფიქრობ, რომ რაღაც აკლია. ისინი ყველგან გამოიყენება. ხელმისაწვდომია მრავალი განსხვავებული მონაცემთა ბაზა, მცირე და სასარგებლო SQLite-დან ძლიერ Teradata-მდე. მაგრამ არის მხოლოდ რამდენიმე სტატია, რომელიც განმარტავს, თუ როგორ მუშაობს მონაცემთა ბაზა. თქვენ შეგიძლიათ მოძებნოთ საკუთარი თავი "howdoesarelationaldatabasework"-ის გამოყენებით, რათა ნახოთ რამდენად ცოტაა შედეგი. უფრო მეტიც, ეს სტატიები მოკლეა. თუ თქვენ ეძებთ უახლეს ხმაურიან ტექნოლოგიებს (BigData, NoSQL ან JavaScript), თქვენ იპოვით უფრო ღრმა სტატიებს, რომლებიც განმარტავს, თუ როგორ მუშაობს ისინი.

არის თუ არა რელაციური მონაცემთა ბაზები ძალიან ძველი და ძალიან მოსაწყენი, რომ აიხსნას უნივერსიტეტის კურსების, კვლევითი ნაშრომების და წიგნების მიღმა?

როგორც დეველოპერს, მეზიზღება რაღაცის გამოყენება, რაც არ მესმის. და თუ მონაცემთა ბაზები გამოიყენება 40 წელზე მეტი ხნის განმავლობაში, მიზეზი უნდა იყოს. წლების განმავლობაში ასობით საათი დავხარჯე ამ უცნაური შავი ყუთების გასაგებად, რომლებსაც ყოველდღე ვიყენებ. რელატიური მონაცემთა ბაზები ძალიან საინტერესოა, რადგან ისინი სასარგებლო და მრავალჯერადი გამოყენების კონცეფციებზე დაყრდნობით. თუ თქვენ გაინტერესებთ მონაცემთა ბაზის გაგება, მაგრამ არასოდეს გქონიათ დრო ან მიდრეკილება ამ ფართო თემის ჩასატარებლად, უნდა ისიამოვნოთ ამ სტატიით.

მიუხედავად იმისა, რომ ამ სტატიის სათაური აშკარაა, ამ სტატიის მიზანი არ არის იმის გაგება, თუ როგორ გამოიყენოთ მონაცემთა ბაზა. ამიტომ, თქვენ უკვე უნდა იცოდეთ როგორ დაწეროთ მარტივი კავშირის მოთხოვნა და ძირითადი მოთხოვნები კრუდ; წინააღმდეგ შემთხვევაში შეიძლება ვერ გაიგოთ ეს სტატია. ეს ერთადერთია რაც უნდა იცოდე, დანარჩენს აგიხსნი.

დავიწყებ კომპიუტერული მეცნიერების ზოგიერთი საფუძვლებით, როგორიცაა ალგორითმების დროის სირთულე (BigO). მე ვიცი, რომ ზოგიერთ თქვენგანს სძულს ეს კონცეფცია, მაგრამ ამის გარეშე თქვენ ვერ შეძლებთ გაიგოთ მონაცემთა ბაზაში არსებული სირთულეები. რადგან ეს დიდი თემაა, ყურადღებას გავამახვილებ რაც მე ვფიქრობ მნიშვნელოვანია: როგორ მუშავდება მონაცემთა ბაზა SQL გამოძიება. უბრალოდ გავაცნობ მონაცემთა ბაზის ძირითადი ცნებებიისე, რომ სტატიის ბოლოს გქონდეთ წარმოდგენა იმაზე, თუ რა ხდება ქუდის ქვეშ.

ვინაიდან ეს არის გრძელი და ტექნიკური სტატია, რომელიც მოიცავს უამრავ ალგორითმს და მონაცემთა სტრუქტურას, დაუთმეთ დრო მის წაკითხვას. ზოგიერთი ცნება შეიძლება რთული გასაგები იყოს; შეგიძლიათ გამოტოვოთ ისინი და მაინც მიიღოთ ზოგადი იდეა.

თქვენ შორის უფრო მცოდნეებისთვის, ეს სტატია დაყოფილია 3 ნაწილად:

• დაბალი და მაღალი დონის მონაცემთა ბაზის კომპონენტების მიმოხილვა
• შეკითხვის ოპტიმიზაციის პროცესის მიმოხილვა
• ტრანზაქციისა და ბუფერული ფონდის მართვის მიმოხილვა

საფუძვლებს დაუბრუნდით

წლების წინ (შორს, შორეულ გალაქტიკაში...), დეველოპერებს ზუსტად უნდა სცოდნოდათ ოპერაციების რაოდენობა, რომლებსაც ისინი კოდირებდნენ. მათ ზეპირად იცოდნენ თავიანთი ალგორითმები და მონაცემთა სტრუქტურები, რადგან არ შეეძლოთ თავიანთი ნელი კომპიუტერების CPU და მეხსიერების დახარჯვა.

ამ ნაწილში მე შეგახსენებთ ზოგიერთ ამ კონცეფციას, რადგან ისინი აუცილებელია მონაცემთა ბაზის გასაგებად. მეც გავაცნობ კონცეფციას მონაცემთა ბაზის ინდექსი.

O(1) vs O(n2)

დღესდღეობით, ბევრ დეველოპერს არ აინტერესებს ალგორითმების დროის სირთულე... და ისინი მართლები არიან!

მაგრამ როდესაც საქმე გაქვთ უამრავ მონაცემთან (მე არ ვსაუბრობ ათასობითზე) ან თუ თქვენ იბრძვით მილიწამებში, კრიტიკული ხდება ამ კონცეფციის გაგება. და როგორც წარმოგიდგენიათ, მონაცემთა ბაზებს ორივე სიტუაციასთან უნდა გაუმკლავდეთ! არ გაიძულებთ დახარჯოთ იმაზე მეტი დრო, ვიდრე საჭიროა აზრის გასაგებად. ეს დაგვეხმარება მოგვიანებით გავიგოთ ხარჯებზე დაფუძნებული ოპტიმიზაციის კონცეფცია (დაჯდა საფუძველზე ოპტიმიზაცია).

კონცეფცია

ალგორითმის დროის სირთულე გამოიყენება იმის სანახავად, თუ რამდენი დრო დასჭირდება ალგორითმის დასრულებას მონაცემთა მოცემული რაოდენობით. ამ სირთულის აღსაწერად ვიყენებთ დიდი O მათემატიკურ აღნიშვნას. ეს აღნიშვნა გამოიყენება ფუნქციით, რომელიც აღწერს რამდენი ოპერაცია სჭირდება ალგორითმს მოცემული რაოდენობის შეყვანისთვის.

მაგალითად, როდესაც ვამბობ "ამ ალგორითმს აქვს სირთულე O(some_function())", ეს ნიშნავს, რომ ალგორითმი მოითხოვს გარკვეული_ფუნქციის (a_certain_amount_of_ta) ოპერაციებს გარკვეული რაოდენობის მონაცემების დასამუშავებლად.

ამ შემთხვევაში, არ არის მნიშვნელოვანი მონაცემების რაოდენობა**, წინააღმდეგ შემთხვევაში ** როგორ იზრდება ოპერაციების რაოდენობა მონაცემთა მოცულობის მატებასთან ერთად. დროის სირთულე არ იძლევა ოპერაციების ზუსტ რაოდენობას, მაგრამ კარგი გზაა შესრულების დროის შესაფასებლად.

ამ დიაგრამაში შეგიძლიათ იხილოთ ოპერაციების რაოდენობა სხვადასხვა ტიპის ალგორითმის დროის სირთულისთვის შეყვანილი მონაცემების რაოდენობასთან შედარებით. მე გამოვიყენე ლოგარითმული მასშტაბი მათ გამოსაჩენად. სხვა სიტყვებით რომ ვთქვათ, მონაცემთა რაოდენობა სწრაფად იზრდება 1-დან 1 მილიარდამდე. ჩვენ ვხედავთ, რომ:

• O(1) ანუ მუდმივი სირთულის რჩება მუდმივი (სხვაგვარად მას არ დაერქმევა მუდმივი სირთულე).
• O(შესვლა(n)) დაბალი რჩება მილიარდობით მონაცემის პირობებშიც კი.
• ყველაზე ცუდი სირთულე - O(n2), სადაც ოპერაციების რაოდენობა სწრაფად იზრდება.
• დანარჩენი ორი გართულება ისევე სწრაფად იზრდება.

მაგალითები

მცირე რაოდენობის მონაცემებით, განსხვავება O(1) და O(n2) შორის უმნიშვნელოა. მაგალითად, ვთქვათ, თქვენ გაქვთ ალგორითმი, რომელსაც სჭირდება 2000 ელემენტის დამუშავება.

• O(1) ალგორითმი დაგიჯდებათ 1 ოპერაცია
• O(log(n)) ალგორითმი დაგიჯდებათ 7 ოპერაცია
• O(n) ალგორითმი დაგიჯდებათ 2 ოპერაცია
• O(n*log(n)) ალგორითმი დაგიჯდებათ 14 ოპერაცია
• O(n2) ალგორითმი დაგიჯდებათ 4 000 000 ოპერაცია

განსხვავება O(1) და O(n2) შორის დიდი ჩანს (4 მილიონი ოპერაცია), მაგრამ თქვენ დაკარგავთ მაქსიმუმ 2 ms-ს, მხოლოდ თვალების დახამხამების დროა. მართლაც, თანამედროვე პროცესორებს შეუძლიათ დამუშავება ასობით მილიონი ოპერაცია წამში. სწორედ ამიტომ შესრულება და ოპტიმიზაცია არ არის პრობლემა ბევრ IT პროექტში.

როგორც ვთქვი, ჯერ კიდევ მნიშვნელოვანია ამ კონცეფციის ცოდნა მონაცემთა უზარმაზარ რაოდენობასთან მუშაობისას. თუ ამჯერად ალგორითმმა უნდა დაამუშავოს 1 ელემენტი (რაც არც ისე ბევრია მონაცემთა ბაზისთვის):

• O(1) ალგორითმი დაგიჯდებათ 1 ოპერაცია
• O(log(n)) ალგორითმი დაგიჯდებათ 14 ოპერაცია
• O(n) ალგორითმი დაგიჯდებათ 1 000 000 ოპერაცია
• O(n*log(n)) ალგორითმი დაგიჯდებათ 14 000 000 ოპერაცია
• O(n2) ალგორითმი დაგიჯდებათ 1 ოპერაცია.

მათემატიკა არ გამიკეთებია, მაგრამ მე ვიტყოდი, რომ O(n2) ალგორითმით თქვენ გაქვთ დრო ყავის დასალევად (თუნდაც ორი!). თუ მონაცემთა მოცულობას კიდევ 0-ს დაამატებთ, გექნებათ დრო, რომ დაიძინოთ.

უფრო ღრმად შევიდეთ

ცნობისთვის:

• კარგი ჰეშის ცხრილის ძიება პოულობს ელემენტს O(1-ში).
• კარგად დაბალანსებული ხის ძიება იძლევა შედეგებს O(log(n)).
• მასივის ძიება იძლევა შედეგებს O(n-ში).
• საუკეთესო დახარისხების ალგორითმებს აქვთ სირთულე O(n*log(n)).
• ცუდი დახარისხების ალგორითმს აქვს სირთულე O(n2).

შენიშვნა: შემდეგ ნაწილებში ჩვენ ვიხილავთ ამ ალგორითმებს და მონაცემთა სტრუქტურებს.

ალგორითმის დროის სირთულის რამდენიმე ტიპი არსებობს:

• საშუალო შემთხვევის სცენარი
• საუკეთესო შემთხვევის სცენარი
• და ყველაზე უარესი სცენარი

დროის სირთულე ხშირად ყველაზე უარესი სცენარია.

მე მხოლოდ ალგორითმის დროის სირთულეზე ვსაუბრობდი, მაგრამ სირთულე ასევე ეხება:

• ალგორითმის მეხსიერების მოხმარება
• დისკის I/O მოხმარების ალგორითმი

რა თქმა უნდა, არის n2-ზე უარესი გართულებები, მაგალითად:

• N4: ეს საშინელებაა! ზოგიერთ ხსენებულ ალგორითმს აქვს ეს სირთულე.
• 3n: ეს კიდევ უარესია! ერთ-ერთ ალგორითმს, რომელსაც ამ სტატიის შუაში ვიხილავთ, აქვს ასეთი სირთულე (და ის რეალურად გამოიყენება მრავალ მონაცემთა ბაზაში).
• ფაქტორიული n: თქვენ ვერასდროს მიიღებთ თქვენს შედეგებს, თუნდაც მცირე რაოდენობის მონაცემებით.
• ნნ: თუ ამ სირთულეს წააწყდებით, უნდა ჰკითხოთ საკუთარ თავს, ნამდვილად არის თუ არა ეს თქვენი საქმიანობის სფერო...

შენიშვნა: მე არ მოგაწოდეთ დიდი O აღნიშვნის რეალური განმარტება, უბრალოდ იდეა. ამ სტატიის წაკითხვა შეგიძლიათ მისამართზე ვიკიპედია რეალური (ასიმპტოტური) განმარტებისთვის.

MergeSort

რას აკეთებთ, როცა გჭირდებათ კოლექციის დახარისხება? Რა? თქვენ ეძახით sort() ფუნქციას... კარგი, კარგი პასუხია... მაგრამ მონაცემთა ბაზისთვის, თქვენ უნდა გესმოდეთ, როგორ მუშაობს ეს sort() ფუნქცია.

არსებობს რამდენიმე კარგი დახარისხების ალგორითმი, ამიტომ მე ყურადღებას გავამახვილებ ყველაზე მნიშვნელოვანზე: შერწყმა დახარისხება. თქვენ შეიძლება ვერ გაიგოთ, რატომ არის მონაცემების დახარისხება სასარგებლო ახლა, მაგრამ თქვენ უნდა გაიაროთ შეკითხვის ოპტიმიზაციის ნაწილი. უფრო მეტიც, შერწყმის დალაგების გაგება დაგვეხმარება მოგვიანებით გავიგოთ საერთო მონაცემთა ბაზის შეერთების ოპერაცია, რომელსაც ეწოდება შერწყმა შეუერთდება (შერწყმის ასოციაცია).

შერწყმა

ბევრი სასარგებლო ალგორითმის მსგავსად, შერწყმის დალაგება ეყრდნობა ხრიკს: N/2 ზომის 2 დახარისხებული მასივის გაერთიანება N-ელემენტებით დალაგებულ მასივში მხოლოდ N ოპერაციებს ხარჯავს. ამ ოპერაციას გაერთიანება ეწოდება.

ვნახოთ, რას ნიშნავს ეს მარტივი მაგალითით:

ეს ფიგურა გვიჩვენებს, რომ საბოლოო დახარისხებული 8 ელემენტიანი მასივის ასაგებად, საჭიროა მხოლოდ ერთხელ გაიმეოროთ 2 4 ელემენტიანი მასივი. ვინაიდან ორივე 4 ელემენტიანი მასივი უკვე დალაგებულია:

• 1) თქვენ ადარებთ ორივე მიმდინარე ელემენტს ორ მასივში (საწყისში მიმდინარე = პირველი)
• 2) შემდეგ აიღეთ ყველაზე პატარა და ჩასვით 8 ელემენტიან მასივში
• 3) და გადადით მასივის შემდეგ ელემენტზე, სადაც აიღეთ ყველაზე პატარა ელემენტი
• და გაიმეორეთ 1,2,3 სანამ არ მიაღწევთ ერთ-ერთი მასივის ბოლო ელემენტს.
• შემდეგ თქვენ იღებთ სხვა მასივის დარჩენილ ელემენტებს, რომ მოათავსოთ ისინი 8 ელემენტიან მასივში.

ეს მუშაობს, რადგან ორივე 4 ელემენტიანი მასივი დალაგებულია და ამიტომ არ გჭირდებათ ამ მასივებში „უკან დაბრუნება“.

ახლა, როდესაც ჩვენ გავიგეთ ხრიკი, აქ არის ჩემი ფსევდოკოდი შერწყმისთვის:

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

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

შერწყმის დალაგება არღვევს პრობლემას პატარა ამოცანებად და შემდეგ პოულობს უფრო მცირე ამოცანების შედეგებს, რათა მიიღონ ორიგინალური ამოცანის შედეგი (შენიშვნა: ამ ტიპის ალგორითმს ეწოდება გაყოფა და დაპყრობა). თუ არ გესმით ეს ალგორითმი, არ ინერვიულოთ; პირველად რომ ვნახე ვერ გავიგე. თუ დაგეხმარება, მე ამ ალგორითმს ორფაზიან ალგორითმს ვხედავ:

• გაყოფის ფაზა, სადაც მასივი იყოფა პატარა მასივებად
• დახარისხების ფაზა არის პატარა მასივების გაერთიანება (კავშირის გამოყენებით) უფრო დიდი მასივის შესაქმნელად.

გაყოფის ეტაპი

გაყოფის ეტაპზე მასივი იყოფა უნიტარულ მასივებად 3 ეტაპად. საფეხურების ფორმალური რაოდენობაა log(N) (რადგან N=8, log(N) = 3).

საიდან ვიცი ეს?

მე გენიოსი ვარ! ერთი სიტყვით - მათემატიკა. იდეა იმაში მდგომარეობს, რომ თითოეული ნაბიჯი ყოფს ორიგინალური მასივის ზომას 2-ზე. ნაბიჯების რაოდენობა არის რამდენჯერაც შეგიძლიათ ორიგინალური მასივის ორად გაყოფა. ეს არის ლოგარითმის ზუსტი განმარტება (ბაზა 2).

დახარისხების ეტაპი

დახარისხების ფაზაში იწყებთ უნიტარული (ერთელემენტიანი) მასივებით. ყოველი ნაბიჯის დროს თქვენ იყენებთ რამდენიმე შერწყმის ოპერაციას და მთლიანი ღირებულებაა N = 8 ოპერაცია:

• პირველ ეტაპზე თქვენ გაქვთ 4 შერწყმა, რომელთა ღირებულებაა თითო 2 ოპერაცია
• მეორე საფეხურზე თქვენ გაქვთ 2 შერწყმა, რომელთა ღირებულება თითო 4 ოპერაციაა
• მესამე საფეხურზე თქვენ გაქვთ 1 შერწყმა, რომელიც ღირს 8 ოპერაცია

ვინაიდან არის log(N) ნაბიჯები, საერთო ღირებულება ნ * log(N) ოპერაციები.

შერწყმის დახარისხების უპირატესობები

რატომ არის ეს ალგორითმი ასეთი ძლიერი?

რადგან:

• თქვენ შეგიძლიათ შეცვალოთ ის მეხსიერების ანაბეჭდის შესამცირებლად ისე, რომ არ შექმნათ ახალი მასივები, არამედ პირდაპირ შეცვალოთ შეყვანის მასივი.

შენიშვნა: ამ ტიპის ალგორითმი ე.წ in-ადგილი (დახარისხება დამატებითი მეხსიერების გარეშე).

• თქვენ შეგიძლიათ შეცვალოთ ის, რომ გამოიყენოს დისკზე სივრცე და მეხსიერების მცირე რაოდენობა ერთდროულად, დისკის მნიშვნელოვანი I/O ზედნადების გარეშე. იდეა არის მეხსიერებაში ჩატვირთოთ მხოლოდ ის ნაწილები, რომლებიც ამჟამად მუშავდება. ეს მნიშვნელოვანია, როდესაც საჭიროა მრავალ გიგაბაიტიანი ცხრილის დახარისხება მხოლოდ 100 მეგაბაიტიანი მეხსიერების ბუფერით.

შენიშვნა: ამ ტიპის ალგორითმი ე.წ გარე დალაგება.

• თქვენ შეგიძლიათ შეცვალოთ ის, რომ იმუშაოს მრავალ პროცესზე / თემაში / სერვერზე.

მაგალითად, განაწილებული შერწყმის დალაგება ერთ-ერთი მთავარი კომპონენტია Hadoop (რაც არის სტრუქტურა დიდ მონაცემებში).

• ამ ალგორითმს შეუძლია ტყვიის ოქროდ გადაქცევა (ნამდვილად!).

ეს დახარისხების ალგორითმი გამოიყენება უმეტეს (თუ არა ყველა) მონაცემთა ბაზაში, მაგრამ ეს არ არის ერთადერთი. თუ გსურთ მეტი იცოდეთ, შეგიძლიათ წაიკითხოთ ეს კვლევითი სამუშაო, რომელშიც განხილულია მონაცემთა ბაზის დახარისხების საერთო ალგორითმების დადებითი და უარყოფითი მხარეები.

მასივი, ხე და ჰეშ ცხრილი

ახლა, როდესაც ჩვენ გვესმის დროის სირთულის და დახარისხების იდეა, უნდა გითხრათ მონაცემთა 3 სტრუქტურის შესახებ. ეს მნიშვნელოვანია, რადგან ისინი თანამედროვე მონაცემთა ბაზების საფუძველია. მეც გავაცნობ კონცეფციას მონაცემთა ბაზის ინდექსი.

Array

ორგანზომილებიანი მასივი არის მონაცემთა უმარტივესი სტრუქტურა. ცხრილი შეიძლება ჩაითვალოს მასივად. Მაგალითად:

ეს 2 განზომილებიანი მასივი არის ცხრილი რიგებით და სვეტებით:

• თითოეული ხაზი წარმოადგენს ერთეულს
• სვეტები ინახავს თვისებებს, რომლებიც აღწერს ერთეულს.
• თითოეული სვეტი ინახავს კონკრეტული ტიპის მონაცემებს (მთლიანი, სტრიქონი, თარიღი...).

ეს მოსახერხებელია მონაცემების შესანახად და ვიზუალიზაციისთვის, თუმცა, როდესაც საჭიროა კონკრეტული მნიშვნელობის პოვნა, ეს არ არის შესაფერისი.

მაგალითად, თუ გინდოდათ იპოვოთ ყველა ბიჭი, რომელიც მუშაობს დიდ ბრიტანეთში, თქვენ უნდა გადახედოთ თითოეულ რიგს, რათა დადგინდეს, ეკუთვნის თუ არა ეს რიგი გაერთიანებულ სამეფოს. N ტრანზაქცია დაგიჯდებათსად N - ხაზების რაოდენობა, რაც არ არის ცუდი, მაგრამ შეიძლება არსებობდეს უფრო სწრაფი გზა? ახლა დროა გავეცნოთ ხეებს.

შენიშვნა: თანამედროვე მონაცემთა ბაზების უმეტესობა გთავაზობთ გაფართოებულ მასივებს ცხრილების ეფექტურად შესანახად: heap-ორგანიზებული ცხრილები და ინდექსით ორგანიზებული ცხრილები. მაგრამ ეს არ ცვლის სვეტების ჯგუფში კონკრეტული მდგომარეობის სწრაფად პოვნის პრობლემას.

მონაცემთა ბაზის ხე და ინდექსი

ორობითი საძიებო ხე არის ორობითი ხე სპეციალური თვისებით, გასაღები თითოეულ კვანძში უნდა იყოს:

• მარცხენა ქვეხეში შენახულ ყველა კლავიშზე მეტი
• ნაკლებია, ვიდრე ყველა გასაღები, რომელიც ინახება მარჯვენა ქვეხეში

ვნახოთ რას ნიშნავს ეს ვიზუალურად

იდეა

ამ ხეს აქვს N = 15 ელემენტი. ვთქვათ, ვეძებ 208:

• ვიწყებ ფესვიდან, რომლის გასაღები არის 136. 136<208 წლიდან ვუყურებ 136-ე კვანძის მარჯვენა ქვეხეს.
• 398>208 ამიტომ მე ვუყურებ 398 კვანძის მარცხენა ქვეხეს
• 250>208 ამიტომ მე ვუყურებ 250 კვანძის მარცხენა ქვეხეს
• 200<208, ამიტომ მე ვუყურებ 200-ე კვანძის მარჯვენა ქვეხეს. მაგრამ 200-ს არ აქვს მარჯვენა ქვეხე, ღირებულება არ არსებობს (რადგან თუ ის არსებობს, ის იქნება მარჯვენა ქვეხეში 200).

ახლა ვთქვათ, ვეძებ 40-ს

• ვიწყებ ფესვიდან, რომლის გასაღები არის 136. ვინაიდან 136 > 40, მე ვუყურებ 136-ე კვანძის მარცხენა ქვეხეს.
• 80 > 40, ამიტომ მე ვუყურებ კვანძის 80-ის მარცხენა ქვეხეს
• 40 = 40, კვანძი არსებობს. ვიღებ მწკრივის ID-ს კვანძის შიგნით (სურათზე არ არის ნაჩვენები) და ვეძებ ცხრილში მოცემულ მწკრივის ID-ს.
• მწკრივის ID-ის ცოდნა საშუალებას მაძლევს ზუსტად ვიცოდე, სად არის მონაცემები ცხრილში, ასე რომ შემიძლია მომენტალურად მოვიძიო.

საბოლოო ჯამში, ორივე ძიება დამიჯდება ხის შიგნით დონეების რაოდენობა. თუ ყურადღებით წაიკითხავთ ნაწილს შერწყმის დალაგების შესახებ, უნდა დაინახოთ, რომ არსებობს log(N) დონეები. თურმე, საძიებო ხარჯების ჟურნალი (N), ცუდი არაა!

დავუბრუნდეთ ჩვენს პრობლემას

მაგრამ ეს ძალიან აბსტრაქტულია, ამიტომ დავუბრუნდეთ ჩვენს პრობლემას. მარტივი მთელი რიცხვის ნაცვლად, წარმოიდგინეთ სტრიქონი, რომელიც წარმოადგენს ვინმეს ქვეყანას წინა ცხრილში. ვთქვათ, გაქვთ ხე, რომელიც შეიცავს ცხრილის "ქვეყანა" ველს (სვეტი 3):

• თუ გსურთ იცოდეთ ვინ მუშაობს დიდ ბრიტანეთში
• თქვენ უყურებთ ხეს, რომ მიიღოთ კვანძი, რომელიც წარმოადგენს დიდ ბრიტანეთს
• "UKnode"-ში ნახავთ გაერთიანებული სამეფოს მუშაკთა ჩანაწერების ადგილმდებარეობას.

ეს ძიება ეღირება log(N) ოპერაციები N ოპერაციების ნაცვლად, თუ თქვენ იყენებთ მასივს პირდაპირ. რაც ახლა წარმოადგინეთ იყო მონაცემთა ბაზის ინდექსი.

თქვენ შეგიძლიათ შექმნათ ინდექსის ხე ველების ნებისმიერი ჯგუფისთვის (სტრიქონი, რიცხვი, 2 სტრიქონი, რიცხვი და სტრიქონი, თარიღი...), თუ თქვენ გაქვთ კლავიშების შედარების ფუნქცია (ანუ ველების ჯგუფები), ასე რომ თქვენ შეგიძლიათ დააყენოთ შეკვეთა გასაღებებს შორის (რაც ეხება მონაცემთა ბაზაში არსებულ ნებისმიერ ძირითად ტიპს).

B+TreeIndex

მიუხედავად იმისა, რომ ეს ხე კარგად მუშაობს კონკრეტული მნიშვნელობის მისაღებად, არის დიდი პრობლემა, როდესაც გჭირდებათ მიიღეთ მრავალი ელემენტი ორ მნიშვნელობას შორის. ეს ეღირება O(N), რადგან თქვენ მოგიწევთ ხის თითოეულ კვანძში დათვალიერება და შეამოწმოთ არის თუ არა ის ამ ორ მნიშვნელობას შორის (მაგ. ხის მოწესრიგებული გადაკვეთით). უფრო მეტიც, ეს ოპერაცია არ არის დისკის I/O მეგობრული, რადგან თქვენ უნდა წაიკითხოთ მთელი ხე. ჩვენ უნდა ვიპოვოთ ეფექტური განხორციელების გზა დიაპაზონის მოთხოვნა. ამ პრობლემის გადასაჭრელად თანამედროვე მონაცემთა ბაზები იყენებენ წინა ხის შეცვლილ ვერსიას, სახელწოდებით B+Tree. B+Tree ხეში:

• მხოლოდ ყველაზე დაბალი კვანძები (ფოთლები) ინფორმაციის შენახვა (სტრიქონების მდებარეობა შესაბამის ცხრილში)
• დანარჩენი კვანძები აქ არის მარშრუტიზაციისთვის სწორ კვანძამდე ძიების დროს.

როგორც ხედავთ, აქ უფრო მეტი კვანძია (ორჯერ). მართლაც, თქვენ გაქვთ დამატებითი კვანძები, "გადაწყვეტილების კვანძები", რომლებიც დაგეხმარებათ იპოვოთ სწორი კვანძი (რომელიც ინახავს რიგების მდებარეობას ასოცირებულ ცხრილში). მაგრამ ძიების სირთულე მაინც არის O(log(N)) (არსებობს კიდევ ერთი დონე). დიდი განსხვავება ისაა ქვედა დონეზე კვანძები დაკავშირებულია მათ მემკვიდრეებთან.

ამ B+Tree-ით, თუ ეძებთ მნიშვნელობებს 40-დან 100-მდე:

• თქვენ უბრალოდ უნდა მოძებნოთ 40 (ან უახლოესი მნიშვნელობა 40-ის შემდეგ, თუ 40 არ არსებობს), როგორც ეს გააკეთეთ წინა ხეზე.
• შემდეგ შეაგროვეთ 40 მემკვიდრე პირდაპირი მემკვიდრე ბმულების გამოყენებით, სანამ არ მიაღწევთ 100-ს.

ვთქვათ, თქვენ იპოვით M მემკვიდრეებს და ხეს აქვს N კვანძი. კონკრეტული კვანძის პოვნა ღირს log(N) წინა ხის მსგავსად. მაგრამ როგორც კი მიიღებთ ამ კვანძს, მიიღებთ M მემკვიდრეებს M ოპერაციებში მათი მემკვიდრეების მითითებით. ამ ძიების ღირებულება მხოლოდ M+log(N) ოპერაციები წინა ხეზე N ოპერაციებთან შედარებით. უფრო მეტიც, თქვენ არ გჭირდებათ სრული ხის წაკითხვა (მხოლოდ M+log(N) კვანძები), რაც ნიშნავს დისკის ნაკლებ გამოყენებას. თუ M არის პატარა (მაგ. 200 მწკრივი) და N დიდი (1 მწკრივი), იქნება დიდი განსხვავება.

მაგრამ აქ არის ახალი პრობლემები (ისევ!). თუ დაამატებთ ან წაშლით რიგს მონაცემთა ბაზაში (და, შესაბამისად, ასოცირებულ B+Tree ინდექსში):

• თქვენ უნდა შეინარჩუნოთ წესრიგი კვანძებს შორის B+Tree-ის შიგნით, წინააღმდეგ შემთხვევაში თქვენ ვერ შეძლებთ კვანძების პოვნა დაუხარისხებელი ხის შიგნით.
• თქვენ უნდა შეინარჩუნოთ დონეების მინიმალური რაოდენობა B+Tree-ში, წინააღმდეგ შემთხვევაში O(log(N)) დროის სირთულე ხდება O(N).

სხვა სიტყვებით რომ ვთქვათ, B+Tree უნდა იყოს თვითმოწესრიგებული და დაბალანსებული. საბედნიეროდ, ეს შესაძლებელია ჭკვიანი წაშლისა და ჩასმის ოპერაციებით. მაგრამ ამას ფასი აქვს: B+ ხეში ჩასმა და წაშლა ღირს O(log(N)). ამიტომ ზოგიერთ თქვენგანს ეს გსმენიათ ძალიან ბევრი ინდექსის გამოყენება არ არის კარგი იდეა. მართლაც, თქვენ ანელებთ ცხრილის მწკრივის სწრაფ ჩასმა/განახლება/წაშლასრადგან მონაცემთა ბაზას სჭირდება ცხრილის ინდექსების განახლება ძვირადღირებული O(log(N)) ოპერაციის გამოყენებით თითოეული ინდექსისთვის. უფრო მეტიც, ინდექსების დამატება ნიშნავს მეტ დატვირთვას ტრანზაქციის მენეჯერი (აღწერილი იქნება სტატიის ბოლოს).

დამატებითი ინფორმაციისთვის შეგიძლიათ იხილოთ ვიკიპედიის სტატია B+ხე. თუ გსურთ მონაცემთა ბაზაში B+Tree-ის დანერგვის მაგალითი, შეხედეთ ამ მუხლის и ამ მუხლის წამყვანი MySQL დეველოპერისგან. ორივე მათგანი ყურადღებას ამახვილებს იმაზე, თუ როგორ ამუშავებს InnoDB (MySQL ძრავა) ინდექსებს.

შენიშვნა: მკითხველმა მითხრა, რომ დაბალი დონის ოპტიმიზაციის გამო, B+ ხე მთლიანად უნდა იყოს დაბალანსებული.

ჰეშტაბი

ჩვენი ბოლო მნიშვნელოვანი მონაცემთა სტრუქტურა არის ჰეშის ცხრილი. ეს ძალიან სასარგებლოა, როდესაც გსურთ სწრაფად მოძებნოთ მნიშვნელობები. უფრო მეტიც, ჰეშის ცხრილის გაგება დაგვეხმარება მოგვიანებით გავიგოთ მონაცემთა ბაზის შეერთების საერთო ოპერაცია, რომელსაც ეწოდება ჰეშის შეერთება ( ჰაში შეერთება). მონაცემთა ამ სტრუქტურას ასევე იყენებს მონაცემთა ბაზა ზოგიერთი შიდა ნივთების შესანახად (მაგ. საკეტი მაგიდა ან ბუფერული აუზიორივე ამ კონცეფციას მოგვიანებით ვიხილავთ).

ჰეშის ცხრილი არის მონაცემთა სტრუქტურა, რომელიც სწრაფად პოულობს ელემენტს მისი გასაღებით. ჰეშის ცხრილის ასაგებად თქვენ უნდა განსაზღვროთ:

• ნახავ თქვენი ელემენტებისთვის
• ჰეშის ფუნქცია გასაღებებისთვის. გასაღების გამოთვლილი ჰეშები იძლევა ელემენტების მდებარეობას (ე.წ სეგმენტები ).
• გასაღებების შედარების ფუნქცია. მას შემდეგ რაც იპოვნეთ სწორი სეგმენტი, თქვენ უნდა იპოვოთ ელემენტი, რომელსაც ეძებთ სეგმენტში ამ შედარების გამოყენებით.

მარტივი მაგალითი

ავიღოთ ნათელი მაგალითი:

ამ ჰეშის ცხრილს აქვს 10 სეგმენტი. იმიტომ რომ ზარმაცი ვარ, მხოლოდ 5 სეგმენტი დავხატე, მაგრამ ვიცი, რომ ჭკვიანი ხარ, ამიტომ დანარჩენ 5-ს დამოუკიდებლად გამოგყვები. მე გამოვიყენე კლავიშის ჰეშის ფუნქციის მოდული 10. სხვა სიტყვებით რომ ვთქვათ, მე ვინახავ ელემენტის გასაღების მხოლოდ ბოლო ციფრს მისი სეგმენტის საპოვნელად:

• თუ ბოლო ციფრი არის 0, ელემენტი ხვდება 0 სეგმენტში,
• თუ ბოლო ციფრი არის 1, ელემენტი ხვდება 1 სეგმენტში,
• თუ ბოლო ციფრი არის 2, ელემენტი ხვდება 2-ში,
• ...

შედარების ფუნქცია, რომელიც მე გამოვიყენე, არის უბრალოდ ტოლობა ორ მთელ რიცხვს შორის.

ვთქვათ, გსურთ მიიღოთ ელემენტი 78:

• ჰეშის ცხრილი ითვლის ჰეშის კოდს 78-ისთვის, რაც არის 8.
• ჰეშის ცხრილი უყურებს მე-8 სეგმენტს და პირველი ელემენტი, რომელიც მას პოულობს, არის 78.
• ის გიბრუნებს 78-ე პუნქტს
• ძებნა ღირს მხოლოდ 2 ოპერაცია (ერთი ჰეშის მნიშვნელობის გამოსათვლელად და მეორე სეგმენტში ელემენტის მოსაძებნად).

ახლა ვთქვათ, რომ გსურთ მიიღოთ ელემენტი 59:

• ჰეშის ცხრილი ითვლის ჰეშის კოდს 59-ისთვის, რაც არის 9.
• ჰეშის ცხრილი ეძებს მე-9 სეგმენტში, პირველი ნაპოვნი ელემენტი არის 99. ვინაიდან 99!=59, ელემენტი 99 არ არის სწორი ელემენტი.
• იგივე ლოგიკით აღებულია მეორე ელემენტი (9), მესამე (79), ..., ბოლო (29).
• ელემენტი ვერ მოიძებნა.
• ძებნა 7 ოპერაცია დაჯდა.

კარგი ჰეშის ფუნქცია

როგორც ხედავთ, ღირებულებიდან გამომდინარე, რომელსაც ეძებთ, ღირებულება არ არის იგივე!

თუ ახლა შევცვლი კლავიშის 1 მოდულის ჰეშის ფუნქციას (ანუ ბოლო 000 ციფრის აღება), მეორე ძიება მხოლოდ 000 ოპერაცია ღირს, რადგან 6 სეგმენტში ელემენტები არ არის. რეალური გამოწვევა არის კარგი ჰეშის ფუნქციის პოვნა, რომელიც შექმნის თაიგულებს, რომლებიც შეიცავს ძალიან მცირე რაოდენობის ელემენტებს.

ჩემს მაგალითში კარგი ჰეშის ფუნქციის პოვნა მარტივია. მაგრამ ეს მარტივი მაგალითია, კარგი ჰეშის ფუნქციის პოვნა უფრო რთულია, როდესაც გასაღები არის:

• სტრიქონი (მაგალითად - გვარი)
• 2 სტრიქონი (მაგალითად - გვარი და სახელი)
• 2 სტრიქონი და თარიღი (მაგალითად - გვარი, სახელი და დაბადების თარიღი)
• ...

ჰეშის კარგი ფუნქციით, ჰეშის ცხრილების ძიება ღირს O(1).

მასივი ჰეშის ცხრილის წინააღმდეგ

რატომ არ გამოიყენოთ მასივი?

ჰმ, კარგი კითხვაა.

• ჰეშის ცხრილი შეიძლება იყოს ნაწილობრივ დატვირთულია მეხსიერებაშიდა დარჩენილი სეგმენტები შეიძლება დარჩეს დისკზე.
• მასივის საშუალებით თქვენ უნდა გამოიყენოთ მიმდებარე სივრცე მეხსიერებაში. თუ ატვირთავთ დიდ მაგიდას ძალიან რთულია საკმარისი უწყვეტი სივრცის პოვნა.
• ჰეშის ცხრილისთვის შეგიძლიათ აირჩიოთ თქვენთვის სასურველი გასაღები (მაგალითად, ქვეყანა და პირის გვარი).

დამატებითი ინფორმაციისთვის შეგიძლიათ წაიკითხოთ სტატია JavaHashMap, რომელიც არის ჰეშის ცხრილის ეფექტური განხორციელება; თქვენ არ გჭირდებათ Java-ს გაგება ამ სტატიაში მოცემული ცნებების გასაგებად.

წყარო: www.habr.com