B-ağaçları ve veritabanı indeksleri

 (planetscale.com)
41 puan yazan GN⁺ 2024-09-11 | 1 yorum | WhatsApp'ta paylaş

B-tree nedir?

  • B-tree, birçok yazılımda, özellikle de veritabanı yönetim sistemlerinde (DBMS) temel bir rol oynar

  • MySQL, Postgres, MongoDB, Dynamo gibi sistemler, indeksler aracılığıyla veriyi verimli biçimde sorgulamak için B-tree'lere dayanır

  • B-tree ve B+tree'nin nasıl çalıştığını, veritabanlarının bunları indekslerde neden kullandığını ve UUID'yi birincil anahtar olarak kullanmanın neden kötü bir fikir olabileceğini öğreneceğiz

  • B-tree, anahtar ve değer olarak bilinen veri çiftlerini, bilgisayar programcılarının ağaca benzer bir yapı dediği yapıda saklar

  • B-tree, düğümlerden (dikdörtgenler) ve çocuk işaretçilerinden (düğümleri bağlayan çizgiler) oluşur

  • En üst düğüme kök düğüm, en alt seviyedeki düğümlere yaprak düğüm, diğer tüm düğümlere ise iç düğüm denir

  • Aşağıda B-tree'nin tanımı yer alır:

    • Her düğüm N adet anahtar/değer çifti saklar (burada N, 1'den büyük ve K'ye eşit ya da küçüktür)
    • Her iç düğüm en az N/2 anahtar/değer çiftine sahiptir (iç düğüm, yaprak ya da kök olmayan düğümdür)
    • Her düğümde N+1 adet çocuk bulunur
    • Kök düğüm, tek düğüm olmadığı sürece en az bir değer ve iki çocuk içerir
    • Tüm yapraklar aynı seviyededir

  • B-tree'nin bir diğer temel özelliği sıralı olmasıdır. Her düğüm içindeki öğeler sırayla tutulur

  • Bu sıralama özelliği sayesinde anahtar arama çok verimli yapılabilir. Arama kök düğümden başlar ve:

    1. Aranan anahtarın düğümde bulunup bulunmadığı kontrol edilir
    2. Yoksa, eklenmek istenmesi durumunda anahtarın düğüm içinde nereye yerleşeceği bulunur
    3. Bu noktada çocuk işaretçisi izlenerek bir sonraki seviyeye geçilir ve süreç tekrarlanır

  • Bu şekilde arama yaparken, tek bir anahtarı bulmak için ağacın her seviyesinde yalnızca bir düğümü ziyaret etmek yeterlidir

  • B-tree, çok büyük miktarda veriye sahipken aynı zamanda uzun süreli depolamada (diskte) kalıcılığın gerektiği durumlar için özel olarak tasarlanmıştır. Bunun nedeni her düğümün sabit sayıda bayt kullanmasıdır

  • B-tree'de her düğümün saklayabileceği değer sayısı, ona ayrılan bayt miktarına ve her anahtar/değer çiftinin tükettiği bayt sayısına bağlıdır

B+tree (veritabanları için optimize edilmiş)

  • B+tree, B-tree'ye benzer; ancak şu kurallar değişir:
    • Anahtar/değer çiftleri yalnızca yaprak düğümlerde saklanır
    • Yaprak olmayan düğümler yalnızca anahtarları ve bunlarla ilişkili çocuk işaretçilerini saklar
  • MySQL'in B+tree'yi indekslerde uygulama biçimine özgü iki ek kural vardır:
    • Yaprak olmayan düğümler N+1 yerine N çocuk işaretçisi saklar
    • Tüm düğümler ayrıca bir "sonraki" ve "önceki" işaretçisi içerir; böylece ağacın her seviyesi aynı zamanda çift bağlı liste gibi davranabilir
  • B+tree'nin veritabanları için daha uygun olmasının iki nedeni vardır:
    1. İç düğümlerin değer saklaması gerekmediği için, her iç düğüme daha fazla anahtar sığdırılabilir. Bu da ağacın derinliğini azaltmaya yardımcı olur
    2. Tüm değerler aynı seviyede saklanır ve en alt seviyedeki bağlı liste üzerinden sıralı biçimde dolaşılabilir

MySQL'de B+tree kullanımı

  • MySQL birden fazla depolama motorunu destekler ve en yaygın kullanılan motor, B+tree'lere büyük ölçüde dayanan InnoDB'dir
  • Hatta InnoDB, tabloların birincil anahtarını ağacın anahtarı olarak kullanarak tüm tablo verisini B+tree içinde saklayacak kadar buna bağımlıdır
  • Yeni bir InnoDB tablosu oluşturduğunuzda bir birincil anahtar belirtmeniz gerekir
  • MySQL, her yeni tablo için bir B+tree oluşturur; birincil anahtar olarak belirlenen değer ağacın anahtarı olur. Değer kısmı ise her satırın geri kalan sütun değerleridir ve yalnızca yaprak düğümlerde saklanır
  • Bu B+tree içindeki her düğümün boyutu varsayılan olarak 16k olarak ayarlanır
  • MySQL bir veri parçasına (anahtar, değer vb.) erişmesi gerektiğinde, başka anahtar ya da değerlere ihtiyaç olmasa bile ilişkili tam sayfayı (B+tree düğümünü) diskten yükler
  • InnoDB tablolarında ikincil indeks oluşturmak da yaygındır. Her ikincil indeks için ek bir kalıcı B+tree kurulur; anahtar, kullanıcının indekslemek istediği sütundur ve değer, ilişkili satırın birincil anahtarıdır

