B+ Ağacı, etkili ekleme, silme ve arama işlemlerine olanak tanıyan B Ağacının bir uzantısıdır.
B Ağacında, Anahtarlar ve kayıtlar hem dahili hem de yaprak düğümlerde saklanabilir. Oysa B+ ağacında kayıtlar (veriler) yalnızca yaprak düğümlerde saklanabilirken, iç düğümler yalnızca anahtar değerleri saklayabilir.
Bir B+ ağacının yaprak düğümleri, arama sorgularını daha verimli hale getirmek için tek bağlantılı listeler biçiminde birbirine bağlanır.
B+ Ağacı, ana bellekte saklanamayan büyük miktarda veriyi depolamak için kullanılır. Ana belleğin boyutu her zaman sınırlı olduğundan B+ ağacının iç düğümleri (kayıtlara erişim anahtarları) ana bellekte, yaprak düğümleri ise ikincil bellekte saklanır.
B+ ağacının iç düğümlerine genellikle indeks düğümleri adı verilir. Aşağıdaki şekilde 3. dereceden bir B+ ağacı gösterilmektedir.
B+ Ağacının Avantajları
- Kayıtlar eşit sayıda disk erişimiyle getirilebilir.
- Ağacın yüksekliği B ağacına göre dengeli ve az kalır.
- B+ ağacında saklanan verilere doğrudan ve sıralı olarak erişebiliriz.
- Anahtarlar indeksleme için kullanılır.
- Veriler yalnızca yaprak düğümlerde depolandığından daha hızlı arama sorguları.
B Ağacı VS B+ Ağacı
| SN | B Ağacı | B+ Ağacı |
|---|---|---|
| 1 | Arama anahtarları tekrar tekrar saklanamaz. | Yedek arama anahtarları mevcut olabilir. |
| 2 | Veriler iç düğümlerin yanı sıra yaprak düğümlerde de saklanabilir | Veriler yalnızca yaprak düğümlerde saklanabilir. |
| 3 | Veriler yaprak düğümlerin yanı sıra iç düğümlerde de bulunabildiğinden, bazı verileri aramak daha yavaş bir süreçtir. | Veriler yalnızca yaprak düğümlerde bulunabildiğinden arama nispeten daha hızlıdır. |
| 4 | Dahili düğümlerin silinmesi çok karmaşık ve zaman alıcıdır. | Öğe her zaman yaprak düğümlerden silineceğinden silme işlemi hiçbir zaman karmaşık bir süreç olmayacaktır. |
| 5 | Yaprak düğümler birbirine bağlanamaz. | Arama işlemlerini daha verimli hale getirmek için yaprak düğümler birbirine bağlanır. |
B+ Ağacına Ekleme
Aşama 1: Yeni düğümü yaprak düğüm olarak ekleyin
Adım 2: Yaprakta gerekli alan yoksa düğümü bölün ve ortadaki düğümü bir sonraki dizin düğümüne kopyalayın.
Aşama 3: Dizin düğümünde gerekli alan yoksa düğümü bölün ve ortadaki öğeyi sonraki dizin sayfasına kopyalayın.
Örnek :
Aşağıdaki şekilde gösterilen 5. sıradaki B+ ağacına 195 değerini ekleyin.
190'dan sonra 120'nin sağ alt ağacına 195 eklenecektir. İstenilen konuma yerleştirin.
Düğüm maksimum öğe sayısından (4) daha fazlasını içerir, bu nedenle onu bölün ve ortanca düğümü ebeveyne yerleştirin.
Artık indeks düğümü 6 çocuk ve 5 anahtar içeriyor, bu da B+ ağaç özelliklerini ihlal ediyor, bu nedenle onu aşağıdaki gibi bölmemiz gerekiyor.
B+ Ağacında Silme
Aşama 1: Anahtarı ve verileri yapraklardan silin.
Adım 2: Yaprak düğüm minimum sayıda öğeden daha az öğe içeriyorsa, düğümü kardeşiyle birleştirin ve aralarındaki anahtarı silin.
Aşama 3: Dizin düğümü minimum sayıda öğeden az içeriyorsa, düğümü kardeşle birleştirin ve anahtarı aralarında aşağı doğru hareket ettirin.
Örnek
Aşağıdaki şekilde gösterilen B+ Ağacından 200 anahtarını silin.
java eşittir
190'ın sağ alt ağacında 195'ten sonra 200 var. Onu silin.
195, 190, 154 ve 129'u kullanarak iki düğümü birleştirin.
Şimdi, öğe 120, düğümde bulunan ve B+ Ağacı özelliklerini ihlal eden tek öğedir. Bu nedenle 60, 78, 108 ve 120'yi kullanarak birleştirmemiz gerekiyor.
Artık B+ ağacının yüksekliği 1 azalacak.
