Veri Yapılarında B Ağacı: Arama, Ekleme, Silme

B Ağacı Nedir?

B Ağacı B ağacı, veri arama, ekleme ve silme işlemlerini daha hızlı ve bellek açısından verimli bir şekilde gerçekleştirmek için belirli bir kurallar kümesine dayanan, kendi kendini dengeleyen bir veri yapısıdır. Bunu başarmak için, bir B ağacı oluşturmak üzere aşağıdaki kurallar izlenir.

B-ağacı, veri yapısında özel bir ağaç türüdür. Bu yöntem ilk olarak 1972'de McCreight ve Bayer tarafından tanıtılmış ve "Yükseklik Dengeli m-Yönlü Arama Ağacı" olarak adlandırılmıştır. Verilerin sıralı kalmasını sağlar ve ekleme, arama ve silme gibi çeşitli işlemleri daha kısa sürede gerçekleştirmenize olanak tanır.

B-Tree Kuralları

İşte B-ağacı oluşturmak için önemli kurallar:

• Tüm yapraklar aynı seviyede oluşturulacaktır.
• Bir B-ağacı, "derece" olarak da adlandırılan (programcı gibi harici bir aktör tarafından belirtilen) bir dizi derece ile belirlenir. m ileriye. Değeri m verilerin öncelikli olarak bulunduğu diskteki blok boyutuna bağlıdır.
• Düğümün sol alt ağacı, alt ağacın sağ tarafına göre daha küçük değerlere sahip olacaktır. Bu, düğümlerin soldan sağa doğru artan sırada sıralandığı anlamına gelir.
• Bir kök düğümün ve alt düğümlerinin içerebileceği maksimum anahtar sayısı şu formülle hesaplanır: m − 1. Örneğin:

  m = 4
  max keys: 4 − 1 = 3

• Kök düğüm hariç her düğüm, en az sayıda anahtar içermelidir. [m/2] − 1. Örneğin:

  m = 4
  min keys: 4/2 − 1 = 1

• Bir düğümün sahip olabileceği maksimum alt düğüm sayısı derecesine eşittir; m.
• Bir düğümün sahip olabileceği minimum çocuk sayısı m/2 olan mertebenin yarısıdır (tavan değeri alınır).
• Bir düğümdeki tüm anahtarlar artan düzende sıralanır.

Neden B-Tree kullanılmalı?

B-ağacı kullanmanın nedenleri şunlardır:

• Disk üzerinde yapılan okuma sayısını azaltır.
• B-ağaçları, disk boyutuna göre boyutlarını (yani alt düğüm sayısını) ayarlayacak şekilde kolayca optimize edilebilir.
• Büyük miktarda veriyi işlemek için özel olarak tasarlanmış bir tekniktir.
• Veritabanları ve dosya sistemleri için kullanışlı bir algoritmadır.
• Büyük veri bloklarını okuma ve yazma söz konusu olduğunda tercih edilebilecek iyi bir seçenek.

B Ağacının Tarihi

