PostgreSQL indeks: B-tree ichidan, Seq Scan va Index Scan

Qisqacha: Indeks — jadval ustuni qiymatlarining tartiblangan nusxasi va har qiymat qaysi qatorda turgani haqidagi ko'rsatkich. Indekssiz Postgres qidirish uchun butun jadvalni varaqlaydi (Seq Scan), indeks bilan esa daraxt bo'ylab bir necha qadamda kerakli joyga tushadi (Index Scan). Postgres'ning asosiy indeksi — B-tree: kanon o'lchovida 2 mln qatorli jadvalda matn = '…' qidiruvi indekssiz 150 ms (39 493 sahifa), indeks bilan 0.08 ms (3 sahifa). Narxi — disk joyi (94 MB) va har yozuvda indeksni yangilash.

Bu darsda

• Indekssiz qidiruv (full scan) nega sekin ekanini sahifalar bilan tushuntirasiz.
• B-tree tuzilishini — ildiz, ichki sahifalar, barglar — chizib bera olasiz.
• CREATE INDEX bilan indeks yaratasiz va EXPLAIN da Seq Scan va Index Scan ni ajratasiz.
• Indeks qachon ishlatilmasligini (ko'p qator qaytadigan shart) bilasiz.
• Indeksning narxini (hajm, yozish) aytasiz.

Oldin bilishingiz kerak: SELECT va WHERE, MVCC: Postgres ichida versiyalar, Ikkilik qidiruv.

1. Nega bu kerak?

Telefon kitobini tasavvur qiling — 2 mln ism, tartibsiz, kim qachon yozilgan bo'lsa shunday. "Karimova Malika"ning raqamini topish uchun boshidan oxirigacha varaqlashga to'g'ri keladi. Endi xuddi shu kitob alifbo tartibida: siz o'rtasini ochasiz, "K" dan keyinmi-oldinmi qaraysiz, yarmini tashlaysiz — va 20–25 qadamda topasiz. Bu ikkilik qidiruv g'oyasi.

Jadval — tartibsiz kitob. Qatorlar diskda kelgan tartibda yotadi (MVCC darsida ko'rdik: UPDATE qatorni yangi joyga ham ko'chiradi). Indeks — kitobning oxiridagi alifbo ko'rsatkichi: "Karimova — 312-bet". Ko'rsatkich tartiblangan va kichik, unda qidirish tez; topilgach, to'g'ri sahifaga o'tasiz.

vazifalar ilovasi o'sib, 2 mln vazifaga yetdi deylik. Foydalanuvchi qidiruv maydoniga vazifa matnini yozdi. Indekssiz har qidiruv butun jadvalni o'qiydi. Kanon buni aynan o'lchagan — keling, raqamlarga qaraymiz.

Maslahat: Bu va keyingi indeks darslarining katta raqamlari — kanonning katta bazasidan: yakuniy vazifalar sxemasi + 2 000 000 vazifa, 20 000 foydalanuvchi (PostgreSQL 18.6, Docker Desktop, Windows 11, i5-12500H). Bunday bazani darsda takrorlash shart emas — vaqtlar baribir mashinaga bog'liq. Bu o'lchovlar sxemaning 012-fayldagi holatida olingan (qurish logi katta-qurish-012.txt). Keyinroq API uchun 013 va 014 fayllari qo'shilib, katta baza qayta qurildi; "Node qadami" bo'limlaridagi reja raqamlari o'sha yangi bazadan (reja-64.txt) — bu alohida o'lchov. Kichik misollarni (100 000 qator) esa o'zimiz ishga tushirdik — ularni siz ham bir necha soniyada takrorlaysiz.

2. Sahifa va full scan

2.1 Jadval — 8 KB lik sahifalar

Postgres jadvalni diskda sahifa (page, block) larga bo'lib saqlaydi — har biri 8 192 bayt. Har sahifada bir necha o'nlab qator. Diskdan har doim butun sahifa o'qiladi, bitta qator emas. Kanon bazasidagi vazifalar jadvali:

SELECT pg_size_pretty(pg_relation_size('vazifalar')) AS jadval,
       pg_relation_size('vazifalar') / 8192 AS sahifalar,
       current_setting('block_size') AS sahifa_bayt;

Natija (kanon, 56-indeks.txt):

 jadval | sahifalar | sahifa_bayt
--------+-----------+-------------
 309 MB |     39493 | 8192
(1 row)

309 MB — 39 493 ta sahifa. vazifalar ning id sida indeks bor (primary key), matn da esa — yo'q.

2.2 Indekssiz qidiruv

Natijada uchta narsaga qarang: Seq Scan so'zi, Buffers dagi sahifalar soni va oxirgi Execution Time. Telefonda sig'ishi uchun kanon chiqishidagi cost=… qavslari qisqartirilgan — raqamlar o'zgarmagan.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM vazifalar WHERE matn = 'Hisobot yozish 1500000 #ish';

Natija (kanon, qisqartirildi):

 Gather (actual time=146.705..149.702 rows=0.00 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   Buffers: shared hit=1328 read=38165
   I/O Timings: shared read=174.028
   ->  Parallel Seq Scan on vazifalar (actual time=142.676..142.676 rows=0.00 loops=3)
         Filter: (matn = 'Hisobot yozish 1500000 #ish'::text)
         Rows Removed by Filter: 666667
         Buffers: shared hit=1328 read=38165
         I/O Timings: shared read=174.028
 Planning:
   Buffers: shared hit=152 read=1
   I/O Timings: shared read=0.013
 Planning Time: 0.684 ms
 Execution Time: 149.726 ms
(15 rows)

Bu so'rov rejasi (query plan) — Postgres so'rovni qanday bajarganining hisoboti. EXPLAIN — rejani ko'rsatadi, ANALYZE — so'rovni haqiqatan bajarib vaqtni o'lchaydi, BUFFERS — nechta sahifa o'qilganini. Rejani to'liq o'qishni EXPLAIN ANALYZE'ni o'qish darsida o'rganamiz. Hozir uchta qatorga qarang:

• Parallel Seq Scan on vazifalar — Seq Scan (sequential scan, ketma-ket skanerlash): jadvalni boshidan oxirigacha o'qish. "Parallel" — 3 jarayon (asosiy + 2 ta yordamchi, Workers Launched: 2) jadvalni bo'lishib o'qidi.
• Buffers: shared hit=1328 read=38165 — 1 328 sahifa xotirada (keshda) bor edi, 38 165 tasi diskdan o'qildi. Jami 39 493 — butun jadval.
• Rows Removed by Filter: 666667 (har jarayonda, loops=3) — 2 mln qator tekshirildi va hammasi tashlandi (rows=0 — bunday matn yo'q edi).

Natija: 150 ms bitta qidiruv uchun. Sekundiga 100 foydalanuvchi qidirsa — server faqat shu bilan band.

3. B-tree: tartiblangan daraxt

3.1 Tuzilishi

B-tree (balanslangan daraxt) — Postgres'ning sukut indeksi. B-tree / B+tree ni algoritmlar qismida ko'rgansiz; bu yerda u amalda. Tuzilishi uch qavatli bino kabi:

• Barg sahifalar (leaf, eng past qavat) — hamma kalitlar tartib bilan, har biri yonida qator manzili (ctid — MVCC darsidagi (sahifa, joy)). Barglar bir-biri bilan zanjir bo'lib bog'langan — diapazon qidiruvi (BETWEEN) chap-o'ngga yurib ketadi.
• Ichki sahifalar — "bu sahifadan pastda A dan F gacha, keyingisida G dan M gacha" degan yo'l ko'rsatkichlari.
• Ildiz (root) — eng yuqorida bitta sahifa.

flowchart TB
  R["Ildiz: … | K | S | …"] --> I1["Ichki: A … J"]
  R --> I2["Ichki: K … R"]
  R --> I3["Ichki: S … Z"]
  I2 --> L1["Barg: Kamola → (5120,3)<br/>Karimova → (812,7)"]
  I2 --> L2["Barg: Lola → (77,1)<br/>Malika → (3019,4)"]
  L1 -.->|keyingi barg| L2

Qidiruv: ildizdan boshlab har qavatda bitta sahifa o'qiladi va "qaysi bolaga tushish" tanlanadi. Bargga yetgach — ctid bo'yicha jadvaldagi sahifaga o'tiladi. Har sahifaga yuzlab kalit sig'adi, shuning uchun daraxt juda "keng va past": millionlab qatorga 3–4 qavat yetadi.

"Balanslangan" — hamma barglar bir xil chuqurlikda. Qaysi qiymatni qidirsangiz ham, qadamlar soni bir xil. Yangi kalit qo'shilganda sahifa to'lsa, u ikkiga bo'linadi va daraxt o'zini o'zi muvozanatda saqlaydi.

3.2 Indeks yaratish

CREATE INDEX t56_matn_idx ON vazifalar (matn);
SELECT pg_size_pretty(pg_relation_size('t56_matn_idx'))
       AS indeks_hajmi;

Natija (kanon; \timing yoqilgan):

CREATE INDEX
Time: 10440.906 ms (00:10.441)
 indeks_hajmi
--------------
 94 MB
(1 row)

CREATE INDEX nom ON jadval (ustun); — sintaksis shu. 2 mln qatorga indeks 10.4 soniyada qurildi va 94 MB joy oldi. Nomlash — loyiha andozasi: <jadval>_<ustun>_idx (CREATE TABLE va cheklovlar); kanon tajriba indeksiga t56_ prefiksini qo'ygan.

Diqqat: Oddiy CREATE INDEX qurilish davomida jadvalga yozishni to'xtatadi (SHARE qulfi — Qulflar darsidagi jadval). 10 soniya — sayt uchun sezilarli. Ishlab turgan bazada CREATE INDEX CONCURRENTLY ishlatiladi — keyingi darsda.

3.3 Indeks bilan qidiruv

Endi xuddi shu so'rov. Natijada yana o'sha uch joyga qarang — endi Index Scan, read=3 va Execution Time:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM vazifalar WHERE matn = 'Hisobot yozish 1500000 #ish';

Natija (kanon, qisqartirildi):

 Index Scan using t56_matn_idx on vazifalar (actual time=0.055..0.056 rows=0.00 loops=1)
   Index Cond: (matn = 'Hisobot yozish 1500000 #ish'::text)
   Index Searches: 1
   Buffers: shared read=3
   I/O Timings: shared read=0.022
 Planning:
   Buffers: shared hit=10 read=3
   I/O Timings: shared read=0.131
 Planning Time: 0.413 ms
 Execution Time: 0.084 ms
(10 rows)

• Index Scan using t56_matn_idx — indeks bo'ylab qidirish.
• Index Cond — shart indeksda tekshirildi (Filter emas — qatorlar bittalab tashlanmadi).
• Buffers: shared read=3 — 3 ta sahifa: ildiz, ichki sahifa, barg. Matn topilmagani uchun jadvalning o'ziga umuman bormadi.
• Index Searches: 1 — PostgreSQL 18 da qo'shilgan qator (17 da yo'q): indeksga necha marta "tushildi".

0.084 ms — taxminan 1 800 barobar tez.

3.4 Daraxtning ichiga qarash

pageinspect kengaytmasi (MVCC darsida jadval sahifasiga qaragan edik) B-tree'ni ham ko'rsatadi:

SELECT level AS ildiz_darajasi, fastroot, fastlevel
FROM bt_metap('t56_matn_idx');

Natija (kanon):

 ildiz_darajasi | fastroot | fastlevel
----------------+----------+-----------
              2 |      122 |         2
(1 row)

Ildiz 2-darajada — barglar 0-darajada, demak 3 qavat: ildiz → ichki → barg. Aynan 3 ta sahifa o'qilgani shundan. Ildiz sahifasida (122-blok) kanon 92 ta yozuvni ko'rdi — ildiz 92 ta bolaga yo'l ko'rsatadi.

4. O'zimiz sinaymiz: 100 000 qator

Katta bazasiz ham xuddi shu manzarani ko'rish mumkin. Kichik jadval — 100 000 mijoz (biz ishga tushirdik: PostgreSQL 17.6):

CREATE TABLE mijoz (
  id int PRIMARY KEY,
  telefon text NOT NULL,
  ism text NOT NULL
);
INSERT INTO mijoz
SELECT g, '+99890' || lpad(g::text, 7, '0'), 'Mijoz ' || g
FROM generate_series(1, 100000) g;
ANALYZE mijoz;
SELECT pg_relation_size('mijoz') / 8192 AS sahifalar;

Natija:

CREATE TABLE
INSERT 0 100000
ANALYZE
 sahifalar
-----------
       736
(1 row)

ANALYZE — jadval haqida statistika yig'adi (qancha qator, qiymatlar qanday taqsimlangan); planner (so'rov rejasini tuzadigan qism) shunga tayanadi (Statistika va planner). lpad(g::text, 7, '0') — sonni 7 xonagacha nollar bilan to'ldiradi: +998900054321.

Telefon bo'yicha qidiruv, indekssiz:

EXPLAIN (COSTS OFF)
SELECT ism FROM mijoz WHERE telefon = '+998900054321';

Natija:

                 QUERY PLAN
---------------------------------------------
 Seq Scan on mijoz
   Filter: (telefon = '+998900054321'::text)
(2 rows)

COSTS OFF — planner baholarini (cost=…) yashiradi, faqat reja shakli qoladi. Seq Scan + Filter — 736 sahifaning hammasi o'qiladi, har qator tekshiriladi.

Indeks qo'shamiz:

CREATE INDEX mijoz_telefon_idx ON mijoz (telefon);
EXPLAIN (COSTS OFF)
SELECT ism FROM mijoz WHERE telefon = '+998900054321';
SELECT ism FROM mijoz WHERE telefon = '+998900054321';

Natija:

CREATE INDEX
                   QUERY PLAN
-------------------------------------------------
 Index Scan using mijoz_telefon_idx on mijoz
   Index Cond: (telefon = '+998900054321'::text)
(2 rows)

     ism
-------------
 Mijoz 54321
(1 row)

Reja Index Scan ga o'zgardi. So'rov matnini o'zgartirmadik — indeks qo'shish so'rovni qayta yozishni talab qilmaydi: Postgres o'zi foydaliroq yo'lni tanlaydi. SQL'ning deklarativ tabiati shu (SQL tili va buyruq turlari): siz "nima kerak"ni yozasiz, "qanday topish"ni baza hal qiladi.

Daraxt balandligi:

CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT level FROM bt_metap('mijoz_telefon_idx');
SELECT pg_relation_size('mijoz_telefon_idx') / 8192 AS sahifalar;

Natija:

CREATE EXTENSION
 level
-------
     2
(1 row)

 sahifalar
-----------
       388
(1 row)

100 000 qatorda ham 3 qavat (level 2), 2 mln qatorda ham 3 qavat. 20 barobar ko'p ma'lumot — qidiruv qadamlari soni bir xil. B-tree'ning kuchi shunda: qadamlar soni qatorlar soniga logarifmik bog'liq. Indeks 388 sahifa — jadvalning (736) yarmidan ko'p: telefon raqami qisqa ustun emas, va har kalit yonida manzil saqlanadi.

Tekshirib ko'ring: Nega daraxtda har sahifaga yuzlab kalit joylashtirish (ikkitadan emas, oddiy ikkilik daraxtdagidek) muhim?

5. Indeks qachon ishlatilmaydi

5.1 Ko'p qator qaytsa

Indeks "ignani pichan ichidan" topish uchun. Shart jadvalning katta qismini qaytarsa, Postgres indeksdan voz kechadi. Kanon: vazifalar ning taxminan 60 % i bajarilgan.

Natijada (asosiy qatorlar, cost=… siz) Seq Scan qatoridagi rows= ga qarang:

EXPLAIN (ANALYZE) SELECT count(*) FROM vazifalar WHERE bajarildi;

Natija (kanon, qisqartirildi):

 Finalize Aggregate (actual time=141.950..157.533 rows=1.00 loops=1)
   ->  Gather (actual time=141.715..157.519 rows=3.00 loops=1)
         ->  Partial Aggregate (actual time=133.291..133.292 rows=1.00 loops=3)
               ->  Parallel Seq Scan on vazifalar (actual time=0.156..105.918 rows=399680.33 loops=3)
                     Filter: bajarildi
                     Rows Removed by Filter: 266986
 Execution Time: 157.571 ms

3 × 399 680 ≈ 1.2 mln qator mos keldi. Ularning hammasini indeks orqali olish — 1.2 mln marta "indeks → jadval sahifasi" sakrashi, sahifalar tartibsiz. Butun jadvalni ketma-ket o'qish arzonroq. Shuning uchun boolean kabi 2–3 qiymatli ustunga oddiy indeks deyarli hech qachon yordam bermaydi. Qisman foydali holatlar uchun maxsus indekslar bor — Partial, expression va covering indekslar.

O'zimizning mijoz jadvalida ham shunday: hamma telefonlar +99890 bilan boshlanadi.

EXPLAIN (COSTS OFF)
SELECT count(*) FROM mijoz WHERE telefon LIKE '+99890%';

Natija:

                  QUERY PLAN
----------------------------------------------
 Aggregate
   ->  Seq Scan on mijoz
         Filter: (telefon ~~ '+99890%'::text)
(3 rows)

Indeks bor, lekin ishlatilmadi — shart 100 % qatorni qaytaradi. (~~ — LIKE ning ichki nomi.)

5.2 Ustun "o'zgartirilgan" bo'lsa

WHERE lower(email) = … — email dagi indeks ishlamaydi: indeksda email ning o'zi tartiblangan, lower(email) emas. Kanon sxemasi buni bilib, lower(email) ga indeks qurgan (CREATE TABLE va cheklovlar). Bu — ifoda indeksi, Partial, expression va covering indekslar darsida.

5.3 Qaysi indeksni tanladi?

Kanon PK bo'yicha qidirganda qiziq narsa topdi (cost=… qisqartirildi; indeks nomiga qarang):

 Index Scan using vazifalar_id_egasi_id_key on vazifalar (actual time=0.053..0.055 rows=1.00 loops=1)
   Index Cond: (id = 1234567)

WHERE id = 1234567 uchun planner vazifalar_pkey emas, vazifalar_id_egasi_id_key ni tanladi — (id, egasi_id) dagi noyob indeks (ALTER TABLE darsidagi tarkibiy FK uchun qo'shilgan). Ikkalasi ham id bilan boshlanadi va ikkalasi ham bitta qatorni 0.08 ms da topadi — planner uchun farqi yo'q. Bu xato emas, lekin eslatma: bir xil ustundan boshlanadigan ikki indeks — ko'pincha ortiqcha (hajm va yozish narxi). Bu sxemada ikkinchisi tarkibiy FK uchun majburiy.

6. Indeksning narxi

Indeks bepul emas:

• Joy: matn indeksi 94 MB (jadval 309 MB). Kanon vazifalar dagi hamma indekslar birgalikda jadvalning o'zidan katta (keyingi darsda o'lchaymiz).
• Yozish: har INSERT har indeksga yozuv qo'shadi; har UPDATE — ko'pincha ham (MVCC darsidagi HOT bundan istisno).
• VACUUM va zaxira: indekslar ham tozalanadi va zaxiraga kiradi.

Kanon yozish narxini ham o'lchadi — va halol natija oldi: 10 000 qator INSERT matn indeksi bilan 1 256.7 ms, usiz 1 260.6 ms — farq yo'q. Sabab: bu sxemada har INSERT trigger'larni (teglar, tarix, versiya) ishga tushiradi va ularning narxi bitta indeks narxini butunlay yashiradi. Toza jadvalda farq ko'rinadi — buni o'zingiz 2-mashqning davomida o'lchab ko'ring. Xulosa: indeks narxi kontekstga bog'liq; "har indeks yozishni X % sekinlashtiradi" degan umumiy son yo'q.

Qoida: indeks — so'rovlar uchun. Har ustunga "ehtimol kerak bo'lar" deb indeks qo'ymang; sekin so'rovni topib, unga mos indeks qo'ying (Sekin so'rovlarni topish).

Tekshirib ko'ring: vazifalar jadvalida qaysi ustunlarda indeks allaqachon bor (kanon sxemasidan eslang) va nega?

7. Node qadami: API ro'yxati qaysi indeksdan o'qiydi

t56_matn_idx loyihaga kirmaydi: matn bo'yicha aniq tenglik qidiruvi ilovada yo'q. Foydalanuvchi matnning bir qismini qidiradi — bunga B-tree yordam bermaydi (Indeks turlari: GIN, GiST, BRIN va pg_trgm darsida). Kanon t56_matn_idx ni faqat o'lchov uchun qurdi va keyin o'chirdi.

Lekin vazifalar-api ning eng ko'p chaqiriladigan so'rovi — GET /v1/vazifalar (ro'yxat) — B-tree'ga tayanadi. node-postgres asoslari darsida PgOmbori ni ulaganimizda sxemaga 013-api-tartib.sql qo'shilgan edi. Undagi indeks (kanondan, qatorlarga bo'lingan):

-- Sukut ro'yxat so'rovi: WHERE egasi_id ORDER BY tartib, id
CREATE INDEX vazifalar_tartib_idx
  ON vazifalar (egasi_id, tartib, id)
  WHERE ochirilgan_vaqt IS NULL;

Kanon PgOmbori.royxat() yuborgan haqiqiy SQL'ni ushlab, katta bazada (013/014 bilan qayta qurilgan, eng ko'p vazifali egasi — 479 ta) EXPLAIN (ANALYZE, BUFFERS, COSTS OFF) bilan ko'rdi. Birinchi sahifa (reja-64.txt):

