B-tree — sorted keylarni balanslangan ko‘p yo‘lli daraxtda saqlaydigan ma’lumotlar tuzilmasi. U database index, filesystem va block storage tizimlarida diskdan samarali qidirish, qo‘shish va o‘chirish uchun ishlatiladi.
B-tree binary tree’dan farqli ravishda har node’da ko‘p key va child pointer saqlaydi. Bu tree balandligini kamaytirib, disk page o‘qishlar sonini qisqartiradi.
Node
B-tree node odatda bitta storage page’ga moslashtiriladi.
Node ichida:
saqlanadi.
Ko‘p key bitta page’da bo‘lgani sabab bitta I/O bilan katta key oralig‘i tekshiriladi.
Root
Tree qidiruvi root node’dan boshlanadi.
Root ko‘pincha memory cache’da saqlanadi.
Rootdagi keylar qaysi child branchga tushishni ko‘rsatadi.
Tree o‘sganda root split bo‘lib yangi root yaratilishi mumkin.
Internal node
Internal node key chegaralari va child pointerlarni saqlaydi.
U odatda haqiqiy row value’ni to‘liq saqlamaydi.
Qidiruv key bilan taqqoslab kerakli child page’ga o‘tadi.
Leaf node
Leaf node qidirilayotgan key va row pointerlarni saqlaydi.
B+tree variantida barcha haqiqiy key entrylar leaflarda bo‘ladi va leaflar bir-biriga linked bo‘lishi mumkin.
Bu range scan uchun qulay.
Database indexlar ko‘pincha B-tree deb atalgan B+treega yaqin variantdan foydalanadi.
Balans
Barcha leaflar rootdan taxminan bir xil chuqurlikda bo‘ladi.
Insert va delete tree’ni balanslangan saqlaydi.
Shu sababli qidiruv murakkabligi keylar soniga logarifmik yaqin.
Tree bir tomonga cho‘zilib ketmaydi.
Branching factor
Har node ko‘p childga ega.
Agar bitta page yuzlab key saqlasa, milliardlab rowli index ham oz sonli levelga ega bo‘lishi mumkin.
Masalan:
root
→ internal
→ leaf
yoki bir necha qo‘shimcha level.
Bu disk random readlar sonini kamaytiradi.
Equality lookup
Key bo‘yicha aniq qidiruv rootdan leafgacha yuradi.
WHERE id = 150
Har levelda binary search yoki optimized search bilan child tanlanadi.
Leaf entry row joylashuviga olib boradi.
Range scan
Sorted structure sabab:
WHERE created_at >= ?
AND created_at < ?
querysi boshlang‘ich leafni topib, keyingi leaflar bo‘ylab ketma-ket yuradi.
Bu hash indexdan asosiy farq.
Ordered output
Index tartibi ORDER BY bilan mos bo‘lsa alohida sort talab qilinmasligi mumkin.
Composite indexda column tartibi muhim.
Ascending va descending yo‘nalish database imkoniyatiga bog‘liq.
Insert
Yangi key mos leafga qo‘shiladi.
Page’da joy bo‘lsa sorted pozitsiyaga yoziladi.
Joy bo‘lmasa node split qilinadi:
- keylar ikki node’ga bo‘linadi;
- parentga separator key qo‘shiladi;
- parent ham to‘lsa split davom etadi.
Split write amplification va page fragmentatsiyaga ta’sir qiladi.
Delete
Key o‘chirilganda entry dead yoki olib tashlangan holatga o‘tadi.
Node juda bo‘sh qolsa sibling bilan merge yoki redistribution bajarilishi mumkin.
Database MVCC sabab fizik cleanupni keyinroq vacuumga qoldirishi mumkin.
Fill factor
Index page yaratishda bo‘sh joy qoldirilishi mumkin.
Bu random insertlar uchun kelajak page splitlarini kamaytiradi.
Kam fill factor:
- ko‘proq disk;
- ko‘proq cache;
- kamroq split.
Read-only yoki appendga yaqin index uchun yuqori zichlik qulay.
Monoton key
Auto-increment IDlar doim indexning o‘ng chetiga qo‘shiladi.
Afzalligi — random page split kamroq.
Kamchiligi — juda parallel tizimda so‘nggi leaf page hot spotga aylanishi mumkin.
Distributed shardingda monoton key barcha write’ni bitta range’ga yig‘ishi mumkin.
Random key
UUIDga o‘xshash random key tree bo‘ylab turli page’larga insert qiladi.
Bu hot edge’ni kamaytirishi mumkin.
Ammo:
xarajatini oshiradi.
Time-ordered UUID kabi variantlar muvozanat izlaydi.
Composite key
B-tree keylari tuple tartibida sorted bo‘ladi.
(user_id, created_at)
avval user_id, keyin uning ichida created_at bo‘yicha tartiblangan.
Shu sababli leftmost prefix qoidasi query imkoniyatiga ta’sir qiladi.
Prefix compression
Internal yoki leaf page’da takroriy key prefixlari compression qilinishi mumkin.
Masalan, ko‘p rowda bir xil tenant ID.
Bu fan-outni oshirib tree balandligini kamaytiradi.
Aniq mexanizm database implementationiga bog‘liq.
Covering index
Leaf entry qidiruv keyidan tashqari query uchun kerakli columnlarni ham saqlashi mumkin.
Database table page’ga bormasdan natija qaytaradi.
Index kattalashadi va har update ko‘proq write qiladi.
Concurrency
Parallel insert va scan page latch hamda transaction locklardan foydalanadi.
Latch ichki data structure’ni qisqa muddat himoya qiladi.
Transaction lock esa logical row va isolation uchun.
Ikkalasini aralashtirmaslik kerak.
B-tree va LSM-tree
B-tree write’ni kerakli sorted page’ga in-placega yaqin tarzda joylashtiradi.
LSM-tree avval memory va sequential logga yozib, keyin sorted fayllarni background compaction qiladi.
B-tree read latency va range queryda barqaror; LSM write throughputda kuchli bo‘lishi mumkin.
Height va cache
Tree yuqori level node’lari tez-tez ishlatilgani sabab buffer cache’da qoladi.
Ko‘p lookup faqat leaf page uchun disk o‘qishini talab qilishi mumkin.
Index working set memoryga sig‘sa qidiruv latency keskin kamayadi.
Corruption nazorati
Page checksum, WAL va recovery index strukturasini himoya qiladi.
Hardware yoki software xatosi indexni buzsa query noto‘g‘ri natija yoki error berishi mumkin.
Index qayta qurilishi mumkin, ammo base table data’sining yaxlitligi alohida tekshiriladi.
Bog‘liq tushunchalar
B-tree index, B+tree, Tree node, Leaf page, Internal node, Range scan, Page split, Composite index, Fill factor, LSM-tree