30 / 69

B-Tree

B-daraxt ma'lumotlar tuzilmasi

B-daraxt (B-tree) — o'z-o'zini muvozanatlovchi (self-balancing) qidiruv daraxtining maxsus turi bo'lib, unda har bir tugun bir nechta kalitni saqlashi va ikkitadan ortiq farzand tugunlarga ega bo'lishi mumkin. Bu Ikkilik qidiruv daraxti (Binary Search Tree)ning umumlashtirilgan shaklidir.

U shuningdek, balandligi muvozanatlangan m-tarmoqli daraxt (height-balanced m-way tree) sifatida ham tanilgan.

B-daraxt misoli

B-daraxt

Nima uchun B-daraxt ma'lumotlar tuzilmasi kerak?

B-daraxtga bo'lgan ehtiyoj qattiq disk (HDD, SSD) kabi jismoniy xotira qurilmalariga murojaat qilish vaqtini qisqartirish zarurati bilan paydo bo'ldi. Ikkilamchi xotira qurilmalari (disklar) ancha sekin, lekin sig'imi juda katta bo'ladi. Shuning uchun diskka murojaatlar sonini (I/O operatsiyalarini) minimallashtiradigan ma'lumotlar tuzilmasiga ehtiyoj bor edi.

Boshqa ma'lumotlar tuzilmalari, masalan, ikkilik qidiruv daraxti (BST), AVL Tree, qizil-qora daraxt (Red-Black Tree) bitta tugunda faqat bitta kalitni saqlashi mumkin. Agar siz juda ko'p sonli kalitlarni saqlashingiz kerak bo'lsa, bunday daraxtlarning balandligi juda katta bo'lib ketadi va murojaat qilish vaqti oshadi.

Biroq, B-daraxt bitta tugunda ko'plab kalitlarni saqlashi va bir nechta farzand tugunlarga ega bo'lishi mumkin. Bu daraxtning balandligini sezilarli darajada pasaytiradi va diskka kamroq murojaat qilish orqali tezkor ishlashni ta'minlaydi.

B-daraxt xususiyatlari

Har bir x tuguni uchun kalitlar o'sish tartibida saqlanadi.
Har bir tugunda x.leaf mantiqiy (boolean) qiymati mavjud bo'lib, agar x barg (leaf) tugun bo'lsa, u true bo'ladi.
Agar n daraxtning tartibi (order) bo'lsa, har bir ichki tugun eng ko'pi bilan n - 1 ta kalit va har bir farzand uchun ko'rsatkich (pointer) saqlashi mumkin.
Ildizdan tashqari har bir tugun eng ko'pi bilan n ta va kamida n / 2 ta farzandga ega bo'lishi mumkin.
Barcha barg tugunlar bir xil chuqurlikka (ya'ni daraxtning h balandligiga) ega bo'ladi.
Ildiz tugun kamida 2 ta farzandga ega bo'ladi va kamida 1 ta kalitni o'z ichiga oladi.
Agar n ≥ 1 bo'lsa, u holda balandligi h va minimal darajasi t ≥ 2 bo'lgan ixtiyoriy n kalitli B-daraxt uchun: h ≥ log_t ((n + 1) / 2).

B-daraxt ustida amallar

B-daraxtda elementni qidirish

B-daraxtda elementni qidirish — bu ikkilik qidiruv daraxtida (BST) element qidirishning umumlashtirilgan shaklidir. Quyidagi qadamlar bajariladi:

Ildiz tugundan boshlab, qidirilayotgan k qiymatini tugunning birinchi kaliti bilan taqqoslang.
Agar k == tugunning birinchi kaliti bo'lsa, tugun va uning indeksini qaytaring.
Agar k.leaf == true bo'lsa, nil qaytaring (ya'ni element topilmadi).
Agar k < ildiz tugunning birinchi kaliti bo'lsa, rekursiv ravishda ushbu kalitning chap farzandidan qidiring.
Agar joriy tugunda bir nechta kalit bo'lsa va k > birinchi kalit bo'lsa, k ni tugundagi keyingi kalit bilan taqqoslang.
Agar k < keyingi kalit bo'lsa, ushbu kalitning chap farzandidan qidiring (ya'ni k birinchi va ikkinchi kalitlar oralig'ida yotadi).
Aks holda, kalitning o'ng farzandidan qidiring.
Barg tugunga yetguncha 1-4 qadamlarni takrorlang.

Qidiruv misoli

Darajasi 3 bo'lgan quyidagi daraxtda k = 17 kalitini qidiraylik:

B-daraxt

k ildizda topilmadi, shuning uchun uni ildiz kaliti bilan taqqoslang:

Ildiz tugunda kalit topilmadi

k > 11 bo'lganligi sababli, ildiz tugunning o'ng farzandiga o'ting:

O'ng qism-daraxtga o'tish

k ni 16 bilan taqqoslang. k > 16 bo'lgani uchun, k ni keyingi kalit 18 bilan taqqoslang:

Kalitlarni chapdan o'ngga taqqoslash

k < 18 bo'lganligi sababli, k qiymati 16 va 18 oralig'ida joylashgan. 16 ning o'ng farzandidan (yoki 18 ning chap farzandidan) qidiring:

k qiymati 16 va 18 oralig'ida joylashgan

k topildi!

k topildi

Elementni qidirish algoritmi

text

BtreeSearch(x, k)
 i = 1
 while i ≤ n[x] and k ≥ key_i[x]        // n[x] - x tugunidagi kalitlar soni
    do i = i + 1
if i ≤ n[x] and k = key_i[x]
    then return (x, i)
if leaf[x]
    then return NIL
