Dalam ilmu komputer, B-tree adalah struktur data pohon yang paling umum digunakan dalam basis data danfile system. B-tree menjaga data tetap terurut dan seimbang. Ide di balik B-tree ini yaitu simpul internal dapat memiliki sejumlah simpul anak dalam cakupan (range) yang telah terdefinisi.
Ketika data disisipkan atau dipidah dari struktur data, sejumlah simpul anak dapat bertukar sepanjang simpul. Untuk tetap mempertahankan cakupan yang telah didefinisikan, simpul internal digabungkan atau dipisahkan. Karena adanya cakupan (range) pada simpul anak, maka B-tree tidak perlu diseimbangkan secara berkala seperti struktur data pohon seimbang yang lain, misalnya self-balancing binary search trees. Akan tetapi, B-tree dapat menghabiskan tempat karena simpul tidak selalu penuh. Batas atas dan batas bawah jumlah simpul anak biasanya tetap untuk implementasi tertentu. Sebagai contoh, dalam 2-3 B-tree (disebut juga 2-3 tree), setiap simpul internal hanya dapat memiliki 2 atau 3 simpul anak.
Sebuah B-tree dijaga keseimbangannya dengan membuat semua simpul daun berada pada ketinggian yang sama. Ketinggian ini akan meningkat perlahan saat elemen-elemen ditambahkan pada pohon, tetapi peningkatan ketinggian secara keseluruhan jarang terjadi. Hal disebabkan karena sebuah B-tree didesain dapat memiliki cabang dalam jumlah besar dan mengandung sejumlah kunci pada tiap simpulnya sehingga ketinggian pohon relative kecil. Hal ini berarti hanya sedikit simpul yang harus dibaca dari disk untuk mengambil data.Tujuannya yaitu untuk mendapatkan akses pada data yang cepat.
B-Tree memiliki kelebihan dibanding implementasi alternatif yang lain karena waktu akses dalam simpulnya jauh di atas waktu akses antarsimpul. Hal ini biasanya muncul ketika kebanyakan simpul berada di penyimpanan sekunder seperti hard drives. Dengan memaksimalkan jumlah simpul anak pada setiap simpul internal, ketinggian pohon berkurang, penyeimbangan muncul tidak terlalu sering, dan efisiensi meningkat. Biasanya nilai ini diset agar setiap simpul mengisi sebuah blok penuh atau pada ukuran yang analog di tempat penyimpanan sekunder.
Tertarik untuk membaca lebih lanjut??
Silahkan Download Lengkap Pengkajian Striktur Data B-Tree dan Contoh Penerapannya
0 komentar:
Posting Komentar