B-tree 2-3 tree‘ga o’xshash, ammo bir necha jihatlar bilan farqlanadi.
- Har bir node’da M-1 gacha key qo’shiladi. Bunda M bitta blokdagi ma’lumotlar soni.
- Root’da kamida 2ta key va boshqa node’larda kamida M/2 key’lar bo’ladi.
- Leaf (tashqi) node’lar ma’lumotlarni saqlaydi, qolgan parentlar faqat ma’lumotga yo’l uchun xizmat qiladi.
B-tree’da qidirish (Search)
Qidirish ham 2-3 tree’dagi kabi:
- Root’dan boshlaydi
- Qidirilayotgan qiymatni intervalda topib, kerakli child’dan davom ettiradi
- Qidirish leaf node’da to’xtaydi.
B-tree’ga ma’lumot qo’shish (Insert)
Qo’shishda ham 2-3 prinsipidan foydalaniladi:
- Qo’shish uchun pastda kerakli pozitsiya qidiriladi
- Node to’lib qolganda, node bo’linadi.
Tahlil
Search va Insert ikkisi O(log N) vaqt talab qiladi. Amaliyotda M = 1024 bo’lgan 65 milliard key’li ma’lumot saqlanuvchi B-tree’dan 4 ta qadamda kerakli ma’lumotni topishimiz mumkin.
B-Tree qidirishda va ma’lumot saqlashda samaradorligi uchun fayl tizimi modelida qo’llaniladi.