=== sukut (tartib, id), 1-sahifa: royxat() 3.1 ms, so'rovlar 2
Limit (actual time=0.010..0.028 rows=21.00 loops=1)
  Buffers: shared hit=24
  ->  Index Scan using vazifalar_tartib_idx on vazifalar v (actual time=0.009..0.025 rows=21.00 loops=1)
        Buffers: shared hit=24
  Buffers: shared hit=1
Execution Time: 0.039 ms

Nima bo'ldi? 2 mln qatorli jadvaldan 21 qator (20 + "keyingisi bormi" uchun bitta ortiqcha) 24 sahifa o'qib, 0.039 ms da olindi — xuddi 3.3 bo'limdagidek Index Scan. Node tomonida bu ko'rinmaydi: pool.query matni o'zgarmaydi, faqat tezlik o'zgaradi. royxat() 3.1 ms — Node'dan o'lchangan to'liq vaqt (ikki so'rov va tarmoq aylanishi). Indeks nega aynan shu uch ustunda — keyingi ikki darsda; commit esa kursorni tuzatgan Keyset pagination darsida.

8. Ko'p uchraydigan xatolar

8.1 "Indeks qo'shdim — so'rov tezlashishi shart"

Shart ko'p qator qaytarsa yoki ustun funksiya ichida bo'lsa — indeks ishlatilmaydi. EXPLAIN bilan tekshiring: Index Scan bormi?