• Veriler diskte bloklar halinde saklanır. Bu veriler ana belleğe (veya RAM'e) getirildiğinde veri yapısı olarak adlandırılır.
• Büyük veri kümelerinde, diskte tek bir kaydı aramak tüm diskin okunmasını gerektirir; bu da yüksek disk erişim sıklığı ve veri boyutu nedeniyle zaman ve ana bellek tüketimini artırır.
• Bu sorunu aşmak için, kayıtların bulundukları bloklara göre kayıt referanslarını kaydeden indeks tabloları oluşturulur. Bu, zaman ve bellek tüketimini önemli ölçüde azaltır.
• Elimizde çok büyük veri olduğu için çok seviyeli indeks tabloları oluşturabiliyoruz.
• Çok seviyeli bir indeks, anahtarlama için bir B ağacı kullanılarak tasarlanabilir.ping Veriler kendi kendini dengeleyecek şekilde sıralanmıştır.

Ara Operayon

B ağacında arama işlemi en basit işlemdir. Aşağıdaki algoritma uygulanır:

• Aranacak anahtar (değer) "k" olsun.
• Kökten başlayarak aramaya başlayın ve aşağıya doğru yinelemeli olarak ilerleyin.
• Eğer k kök değerinden küçükse, sol alt ağaçta arama yapın; eğer k kök değerinden büyükse, sağ alt ağaçta arama yapın.
• Düğümde bulunan k varsa, düğümü döndürmeniz yeterlidir.
• Düğümde k bulunamazsa, daha büyük bir anahtarla çocuğa doğru ilerleyin.
• Ağaçta k bulunamazsa NULL değerini döndürürüz.

Ekle Operayon

B ağacı kendi kendini dengeleyen bir ağaç olduğundan, herhangi bir düğüme zorla anahtar ekleyemezsiniz. Aşağıdaki algoritma geçerlidir:

• Arama işlemini çalıştırın ve uygun ekleme yerini bulun.
• Yeni anahtarı uygun konuma ekleyin, ancak düğümde zaten maksimum sayıda anahtar varsa:
• Düğüm, yeni eklenen anahtarla birlikte ortadaki öğeden ayrılacaktır.
• Ortadaki eleman diğer iki alt düğümün ebeveyni olacaktır.
• Düğümlerin anahtarları artan sırada yeniden düzenlemesi gerekir.

Yukarıdaki örnekte:

• Düğümdeki uygun konumda anahtarı arayın.
• Hedef düğüme anahtarı ekleyin ve kuralları kontrol edin.
• Ekleme işleminden sonra, düğümün minimum 1 olan anahtar sayısından fazla veya ona eşit anahtar sayısı var mı? Bu durumda evet, var. Bir sonraki kuralı kontrol edin.
• Ekleme işleminden sonra, düğümün maksimum sayı olan 3'ten fazla anahtarı var mı? Bu durumda hayır, yok. Bu, B ağacının herhangi bir kuralı ihlal etmediği ve ekleme işleminin tamamlandığı anlamına gelir.

Yukarıdaki örnekte:

• Düğüm maksimum anahtar sayısına ulaştı.
• Düğüm bölünecek ve ortadaki anahtar, diğer iki düğümün kök düğümü haline gelecektir.
• Çift sayıda anahtar olması durumunda, orta düğüm sol veya sağ önyargıya göre seçilecektir.

Yukarıdaki örnekte:

• Düğümün maksimum anahtar sayısından daha az anahtarı var.
• 1, 3'ün yanına eklenmiş ancak artan sıralama kuralı ihlal edilmiş.
• Bu sorunu düzeltmek için anahtarlar sıralandı.

Benzer şekilde, 13 ve 2 sayıları da düğümlere kolayca eklenebilir, çünkü bu sayılar düğümler için geçerli olan "maksimum anahtar sayısından az" kuralını karşılamaktadır.

Yukarıdaki örnekte:

• Düğümün maksimum anahtarlara eşit anahtarları var.
• Anahtar hedef düğüme ekleniyor, ancak maksimum anahtar kuralını ihlal ediyor.
• Hedef düğüm bölünmüştür ve sol eğilime göre orta anahtar artık yeni alt düğümlerin ebeveynidir.
• Yeni düğümler artan sırada düzenlenir.

Benzer şekilde, yukarıdaki kurallara ve durumlara dayanarak değerlerin geri kalanı B Ağacına kolayca eklenebilir.

Sil Operayon

Silme işlemi, ekleme ve arama işlemlerine göre daha fazla kurala sahiptir. Aşağıdaki algoritma uygulanır:

• Arama işlemini çalıştırın ve düğümlerde hedef anahtarı bulun.
• Aşağıdaki bölümlerde açıklandığı gibi, hedef tuşun konumuna bağlı olarak üç koşul uygulanır.

Hedef anahtar yaprak düğümdeyse

• Target Bu, yaprak düğümde minimum anahtar sayısından daha fazla sayıda anahtar içeriyor. Bunu silmek, B Ağacının özelliğini ihlal etmeyecektir.
• Target Bu, yaprak düğümde yer alıyor ve minimum anahtar düğümlerine sahip. Bunu silmek, B Ağacının özelliğini ihlal edecektir.
• Hedef düğüm, hemen solundaki veya hemen sağındaki (kardeş) düğümden bir anahtar ödünç alabilir.
• Kardeş diyecek Evet Minimum sayıdan daha fazla anahtara sahipse.
• Anahtar üst düğümden ödünç alınacak, maksimum değer üst düğüme aktarılacak, üst düğümün maksimum değeri hedef düğüme aktarılacak ve hedef değer silinecektir.
• Target Anahtar yaprak düğümde bulunuyor, ancak kardeş düğümlerin hiçbirinde minimum sayıdan fazla anahtar yok: anahtarı arayın, kardeş düğümlerle ve üst düğümlerin minimum değeriyle birleştirin, toplam anahtar sayısı artık minimum değerden fazla olacak ve hedef anahtar, bir üst düğümün minimum değeriyle değiştirilecektir.

Hedef anahtar dahili bir düğümdeyse

• Ya sıralı bir öncül ya da sıralı bir ardıl seçin.
• Sıralı bir öncül söz konusu olduğunda, sol alt ağacındaki en büyük anahtar seçilecektir.
• Sıralı ardıl durumunda, sağ alt ağacındaki en küçük anahtar seçilecektir.
• Hedef anahtarın sıralı öncülünün minimum anahtar sayısından daha fazla anahtarı varsa, ancak o zaman hedef anahtarı sıralı öncüllerin maksimum değeriyle değiştirebilir.
• Hedef anahtarın sıralı öncülünün minimum anahtar sayısından fazla anahtarı yoksa, sıralı ardılın minimum anahtarını arayın.
• Hedef anahtarın sıralı öncülü ve halefinin her ikisi de minimum anahtarlardan daha az anahtara sahipse öncül ve ardılları birleştirin.

Hedef anahtar bir kök düğümdeyse

• Sıralı öncül alt ağacının en büyük elemanıyla değiştirin.
• Silme işleminden sonra hedef düğümde minimum değerden daha az anahtar kalırsa, hedef düğüm, kardeş düğümünün ebeveyni aracılığıyla kardeş düğümünden maksimum değeri ödünç alır.
• Hedef, üst öğenin maksimum değerini alacak, ancak kardeş öğenin maksimum değerine sahip düğümlerini de içerecektir.

Şimdi silme işlemini bir örnekle anlayalım.

Yukarıdaki diyagram, bir B-ağacındaki silme işleminin farklı durumlarını göstermektedir. Bu B-ağacı 5. derecedendir; bu, herhangi bir düğümün sahip olabileceği en az 3 çocuk düğümü ve en fazla 5 çocuk düğümü sayısı anlamına gelir. Buna karşılık, herhangi bir düğümün sahip olabileceği en az ve en fazla anahtar sayısı sırasıyla 2 ve 4'tür.

Yukarıdaki örnekte:

• Hedef düğüm, silinecek hedef anahtara sahiptir.
• Hedef düğümde minimum anahtar sayısından daha fazla anahtar bulunmaktadır.
• Anahtarı silmeniz yeterli.

Yukarıdaki örnekte:

• Hedef düğümün anahtarları minimum anahtar sayısına eşit olduğundan, koşulları ihlal edeceği için doğrudan silemeyiz.

Şimdi, aşağıdaki diyagram bu anahtarın nasıl silineceğini açıklıyor:

• Hedef düğüm, ardılı (sağ kardeş) olmadığı için, bu durumda doğrudan kardeşinden, yani sıralı öncülünden (sol kardeş) bir anahtar ödünç alacaktır.
• Sıralı öncülün maksimum değeri üst düğüme aktarılacak ve üst düğüm de maksimum değeri hedef düğüme aktaracaktır (aşağıdaki şemaya bakınız).

Aşağıdaki örnek, sıralı halefinden değere ihtiyaç duyan bir anahtarın nasıl silineceğini göstermektedir.

• Hedef düğüm, en yakın kardeşinden, bu durumda sıradaki ardılından (sağ kardeş) bir anahtar ödünç alacaktır, çünkü sıradaki öncülü (sol kardeş) minimum anahtarlara eşit anahtarlara sahiptir.
• Sıralı halefin minimum değeri ebeveyne aktarılacak ve ebeveyn maksimum değeri hedef düğüme aktaracaktır.

Aşağıdaki örnekte, hedef düğümün hedef düğüme anahtar verebilecek herhangi bir kardeş düğümü bulunmamaktadır. Bu nedenle, birleştirme gereklidir. Bu tür bir anahtarın silinme prosedürüne bakın:

• Hedef düğümü, üst anahtar ile birlikte, kendisine en yakın kardeş düğümlerinden herhangi biriyle birleştirin.
• Birleştirme işlemini gerçekleştiren iki düğüm arasında yer alan üst düğümün anahtarı seçilir.
• Birleştirilmiş düğümden hedef anahtarı silin.

Sil Operation Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Çıktı: En büyük öğe B Ağacından silinir.

SSS