Birincil anahtar seçimi: ekleme

  • Tablo verisinin B+tree içinde nasıl dizileceği seçtiğiniz anahtara bağlı olduğundan, PRIMARY KEY seçimi tablodaki tüm verinin disk düzenini etkiler
  • Birincil anahtar olarak yaygın biçimde seçilen iki seçenek şunlardır:
    • tamsayı dizisi (BIGINT UNSIGNED AUTO_INCREMENT gibi)
    • UUID (birden fazla sürümü vardır)
  • UUIDv4 birincil anahtarı kullanmanın sonuçlarını düşünürsek, ekleme sırasında:
    1. Ekleme için ziyaret edilecek düğüm önceden tahmin edilemez
    2. Eklemenin yapılacağı hedef yaprak düğüm tahmin edilemez
    3. Yapraktaki değerler sıralı değildir
  • Çok sayıda ekleme sırasında ağacın birçok düğümünü (sayfasını) ziyaret etmek gerektiğinden 1 ve 2 numaralı sorunlar ortaya çıkar. Bu aşırı okuma ve yazma işlemleri performans düşüşüne yol açar
  • BIGINT UNSIGNED AUTO_INCREMENT birincil anahtar olarak kullanıldığında:
    1. Yeni değer eklenirken her zaman en sağdaki yol izlenir
    2. Yapraklar yalnızca ağacın sağ tarafına eklenir
    3. Yaprak seviyesindeki veriler eklenme sırasına göre sıralanır
  • 1 ve 2 numaralı maddeler nedeniyle, sıralı biçimde gerçekleşen çok sayıdaki ekleme aynı sayfa yolunu tekrar ziyaret eder; böylece çok sayıda anahtar/değer çifti eklenirken I/O istekleri azalır

Birincil anahtar seçimi: veriyi sıralı okuma

  • Veritabanında veriyi zaman sırasına göre sorgulamak yaygındır
  • UUIDv4 birincil anahtar kullanıldığında, sorgu sonucundaki değer dizisi birden fazla ardışık olmayan yaprak düğüme dağılır
  • Sıralı şekilde eklenmiş değerler aranıyorsa, sonucu içeren tüm sayfalar birbirine bitişik olur. Birden fazla satır sorgulandığında bunların hepsi tek bir sayfa içinde bile yan yana olabilir
  • Bu tür sorgu kalıplarında sıralı bir birincil anahtar kullanmak, okunması gereken sayfa sayısını azaltabilir

Birincil anahtar seçimi: boyut

  • Birincil anahtarın boyutu da önemli bir değerlendirme unsurudur. Birincil anahtar her zaman:
    1. Tükenmeyecek kadar büyük olmalı
    2. Aşırı depolama alanı kullanmayacak kadar küçük olmalı
  • Tamsayı dizileri için, daha küçük tablolarda MEDIUMINT (16 milyon benzersiz değer) veya INT (4 milyar benzersiz değer) kullanılabilir
  • Büyük tablolar için güvenli tarafta kalmak adına BIGINT kullanılır (1.8e19 olası değer). BIGINT 64 bittir (8 bayt)
  • UUID genellikle 128 bittir (16 bayt); yani MySQL'deki en büyük tamsayı türünün iki katıdır
  • B+tree düğümleri sabit boyutlu olduğundan, BIGINT kullanıldığında düğüm başına UUID'ye kıyasla daha fazla anahtar sığdırılabilir. Bu da daha sığ ağaçlar ve daha hızlı sorgular anlamına gelir

B+tree, sayfalar ve InnoDB

  • B+tree'nin büyük avantajlarından biri, düğüm boyutunu istediğiniz gibi ayarlayabilmenizdir
  • InnoDB'de B+tree düğümleri genellikle InnoDB sayfası boyutu olan 16k olarak ayarlanır
  • Sorgu işleme sırasında (dolayısıyla B+tree üzerinde gezinirken) InnoDB diskten tek tek satır ve sütun okumaz. Bir veri parçasına erişmesi gerektiğinde ilgili tam sayfayı diskten yükler
  • InnoDB bunu hafifletmek için bazı teknikler kullanır; başlıcası buffer pool'dur. Buffer pool, diskteki sayfalar ile MySQL sorgu yürütmesi arasında yer alan, InnoDB sayfaları için bellek içi bir önbellektir
  • MySQL bir sayfayı okumak zorunda kaldığında önce bunun zaten buffer pool'da olup olmadığını kontrol eder. Varsa oradan okur ve disk I/O işlemini atlar. Yoksa sayfayı diskten bulur, buffer pool'a ekler ve ardından sorgu yürütmeye devam eder
  • Buffer pool, sorgu performansını muazzam ölçüde artırır. Buffer pool olmasaydı, sorgu iş yükünü karşılamak için çok daha fazla disk I/O işlemi yapılması gerekirdi

