B*-Tree (BTree, BPlusTree) Veri Yapısı ile Veri İndeksleme

Veri indeksleme

Veri asıl kaynağına yazılırken bir format takip edilir. Bu formata göre, bazı sorgulamaların yapılması çok zaman almaktadır. Bazen tüm verinin taranması gerekebilir. Veriye erişimi hızlandırmak için, asıl veriye ek olarak, farklı biçimlerde tekrar bilgi yazılması gerekmektedir. Farklı biçimlerde verinin tekrar yazılması işlemi "indeksleme" olarak adlandırılmaktadır. İndeksleme yaklaşımında, indekslenecek anahtar veri ve asıl veriye referans bulunmaktadır. (<Key,Pointer>) Asıl veri değiştiğinde, indeks verilerinin de güncellenmesi gerekir.

Bu yazımızda; önemli indeksleme tekniklerinden olan BTree ve BPlusTree veri yapılarının özellikleri hakkında bilgi verilecektir. BPlusTree, ilişkisel veritabanlarında en çok kullanılan ağaç veri yapısıdır.

BTree Veri yapısı

BTree, ağaç şeklinde dinamik bir veri yapısıdır. Nodlar ve nod içindeki sıralı elemanlardan oluşur. Kök noddan başlayarak; her bir elemanın küçük değerleri, sola doğru, büyük değerleri ise, sağa doğru, alt nod üzerinde yer almaktadır. Her bir eleman ile birlikte alt noda ait referansı da saklanmaktadır. Anahtar bilgilerde mükerrerliğe izin verilmemiştir.
Bir örnek vermemiz gerekirse; Elimizde, 1..10 şeklinde anahtar bilgileri (Key) olan bir veri kümemiz var. Bir nod içinde 3 eleman olacak şekilde, BTree veri yapısına yüklendiğinde, aşağıdaki gibi bir görüntü elde edilecektir:

Kök nod üzerinde bir veri elemanı bulunmaktadır. 4 değerinden küçük değerler için sola doğru alt nod izlenir. Büyük değerler için, sağa doğru alt nod izlenir.

Önemli parametreler
Yükseklik: Veri yapısındaki aşağıya doğru olan nod sayısı.
Nod içindeki eleman sayısı: Nod içinde sıralı olarak yerleştirilen anahtar bilgilerin sayısı
Kayıt Kapasitesi: Saklanabilecek maksimum anahtar sayısı.

Örnek
Yükseklik 3, Nod içindeki kayıt 100 ise,
Toplam kayıt sayısı = 1003 = 1,000,000
Her bir ekleme/silme işleminden sonra, ağaç şekli dengeli (balans) bir şekilde tutulmaktadır. Uç yaprak (leaf) nodların, kök noddan uzaklığı hep aynı kalmaktadır. Bu durum, sorgulama etkinliği açısından önemlidir.

BPlusTree Veri yapısı

Bilginin saklanma şeklinde değişiklikler vardır.
Yukarıdaki aynı veri kümesini, BPlusTree veri yapısına yüklediğimizde, aşağıdaki gibi bir görüntü elde edilecektir:

BPlusTree’nin,  BTree veri yapısına göre farkları aşağıda listelenmiştir:
1) Uçtaki yaprak (Leaf) seviyesinde bilgiler tutulur. Üst nodlarda veri yoktur. Sadece sınıflandırma amaçlıdır. Hızlı erişim için kullanılır.
2) Yaprak seviyesindeki ağaç nodları iki yönlü olarak birbirine bağlanmıştır ve sıralıdır. Bu şekilde, aralık şeklindeki sorgular daha hızlı gerçekleştirilir.

Arama İşlemi

Kök nod üzerinden, arama başlatılır. “Eşittir” araması yapılıyorsa, nod içinde kendisinden büyük değer aranır. Kendisinden büyük değer bulunursa, alt nod referansı alınır. Kendisinden büyük değer bulunamazsa, en son elamanın alt nod referansı alınır. Aramaya tekrarlamalı (recursive) devam edilir. Uç yaprak (Leaf) noda erişilir. Nod içinde, değer aranır. Arama tamamlanır.
Index dosyasında, K adedinde anahtar varsa ve nod içinde bulunacak anahtar sayısı N ise, gezilecek maksimum yol,  logN/2(K) dir.

Ekleme işlemi

Eklenecek olan anahtar değeri üzerinden arama yapılır. Uç yaprak (Leaf) nodu bulunur. Eğer, nod içinde yer varsa, sıralı olarak eklenir. Nod içindeki eleman sayısına erişildiğinde, ilgili nod parçalanır. Ortadaki değer, yukarı noda gönderilir. (Recursive) Küçük değerler, yeni oluşturulan başka bir noda taşınır. Bu şekildeki işlemlerle, veri yapısındaki denge (balans) her zaman korunur.

Değerlendirme

BPlusTree, veritabanı sistemleri tarafından tercih edilmektedir ve en önemli bileşenlerinden birisidir.
BTree ve BPlusTree veri yapıları, sorgulamaları daha hızlı yapabilmek için geliştirilmiştir. Ekleme/Güncelleme performansına göre, sorgulama yaklaşımı daha verimlidir. BTree, anahtar aramalarda daha iyi performans sağlarken, aralık aramalarında BPlusTree daha performanslıdır. BPlusTree veri olmayan nodlar (NonLeaf) sebebiyle, daha çok yer kaplamaktadır. NOSQL, GRAPH veritabanlarında çok fazla yapısal, yarı yapısal ya da yapısal olmayan veriyi hızlı ekleme ve sorgulamak için kullanılan yöntemlerden biridir (http://nosql-database.org/). CRYPTTECH olarak, BPlusTree yaklaşımını tercih ettik ve üzerinde çalışmalar gerçekleştirmekteyiz. Nod içindeki eleman sayısı, bir performans denge noktasıdır. Bu değer küçük olduğunda, ağaç yapısındaki yükseklik artmaktadır. Bu durumda, aranan anahtar bilgiye erişim için gezilmesi gereken nod sayısı artmaktadır. Nod sayısı büyüdükçe, diskten transfer edilmesi gereken bilgi büyüklüğü artmaktadır. Ek olarak, nod içinde sıralı arama da, daha çok zaman almaktadır. Yaptığımız performans testlerinde, nod içindeki eleman sayısı için en uygun değeri 15 olarak tespit ettik.

Tarık KOBALAS 
Teknoloji Direktörü

Referanslar
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
Advanced Database Systems -Demetris Zeinalipour (University of Cyprus)
Prof. Eamonn Keogh (CS166 – B+Tree Presentation, From a Text Book)