B+ AĞACI: Arama, Ekleme ve Silme Operaleri

B+ Ağacı nedir?

A B+ Ağacı B+ ağacı, öncelikle birden fazla seviyede dinamik indeksleme uygulamak için kullanılır. B-ağacına kıyasla, B+ ağacı veri işaretçilerini yalnızca ağacın yaprak düğümlerinde saklar; bu da arama sürecini daha doğru ve hızlı hale getirir.

B+ Ağacı Kuralları

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

• Yapraklar veri kayıtlarını depolamak için kullanılır.
• Kayıtlar, ağacın iç düğümlerinde saklanır.
• Hedef anahtar değeri dahili düğümden küçükse, hemen solundaki işaretçi takip edilir.
• Hedef anahtar değeri dahili düğümden büyük veya ona eşitse, hemen sağındaki işaretçi takip edilir.
• Kökün en az iki çocuğu vardır.

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

İşte B+ Ağacını kullanmanın nedenleri:

• Anahtarlar öncelikle doğru sayfaya yönlendirerek aramayı kolaylaştırmak için kullanılır.
• B+ ağacı, ağaçtaki artış ve azalışı yönetmek için bir "doluluk 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.
• B+ ağacının tüm yaprak düğümleri birbirine bağlı olduğundan, tüm elemanların kapsamlı bir şekilde taranması yalnızca tek bir doğrusal geçiş gerektirir.

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

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

Ara Operayon

B+ ağacında arama, gerçekleştirilmesi en kolay işlemlerden biridir ve hızlı ve doğru sonuçlar verir.

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ğeri ve Ağaçtaki yeni bir konumla doğru bir şekilde bağlantılıdır.
• Tam olarak kullanılması durumunda ana düğümü daha fazla konuma bölün.
• Artık daha iyi sonuçlar için, merkez anahtar o yaprak düğümün en üst düzey düğümüyle ilişkilendiriliyor.
• Üst düzey düğüm bulununcaya kadar yukarıdaki adımlarda açıklanan işlemi yinelemeye devam edin.

Ekle OperaAlgoritma

1. If 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 düğümümüz var ve 1, 4 ve 6 olan ilk 3 eleman, düğümlerin uygun yerlerine ekleniyor.
• Veri serisindeki bir sonraki değer 12'dir ve bu değerin Ağacın bir parçası haline getirilmesi gerekmektedir.
• Bunu başarmak için düğümü bölün ve işaretçi eleman olarak 6 ekleyin.
• Şimdi, bir ağacın sağ hiyerarşisi oluşturuluyor ve kalan veri değerleri buna göre kee tarafından ayarlanıyor.ping Sağdaki anahtar-değer düğümlerine karşılık gelen eşit veya büyük değerler için geçerli kuralları aklınızda bulundurun.

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 girdisi bulmamız, ardından yaprak girdisi kayıt silme koşullarını tam olarak karşılıyorsa ağaçtan silmemiz gerekiyor.
• Eğer yaprak düğümü yalnızca yarı dolu olma şartını karşılıyorsa, işlem tamamlanmıştır; aksi takdirde, yaprak düğümünde minimum sayıda giriş vardır ve silinemez.
• Sağ ve soldaki diğer bağlantılı düğümler, herhangi bir girişi boşaltabilir ve ardından bunları yaprağa taşıyabilir. Bu kriterler karşılanmazsa, ağaç hiyerarşisinde yaprak düğümü ve ona bağlı düğümü birleştirmelidirler.
• Bir yaprak düğümün sağındaki veya solundaki komşularıyla birleşmesi durumunda, yaprak düğümde veya üst düzey düğüme işaret eden bağlantılı komşudaki değer girdileri silinir.

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

• Öncelikle silinecek elemanın kesin yerleri Ağaçta belirlenir.
• Burada, silinecek öğe yalnızca en alt düzeyde doğru bir şekilde tanımlanabilir, dizin konumunda değil. Bu nedenle, öğe, silme kurallarını etkilemeden silinebilir; bu kurallar, en temel anahtarın değeridir.

• Yukarıdaki örnekte 31'i Ağaçtan silmemiz gerekiyor.
• Index ve Leaf'te 31 sayısının geçtiği yerleri bulmamız gerekiyor.
• 31 sayısının hem Index hem de Leaf düğüm seviyesinde mevcut olduğunu görüyoruz. Bu nedenle, her iki örnekten de siliyoruz.
• Ancak 42'ye işaret eden indeksi doldurmamız gerekiyor. Şimdi 25'in altındaki sağdaki çocuğa bakacağız ve en küçük değeri alıp indeks olarak yerleştireceğiz. Dolayısıyla, mevcut tek değer 42 olduğundan, bu indeks olacaktır.

Sil OperaAlgoritma

1) Start at the root and go up to the 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 üst düğümlerindeki değerleri ayarlamak için kardeş düğümlerden anahtarlar ödünç alınır.

SSS