B+ TREE : Ara, Ekle ve Sil OperaÖrnekler

B+ Ağacı nedir?

A B+ Ağacı öncelikle birden fazla düzeyde dinamik indekslemenin uygulanması için kullanılır. B- Ağacı ile karşılaştırıldığında B+ Ağacı, veri işaretçilerini yalnızca Ağacın yaprak düğümlerinde saklar, bu da daha fazla arama işleminin daha doğru ve daha hızlı olmasını sağlar.

B+ Ağacı Kuralları

İşte B+ Ağacı için temel kurallar.

• Yapraklar veri kayıtlarını depolamak için kullanılır.
• Ağacın dahili düğümlerinde depolanır.
• Bir hedef anahtar değeri dahili düğümden küçükse, hemen sol tarafındaki nokta takip edilir.
• Bir hedef anahtar değeri dahili düğümden büyük veya ona eşitse, o zaman sağ tarafındaki nokta takip edilir.
• Kökün en az iki çocuğu vardır.

Neden B+ Ağacı kullanılmalı?

B+ Tree'yi kullanmanın nedenleri şunlardır:

• Anahtar öncelikle uygun Yaprağa yönlendirerek aramaya yardımcı olmak için kullanılır.
• B+ Ağacı, bir ağaçtaki artış ve azalmayı yönetmek için bir "doldurma faktörü" kullanır.
• B+ ağaçlarında, iç düğümlerle ilişkili verilere sahip olmadıkları için çok sayıda anahtar kolayca hafıza sayfasına yerleştirilebilir. Bu nedenle yaprak düğümünde bulunan ağaç verilerine hızlı bir şekilde ulaşacaktır.
• Tüm öğelerin kapsamlı bir şekilde taranması, bir B+ ağacının tüm yaprak düğümlerinin birbirine bağlı olması nedeniyle yalnızca tek bir doğrusal geçişe ihtiyaç duyan bir ağaçtır.

B+ Ağacı ve B Ağacı

İşte B+ Ağacı ile B Ağacı arasındaki temel farklar:

B+ Ağacı	B Ağacı
Arama tuşları tekrarlanabilir.	Arama anahtarları gereksiz olamaz.
Veriler yalnızca yaprak düğümlere kaydedilir.	Hem yaprak düğümler hem de dahili düğümler veri depolayabilir
Yaprak düğümde depolanan veriler, aramanın daha doğru ve daha hızlı olmasını sağlar.	Leaf ve dahili düğümlerde depolanan veriler nedeniyle arama yavaştır.
Bir öğe yalnızca bir yaprak düğümden kaldırıldığı için silme işlemi zor değildir.	Öğelerin silinmesi karmaşık ve zaman alıcı bir işlemdir.
Bağlantılı yaprak düğümleri aramayı verimli ve hızlı hale getirir.	Yaprak düğümleri bağlayamazsınız.

Ara Operayon

B+ Tree'de arama, yürütülmesi ve ondan hızlı ve doğru sonuçlar alınması en kolay prosedürlerden biridir.

Aşağıdaki arama algoritması uygulanabilir:

• Gerekli kaydı bulmak için aşağıdaki komutu çalıştırmanız gerekir: Ikili arama Ağaçtaki mevcut kayıtlar üzerinde.
• Arama anahtarıyla tam eşleşme olması durumunda ilgili kayıt kullanıcıya döndürülür.
• Ana düğümde, geçerli düğümde veya yaprak düğümde yapılan aramada tam anahtarın bulunamaması durumunda kullanıcıya bir "bulunamadı mesajı" görüntülenir.
• Daha iyi ve daha doğru sonuçlar için arama süreci yeniden çalıştırılabilir.

Ara OperaAlgoritma

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

Çıktı:

Tam anahtara karşılık gelen eşleşen kayıt kullanıcıya gösterilir; aksi takdirde kullanıcıya başarısız bir girişim gösterilir.

Ekle Operayon

Ekleme işlemi için aşağıdaki algoritma uygulanabilir:

• Düğümlerdeki öğelerin yüzde 50'si depolama için yeni bir yaprağa taşınır.
• Yeni Yaprağın ebeveyni, minimum anahtar değeriyle ve Ağaçtaki yeni bir konumla doğru bir şekilde bağlanır.
• Tam olarak kullanılması durumunda ana düğümü daha fazla konuma bölün.
• Artık daha iyi sonuçlar elde etmek için orta anahtar, o Yaprağın en üst düzey düğümüyle ilişkilendirilir.
• Üst düzey düğüm bulununcaya kadar yukarıdaki adımlarda açıklanan işlemi yinelemeye devam edin.

