B-Tree

Türkçe karşılığı: b-ağacı
Okunuşu: bi tri

Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.

Güncellendi 30 Eylül 20263 dk okuma

Kısaca

B-tree, düğümleri çok sayıda sıralı anahtar ve çocuk tutan, kendini dengeleyen arama ağacıdır; sığ kaldığından aramalar çok az disk ya da sayfa okuması ister.

B-tree nedir?

B-tree, diskteki ya da SSD'deki sayfalar gibi büyük bloklar halinde saklanan veriler için tasarlanmış dengeli bir arama ağacıdır. İkili arama ağacı gibi bir anahtar ve iki çocuk tutmak yerine her düğüm çoğu zaman yüzlerce olan çok sayıda sıralı anahtar tutar ve anahtar sayısından bir fazla çocuğu vardır. Bu, ağacı çok geniş ve çok sığ yapar: düğüm başına birkaç yüz anahtarla bir B-tree milyarlarca satırı yalnızca dört ya da beş seviyede indeksleyebilir.

Aramak için kökten başlar, hedefin düğümün sıralı anahtarları arasında nereye düştüğünü bulur ve yaprağa ulaşana kadar tekrarlayarak iki komşu anahtar arasındaki çocuk işaretçisini izlersiniz. Her düğümün bir asgari ve bir azami anahtar sayısı vardır: bir ekleme bir düğümü aşırı doldurduğunda düğüm ikiye bölünür ve ortadaki anahtarını ebeveynine iter; bir silme düğümü fazla boşalttığında ise kardeşinden ödünç alır ya da onunla birleşir. Ağaç yalnızca kökte uzadığı için tüm yapraklar aynı derinlikte kalır; bu da arama, ekleme ve silme için O(log n) garantisi verir. Çoğu veritabanı, tüm değerleri yapraklarda tutan ve yaprakları sıralı olarak birbirine bağlayan B+ tree sürümünü kullanır; böylece aralık taramaları ağaçta yukarı tırmanmadan yan yana yürüyebilir.

B-tree çok ciltli bir ansiklopedi gibi çalışır: sırt etiketleri hangi cildi açacağınızı söyler, her sayfanın üstündeki kılavuz sözcükler sizi tek bir sayfaya indirger ve ancak ondan sonra maddeleri okursunuz. Bir düğümü okumak bir sayfa okumasına mal olur, depolamadan okumak ise anahtarları bellekte karşılaştırmaktan çok daha yavaştır; dolayısıyla daha az seviye daha hızlı sorgular demektir. B-tree'lerin, özellikle de B+ tree'lerin çoğu ilişkisel veritabanında varsayılan indeks yapısı olmasının ve birçok dosya sisteminin dizinleri ile dosya meta verisini düzenlemek için onları kullanmasının nedeni budur.

Adına rağmen B-tree bir ikili ağaç değildir: düğümlerinin ikiden çok daha fazla çocuğu vardır ve B harfi binary anlamına gelmez. Mucitleri Rudolf Bayer ile Edward McCreight B'nin neyi ifade ettiği konusunda hiçbir zaman karar vermemiştir ve ad hem b-tree hem B-tree olarak yazılır. B-tree'ler ayrıca yazma yoğun birçok veritabanının bunun yerine kullandığı LSM ağaçlarıyla (log-structured merge tree) karşılaştırılır: B-tree'ler veriyi yerinde günceller ve okumada üstündür; LSM ağaçları ise yazmaları bellekte biriktirip daha sonra diske birleştirir ve daha hızlı yazma için daha yavaş okumayı göze alır.

Önemli noktalar

B-tree düğümü çok sayıda sıralı anahtar ve çocuk işaretçisi tutar; bu yüzden ağaç geniş ve sığdır.
Tüm yapraklar aynı derinlikte olduğundan arama, ekleme ve silme O(log n) sürer.
Düğümler taştığında bölünür, fazla boşaldığında birleşir ve böylece ağaç dengeli kalır.
Daha az seviye daha az sayfa okuması demektir; veritabanları ve dosya sistemleri B-tree'leri bu yüzden kullanır.
Çoğu veritabanı indeksi, yapraklarını hızlı aralık taramaları için bağlayan B+ tree sürümünü kullanır.

Örnek

SQL'de B-tree indekslerisql

-- A standard index in most relational databases is a B-tree (usually a B+ tree)
CREATE INDEX idx_orders_created_at ON orders (created_at);

-- An equality lookup walks from the root to one leaf: a handful of page reads
SELECT * FROM orders WHERE id = 42;

-- A range query finds the first matching leaf, then scans the linked leaves in order
SELECT * FROM orders
WHERE created_at BETWEEN '2026-09-01' AND '2026-09-30'
ORDER BY created_at;

-- In PostgreSQL, btree is the default index type, but it can be named explicitly
CREATE INDEX idx_users_email ON users USING btree (email);

Sık sorulan sorular

B-tree ile ikili arama ağacı arasındaki fark nedir?

İkili arama ağacı düğümü bir anahtar tutar ve en fazla iki çocuğu vardır; bu yüzden büyük bir ağaç çok sayıda seviye derinliğindedir. B-tree düğümü ise çok sayıda anahtar tutar ve çok sayıda çocuğu vardır; bu da ağacı yalnızca birkaç seviye derinlikte tutar ve depolamadan yapılan yavaş okumaları en aza indirir.

B-tree ile B+ tree arasındaki fark nedir?

B-tree'de anahtarlar ve değerleri herhangi bir düğümde bulunabilir. B+ tree'de iç düğümler yalnızca aramaya yön verir ve tüm değerler, sıralı olarak bağlı yapraklarda yaşar; bu da aralık taramalarını hızlandırır. Çoğu veritabanı indeksi B+ tree'dir.

B-tree'deki B neyi ifade eder?

Kimse tam olarak bilmiyor. Yapıyı 1970 civarında icat eden Rudolf Bayer ve Edward McCreight bunu hiçbir zaman tanımlamadı; yaygın tahminler arasında balanced (dengeli), broad (geniş), Bayer ve o sırada çalıştıkları yer olan Boeing bulunuyor.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin