B + Ağacı nedir?
Bir B + Ağacı , öncelikle birden çok seviyede dinamik indeksleme uygulamak için kullanılır. B-Ağacı ile karşılaştırıldığında, B + Ağacı, veri işaretleyicilerini yalnızca Ağacın yaprak düğümlerinde depolar, bu da aramayı daha doğru ve daha hızlı hale getirir.
Bu B + Ağacı eğitiminde şunları öğreneceksiniz:
- B + Ağacı nedir?
- B + Ağacı için Kurallar
- Neden B + Ağacı kullanmalısınız?
- B + Ağaç ve B Ağacı
- Arama İşlemi
- İşlem Ekle
- İşlemi Sil
B + Ağacı için Kurallar
İşte B + Ağacı için temel kurallar.
- Yapraklar, veri kayıtlarını saklamak için kullanılır.
- Ağacın dahili düğümlerinde saklanır.
- Bir hedef anahtar değeri dahili düğümden daha düşükse, o zaman hemen sol tarafındaki nokta izlenir.
- Bir hedef anahtar değeri dahili düğümden büyükse veya ona eşitse, o zaman sağ tarafındaki nokta izlenir.
- Kökün en az iki çocuğu vardır.
Neden B + Ağacı kullanmalısınız?
İşte, B + Ağacı kullanmanın nedenleri:
- Anahtar, öncelikle uygun Yaprağa yönlendirilerek 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ından bellek sayfasına çok sayıda anahtar kolayca yerleştirilebilir. Bu nedenle, yaprak düğümündeki ağaç verilerine hızlı bir şekilde erişecektir.
- Tüm öğelerin kapsamlı bir taraması, bir B + ağacının tüm yaprak düğümleri birbirine bağlı olduğu için yalnızca bir doğrusal geçiş gerektiren bir ağaçtır.
B + Ağaç ve B Ağacı
İşte, B + Ağacı ile B Ağacı arasındaki temel farklar
| B + Ağaç | B Ağacı |
| Arama tuşları tekrar edilebilir. | Arama tuşları gereksiz olamaz. |
| Veriler yalnızca yaprak düğümlere kaydedilir. | Hem yaprak düğümleri hem de dahili düğümler verileri depolayabilir |
| Yaprak düğümde depolanan veriler, aramayı daha doğru ve daha hızlı hale getirir. | Leaf ve dahili düğümlerde depolanan veriler nedeniyle arama yavaş. |
| Bir öğe yalnızca bir yaprak düğümünden kaldırıldığı için silme işlemi zor değildir. | Öğelerin silinmesi karmaşık ve zaman alan bir süreçtir. |
| Bağlantılı yaprak düğümleri, aramayı verimli ve hızlı hale getirir. | Yaprak düğümlerini bağlayamazsınız. |
Arama İşlemi
B + Ağacı'nda arama, yürütmek ve ondan hızlı ve doğru sonuçlar almak için en kolay prosedürlerden biridir.
Aşağıdaki arama algoritması uygulanabilir:
- Gerekli kaydı bulmak için, Ağaçtaki mevcut kayıtlar üzerinde ikili aramayı gerçekleştirmeniz gerekir.
- Arama anahtarıyla tam bir eşleşme olması durumunda, ilgili kayıt kullanıcıya döndürülür.
- Tam anahtarın üst, geçerli veya uç düğümde arama tarafından bulunmaması 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.
Arama İşlemi Algoritması
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Çıktı :
Tam anahtara karşı eşleşen kayıt kümesi kullanıcıya görüntülenir; aksi takdirde, kullanıcıya başarısız bir girişim gösterilir.
İşlem Ekle
Aşağıdaki algoritma, ekleme işlemi için geçerlidir:
- Düğümlerdeki öğelerin yüzde 50'si depolama için yeni bir yaprağa taşınır.
- Yeni Yaprağın üst öğesi, minimum anahtar değeri ve Ağaçtaki yeni bir konumla doğru bir şekilde bağlantılıdır.
- Tamamen kullanılması durumunda ana düğümü daha fazla konuma bölün.
- Şimdi, daha iyi sonuçlar için, merkez anahtar o Yaprağın en üst düzey düğümü ile ilişkilendirilmiştir.
- En üst düzey düğüm bulunmayana kadar, yukarıdaki adımlarda açıklanan işlemi yinelemeye devam edin.
İşlem Algoritması Ekle
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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 gerekli yaprak düğümüne başarıyla yerleştirecektir.
Yukarıdaki B + Ağacı örnek örneği aşağıdaki adımlarda açıklanmıştır:
- Öncelikle 3 düğümümüz var ve düğümlerdeki uygun konumlara 1, 4 ve 6 olan ilk 3 eleman ekleniyor.
- Veri dizisindeki bir sonraki değer Ağacın parçası haline getirilmesi gereken 12 değeridir.
- Bunu başarmak için düğümü bölün, işaretçi öğesi olarak 6'yı ekleyin.
- Şimdi, bir ağacın sağ hiyerarşisi oluşturulur ve kalan veri değerleri, sağdaki anahtar / değer düğümlerine göre değerlere eşit veya onlardan daha büyük geçerli kurallar akılda tutularak buna göre ayarlanır.
İşlemi Sil
B + Ağacındaki silme prosedürünün karmaşıklığı, ekleme ve arama işlevselliğinin karmaşıklığını aşar.
B + Ağacından bir öğe silerken aşağıdaki algoritma uygulanabilir:
- Öncelikle, ağaçta anahtarı ve işaretçiyi tutan bir yaprak girişi bulmalıyız. , Yaprak, kayıt silme işleminin tam koşullarını karşılıyorsa, Ağaçtan yaprak girişini silin.
- Yaprak düğümün yalnızca yarı dolu olma gibi tatmin edici faktörünü karşılaması durumunda işlem tamamlanır; aksi takdirde, Yaprak düğümünün minimum girdileri vardır ve silinemez.
- Sağdaki ve soldaki diğer bağlantılı düğümler herhangi bir girişi boşaltabilir ve ardından onları Yaprağa taşıyabilir. Bu kriterler yerine getirilmezse, ağaç hiyerarşisinde yaprak düğümü ve ona bağlı düğümü birleştirmeleri gerekir.
- Yaprak düğümün komşuları ile sağda veya solda birleştirilmesi üzerine, yaprak düğümdeki veya üst düzey düğüme işaret eden bağlı komşulardaki değerlerin girişleri silinir.
Yukarıdaki örnek, belirli bir düzenin B + Ağacından bir öğeyi kaldırma prosedürünü göstermektedir.
- İlk olarak, ağaçta silinecek öğenin tam yerleri belirlenir.
- Burada silinecek öğe, dizin yerleşiminde değil, yalnızca yaprak düzeyinde doğru bir şekilde tanımlanabilir. Bu nedenle öğe, çıplak minimum anahtarın değeri olan silme kurallarını etkilemeden silinebilir.
- Yukarıdaki örnekte, Ağaçtan 31 silmemiz gerekiyor.
- Index ve Leaf'te 31'in örneklerini bulmamız gerekiyor.
- 31'in hem İndeks hem de Yaprak düğüm seviyesinde mevcut olduğunu görebiliriz. Bu nedenle, her iki örnekten de siliyoruz.
- Ama 42'yi gösteren indeksi doldurmamız gerekiyor. Şimdi 25 yaşın altındaki doğru çocuğa bakıp minimum değeri alıp indeks olarak yerleştireceğiz. Yani, 42 mevcut tek değer olarak, endeks olacak.
İşlem Algoritmasını Sil
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Çıktı :
Anahtar "K" silinir ve anahtarlar, kardeşlerden, n'deki ve gerekirse üst düğümlerindeki değerleri ayarlamak için ödünç alınır.
Özet:
- B + Tree, veriler üzerinde doğru ve daha hızlı arama, ekleme ve silme prosedürleri yürütmek için kendi kendini dengeleyen bir veri yapısıdır.
- Bağlantılı ağaç yapısından geçmek onu verimli kıldığından, eksiksiz verileri veya kısmi verileri kolayca alabiliriz.
- B + ağaç yapısı, depolanan kayıtların sayısındaki artış / azalma ile büyür ve küçülür.
- Verilerin yaprak düğümlerde depolanması ve ardından iç düğümlerin dallara ayrılması, 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 kaplar.