8.2 Har ustunga indeks

Joy, yozish va VACUUM narxi. Faqat haqiqiy so'rovlar uchun.

8.3 Ishlab turgan jadvalda oddiy CREATE INDEX

Qurilish davomida yozuvlar to'xtaydi. CREATE INDEX CONCURRENTLY (keyingi dars).

8.4 Kichik jadvalda indeks kutish

100 qatorli jadvalda Postgres ko'pincha Seq Scan tanlaydi — 1–2 sahifani o'qish indeksdan arzon. Bu to'g'ri xatti-harakat. Tezlikni katta, real hajmdagi ma'lumotda sinang.

8.5 Tashqi kalitga indeks qo'ymaslik

Postgres FK ustuniga indeksni o'zi yaratmaydi; JOIN va ON DELETE CASCADE sekinlashadi. Har FK ustuniga indeks (kanon review'i buni tekshirgan — Amaliyot: real loyiha sxemasi).

9. Mashqlar

1-mashq (oson): Necha qadam?

Tartiblangan 1 000 000 telefon raqami ichidan bittasini (a) boshidan ketma-ket qidirsangiz, eng yomon holatda nechta solishtirish? (b) ikkilik qidiruv bilan-chi? (c) har sahifaga 300 kalit sig'adigan B-tree'da nechta sahifa o'qiladi?

