DBMS-də çeşidləmə metodu

Qeydlərin bir və ya daha çox sütunun artan və ya azalan qaydada saxlanılması üsuludur. Faydalıdır, çünki bəzi sorğular bizdən sıralanmış qeydləri qaytarmağımızı xahiş edəcək və ya birləşmə kimi əməliyyatlar sıralanmış qeydlərdə daha təsirli olacaq. Bütün qeydlər default olaraq əsas açar sütununa əsasən sıralanır. Bundan əlavə, qeydləri tələb olunduğu kimi digər sütunlara əsasən sıralamaq üçün təyin edə bilərik. Əsasən iki növ çeşidləmə metodundan istifadə olunur.

Tez Sort

Bir cədvəl ölçüsü kiçikdirsə və cari yaddaşa yerləşdirilə bilərsə, sürətli sort istifadə edilə bilər. Adından da göründüyü kimi çeşidləmə sadə və asandır. Bu metodda sütun dəyərləri arasında bir dönmə elementi müəyyən edilir və dönmə elementi pivotun soluna, dönmə elementlərindən daha böyük isə pivotun sağına köçürülür. Sıralamaq üçün çox az əlavə yer (n log (n)) tələb olunur. Ən yaxşı halda sıralamaq üçün yalnız n log (n) vaxt, ən pis halda yalnız n2 vaxt lazımdır. Ancaq bu metod daha az sabitdir, çünki çeşidləmə zamanı iki oxşar qeydin vəziyyətini dəyişdirə bilər.

Birləşdir Sort

Daha böyük üçün masaları cari yaddaşa yerləşdirilə bilməyən bu cür çeşidləmə istifadə olunur. Sürətli çeşidləmə ilə müqayisədə daha yaxşı performansa malikdir. Bu növün necə edilə biləcəyini görək.

Tutaq ki, hər blokda iki qeyd, yaddaşda isə 2 blok saxlaya bilər. Yəni yaddaş böyük cədvəllərin bütün qeydlərini saxlaya bilməz; yalnız 4 qeyd edə bilər. Tutaq ki, ilk cədvəldə hər blokda iki qeyd olan 12 qeyd var. Birləşdirmə növü tətbiq edildikdə, qeydlər hər biri iki blok olmaqla 3-ə bölünür. Hər blok keçid 1-də birləşdirilir və keçid 2 üçün sıralanır, burada yenidən birləşdirilir və çeşidlənir. Son mərhələdə keçid 2-dəki bloklar birləşdirilir və son nəticəni vermək üçün sıralanır. Birləşdirmə növü bu şəkildə işləyir.

Tutaq ki, bir yaddaş M blokları saxlaya bilər və N (bizim vəziyyətimizdə R3-dan R0-ə qədər 2 ötürmə) ilkin işləmə sayı ola bilər. Birləşdirmə növü başladıldıqda, M qeydlərini davamlı oxuyur, sıralayır və Ri olaraq saxlayır. Blokları N dəfə oxuyur və sıralayır və RN qaçışları yaradır.
Yuxarıdakı nümunəmizdə yaddaş 2 blok məlumat saxlaya bilər. Birləşdirmə sortu başladıldıqda, sıralamaq üçün hər biri 2 blok məlumatı oxuyur və sonra R0-dan R2-yə kimi 3 qaçış yaradaraq saxlanılır.

İndi işi nəzərdən keçirin

N <M

Bu vəziyyətdə, hər bir işi saxlamaq üçün N yaddaş blokunu və son çıxışı üçün birini istifadə edir. yəni; fərz edək ki, blok ölçüsü M = 4 və başlanğıc cədvəldəki qeydlərin ümumi sayı 16-dır və hər blok yalnız 2 qeyd saxlaya bilər, onda ilkin mərhələdə 2 işimiz olacaq. yəni; N

N blok sıralanana və boşaldılıncaya qədər aşağıdakı addımları təkrarlayacaqdır

  • Giriş girişlərindən ən kiçik qeydləri seçin və çıxış blokuna yazın. . Sonra ən kiçik qeydləri müvafiq run blokundan silər. yəni; yuxarıdakı hər iki qaçışda da ən kiçik qeydləri axtarır və çıxış blokunda saxlayır - ilk addım (1, e) çıxış blokunda saxlanılır və R0-dan çıxarılır.
  • Çıxış bloku doludursa, diski yeniləyin və çıxış blokunu boşaltın.

N> = M

Bu vəziyyətdə blokları dəfələrlə birləşdirməliyik. M-1 qaçışları hər keçiddə birləşdirilir və sıralanır. Hər bir birləşmə M-1 ilə işləmə sayını azaldacaq.

Yuxarıdakı ilk nümunəmizdə,
Yaddaşın saxlaya biləcəyi blok sayı (M) = 2
Sıfırdan ikiyə başlayaraq ilkin qaçışların sayı (N) = 3.
Beləliklə birləşmə keçidlərinin sayı = M-1 = 1 → R1 → R0 və R1 birləşdirilir və sıralanır. İkinci blokda yalnız R2 qalır və sıralanır.
Hər keçiddə birləşmə blok sayını = M-1 = 1 → 2 azaldır, çünki sayma sıfırdan başlayır.

Birləşdirmə sortunun işi belədir. Bu metodda sorğunun qiymətini görək.

Axtarışın ümumi sayı

  • Başlanğıcda birinin qeydləri oxumağa, birinin isə hər dövrdə qeydlərin saxlanmasına ehtiyac var. Buna görə hər bir iş üçün 2B / M axtarma tələb olunur. yəni; blokdakı qeydləri ən kiçik qeyd üçün axtarmalı və yaddaş blokunda saxlamalıdır. Buna görə qeydləri oxumaq və yazmaq üçün hər birinin axtardığını tələb edir.
  • Birləşmə keçidi axtarma sayı = 2B / NB, burada NB oxunan və saxlanılan blokların sayıdır.
  • Beləliklə, axtarışın ümumi sayı = 2B / M + (B / NB) (2logM-1 (B / M) -1)

Blok köçürməsinin ümumi sayı

  • Əvvəlcə bunu tələb edir B / M çeşidlənməmiş məlumatları yaddaş bloklarına paylamaq üçün çalışır, burada B ilkin cədvəldəki blokların ümumi sayıdır. N zaman = M → 2> 4, 8/4 = 2 qaçış keçirdik.
  • İlkin qaçışların yaradılması hər blok üçün oxunma və yazma tələb olunur və bu səbəbdən blok köçürmə sayı 2B-dir. . N zaman = M → 2> 4, 2 * 8 = 16 blok köçürməmiz var idi.
  • Tələb edir logm-1 (B / M) qeydləri birləşdirmək və sıralamaq üçün birləşmə keçir. N zaman log3 (2) = 1və N> = M → 3> 2 olduqda giriş 1 (3) birləşmə keçir.
  • Hər keçid oxunmalı və sıralanmış qeydləri yaddaşa yazmalıdır. Saxlanılması tələb olunmayacağı və birbaşa istifadəçiyə göndərilə biləcəyi üçün son nəticə yazısı laqeyd edilə bilər. Buna görə blok köçürmə = 2B olacaqdır.
  • Beləliklə, birləşmə növü üçün blok köçürməsinin ümumi sayı = B * (2 logm-1 (B / M) +1)

Şərh yaz

Translate »