Ocak 1007

B Ağacı (B Tree)

Bilgisayar bilimlerinde bir B ağacı, veri sıralaması tutar ve logaritmik azalan zamanda ağaç yapısında ekleme, çıkartma ve arama işlemlerine izin verir. B ağaçları ikili sıralama ağaçlarının daha genel halidir.

Özelikleri:

  • Her B ağacının m değerinde bir faktör değeri vardır (m>1 koşulu sağlanmalıdır).
  • Her düğümde en fazla m adet çocuk bulunmalıdır. m sayısından daha fazla çocuk olması durumunda düğüm parçalanır.
  • Kök ve yaprak düğümleri haricinde en az m/2 adet eleman bulunmalıdır. Aksi takdirde diğer düğümlerle birleştirme işlemi uygulanır.
  • Ağacın derinliği her yaprak için aynı olmalıdır.
  • Her bir düğümde k çocuk bulunuyorsa k-1 sayıda elemanı gösteren anahtar (key) bulunmalıdır.

 

Örnek B ağacı aşağıdaki şekildeki gibidir:

B Ağacı 

B ağacı üzerindeki işlemler:

B-Tree-Search(x, k)
i <- 1
while i <= n[x] and k > keyi[x]
     do i <- i + 1
if i <= n[x] and k = keyi[x]
     then return (x, i)
if leaf[x]
     then return NIL
     else Disk-Read(ci[x])
          return B-Tree-Search(ci[x], k)

B ağacındaki arama ikili araçtaki arama ile benzerdir. Arama sırasında sağ - sol taraf seçenekleri yerine n tane farklı taraf vardır. Düğüm içerisinde lineer bir arama yapılarak doğru çocuk düğüme yönlenebilir. İstenilen değere küçük eşit değer bulunduktan sonra, bulunan key değerinin sol tarafındaki çocuk düğüme gidilir. Eğer Düğümdeki tüm keylerin değerleri aranan değerden küçükse en sağdaki çocuk düğüme dallanılır. Aranan değer bulununca arama işlemi sonlanır. Arama sırasındaki geçen zaman ağacın derinliğine bağlı O(logt n) olarak hesaplanır.

B ağacı arama

B-Tree-Create(T)
x <- Allocate-Node()
leaf[x] <- TRUE
n[x] <- 0
Disk-Write(x)
root[T] <- x

Boş B ağacı yaratma işlemidir. Çocuk düğümü olmayan kök düğümü yaratır. B-Tree-Create işlemi O(1) zamanda koşulur.

B-Tree-Insert(T, k)
r <- root[T]
if n[r] = 2t – 1
     then s <- Allocate-Node()
          root[T] <- s
          leaf[s] <- FALSE
          n[s] <- 0
          c1 <- r
          B-Tree-Split-Child(s, 1, r)
          B-Tree-Insert-Nonfull(s, k)
     else B-Tree-Insert-Nonfull(r, k)
B-Tree-Split-Child(x, i, y)
z <- Allocate-Node()
leaf[z] <- leaf[y]
n[z] <- t – 1
for j <- 1 to t – 1
     do keyj[z] <- keyj+t[y]
if not leaf[y]
     then for j <- 1 to t
          do cj[z] <- cj+t[y]
n[y] <- t – 1
for j <- n[x] + 1 downto i + 1
     do cj+1[x] <- cj[x]
ci+1 <- z
for j <- n[x] downto i
     do keyj+1[x] <- keyj[x]
keyi[x] <- keyt[y]
n[x] <- n[x] + 1
Disk-Write(y)
Disk-Write(z)
Disk-Write(x)

Eğer düğümdeki eleman sayısı faktör değerine ulaşmışsa ayırma işlemi uygulanması gerekir. Ayırma işlemi, tümüyle dolu bir düğümü 2t-1 key), 2 adet düğüme (t-1 key) dönüştürür. Unutulmamalıdır ki, ayırma işlemi ile bir tane key ebeveyn düğüme kayar. Ayırma işlemi O(t) kadar zamanda gerçekleşir.

B ağacı ekleme

B-Tree-Delete(x)

B ağaçları için silme işlemi mümkündür. Fakat diğer işlemlere nazaran daha çok dikkat gerektiren bir işlemdir. Çünkü çıkartma işlemi sonrasında eğer key sayısı koşulumuzu sağlamıyorsa düğümlerde birleştirme işlemi yapılmalıdır. Fakat bu durumda da ağacın dengeli olmasına (derinliğinin her yaprak için aynı olmasına) dikkat edilmelidir.

 

Bu kadar yazı okudunuz. Ancak B Tree nin B’sinin neyin kısaltması olduğundan hiç biryerde bahsetmedim. Bahsedememem de zaten. Bu algoritmayı yazandan başka kimse bilmiyor bunu. Sadece varsayımlardan behsediliyor. Yazımın sonunda bu konu hakkında ufak bir alıntı yapmak istiyorum:

The origin of "B-tree" has never been explained by the authors. ... "balanced," "broad," or "bushy" might apply. Others suggest that the "B" stands for Boeing. [Bayer and McCreight were at Boeing Scientific Research Labs in 1972.] Because of his contributions, however, it seems appropriate to think of B-trees as "Bayer"-trees.     -  

Douglas Comer, The Ubiquitous B-Tree, Computing Surveys, 11(2):123, June 1979.

Tags: | Categories: Algoritma