else
    return BtreeSearch(c_i[x], k)

B-daraxtning boshqa amallari haqida batafsil ma'lumot olish uchun quyidagi darslarga qarang:

B-daraxt amallari kodi

package main

import "fmt"

// BTreeNode tugun strukturasi
type BTreeNode struct {
	keys     []int
	children []*BTreeNode
	leaf     bool
	t        int // Minimal daraja (minimum degree)
}

func newBTreeNode(t int, leaf bool) *BTreeNode {
	return &BTreeNode{
		keys:     make([]int, 0, 2*t-1),
		children: make([]*BTreeNode, 0, 2*t),
		leaf:     leaf,
		t:        t,
	}
}

// Daraxtni aylanib chiqish (traversal)
func (n *BTreeNode) traverse() {
	i := 0
	for i = 0; i < len(n.keys); i++ {
		if !n.leaf {
			n.children[i].traverse()
		}
		fmt.Printf(" %d", n.keys[i])
	}
	if !n.leaf {
		n.children[i].traverse()
	}
}

// Kalitni qidirish
func (n *BTreeNode) search(k int) *BTreeNode {
	i := 0
	for i < len(n.keys) && k > n.keys[i] {
		i++
	}
	if i < len(n.keys) && n.keys[i] == k {
		return n
	}
	if n.leaf {
		return nil
	}
	return n.children[i].search(k)
}

// BTree strukturasi
type BTree struct {
	root *BTreeNode
	t    int
}

func NewBTree(t int) *BTree {
	return &BTree{
		root: nil,
		t:    t,
	}
}

func (tree *BTree) Traverse() {
	if tree.root != nil {
		tree.root.traverse()
	}
}

func (tree *BTree) Search(k int) *BTreeNode {
	if tree.root == nil {
		return nil
	}
	return tree.root.search(k)
}

func (tree *BTree) Insert(k int) {
	if tree.root == nil {
		tree.root = newBTreeNode(tree.t, true)
		tree.root.keys = append(tree.root.keys, k)
		return
	}

	if len(tree.root.keys) == 2*tree.t-1 {
		s := newBTreeNode(tree.t, false)
		s.children = append(s.children, tree.root)
		s.splitChild(0, tree.root)

		i := 0
		if s.keys[0] < k {
			i++
		}
		s.children[i].insertNonFull(k)
		tree.root = s
	} else {
		tree.root.insertNonFull(k)
	}
}

func (n *BTreeNode) insertNonFull(k int) {
	i := len(n.keys) - 1

	if n.leaf {
		n.keys = append(n.keys, 0)
		for i >= 0 && n.keys[i] > k {
			n.keys[i+1] = n.keys[i]
			i--
		}
		n.keys[i+1] = k
	} else {
		for i >= 0 && n.keys[i] > k {
			i--
		}
		i++
		if len(n.children[i].keys) == 2*n.t-1 {
			n.splitChild(i, n.children[i])
			if n.keys[i] < k {
				i++
			}
		}
		n.children[i].insertNonFull(k)
	}
}

func (n *BTreeNode) splitChild(i int, y *BTreeNode) {
	t := n.t
	z := newBTreeNode(t, y.leaf)

	medianKey := y.keys[t-1]

	// z ga t dan keyingi kalitlarni berish
	for j := t; j < len(y.keys); j++ {
		z.keys = append(z.keys, y.keys[j])
	}

	if !y.leaf {
		for j := t; j < len(y.children); j++ {
			z.children = append(z.children, y.children[j])
		}
		y.children = y.children[:t]
	}

	y.keys = y.keys[:t-1]

	// z ni n.children ga i+1 o'rniga joylashtirish
	n.children = append(n.children, nil)
	for j := len(n.children) - 1; j > i+1; j-- {
		n.children[j] = n.children[j-1]
	}
	n.children[i+1] = z

	// medianKey ni n.keys ga i o'rniga joylashtirish
	n.keys = append(n.keys, 0)
	for j := len(n.keys) - 1; j > i; j-- {
		n.keys[j] = n.keys[j-1]
	}
	n.keys[i] = medianKey
}

func main() {
	t := NewBTree(3)
	t.Insert(8)
	t.Insert(9)
	t.Insert(10)
	t.Insert(11)
	t.Insert(15)
	t.Insert(16)
	t.Insert(17)
	t.Insert(18)
	t.Insert(20)
	t.Insert(23)

	fmt.Print("B-daraxt elementlari:")
	t.Traverse()
	fmt.Println()

	k := 10
	if t.Search(k) != nil {
		fmt.Printf("%d topildi\n", k)
	} else {
		fmt.Printf("%d topilmadi\n", k)
	}

	k = 2
	if t.Search(k) != nil {
		fmt.Printf("%d topildi\n", k)
	} else {
		fmt.Printf("%d topilmadi\n", k)
	}
}

B-daraxtda qidirish murakkabligi

Holat	Vaqt murakkabligi
Eng yomon holat (Worst case)	`Θ(log n)`
O'rtacha holat (Average case)	`Θ(log n)`
Eng yaxshi holat (Best case)	`Θ(log n)`

Xotira murakkabligi	Murakkablik
O'rtacha holat xotirasi	`Θ(n)`
Eng yomon holat xotirasi	`Θ(n)`

B-daraxtning qo'llanilishi

Ma'lumotlar bazalari (Databases) va fayl tizimlari (File systems) da indekslash uchun.
Katta hajmdagi ma'lumotlar bloklarini saqlash va ularga tezkor kirish uchun (ikkilamchi xotira vositalarida).
Ko'p darajali indekslash (multilevel indexing) tizimlarida.

Oldingi

Keyingi