B Ağacı (B-Tree)
Yazan : Şadi Evren ŞEKER
İçerik
1. B-Ağacının Tanımı
2. Örnek B-Ağacı
3. B-Ağacında Arama
4. B-Ağacına Ekleme
5. B-Ağacından Silme
İsminin nereden geldiği (B harfinin) tartışmalı olduğu bu ağaç yapısındaki amaç arama zamanını kısaltmaktır. Buna göre ağacın her düğümünde belirli sayıda anahtar veya kayıt tutularak arama işleminin hızlandırılması öngörülmüştür.
Arama hızının artmasına karşılık silme ve ekleme işlemlerinin nispeten yavaşlaması söz konusudur.
Bir B-Ağacı (B-Tree) aşağıdaki özelliklere sahip olmalıdır:
- Her düğümün (node) en fazla m çocuğu bulunmalıdır. (Bu sayının üzerinde eleman bulunursa düğümün çoğaltılması gerekir)
- Kök (root) ve yaprak (leaf) düğümleri haricindeki her düğümün en az m/2 adet elemanı bulunmalıdır. (Bu sayının altında eleman bulunursa düğüm kaldırılır)
- Bütün yapraklar aynı seviyede olmak zorundadır. Bir yaprağın seviyesinin düşmesi durumunda (daha yukarı çıkması veya daha sığ olması durumunda) ağaçta yapısal değişiklik gerekir.
- Herhangi bir düğümde k çocuk bulunuyorsa k-1 elemanı gösteren anahtar (key) bulunmalıdır.
Aşağıda örnek bir b ağacı gösterilmiştir:
Aşağıda b ağacı üzerinde yapılan ekleme, silme ve arama işlemleri açıklanmıştır.
Bağacında (Btree) arama işlemi kökten başlar. Aranan sayı kök düğümde bulunamaması halinde arama işlemi kökte bulunan anahtarların sağında solunda veya arasında şeklinde yönlendirilir. Örneğin yukarıdaki B-ağacında 87 anahtarı aranıyor olsun. Arama işlemi için aşağıdaki adımlar gerekir:
1. kök düğüme bakılır. 87 değeri 65’ten büyüktür. Kök düğümde tek anahtar olduğu için 65’in sağındaki gösterici(pointer) takip edilir.
2. 65. sağındaki düğüme gidilir ve ilk anahtar olan 82 ile aranan anahtar olan 87 karşılaştırılır. 87 değeri 82’den büyüktür. Öyleyse ikinci anahtar olan 97 ile karşılaştırılır. 87 bu değerden küçük olduğu için bu düğümde 82 ile 97 arasında bulunan gösterici izlenir.
3. Son olarak 82 ile 97 arasındaki düğüm izlenerek ulaşılan düğümdeki anahtar ile 87 karşılaştırılır. Bu düğümdeki ilk anahtar 85’tir. 87 bu değerden büyüktür. Düğümdeki bir sonraki anahtar alınır ve 87 değeri bulunur.
B-ağaçlarının bir özelliği ağacın her düğümündeki anahtarların sıralı oluşudur. Bu yüzden bir düğümde istenen anahtar aranırken, düğümde bulunan sayılara teker teker bakılır (linear search, doğrusal arama)
B ağaçlarında veri yaprak düğümlerden gösterilir (pointer). Yani aslında veri ağacın düğümlerinde değil son düğümlerden gösterilen hafıza bölmeleri (RAM veya Dosya) olarak tutulur. Dolayısıyla B ağacında ekleme işlemi sırasında anahtarlar üzerinden arama ve değişiklikler yapılır ve nihayetinde amaç B ağacının son düğümleri olan yaprak düğümlerden veriyi göstermektir.
B ağaçlarında veri eklemek için aşağıdaki adımlar takip edilir:
1. Ağaçta eklenecek doğru yaprak düğümü aranır. (Bu işlem için bir önceki adımda anlatılan arama algoritması kullanılır)
2. Şayet bulunan yaprak düğümde azami anahtar sayısından (maximum key number) daha az eleman varsa (yani anahtar eklemek için boş yer varsa) bu düğüme ekleme işlemi yapılır.
3. Şayet yeterli yer yoksa bu durumda bulunan bu yapra düğüm iki düğüme bölünür ve aşağıdaki adımlar izlenir:
1. Yeni eleman eklendikten sonra düğümde bulunan anahtarlar sıralanır ve ortadaki elemandan bölünür. (median değeri bulunur)
2. Ortanca değerden büyük elemanlar yeni oluşturulan sağ düğüme ve küçük elemanlar da sol düğüme konulur.
3. Ortanca eleman (median) ise bir üst düğüme konulur.
Yukarıdaki ekleme işlemini aşağıdaki örnek ağaç üzerinden görelim.
Örneğin azami anahtar sayısıs 2 olan yukarıdaki örnek ağaçta ekleme işlemi yapalım ve değer olarak 60 ekleyelim:
Yukarıdaki ekleme işlemi, ekleme algoritmamızdaki 2. durumda gerçekleşmektedir. Yani anahtarımızın ekleneceği yaprakta boş yer bulunmaktadır ve buraya yeni anahtarı ekleriz.
Şayet yukarıdaki ağaca 80 değerini ekleyecek olsaydık bu durumda da algoritmamızdaki 3. ihtimal gerçekleşmiş olacaktı.
Görüldüğü üzere 80 anahtarının ekleneceği düğüm dolmuş ve azami 2 anahtar olamsı gerekirken 3 anahtar olmuştur. Ortanca değer (median) 70 olan bu ekleme işleminden sonra ortanca değer bir üst düğüme çıkmış ve iki farklı düğüme ortanca elemanın solundaki ve sağındaki değerler yukarıdaki şekilde dağıtılmıştır.
B ağacı yukarıdaki özellikleri bölümünde anlatılan özelliklerin bozulmaması için silme işlemi sırasında aşağıdaki iki yöntemden birisini izler:
1. çözümde ağaçtan ilgili anahtar bulunup silinir ve bütün ağaç yeniden inşa edilir
2. çözümde ağaçtan ilgili anahtar bulunup silinir ve bulma işlemi sırasında geçilen ağacın kısımları yeniden inşa edilir.
Ayrıca B+ ağacı (B plus tree) ve B# ağacı (B number tree) şeklinde alt çeşitleri de bulunmaktadır.
Ayrıca B ağacının özel birer uygulaması olarak aşağıdaki ağaçlara bakabilirsiniz:
Teşekkürler
Merhabalar hocam, B-Tree’de arama işleminin zaman karmaşıklığı nedir? (nlog2n??)
taman sanırım buldum, O(logn)
evet logn ‘dir ve logaritmanın tabanı, düğüm boyutudur. Yani bir düğümdeki eleman sayısı kadar farklı alternatif her adımda incelendiği için problemi bu kadar alt parçaya böler ve basitleştirir.
Örneğin düğüm boyutumuz 5 olsun. Arama algoritmamız ilk adımda problemi 5 parçaya böler ve bunlardan birisine iner. Dolayısıyla her adımda problemin kalan kısmının %20’si aranmak üzere seçilir.
Diğer bir deyişle ağacın derinliği (kökten yapraklara kadar olan uzaklık) oluşturulurken logn seviye yeterlidir.
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication14 { class Node { public int? veri; public Node leftNode, rightNode; public Node(int? veri, Node leftNode, Node rightNode) { this.veri = veri; this.rightNode = rightNode; this.leftNode = leftNode; } } class uygulama { static void ekle(int veri, Node root) { Node yeniNode = new Node(veri, null, null); //daha önce node yok ise yeniNode root olacak if (root.veri == null) root.veri = veri; else { Node current = root; Node parent; //geçici root (temp gibi) while (true) { parent = current; if (veri = temp.veri) { temp.veri = temp.rightNode.veri; gecici.rightNode = temp.rightNode.rightNode; } } } } static void preorder(Node node) { Console.WriteLine(node.veri); if (node.leftNode != null) preorder(node.leftNode); if (node.rightNode != null) preorder(node.rightNode); } static void inorder(Node node) { Console.WriteLine(node.leftNode); if (node.veri != null) inorder(node.veri); if (node.rightNode != null) inorder(node.rightNode); } static void postorder(Node node) { Console.WriteLine(node.leftNode); if (node.rightNode != null) postorder(node.rightNode); if (node.veri != null) postorder(node.veri); } static void Main(string[] args) { Node root = new Node(null, null, null); //kök node oluşturma ekle(15, root); ekle(10, root); preorder(root); sil(12, root); } } }sil işlemi çalışmıyor kafam çok karıştı hatalarmda yardm edersenz sevinirm.
kodunuzu inceledim ve visual studio ile denedim (CSharp yazdığınızı varsayıyorum). Ancak kodunuzda çok sayıda tanımlanmamış değişken kullanılması söz konusu. Örneğin temp ve gecici gibi.
Mümkünse kodunuzu içeren projeyi bir rar veya zip dosyası haline getirip mail ile bana ulaştırın. Vakit konusunda söz vermemekle birlikte inceleyip size hatanızı ve düzeltilmiş halini ulaştırmaya çalışırım.
başarılar
yukarıdaki bu kod, btree kodu değil bst (binary search tree) kodudur. Sorunuzun çözümünü daha önce bir ders sayfamda yayınlamıştım http://www.sadievrenseker.com/datastr2009/ adresine bakabilirsiniz.
başarılar
Sırası (order) 50 olan bir B+ ağaçta, yaprak olmayan
bir düğümde 95 işaretçi bulunmaktadır.
Buna göre bu düğümde kaç anahtar vardır?
A) 48 B) 49 C) 93 D) 94 E) 95
Her disk bloğuna 10 kaydın sığabildiği, 5 000 000
kaydın tutulduğu R(A,B,C,D,E) dosyası vardır. A özniteliği
anahtar alandır ve bu alandaki veriler 0 ile
4 999 999 arasında değişen değerler alabilmektedir.
R dosyası A değerlerine göre sıralı saklanmaktadır.
Ayrıca bu dosya için A özniteliğine göre, hem bir B+
ağacı hem de karım (hash) dizin vardır.
Buna göre,
I. σA>50 000 (R)
II. σA=50 000 (R)
III. σA>50 000 ∧ A<50 010 (R)
IV. σA≠50 000 (R)
sorgularından hangileri için B+ ağaç dizinini kullanmak
en hızlı ve en ucuz çözüm olur?
(σ : İlişkisel cebirdeki seçme işlemi)
A) Yalnız II B) Yalnız III
C) Yalnız I ve III D) Yalnız I ve IV
E) Yalnız II ve IV
şimdiden teşekkürler..
Öncelikle sorunuzu ilgili olduğu konu olan b-ağacı başlığına taşıdım.
B ağaçlarında, düğümlerde, anahtar sayının bir fazlası kadar işaretçi bulunur. Yukarıdaki yazıdaki şekillerden bunu görebilirsiniz. Örneğin düğümde 2 anahtar bulunduğunda 3 işaretçi bulunmaktadır. Bu durumda 95 işaretçi (gösterici , pointer) bulunan bir düğümde 94 adet anahtar bulunacaktır.
ikinci sorunuz ise veri tabanı konusu ile daha çok ilgili olmakla birlikte, sorudaki indeksleme yapısının iyi anlaşılması gerkir.
Soruda bir özetleme fonksiyonu (karım ,hash ) kullanıldığından bahsedilmiş. Bu durumda eşitlik kontrolünde O(1) zamanına sahip erişim zaten hash ile yapılabiliyor demektir. Benzer şekilde eşit olmama durumu da O(1) zamanında kontrol edilebilir. Dolayısıyla sorudaki II. ve IV. aramaların vakit olarak B+ ağacından daha hızlı zaten yapılabilmesi söz konusudur.
Geriye kalan I ve III şıklarınız cevap olacaktır. Buradaki B ağaçlarının erişim süresinin O(log n) ve hash indekslemenin erişim süresinin O(1) olduğunu hatırlamanız yeterlidir.
Başarılar
Merhabalar. B Tree’lerle ilgili mantığı yazınızı okuyarak çok rahat anlayabildim. Ancak elimde büyük bir text var ve burdan kelime arama işlemini B trees ile yapmaya çalışıyorum. Bu konuyla ilgili örnek teşkil etmesi amacıyla kod koyabilirmisiniz? Şimdiden teşekkür ediyorum.
tunahancankurt.blogspot.com
merhaba hocam, benim B+ tree nin min ve max derinliğini bulmamızı sağlayan formül nedir?bir çok yerde hep farklı farklı formüller yazılmış kafam iyice karıştı. teşekkürler şimdiden.
Öncelikle B-Ağacının derinliğini hesaplayalım.
En iyi ihtimalle bütün düğümler doludur. Yani bir düğümde m kadar eleman tutulabiliyorsa (node size) ve elimizde n tane elemanı eklemek gibi bir dert varsa
log(n) / log(m+1)
veya log(m+1)n
derinliği var demektir. Burada neden m+1 aldığımızı şu şekilde açıklayayım, m kayıt duruyorsa m+1 çocuğu var demektir. Buna ağaçlarda dallanma çarpanı (branching factor) ismi verilir. Bu durum zaten bütün, parçala fethet (divide and conquere) yaklaşımları için ortak bir şekilde logaritmik çıkar.
En kötü durumda ise B-ağacının bir çocuğu olması için en azından yarısının dolu olması gerekecektir (kök düğüm (root) hariç, çünkü burada düğüm boyutu (node size) ne olursa olsun, tek değer olabilir). Dolayısıyla d=m/2 dersek
logdn
veya
log(m+1)/2n
boyutunda olacaktır.
Gelelim B+ ağacına. Öncelikle belirtmek gerekir ki B+ ağacı, kayıt tekrarı yapar. Yani yukarıdaki klasik B ağacı gibi bir anahtar bir kere tutulmaz. Bu durumda elimizde kesin olarak tutulan veri, en alt seviyedeki yaprak düğümlerdir (leaf nodes).
Bütün yaprak düğümlerin tam dolu olması halinde n/(m+1) kadar yaprak düğüm bulunacaktır. Bu düğümleri indeksleyecek ağaçta ise en azından log(m+1)(n/(m+1)) düğüm bulunması gerekir. Bu değer ve ilave bir yaprak düğümlerin bulunduğu seviye dersek:
log(m+1)(n/(m+1)) + 1
En kötü durumda, yaprak düğümlerde boşluklar olacaktır. Bu durumda yaprak düğüm sayısı en fazla n/m/2 olabilir. (yine en az m/2 değerin düğümde olması gerektiğini kabul ediyoruz).
yani 2n / m adet düğümden bahsediyoruz.
Formülde sadece düğüm değerlerini güncellersek (h derinlik olmak üzere):
h = log(m+1)/2(2n/(m+1)) + 1
Sonucuna ulaşırız. Bu formülün tersi de bulunabilir. Örneğin derinliğin verildiği durumlarda kaç kayıt tutabileceğimizi soralım. (derinlik h olmak üzere)
(m+1)h – (m+1)(h-1)
olur. Bu değer, aynı zamanda bir ağacın yaprak düğüm sayısını (leaf node) veren formüldür.
Yine derinliği verilen ağaç için, en az düğüm sayısını sorarsak ve yine düğümlerin yarısının dolu olacağını kabul edersek:
[(m+1) / 2 ]h – [(m+1) / 2 ]h-1
değeri bulunur. Bu değer sadeleştirilirse :
= [(m+1) / 2 ]h-1 ( [(m+1) / 2 ] – 1 )
= [(m+1) / 2 ]h-1 ( ((m+1) – 1) / 2 )
= [(m+1) / 2 ]h-1 (m/2)
şeklinde bir sonuca erişilir.
Kaynaklarda farklı değerler yazıyor olabilir. Bunların temel sebepler dallanma oranı (branching factor) kabulündeki farklılıklar, veya b-ağacı ile b+ağacının karıştırılması olabilir.
Gerçi bir de benim gibi geç saatte cevap veren (sabah 6) ve hata yapanlar olabilir (ben de hata yapmış olabilirim) ama işlem hatası yapmış olsam bile hesaplama mantığı yukarıdaki şekilde olacak. Yine de daha sonra bir kere daha yazdıklarımı kontrol edeceğim.
Başarılar
What is the minimum and maximum depth for a B+tree containing 100 records with an index of order 7 and data nodes holding up to 6 records? order değerini index nodlarda tutulması gereken min. eleman sayısı olarak aldım.
o zaman bu soruda minimum derinlik için hesaplarsak tüm leaf nodlar dolu olursa 100/6 tane leaf node olacak. sizin branching factor dediğiniz m+1 bu soruda 2*7+1=15 olacak. o zaman minimum derinlik (log15(100/6))+1 oluyor.
maximum derinlik için de leaf nodların da index nodların da yarısının dolu olduğunu düşünüyoruz.yani 100/(6/2) tane leaf nodumuz oluyor. branching factor de floor((7*2+1)/2)=8 oluyor. dolayısıyla maximum derinlik de (log8(100/3)) oluyor. doğru mudur?
Hayır dallanma oranı (branching factor) hatalı. Bakın soruda zaten her düğümden 7 alt düğüm çıkabileceği ve her düğümün 6 kayıt tutabileceği (node size) verilmiş. Bu azami doluluk durumudur. Oysaki siz en fazla derinlik ve dolayısıyla en fazla düğümün olduğu durumu istiyorsunuz. Dolayısıyla düğümlerin içinin en az dolulukta olması gerekir.
6/2 = 3 düğümdeki tutulan eleman sayısı (asgari)
3 + 1 = 4 ise dallanma oranınız (branching factor) olacaktır (asgari).
Yaprak düğüm ise yine aynı hesaplama ile 100/3 = 33 adet düğümden ibaret (asgari).
Dolayısıyla deriniliğiniz log433 = 3 olacaktır. Ayrıca bir de yaprakların durduğu son seviye olacağı için derinlik 4 olmalı (azami).
Yukarıda verdiğim formülü kullanırsanız,
h = log(m+1)/2(2n/(m+1)) + 1 , m = 6, n = 100 için
h = log(6+1)/2(2 x 100 /(6+1)) + 1
h = log4(200/7) + 1
h = log4(29) + 1
h = 2.418 + 1
h = 3.418 bulunur ki yarım derinlik olmayacağı için bu değerin her zaman tavanı (ceiling) alınır
h = 4 bulunmuş olur ki yukarıda formül kullanmadan hesapladığımız değer ile aynı sonuçtur.
En az derinliği bulmak için de yapraklarda 100/6 = 16.6 = 17 düğüm olacağını ve 17 düğümü indekslemek için de tam dolu düğümlerle dallanma oranı 7 olan bir ağaç olacağını dolayısıyla log717 seviye olacağını hesaplayabiliriz. Bu durumda 2 seviye indeks ve 1 seviye yapraklar olacağı için 3 seviye bulunur.
Branching factor hiçbir durumda 8 veya 15 olamaz. m+1 ile kastedilen düğüm boyutu (node size) + 1 ‘dir ve sizin durumunuzda 6+1 olarak hesaplanmalıdır zaten soruda bu değer ayrıca 7 olarak verilmiş. Ancak derindiğin yüksek çıkmasını istediğimiz soruda, (m+1) / 2 = 7/2 = 4 olarak hesaplıyoruz. Bu ise düğümlerin yarısının dolu olduğu dolayısıyla branching factor değerinin en düşük olduğu ve dolayısyıla en derin ağaç ihtimalidir.
Daha açık olması açısından yukarıdaki yazıda yer alan şekli incleyelim:
Şimdi burada düğümboyutu (m) 2 ve dallanma oranı (branching factor) 3 olmuş. Diğer bir deyişle her düğümden 3 çocuk çıkıyor. Ancak biz en derin ağacı istediğimiz için bu düğümlerin yarısının dolu olduğu yani m/2 = 2/2 = 1 olduğu durumu istiyoruz. Bu durumda her düğümden 2 çocuk çıkacak (1 + 1 = 2 veya (m+1)/2 = 3/2 = 2) hesaplama da buna göre yapılacak.
En az derinlik istendiğinde ise düğümler tam dolu kabul edilecek yani her düğümde 2 anahtar (key) olacak ve dallanma oranı 3 olacak ve buna göre hesap yapılacak.
Başarılar
şimdi anladım hocam,çok teşekkür ederim.
şadi hocam eleman ekleme örneğimizde 60 elemanını eklerken hemen kökte 50 nin yanında boş anahtar varken oraya neden eklemiyoruz?
Ekleme sırasında yapraklar öncelikli yani ekleyebildiğimiz kadar aşağıya ekliyoruz. Gerçi bunu böyle söylemek çok doğru değil ama anlaşılsın diye böyle ifade ettim. Aslında daha doğrusu şu, şayet yukarı eklerseniz o zaman o kökten 3 adet pointer çıkması gerekir yeni çıkan pointer boş bir kutuyu gösterecek ve o kutuda eleman olmayacak bu durumda 60 o kutuya eklenecek ki bu durumda da 3 düğüm (kutu) ile çözülebilecek problem için ilave fazladan bir düğüm (node) daha tutulmuş olacak. B-Tree bu anlamda hafızayı verimli kullanmaya çalışıyor.
Başarılar
verdiğiniz bilgilerden dolayı çok teşekkür ederim hocam.
Hocam B-Tree lerde aynı anahtar değeri girilebilir mi? örneğin; 35 değeri bulunuyor ve bir 35 değeri daha geliyor bu gelen değer ağaca eklenir mi? Teşekkür ederim.
Hepsi olur. Yani b-ağacında isterseniz çift girdiye (aynı değerli anahtarlar) izin vermeyebilirsiniz, isterseniz sağa isterseniz sola koyabilirsiniz. Birisini kabul ederek hep aynı şekilde çalıştırırsanız (arama, ekleme, silme vs.) sorun olmaz.
Ancak genel olarak birden fazla anahtara izin verilir (duplicate entry). Bunun en temel sebebi, veri tabanı gibi çeşitli kolonlarda b-ağacının kullanılıyor olmasıdır. Örneğin hızlı arama yapmak için veri tabanındaki bir kolon (mesela personel bilgilerinin tutulduğu bir tabloda yaş kolonu olsun), üzerinde b-ağacı oluşturmak isteyelim. Bu durumda, aynı yaşa sahip çok sayıda kişinin olmasına izin vermemiz gerekir. Diğer bir deyişle genel kullanım olarak birden fazla, aynı anahtara izin verilmesi çoğu durumda gerekir. Sağa mı sola mı konulacağı ise basit bir büyük veya küçük operatorüne bağlıdır ve programcı istediği gibi kodlayabilir.
Başarılar
Hocam B tree ile B+ tree arasındaki farklar nelerdir? Teşekkürler hocam.
Kök (root) ve yaprak (leaf) düğümleri haricindeki her düğümün en az m/2 adet elemanı bulunmalıdır. (Bu sayının altında eleman bulunursa düğüm kaldırılır)
Bu ifade yanlış kanımca sadece root hariç, leafler %50 doluluk kuralına dahildir.
Çok çok teşekkürler.
Şadi hocam
b+tree nin algoritma karmaşıklığı nedir ve b+tree ile b-tree nin algoritma karmaşıklığının farklı olmasının sebebi nedir
B+ Ağaçların ikili ağaçlar ile farklarını tanımlayınız. Bu ağaç türünün algoritma karmaşıklığını hesaplayınız. çok acil
“Arama hızının artmasına karşılık silme ve ekleme işlemlerinin nispeten yavaşlaması söz konusudur.”
Hocam kaynaklarda silme ve ekleme işleminin de O(lgn) sürede olduğundan ve hızlı olduğundan bahsedilmiş?
doğrudur logaritmik zamanda (yani O(lgn) ) çalışırlar, ve doğrudur nispeten yavaş çalışırlar (bloklarda boş yer aramak, indekslerin değiştirilmesi, düğümlerin bölünmesi gibi ilave işlemler (rebalance) için vakit harcanması gerekir).
Teşekkürler hocam. Bir de silme kısmıyla ilgili biraz daha detay verebilir misiniz? Diğer kaynaklarda birçok farklı case den bahsedilmiş.
çok faydalı olmuş teşekkürler.
Hocam merhaba,
sanirim silme biraz kisa olmus. Kisa olmus dan kastim, bazen Döndürme/kaydirma(rotation) gerek miyor mu?
Tesekkürler