- Yakın zamanda Alex Petrov'un Database Internals kitabını okurken, DBMS depolama motorlarının nasıl uygulandığına, özellikle de B-Tree veri yapısı optimizasyonlarına dair içeriklerle karşılaştım
- Üniversitede B-Tree'yi öğrenirken bunu sadece “daha iyi bir BST” gibi anlamıştım; bu yüzden gerçekte neden kullanıldığını pek hissedememiştim
- Disk I/O'su hesaba katıldığında, büyük ölçekli veriyi depolamak ve hızlı aramak için B-Tree yapısı uygundur
- Bu yazı, B-Tree'nin neden gerekli olduğunu, nasıl çalıştığını ve gerçek uygulamalarda hangi optimizasyonların mümkün olduğunu tanıtıyor
- Tek bir düğümde çok sayıda anahtar toplayarak disk erişim sayısını azaltmak gibi yaklaşımlar başlıca özelliklerindendir
Diskin getirdiği kısıtlar
- Tüm verinin belleğe sığmadığı bir durum varsayılır
- Diskin bir seferde sayfa birimiyle okuma ve yazma yaptığı kabul edilir
- Disk erişimi, bellek erişimine kıyasla çok yavaştır
- Bu nedenle veri yapısının, veriyi sayfa merkezli yerleştirmesi ve en az disk erişimiyle mümkün olduğunca çok anahtar karşılaştırması yapması gerekir
- BST doğrudan diskte tutulursa düğümler dağınık kalır; bu da arama sayısı kadar disk erişiminin artmasına yol açar
- B-Tree, bir düğümde birden fazla anahtar tutarak tek disk okumasında birçok anahtarın karşılaştırılabilmesini sağlar
Slot page
- Veriyi diske yerleştirirken yönetim birimi olarak “page” kullanılır
- Her page içinde bir header, değişken uzunluklu veriyi tutan hücreler ve hücre konum bilgisini saklayan bir offset pointer dizisi bulunur
- Slot page yapısı, anahtar boyutları değişken olsa bile yeniden düzenleme yükü olmadan sıralı düzeni koruyabilme avantajı sağlar
- Anahtar silme veya ekleme sırasında gerçek veriyi taşımak yerine yalnızca pointer'ları yeniden sıralamak çok daha verimlidir
- Örneğin SQLite, bu tür bir page yapısı içinde bir free list tutarak silinen hücre alanlarını yeniden kullanır
B-Tree araması
- B-Tree arama algoritması basittir:
- Kök düğümden başlanır
- Mevcut düğümdeki ayırıcı anahtarlara (Separator Key) bakılarak aranan anahtarın bulunma olasılığı en yüksek çocuk düğüm seçilir
- Ağaç özyinelemeli olarak dolaşılır
- Aranan anahtarı içeren yaprak düğüm bulunursa işlem tamamlanır; bulunamazsa anahtarın mevcut olmadığı kabul edilir
- İç düğümlerde gerçek veri yerine yalnızca ayırıcı anahtarlar bulunabilir ve çoğu durumda gerçek veri sadece yaprak düğümlerde tutulur
- Düğüm içindeki anahtarları ikili aramayla verimli biçimde bulabilmek için her düğümde anahtarlar sıralı tutulur
Ayırıcı anahtarın (Separator Key) kısaltılması
- İç düğümlerdeki ayırıcı anahtarların, gerçek anahtarın tamamını değil, yalnızca aralığı ayırt etmeye yetecek kadarını tutması yeterlidir
- Örneğin 0xAAAAAA ile 0xBBBBBB arasını ayırmak için 0xBBBBBB'nin tamamını saklamak gerekmez; daha kısa bir ön ekle de ayrım yapılabilir
- Anahtar uzunluklarının büyük olduğu veritabanlarında bu tür kısaltmalar ciddi depolama tasarrufu sağlar
- Ayırıcı anahtar kısaltmanın yanı sıra, prefix ve suffix bölümlerini verimli biçimde küçültmeye yönelik stratejiler de vardır
- Yaprak düğümler çok daha fazla olduğu için, prefix sıkıştırmasının performansa daha büyük katkı sağladığını savunan görüşler de vardır
Overflow page
- Bir düğüm çok fazla anahtar içerdiğinde ve bunlar tek bir page'e sığmadığında overflow page kullanılır
- Anahtarın tamamını overflow page'e aynen taşımak yerine, düğümde yalnızca kısa bir prefix bırakılır ve geri kalanı ayrı tutulur
- Böylece anahtarın varlığını ya da aralık sorgusunu kontrol ederken önce düğümdeki prefix incelenir, yalnızca gerçekten gerektiğinde overflow page okunur
- Bu yaklaşım ek page tahsisi gerektirse de toplam arama maliyetini düşürür
Kardeş pointer'ları
- Bazı uygulamalarda düğümler, sol ve sağ kardeş düğümlerin pointer'larını da saklar
- Bu sayede aralık sorgularında bir yaprak düğümden doğrudan kardeş düğüme geçilerek ardışık anahtarlar hızlıca taranabilir
- Kardeş pointer'ları yoksa yeniden ebeveyn düğüme çıkıp aşağı inme süreci tekrarlandığından I/O maliyeti artar
- Kardeş düğümlerin kapsadığı anahtar aralıkları birbiriyle çakışmadığı için, sağ kardeş pointer'ına geçildiğinde bunun “bir sonraki anahtar aralığı” olduğu garanti edilir
B-Tree varyantları
- B⁺-Tree dışında da çeşitli türev veri yapıları vardır
- WiredTiger gibi “Lazy B-Tree” ya da Lazy-Adaptive Tree, yazma işlemlerini buffer'layarak performansı artıran yaklaşımlar kullanır
- FD-Tree, SSD özelliklerine uygun tasarlanmış bir yapıdır ve blok düzeyinde yazma gibi fiziksel kısıtları dikkate alır
- Bw-Tree (Buzzword Tree), yüksek eşzamanlılık ve bellekteki ağaç erişimi için optimize edilmiş bir veri yapısıdır
Sonuç
- Soyut “B⁺-Tree” kavramı ile bunun gerçek hayattaki uygulaması olan “SQLite'ın DB formatı” arasında çok sayıda optimizasyon ve uygulama detayı farkı bulunur
- Bu optimizasyonlar Big-O karmaşıklığını değiştirmese de gerçek ortamlarda veritabanı performansı ve kullanılabilirliği üzerinde büyük etki yaratır
- Burada anlatılanların ötesinde, her depolama sistemi için çok sayıda ince ayar gerekebilir
- “Sadece biraz ek bilgi gerekir” ifadesinin arkasında uygulama karmaşıklığı ve hata ayıklama zorluğu yatar
- B-Tree yapısını daha gerçekçi çizen örneklerden biri olarak, Designing Data Intensive Applications içindeki B-Tree diyagramı özellikle etkileyicidir
1 yorum
Hacker News görüşü
Sayfanın yapısı başlık, hücreler ve ofset işaretçilerinden oluşuyor; bu da değişken boyutlu verileri depolayabilme avantajı sağlıyor
B-tree hakkında animasyonlar da içeren harika bir makale
Birkaç yıl önce Ibrahim Jaluta'nın araştırmasına dayanarak eşzamanlı olarak kurtarılabilir bir B-link Tree uygulamıştım
B-tree'yi daha iyi anlamak için bir SQLite disk sayfası gezgini yaptım
B-link Tree, eşzamanlılık ve kilitleme hakkında içerik eksik, ama bu gereğinden fazla bilgi olabilir
Geçmiş yorum: Hacker News
Ayrıntıların önemini çok iyi anlatan harika bir makale
Golang kullanarak B-tree uygulaması hakkında iyi bir kaynak
Bu makalenin büyük bir hayranıyım; yazarınkine benzer şekilde ben de 'bulanık bir anlayışa' sahiptim