İndekslərin işləmə prinsipləri: verilənlər strukturu və axtarış alqoritmləri

Bu gün indekslərin arxitekturasına bir az daha dərindən baxacağıq və onların əslində necə işlədiyini araşdıracağıq. Çünki indeksin quruluşunu bilmək təkcə sorğuların niyə daha sürətli işlədiyini başa düşmək üçün yox, həm də müxtəlif tapşırıqlar üçün optimal indeksləri necə seçmək lazım olduğunu anlamağa kömək edir.

İndeksin strukturu deyəndə, məlumatların indeksin içində necə təşkil olunduğu nəzərdə tutulur ki, bu da sürətli axtarışı təmin edir. Təsəvvür elə sənədlərlə dolu bir şkaf var. Əgər sənədlər sadəcə bir yerdə qarışıq halda yığılıbsa, lazımi sənədi tapmaq çətin olacaq. Amma əgər şkaf əlifba sırası ilə düzülüb, axtarış xeyli asanlaşır. İndekslər də məhz belə işləyir: məlumatları elə qaydada düzürlər ki, lazım olan informasiyanı tapmaq maksimum dərəcədə tez baş versin.

B-TREE indeksinin strukturu

B-TREE (balanced tree — balanslaşdırılmış ağac) PostgreSQL-də ən çox istifadə olunan indeks növüdür. Əslində bu, ağac tipli bir strukturdur, burada məlumatlar düyünlərdə (node) təşkil olunur və axtarış kök düyündən (root) yarpaqlara (leaf) doğru gedir.

Bu necə görünür:

         Kok
          /       |       \
      Duyun 1    Duyun 2    Duyun 3
     /   \       |       /   \
Yarpaq1 Yarpaq2   Yarpaq3  Yarpaq4 Yarpaq5

Hər bir düyün axtarışa istiqamət verən açar dəyərləri saxlayır. Məsələn, əgər kök düyündə [10, 20, 30] dəyərləri varsa:

• Bütün 10-dan kiçik məlumatlar Yarpaq 1-dədir.
• 10 ilə 20 arasında olanlar — Yarpaq 2-də və s.

B-TREE indeksinin üstünlükləri:

• Məlumatların sürətli axtarışı: axtarışın mürəkkəbliyi O(log n) olur, bu da xətti axtarışdan xeyli sürətlidir.
• Aralıq (range) axtarış üçün uyğundur (məsələn, 10 ilə 50 arasındakı bütün dəyərləri tapmaq).

Nümunə: tutaq ki, bizdə students adlı cədvəl var və age sütunu mövcuddur. Bu sütunda B-TREE indeksi yaradırıq:

CREATE INDEX age_idx ON students (age);

PostgreSQL yaş dəyərləri üçün balanslaşdırılmış ağac yaradır və bu, müəyyən yaşda və ya yaş aralığında olan tələbələri tez tapmağa imkan verir.

B-TREE-də axtarış alqoritmi

Sən sorğu göndərəndə, PostgreSQL indeksi belə istifadə edir:

1. Axtarış açarını müəyyən edir (məsələn, yaş 25).
2. Kök düyündən başlayır.
3. Açarı düyünün dəyərləri ilə müqayisə edir və uyğun alt düyünə keçir.
4. 3-cü addımı təkrarlayır, ta ki yarpağa çatana qədər.
5. Açarla uyğun gələn məlumatları yarpaqdan qaytarır.

Sorğu nümunəsi:

SELECT * FROM students WHERE age = 25;

İndeks skan ediləcək məlumatların sayını azaldır və sürətli axtarış təmin edir.

Axtarış alqoritmləri və performans

İndekslər axtarışı sürətləndirir, çünki skan edilməli olan sətirlərin sayını azaldır. İndeks olmadan PostgreSQL bütün cədvəli skan edir (buna ardıcıl skan və ya Seq Scan deyilir). İndeks olduqda isə indeks skanı (Index Scan) baş verir və bu, xeyli sürətlidir.

Ardıcıl və indeks skanının müqayisəsi

• Ardıcıl skan (Seq Scan):

  • PostgreSQL cədvəldəki hər sətri oxuyur, sorğunun şərtlərini yoxlayır və uyğun gələn sətirləri qaytarır.
  • İndeks yoxdursa və ya sorğu demək olar ki, bütün cədvəli əhatə edirsə istifadə olunur.

• İndeks skanı (Index Scan):

  • PostgreSQL uyğun sətirləri tapmaq üçün indeksi istifadə edir və yalnız onlar üçün cədvələ müraciət edir.
  • Böyük cədvəllərdə, sorğu az sayda məlumatı əhatə edirsə, xeyli sürətlidir.

Nümunə: indeks olmadan yaş axtarışı

SELECT * FROM students WHERE age = 25;

nəticədə bəlkə də 1 milyon sətrin oxunması lazım olacaq. B-TREE indeksi ilə sistem, məsələn, cəmi 100 sətri oxuyur.

İndeks strukturunun performansa təsiri

İndekslər ona görə sürətlidir ki, skan edilən məlumatların həcmini azaldır. Məsələn, cədvəldə milyonlarla sətr varsa, indeks onları elə təşkil edir ki, sorğu yalnız bir neçə düyünü oxuyur, bütün cədvəli yox.

İndeksin strukturunu başa düşmək çox vacibdir. İndekslərin necə işlədiyini bilmək, niyə bəzi sorğuların yavaş getdiyini və onları necə sürətləndirmək lazım olduğunu anlamağa kömək edir.

Bundan əlavə, hansı indeksin lazım olduğunu başa düşmək də vacibdir. Aralıq axtarış üçün B-TREE uyğundur. Massivlər və ya JSONB üçün — GIN. Yanlış indeks seçimi database-i yavaşdırır.

Real nümunələr

Gəlin baxaq, indekslər bizə işdə necə kömək edir.

Sıralama üçün indeks

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

B-TREE indeksi ilə PostgreSQL məlumatları birbaşa indeksdən sıralanmış şəkildə qaytara bilir, əlavə sort olmadan.

Aralıq üçün indeks

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

B-TREE indeksi verilmiş aralığa düşən sətirləri tez tapmağa imkan verir.

Tez-tez verilən suallar və tələlər

Niyə həmişə indeks istifadə etmək olmaz? İndekslər diskdə yer tutur və insert, update, delete əməliyyatlarını yavaşladır, çünki indeks strukturu da yenilənməlidir. Ona görə də indeksləri yalnız tez-tez istifadə olunan sütunlar üçün yaratmaq lazımdır.

İndekslər nə vaxt kömək etmir? Əgər sorğu cədvəlin böyük hissəsini əhatə edirsə (məsələn, WHERE true), PostgreSQL Seq Scan seçir, çünki indeks düyünlərini oxumaq üstünlük vermir.