B-tree 2-3 tree'ga öxşaş, ammo bir neça jihatlar bilan farqlanadi.

• Har bir node'da M-1 gaça key qöşiladi. Bunda M bitta blokdagi ma'lumotlar soni.
• Root'da kamida 2ta key va boşqa node'larda kamida M/2 key'lar böladi.
• Leaf (taşqi) node'lar ma'lumotlarni saqlaydi, qolgan parentlar faqat ma'lumotga yöl uçun xizmat qiladi.

B-tree. Image credit: algs4.cs.princeton.edu

B-tree'da qidiriş (Search)

Qidiriş ham 2-3 tree'dagi kabi:

• Root'dan boşlaydi
• Qidirilayotgan qiymatni intervalda topib, kerakli çild'dan davom ettiradi
• Qidiriş leaf node'da töxtaydi.

B-tree'ga ma'lumot qöşiş (Insert)

Qöşişda ham 2-3 prinsipidan foydalaniladi:

• Qöşiş uçun pastda kerakli pozitsiya qidiriladi
• Node tölib qolganda, node bölinadi.

Tahlil

Search va Insert ikkisi O(log N) vaqt talab qiladi. Amaliyotda M = 1024 bölgan 65 milliard key'li ma'lumot saqlanuvçi B-tree'dan 4 ta qadamda kerakli ma'lumotni topişimiz mumkin.

B-Tree qidirişda va ma'lumot saqlaşda samaradorligi uçun fayl tizimi modelida qöllaniladi.