Diğer durumlar

  • Burada ağırlıklı olarak sıralı anahtarlarla rastgele/UUID anahtarlarını karşılaştırmaya odaklandık; ancak bu ilkeler, değerlendirdiğiniz birincil ya da ikincil anahtar türü ne olursa olsun akılda tutulması yararlı noktalardır
  • Örneğin user.created_at zaman damgasını indeks anahtarı olarak kullanmayı düşünebilirsiniz; bu, sıralı tamsayıya benzer özellikler taşır. Eski verileri eklemediğiniz sürece eklemeler genellikle her zaman en sağdaki yola gider
  • Buna karşılık user.email_address gibi bir string, rastgele anahtarlara daha çok benzer. Kullanıcılar hesaplarını e-posta adreslerinin alfabetik sırasına göre oluşturmadığı için eklemeler B+tree'nin geneline yayılır

Sonuç

  • B+tree, indeksler ve birincil anahtar seçimi hakkında oldukça fazla konu ele alındı
  • Yüzeyden bakıldığında basit görünse de, veritabanı performansını en üst düzeye çıkarmak için dikkate alınması gereken ince farklar vardır
  • Daha fazla deneme yapmak için etkileşimli B+tree web sitesini ziyaret edebilirsiniz

İlgili okumalar

1 yorum

 
GN⁺ 2024-09-11
Hacker News görüşleri

  • Wiki’yi B-Tree gibi yönetme stratejisini kullanarak faydalı kalmasını sağlıyorum

    • Landing page sayısı çok artarsa bağlantıları ve paragrafları alt sayfalara taşıyorum
    • Benzer ve eski bağlantıları konuya uygun kardeş sayfalara taşıyorum
    • Sonunda eski belgeler landing page’den üç seviye aşağı taşınmış oluyor
    • Dokümantasyon işi sonuçta bir arama problemine dönüşüyor
    • Cuma öğleden sonrasını verimli geçirmek için güzel bir yöntem

  • Uzun zamandır böyle bir şey arıyordum, harika bir gönderi

    • Keşke bileşik indekslerle ilgili bir bölüm de olsaydı

  • Harika görseller için teşekkürler

    • Aerospike üzerinde BTree+ indeksleme desteği üzerinde çalıştım
    • Süresi dolmuş anahtarları BTree+’dan kaldırmak zorlayıcıydı
    • Yalnızca ilk kardeş yaprak düğüm içinde tek seviyelik dallanmayı birleştirmeye karar verdik
    • Hızı artırmak ve kilit çekişmesini azaltmak için BTree+ üzerine sharding ekledik
    • Temizlik sürecinde BTree+ dengesiz hale gelebilir
    • Ek temizlik işlerinden kaçınmak için indeks yeniden oluşturma özelliği sunduk

  • Firefox mobilde cookie modal çalışmıyor

    • Kullanıcının bunu tarayıcıdan ayarlayabilmesi gerekir

  • UUID sütunlarını birincil anahtar olarak kullanmamalısınız

    • 128 bitlik int’i tüm ilişki taraflarına kopyalamak zorunda kalırsınız
    • Çoğu durumda tamamen rastgele olur
    • Dahili tablo ilişkileri için bigserial (64 bit) PK, uygulama düzeyi tanımlayıcılar ve doğal anahtarlar içinse UUID (128 bit) kullanılmalı
    • Veritabanınız çok daha mutlu olur

  • Harika bir eğitim materyali

    • Bu tür interaktif demolar gerçekten çok yardımcı oluyor

  • Disk bloğu ve B-Tree düğümleri 16k ise ve anahtar, değer, çocuk işaretçilerinin hepsi 8 bitse, düğüm başına 682 anahtar/değer ve 683 çocuk işaretçisi saklanabilir

    • Üç seviyeli bir ağaç 300 milyondan fazla anahtar/değer çifti saklayabilir
    • Her öğe başına 8 bayt olmalı

  • Harika bir makale

    • InnoDB’nin veriyi B-tree’nin içinde saklamasına clustered index deniyor
    • MyISAM non-clustered index idi
    • Oracle ve benzerleri bunu seçme imkanı veriyor

  • Grafikte v0, v1, ...v10’un ne anlama geldiğini soruyor

    • Bunların farklı sayfaları mı ifade ettiğini merak ediyor

  • Çok güzel bir interaktif görselleştirme

    • Eğitim ve yaygınlaştırma açısından birinci sınıf