Translate

Minggu, 09 Maret 2014

Implementasi B-Tree

Struktur pohon mendukung berbagai operasi dasar set dinamis termasuk Search, Predecessor, Successor, Minimum , Maksimum , Insert , dan Delete dalam waktu sebanding dengan ketinggian pohon . Idealnya , pohon akan seimbang dan tinggi akan log n dimana n adalah jumlah node dalam pohon . Untuk memastikan bahwa ketinggian pohon sekecil mungkin dan karena itu memberikan running time terbaik , struktur pohon seimbang seperti Red-Black Tree , AVL Tree , atau B- Tree harus digunakan .

Ketika bekerja dengan set data yang besar , seringkali tidak mungkin atau diinginkan untuk mempertahankan seluruh struktur dalam penyimpanan utama ( RAM ) . Sebaliknya , porsi yang relatif kecil dari struktur data dipertahankan dalam penyimpanan utama , dan data tambahan dibaca dari penyimpanan sekunder yang diperlukan . Sayangnya , disk magnetik , bentuk paling umum dari penyimpanan sekunder , secara signifikan lebih lambat dibandingkan random access memory ( RAM ) . Bahkan , sistem sering menghabiskan lebih banyak waktu mengambil data daripada benar-benar mengolah data.

B - Tree adalah pohon seimbang yang dioptimalkan untuk situasi saat sebagian atau seluruh pohon harus dipertahankan dalam penyimpanan sekunder seperti disk magnetik . Karena akses disk yang mahal ( memakan waktu ) operasi , b-tree mencoba untuk meminimalkan jumlah akses disk . Sebagai contoh, b - tree dengan ketinggian 2 dan faktor percabangan 1001 dapat menyimpan lebih dari satu miliar kunci tetapi membutuhkan paling banyak dua akses disk untuk mencari setiap node.

Contoh:












Dalam mengaplikasikan suatu struktur data ke dalam sebuah basis data, ada beberapa hal yang harus diperhatikan. Hal-hal tersebut antara adalah :

  •  Lama pencarian sebuah elemen. Untuk data yang sangat besar, pencarian bisa memakan waktu yang lama. Waktu pencarian bisa menjadi lebih lama lagi apabila data tidak disimpan secara terurut, dan berada dalam media penyimpanan dengan kecepatan tulis lambat.
  • Pengindeksan data. Dengan memberi indeks pada blok-blok tertentu data, kita dapat memangkas waktu pencarian dengan hanya mencari di blok tertentu, dan bukannya di seluruh data.
  • Penghapusan dan Penambahan data. Kedua operasi tersebut membuat manajemen data dan indeksnya menjadi lebih rumit. Penambahan data bisa berbahaya karena harus mengalokasikan tempat untuk data yang baru, yang berarti harus menggeser data-data yang sudah ada sebelumnya. Salah satu cara mengatasinya adalah dengan sengaja membiarkan sebagian memori tetap kosong, dan dipakai hanya jika ingin menambahkan elemen baru. 

B-tree menangani semua masalah di atas dengan cara-cara berikut :

  • Menjaga data tetap terurut untuk akses sekuensial.
  • Menggunakan indeks hierarki untuk meminimalisir akses ke media penyimpanan
  • Menggunakan blok penuh-parsial untuk mempercepat penambahan dan penghapusan data.
  • Indeks disesuaikan secara elegan menggunakan algoritma rekursif.
  • Meminimalisir proses yang terbuang dengan memastikan semua simpul setidaknya setengah penuh.

Karena dapat mengatasi masalah-masalah tersebut itulah maka B-tree kerap dipakai dalam sistem manajemen basis data. Kelebihan lain dari B-tree adalah kemampuan untuk menangani operasi penambahan dan penghapusan data dalam jumlah yang tak terhingga, selama masih ada tempat di media penyimpanan. Variasi B-tree yang paling banyak digunakan dalam basis data adlah B+ tree.


Selain dalam basis data, B-tree juga digunakan pada berkas sistem. B-tree digunakan karena memungkinkan akses acak ke blok mana pun pada sebuah berkas tertentu. Selain itu, B-tree juga mengatasi masalah mengubah alama blok berkas menjadi alamat blok fisik.B-tree digunakan dalam berkas sistem HFS dari Apple, NTFS dari Microsoft, dan beberapa berkas sistem Linux. Variasi dari B-tree yang juga banyak dipakai dalam berkas sistem adalah B*-tree. Selain itu, beberapa sistem operasi seperti TOPS-20 dan TENEX menggunakan struktur data serupa B-tree di dalamnya.

sumber:

Diposting oleh di Tidak ada komentar:
Label:
Langganan: Postingan (Atom)