2-mashq (o'rta): Indeksdan oldin va keyin

200 000 qatorli m56_buyurtma (id, mijoz_id, summa) jadvalini yarating (mijoz_id = g % 5000, ya'ni har mijozda 40 ta buyurtma). ANALYZE qiling. "77-mijozning buyurtmalari summasi" so'rovining rejasini (EXPLAIN (COSTS OFF)) indeksdan oldin va mijoz_id ga indeks qo'shgandan keyin chiqaring. Oxirida 77-mijozning buyurtmalar soni. Eslatma: % — bo'linish qoldig'i, generate_series — Ifodalar va funksiyalar.

DROP TABLE IF EXISTS m56_buyurtma;
CREATE TABLE m56_buyurtma (
  id int PRIMARY KEY,
  mijoz_id int NOT NULL,
  summa int NOT NULL
);
INSERT INTO m56_buyurtma
SELECT g, g % 5000, 10000 + g % 90000
FROM generate_series(1, 200000) g;
ANALYZE m56_buyurtma;
EXPLAIN (COSTS OFF)
SELECT sum(summa) FROM m56_buyurtma WHERE mijoz_id = 77;
CREATE INDEX m56_buyurtma_mijoz_idx ON m56_buyurtma (mijoz_id);
EXPLAIN (COSTS OFF)
SELECT sum(summa) FROM m56_buyurtma WHERE mijoz_id = 77;
SELECT count(*) FROM m56_buyurtma WHERE mijoz_id = 77;
DROP TABLE m56_buyurtma;

Aggregate
  ->  Seq Scan on m56_buyurtma
        Filter: (mijoz_id = 77)
Aggregate
  ->  Bitmap Heap Scan on m56_buyurtma
        Recheck Cond: (mijoz_id = 77)
        ->  Bitmap Index Scan on m56_buyurtma_mijoz_idx
              Index Cond: (mijoz_id = 77)
40

3-mashq (qiyin): B-tree balandligi

qavatlar(qatorlar, sigim) funksiyasini yozing: barglar soni ceil(qatorlar / sigim), keyin har qavatda sahifalar sigim ga bo'linadi, toki bitta (ildiz) qolguncha. Sig'im 300 bilan 1 000, 100 000, 2 000 000 va 1 000 000 000 qator uchun qavatlar sonini chiqaring. Natijani o'zimizning (100 000 — level 2) va kanonning (2 mln — level 2) bt_metap natijalari bilan solishtiring. Eslatma: Math.ceil, while — JS asoslaridan; 1_000 — sonlardagi ajratgich.

// sigim — bitta sahifaga sig'adigan kalitlar (bolalar) soni
function qavatlar(qatorlar, sigim) {
  let sahifalar = Math.ceil(qatorlar / sigim); // barglar
  let qavat = 1;
  while (sahifalar > 1) {
    sahifalar = Math.ceil(sahifalar / sigim);
    qavat++;
  }
  return qavat;
}

for (const n of [1_000, 100_000, 2_000_000, 1_000_000_000]) {
  const q = qavatlar(n, 300);
  console.log(`${n} qator: ${q} qavat — ${q} sahifa o'qiladi`);
}

1000 qator: 2 qavat — 2 sahifa o'qiladi
100000 qator: 3 qavat — 3 sahifa o'qiladi
2000000 qator: 3 qavat — 3 sahifa o'qiladi
1000000000 qator: 4 qavat — 4 sahifa o'qiladi

10. Real ishda

• Har backend'ning birinchi optimallashtirishi: sekin sahifa → sekin so'rov → EXPLAIN → yetishmayotgan indeks. Ko'p "server sekin" muammolari bitta CREATE INDEX bilan hal bo'ladi.
• ORM'lar: Prisma'da @@index([egasi_id]), @unique — sxemadan indeks yaratadi (27-qism); lekin qaysi indeks kerakligini baribir siz hal qilasiz.
• Managed bazalar (Supabase, Neon, RDS) indeks tavsiyalari beradi — ular ham shu EXPLAIN va statistikaga tayanadi (hujjat bo'yicha, kursda sinalmagan).
• Intervyu: "Indeks qanday ishlaydi?", "Nega indeks bo'lsa ham Seq Scan?", "Indeksning kamchiliklari?" — backend intervyusining doimiy savollari.

Xulosa

• Indekssiz qidiruv — butun jadvalni o'qish (Seq Scan): kanonda 39 493 sahifa, 150 ms.
• B-tree — tartiblangan, balanslangan daraxt: ildiz → ichki → barg → jadvaldagi qator (ctid).
• Sahifaga yuzlab kalit sig'adi — 100 ming ham, 2 mln qator ham 3 qavat; kanonda 3 sahifa, 0.08 ms.
• CREATE INDEX so'rov matnini o'zgartirmaydi — planner o'zi Index Scan'ni tanlaydi.
• Ko'p qator qaytaradigan shart (60 % bajarildi) — indeks bo'lsa ham Seq Scan.
• Indeks narxi — joy va yozish; faqat haqiqiy so'rovlar uchun qo'ying.

Keyingi dars: Qaysi ustunga va qanday tartibda indeks — selektivlik, tarkibiy indekslar va ustunlar tartibi: "tenglik → diapazon → saralash".

Manbalar

• PostgreSQL 18 hujjati: Indexes — Introduction.
• PostgreSQL 18 hujjati: B-Tree Indexes.
• PostgreSQL 18 hujjati: Using EXPLAIN.
• PostgreSQL 18 hujjati: Database Page Layout.