You Are Reading

0

Pengkajian Striktur Data B-Tree dan Contoh Penerapannya

Sang Pencari Kebenaran
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??

0 komentar:

Posting Komentar

 
Copyright 2010 Blog Pribadi Abd Umar