Ekle OperaAlgoritma

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. Else, divide the node into more locations to fit more records.
      a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
      b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
      c. Divide the top-level node if it gets full of keys and addresses.
          i. Similarly,  insert a key in the center of the top-level node in the hierarchy of the Tree.
     d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore. 

3) Build a new top-level root node of 1 Key and 2 indicators.  

Çıktı:

Algoritma, öğeyi belirleyecek ve onu gerekli yaprak düğümüne başarıyla yerleştirecektir.

Yukarıdaki B+ Ağacı örnek örneği aşağıdaki adımlarda açıklanmaktadır:

• Öncelikle 3 adet düğümümüz var ve ilk 3 eleman olan 1, 4 ve 6, düğümlerdeki uygun yerlere ekleniyor.
• Veri serisindeki bir sonraki değer, Ağacın bir parçası yapılması gereken 12'dir.
• Bunu başarmak için düğümü bölün, işaretçi öğesi olarak 6 ekleyin.
• Artık bir ağacın sağ hiyerarşisi oluşturulur ve geri kalan veri değerleri, sağdaki anahtar/değer düğümlerine göre geçerli değerlere eşit veya daha büyük kuralları akılda tutularak buna göre ayarlanır.

Sil Operayon

B+ Ağacındaki silme prosedürünün karmaşıklığı, ekleme ve arama işlevselliğinin karmaşıklığını aşmaktadır.

B+ Ağacından bir öğeyi silerken aşağıdaki algoritma uygulanabilir:

• Öncelikle Ağaçta anahtarı ve işaretçiyi tutan bir yaprak girişi bulmamız gerekiyor. , Yaprak kayıt silme koşullarını tam olarak karşılıyorsa yaprak girişini Ağaçtan silin.
• Yaprak düğümü yalnızca yarı doluluk gibi tatmin edici bir faktörü karşılıyorsa, işlem tamamlanır; aksi takdirde, Yaprak düğümü minimum girdiye sahip olur ve silinemez.
• Sağdaki ve soldaki diğer bağlı düğümler herhangi bir girişi boşaltabilir ve ardından bunları Yaprak'a taşıyabilir. Bu kriterlerin karşılanmaması durumunda yaprak düğümü ve ona bağlı düğümü ağaç hiyerarşisinde birleştirmeleri gerekir.
• Yaprak düğümün sağdaki veya soldaki komşularıyla birleşmesi üzerine, yaprak düğümdeki veya bağlantılı komşudaki üst düzey düğüme işaret eden değer girişleri silinir.

Yukarıdaki örnek, belirli bir sıradaki B+ Ağacından bir öğeyi kaldırma prosedürünü göstermektedir.

• Öncelikle silinecek elemanın kesin yerleri Ağaçta belirlenir.
• Burada silinecek öğe indeks yerleşiminde değil, yalnızca yaprak seviyesinde doğru bir şekilde tanımlanabilir. Dolayısıyla öğe, minimum minimum anahtarın değeri olan silme kurallarını etkilemeden silinebilir.

• Yukarıdaki örnekte 31'i Ağaçtan silmemiz gerekiyor.
• Index ve Leaf'te 31'in örneklerini bulmamız gerekiyor.
• 31'in hem Dizin hem de Yaprak düğüm düzeyinde mevcut olduğunu görebiliriz. Bu nedenle, onu her iki örnekten de siliyoruz.
• Ancak 42'yi gösteren indeksi doldurmamız gerekiyor. Şimdi sağdaki 25 yaş altı çocuğa bakıp minimum değeri alıp indeks olarak yerleştireceğiz. Yani mevcut tek değer olan 42, endeks haline gelecektir.

Sil OperaAlgoritma

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) If n has at least ceil(m/2) keys, done!
            ii) If n has less than ceil(m/2) keys,
                If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

Çıktı:

“K” Anahtarı silinir ve gerekirse n ve onun ana düğümlerindeki değerleri ayarlamak için kardeşlerden anahtarlar ödünç alınır.

ÖZET

• B+ Ağacı kendi kendini dengeleyen bir ağaçtır veri yapısı Verilerde doğru ve hızlı arama, ekleme ve silme işlemlerini gerçekleştirmek için
• Bağlantılı ağaç yapısından geçmek onu verimli kıldığından tam veriye veya kısmi veriye kolaylıkla ulaşabiliriz.
• B+ ağaç yapısı saklanan kayıt sayısındaki artış/azalışla birlikte büyür ve küçülür.
• Verilerin yaprak düğümlerde depolanması ve ardından dahili düğümlerin dallanması, ağaç yüksekliğini açıkça kısaltır, bu da disk giriş ve çıkış işlemlerini azaltır ve sonuçta depolama aygıtlarında çok daha az yer tüketir.