Merhaba Yazılım Karavanı Ailesi 🙂

Bir önceki yazımda ağaç veri yapısından bahsetmiştim. Şimdi sizlere B Ağaçlarından bahsedecek ve örnekler çözeceğim. Bu yazıda B ağaçlarına eleman ekleme, daha sonraki yazılarımda ise B ağaçlarından eleman silme ve B ağaçlarında dolaşım işlemlerini gerçekleyeceğiz. İşinize yaramasını dilerim. B ağaçları, ilk kez Boeing firmasında çalışan Bayer isimli bir mühendis tarafından tanıtılmıştır.
B ağaçları, hem sıralı hem de doğrudan erişimleri desteklediği için bilgisayar literatüründe en çok kullanılan veri yapılarından birisi olmuştur.

Kullanıldığı yerler:
– Veritabanı Yönetim Sistemleri
– İşletim Sistemlerinin Dosya-Dizin Yapıları

B ağaçları ikili arama ağaçlarının aksine bir düğümde birden fazla veri tutulmasına olanak sağlamaktadır. Bir düğümde kaç veri tutulacağı ise o ağacın kapasite derecesi (capacity order-d) ile belirlenmektedir.

d, B ağacının kapasite değeri olacak şekilde;
1. Kök düğümde en az 1, en çok 2d kayıt tutulabilir.
2. Kök düğümden en az 2, en çok (2d+1) düğüme işaret edilebilir.
3. Kök düğüm dışındaki herhangi bir düğüm en az d, en çok 2d kayıt içerebilir.
4. Kök düğüm dışındaki herhangi bir düğüm en az (d+1), en çok (2d+1) düğüme işaret eder.
5. B ağaçları, ikili arama ağaçlarının aksine yukarıdan aşağıya doğru değil de aşağıdan yukarıya doğru büyür. Bu doğrultuda B ağaçları rotasyon işlemlerine gerek duymaz ve sürekli dengeli halde bulunurlar.

**ÖNEMLİ NOT** B ağaçları, kök düğüm dışında diğer düğümlerin en az %50 doluluk oranını ister.

Örneğin; Kapasite derecesi (d=1) 1 olan B ağacı düğümü, i. özellikten en az 1, en çok 2 kayıt tutabilir.

ii. Özellikten yola çıkarak, kök düğümünün en az 2, en çok ise 3 düğüme işaret etmesi gerektiğini söyleyebiliriz.
Bu durumda basit bir B ağacı oluşturacak olursak;

Şeklinde düşünebiliriz. B ağaçlarına karşı ufak da olsa fikrimiz oluştuğuna göre B ağacına eleman ekleme ile devam edelim.

B Ağacına Eleman Ekleme (Insert B-Tree)
78, 52, 81, 40, 33, 90, 85, 20, 38 sayılarını kapasite derecesi (d=1) olan B ağacına yerleştirelim.

1) d=1 olduğu için kök düğümü en fazla 2 elaman alabilir. Ayrıca elemanları eklerken %50 doluluk şartını unutmamamız da fayda var. 78 elemanını ekledik. Root düğüm maksimum iki eleman alabileceği için sıradaki eleman olan 52 yi ekleyelim.

ii.

2) Üçüncü eleman olan 81’i rootta yer bulunmadığı için artık roota ekleyemeyiz. Peki şimdi ne yapmalıyız? İlk üç elamanı yan yana fakat sıralı olarak düşünelim.
52 78 81, bu durumda ortanca sayı yukarı taşınmalıdır.

iii.

Hala her bir düğümün iki eleman alabileceğini unutmamalıyız 🙂

3) Şimdi geldik 4. Eleman olan 40 sayısını B ağacına eklemeye…

İkili arama ağaçları gibi düşündüğümüzde 40<78 olduğu için sol tarafa kayacaktır. Sol taraftaki düğümde ise 40<52 olduğu aynı zamanda hala bir elemanlık yer olduğu için 40 ı ağaca eklemekte hiçbir sorun bulunmamaktadır (d=1 olduğu için her düğümde 1 eleman %50 doluluk şartını sağlar).

iv.

4) Elemanımız olan 33 ü eklememiz gerekiyor. Fakat biliyorum ki siz de sol taraftaki düğümün dolmuş olduğunu farkettiniz. Az önce roota yaptığımız yukarı kaydırma işlemini şimdi çocuk düğümlere yapalım.

Bu durumda 33 40 52 ‘yi sıraladığımız zaman 40’ın ortanca olduğunu ve yukarı taşması gerektiğini görüyoruz.

Sanırım buraya kadar hiçbir sorunumuz kalmadı. Sıradaki elemana bakalım 🙂

5) 90 ı eklediğimiz zaman hiçbir taşırma işlemi yapmamıza gerek yok çünkü 78<90 ve 81<90 olduğu için 81 elemanın bulunduğu düğümde hala bir elemanlık boşluk bulunmaktadır. Ee ekleyelim o halde 🙂

vi.

6) 85’ eklemek istediğimiz zaman kaydırma işlemi yapmamız gerekmektedir. Bu durumda 81 85 ve 90’ı sıralayıp 85’i kaydırmamız gerektiğini gördük. Peki 85’i kaydırdığımız zaman kökün de dolu olduğunu gördük mü? 40 78 ve 85 elemanlarını d=1’ den ötürü aynı rootta tutamayacağımız için rottan da kaydırma işlemi yapmamız gerekiyor. Bu durumda 40 78 ve 85’i sıralayarak ortanca olan 78’i root yapalım.

vii.

7) Ağacın 6. Adımdaki son haline baktığımız zaman 20 elamanını rahatlıkla ağacın en soluna yerleştirebilecek olduğumuzu görüyoruz.

viii.

8) Geldik son eleman olan 38’i eklemeye… Baktığımız zaman sol tarafta olması gerektiğinin hepimiz farkındayız fakat sol tarafta nereye yerleştirmeliyiz? Bu durumda şunu yapmalıyız 38<78 ve 38<40 olduğu için tekrar sol tarafa yerleşmelidir. Bu durumda 20 33 ve 38’i sıralayıp 33’ün bir üst düğüme kayması gerektiğini gördük. O halde:

ix.