B ağacı ve ikili ağaç arasındaki diğer bir fark, B ağacının tüm alt düğümlerinin aynı seviyede olması ve ikili ağacın böyle bir kısıtlamaya sahip olmaması gerektiğidir. Bir ikili ağacın maksimum 2 alt ağacı veya düğümü olabilir, oysa B ağacında M, B ağacının sırası olduğu M alt sınıfı veya düğümü olmayabilir.
Karşılaştırma Tablosu
| Karşılaştırma için temel | B-tree | İkili ağaç |
|---|---|---|
| Temel kısıtlama | Bir düğümde maksimum M sayısı alt düğümlere sahip olabilir (burada M ağacın sırasıdır). | Bir düğümde en fazla 2 alt ağaç sayısı olabilir. |
| Kullanılmış | Veriler diskte depolandığında kullanılır. | Kayıtlar ve veriler RAM'de depolandığında kullanılır. |
| Ağacın yüksekliği | log M N (m, M yollu ağacın sırasıdır) | log 2 N |
| Uygulama | Birçok DBMS'de kod indeksleme veri yapısı. | Kod optimizasyonu, Huffman kodlaması vb. |
B-tree'un tanımı
B-ağacı dengeli M-yollu bir ağaçtır ve aynı zamanda dengeli ağaç olarak da bilinir. Düğümlerin düzensiz hareketler temelinde organize edildiği ikili arama ağacına benzer. B-ağacının uzay karmaşıklığı O (n) 'dir. Ekleme ve silme süresi karmaşıklığı O (log n) 'dir.
B ağacı için geçerli olması gereken belirli koşullar vardır:
- Ağacın yüksekliği mümkün olduğunca asgari olmalıdır.
- Ağacın yapraklarının üstünde boş alt ağaç bulunmamalıdır.
- Ağacın yaprakları aynı seviyede gelmelidir.
- Bütün düğümler izin düğümleri dışında en az sayıda çocuğa sahip olmalıdır.
M düzeninde B ağacının özellikleri
- Her bir düğüm maksimum M çocuk sayısına ve minimum M / 2 çocuk sayısına veya herhangi bir sayıya 2 ila maksimum olabilir.
- Her bir düğümde, maksimum M-1 tuşlarına sahip çocuklardan bir anahtar daha az bulunur.
- Anahtarların düzenlenmesi düğümlerin içinde belirli bir düzendedir. Anahtarın solunda bulunan alt ağaçta bulunan tüm anahtarlara, anahtarın öncülleridir ve anahtarın sağında bulunanlara halefler adı verilir.
- Tam bir düğümün yerleştirilmesi sırasında, ağaç iki parçaya bölünür ve ortanca değere sahip olan anahtar üst düğüme yerleştirilir.
- Birleştirme işlemi, düğümler silindiğinde gerçekleşir.
İkili ağaç tanımı
Bir İkili ağaç, alt düğümleri için en fazla iki işaretçiye sahip olan bir ağaç yapısıdır. Bir düğümün sahip olabileceği en yüksek derecenin 2 olduğu ve sıfır veya bir derecelik düğümün de olabileceği anlamına gelir.
İkili bir ağacın kesinlikle ikili ağaç, tam ikili ağaç, uzatılmış ikili ağaç, vs. gibi bazı varyasyonları vardır.
- Kesinlikle ikili ağaç, her bir terminal olmayan düğümün sol alt ağaç ve sağ alt ağaç içermesi gereken bir ağaçtır.
- Bir ağaç, her bir seviyede 2 i düğüme sahip olmanın şartını sağladığı zaman, bir Komple İkili ağacı olarak adlandırılır.
- Dişli ikili, 0 düğüm sayısı veya 2 düğüm sayısından oluşan ikili bir ağaçtır.
Geçiş Teknikleri
Ağaç geçişi, her bir düğümün tam olarak bir kez sistematik bir şekilde ziyaret ettiği ağaç veri yapısı üzerinde yapılan en yaygın işlemlerden biridir.
- Sıralama - Bu ağaç geçişinde sol alt ağaç tekrar tekrar ziyaret edildikten sonra kök düğüm ziyaret edilir ve son sağ alt ağaçta ziyaret edilir.
- Preorer- Bu ağaç geçişinde kök düğüm ilk önce sol alt ağaçta ve son sağ alt ağaçta ziyaret edilir.
- Postor- Bu teknik sol alt ağaçtan sonra sağ alt ağaçtan ve son kök düğümden ziyaret eder.
B Ağacı ve İkili Ağaç Arasındaki Temel Farklılıklar
- B ağacında, terminal olmayan bir düğümün sahip olabileceği en fazla alt düğüm sayısı, M'nin B ağacının sırası olduğu M'dir. Öte yandan, bir İkili ağacın en fazla iki alt ağacı veya alt düğümü olabilir.
- Veriler diskte depolanırken B-ağacı kullanılırken, veriler RAM gibi hızlı bellekte saklanırken ikili ağaç kullanılır.
- B-ağacı için bir başka uygulama alanı, DBMS'deki kod indeksleme veri yapısının aksine, İkili ağaç kod optimizasyonunda, huffman kodlamasında vs. kullanılır.
- Bir B-ağacının maksimum yüksekliği log M N'dir (M, ağacın sırasıdır). Karşıt olarak, ikili ağaç maksimum yüksekliği log 2 N'dir (N düğüm sayısıdır ve baz 2'dir çünkü ikilidir).
Sonuç
B-ağacı ikili ve ikili arama ağacı üzerinde kullanılır ve bunun ana nedeni CPU'nun düşük bant genişliği kanalından CPU'ya bağlandığı sırada CPU'nun yüksek bant genişliği kanallarıyla önbelleğe bağlandığı bellek hiyerarşisidir. Kayıtlar RAM'de saklandığında (küçük ve hızlı) bir ikili ağaç, kayıtlar diskte saklandığında (büyük ve yavaş) B-ağacı kullanılır. Bu nedenle, İkili ağaç yerine B-ağacı kullanımı, yüksek dallanma faktörü ve düşük ağaç yüksekliği nedeniyle erişim süresini önemli ölçüde azaltır.
