B+ Tree

B+ daraxt (B+ Tree) — o'z-o'zini muvozanatlovchi (self-balancing) qidiruv daraxtining takomillashtirilgan shakli bo'lib, unda barcha haqiqiy ma'lumot qiymatlari (rekordlar) faqat barg (leaf) darajasida saqlanadi. Ichki tugunlar esa faqat kalitlar va yo'naltiruvchi ko'rsatkichlarni (indekslarni) o'z ichiga oladi.

B+ daraxtini o'rganishdan oldin tushunilishi kerak bo'lgan muhim tushuncha bu — ko'p darajali indekslash (multilevel indexing) dir. Ko'p darajali indekslashda quyidagi rasmda ko'rsatilganidek, indekslar ustidan yangi indekslar iyerarxiyasi hosil qilinadi. Bu katta hajmdagi ma'lumotlarga tezkor va oson kirish imkonini beradi.

B+ daraxt yordamida ko'p darajali indekslash (Multilevel Indexing)

B+ daraxtning xususiyatlari

1. Barcha barg tugunlar bir xil darajada (chuqurlikda) joylashadi.
2. Ildiz tugun kamida ikkita farzandga ega bo'ladi.
3. Ildizdan tashqari har bir tugun eng ko'pi bilan m ta va kamida m / 2 ta farzandga ega bo'lishi mumkin.
4. Har bir tugun eng ko'p m - 1 ta kalit va kamida ⌈m / 2⌉ - 1 ta kalitni saqlashi mumkin.
5. Barcha barg tugunlar o'zaro bir yo'nalishli (yoki ikki yo'nalishli) bog'langan ro'yxat (linked list) orqali bog'langan bo'ladi. Bu esa oraliq qidiruvlarni (range queries) juda tezkor qiladi.

B-daraxt va B+ daraxt o'rtasidagi farqlar

B-daraxt tuzilishi

B+ daraxt tuzilishi

• Ma'lumot ko'rsatkichlari: B+ daraxtda ma'lumotlarga ko'rsatkichlar faqat barg tugunlarda joylashgan bo'ladi. B-daraxtda esa ma'lumot ko'rsatkichlari ichki, barg yoki ildiz tugunlarning barchasida bo'lishi mumkin.
• Barglarning bog'lanishi: B-daraxtda barg tugunlar o'zaro bog'lanmagan. B+ daraxtda esa barcha barglar zanjirsimon bog'langan ro'yxat shaklida birlashtirilgan.
• Tezlik: B+ daraxtdagi amallar (ayniqsa oraliqli qidiruv va ketma-ket o'qish) B-daraxtga qaraganda ancha tezroq ishlaydi.
• Balandlik: B+ daraxtning ichki tugunlarida faqat kalitlar (indekslar) saqlangani sababli, bitta tugunga ko'proq yo'naltirgich sig'adi va daraxtning balandligi B-daraxtga nisbatan ham pastroq bo'ladi.

B+ daraxtda elementni qidirish

Tartibi m bo'lgan B+ daraxtda ma'lumotni qidirish quyidagi bosqichlarda amalga oshiriladi. Qidirilayotgan element k bo'lsin:

1. Ildiz tugundan boshlang. k ni ildiz tugundagi kalitlar [k_1, k_2, k_3, ..., k_{m-1}] bilan taqqoslang.
2. Agar k < k_1 bo'lsa, ildiz tugunning chap farzandiga o'ting.
3. Agar k == k_1 bo'lsa, k_2 bilan taqqoslang. Agar k < k_2 bo'lsa, k qiymati k_1 va k_2 orasida yotadi. Shuning uchun k_2 ning chap farzandidan qidiring.
4. Agar k > k_2 bo'lsa, 2 va 3-bosqichlar kabi k_3, k_4, ..., k_{m-1} kalitlari bo'ylab davom eting.
5. Barg tugunga yetguncha yuqoridagi amallarni takrorlang.
6. Agar k barg tugunda mavjud bo'lsa, true (topildi), aks holda false (topilmadi) qaytaring.

Qidiruv misoli

Quyidagi B+ daraxtida k = 45 kalitini qidiraylik:

B+ daraxt

1. k ni ildiz tugun bilan taqqoslang:

Ildiz tugunda kalit topilmadi

2. k > 25 bo'lganligi sababli, o'ng farzandga o'ting:

Ildizning o'ng farzandiga o'tish

3. k ni 35 bilan taqqoslang. k > 30 (va k > 35) bo'lgani uchun, k ni 45 bilan taqqoslang:

Ichki tugunda kalitlarni taqqoslash

4. k ≥ 45 bo'lganligi sababli, eng o'ngdagi farzand tugunga o'ting:

Barg tugunga o'tish

5. 45 kaliti barg tugundan topildi!

k topildi

B+ daraxt amallari dasturiy kodi

package main

import "fmt"

// BPNode B+ daraxt tugun strukturasi
type BPNode struct {
	isLeaf   bool
	keys     []int
	children []*BPNode
	next     *BPNode // Barg tugunlar uchun bog'langan ro'yxat ko'rsatkichi
}

func newBPNode(isLeaf bool) *BPNode {
	return &BPNode{
		isLeaf:   isLeaf,
		keys:     make([]int, 0),
		children: make([]*BPNode, 0),
		next:     nil,
	}
}

// BPlusTree strukturasi
type BPlusTree struct {
	root  *BPNode
	order int // Har bir tugundagi maksimal farzandlar soni (m)
}

func NewBPlusTree(order int) *BPlusTree {
	root := newBPNode(true)
	return &BPlusTree{
		root:  root,
		order: order,
	}
}

// Search - B+ daraxtda kalitni qidirish
func (tree *BPlusTree) Search(k int) bool {
	curr := tree.root
	for !curr.isLeaf {
		i := 0
		for i < len(curr.keys) && k >= curr.keys[i] {
			i++
		}
		curr = curr.children[i]
	}

	for _, key := range curr.keys {
		if key == k {
			return true
		}
	}
	return false
}

// Insert - B+ daraxtga element qo'shish
func (tree *BPlusTree) Insert(k int) {
	root := tree.root
	if len(root.keys) == tree.order-1 {
		newRoot := newBPNode(false)
		newRoot.children = append(newRoot.children, root)
		tree.splitChild(newRoot, 0, root)
		tree.root = newRoot
		tree.insertNonFull(newRoot, k)
	} else {
		tree.insertNonFull(root, k)
	}
}

func (tree *BPlusTree) insertNonFull(node *BPNode, k int) {
	if node.isLeaf {
		idx := 0
		for idx < len(node.keys) && node.keys[idx] < k {
			idx++
		}
		if idx < len(node.keys) && node.keys[idx] == k {
			return // Takroriy qiymat kiritilmaydi
		}
		node.keys = append(node.keys, 0)
		for j := len(node.keys) - 1; j > idx; j-- {
			node.keys[j] = node.keys[j-1]
		}
		node.keys[idx] = k
		return
	}

	idx := 0
	for idx < len(node.keys) && k >= node.keys[idx] {
		idx++
	}

	child := node.children[idx]
	if len(child.keys) == tree.order-1 {
		tree.splitChild(node, idx, child)
		if k >= node.keys[idx] {
			idx++
		}
	}
	tree.insertNonFull(node.children[idx], k)
}

func (tree *BPlusTree) splitChild(parent *BPNode, idx int, child *BPNode) {
	mid := len(child.keys) / 2
	promotedKey := child.keys[mid]

	newNode := newBPNode(child.isLeaf)

	if child.isLeaf {
		newNode.keys = append(newNode.keys, child.keys[mid:]...)
		child.keys = child.keys[:mid]

		newNode.next = child.next
		child.next = newNode
	} else {
		newNode.keys = append(newNode.keys, child.keys[mid+1:]...)
		newNode.children = append(newNode.children, child.children[mid+1:]...)

		child.keys = child.keys[:mid]
		child.children = child.children[:mid+1]
	}

	parent.children = append(parent.children, nil)
	for j := len(parent.children) - 1; j > idx+1; j-- {
		parent.children[j] = parent.children[j-1]
	}
	parent.children[idx+1] = newNode

	parent.keys = append(parent.keys, 0)
	for j := len(parent.keys) - 1; j > idx; j-- {
		parent.keys[j] = parent.keys[j-1]
	}
	parent.keys[idx] = promotedKey
}

// PrintLeaves - Barg tugunlar zanjirini chiqarish
func (tree *BPlusTree) PrintLeaves() {
	curr := tree.root
	for !curr.isLeaf {
		curr = curr.children[0]
	}

	fmt.Print("B+ daraxt barglari (bog'langan ro'yxat): ")
	for curr != nil {
		for _, k := range curr.keys {
			fmt.Printf("%d ", k)
		}
		curr = curr.next
	}
	fmt.Println()
}

func main() {
	tree := NewBPlusTree(4) // order = 4
	elements := []int{5, 15, 25, 35, 45, 55, 40, 30, 20}
	for _, e := range elements {
		tree.Insert(e)
	}

	tree.PrintLeaves()

	for _, k := range []int{45, 15, 99} {
		if tree.Search(k) {
			fmt.Printf("Kalit %d: topildi\n", k)
		} else {
			fmt.Printf("Kalit %d: topilmadi\n", k)
		}
	}
}

Qidiruv murakkabligi

• Vaqt murakkabligi (Time Complexity):
  • Agar tugun ichida chiziqli qidiruv (linear search) ishlatilsa, umumiy murakkablik: Θ(t * log_t n) yoki Θ(log n).
  • Agar ikkilik qidiruv (binary search) ishlatilsa: Θ(log_2 t * log_t n).
• Xotira murakkabligi (Space Complexity): Θ(n).

B+ daraxtning qo'llanilishi

• Ko'p darajali indekslash (Multilevel Indexing)
• Daraxtda tezkor qidiruv, qo'shish va o'chirish amallarini ta'minlash
• Relyatsion ma'lumotlar bazalarida (PostgreSQL, MySQL InnoDB va b.) asosiy B-Tree indeks turi sifatida keng qo'llaniladi.