B+Tree

Masih dalam kelompok struktur data hirarkis, kuliah hari ini membahas B+Tree. Struktur data ini semula adalah varian dari struktur data (a,b)-Tree, namun dalam perkembangannya struktur ini digunakan secara spesifik sebagai struktur data eksternal (i.e., indexed file) dan kemudian dalam DBMS relasional untuk mengorganisasikan index key dari tabel basis data.

Sebagai struktur data eksternal B+Tree biasanya berupa n-ary tree dengan n bilangan yang cukup besar. Dengan demikian untuk n=100, data dalam jumlah jutaan dapat diorganisasikan dalam B+Tree yang memiliki tinggi = 3. Dengan bentuknya yang landai demikian memungkinkan data diakses secara cepat dengan hanya melalui pembacaan 3 buah node B+Tree sebelum membaca blok datanya .

Dalam kuliah telah dibahas mekanisme yang terjadi saat masuknya key data ke dalam struktur B+Tree serta saat suatu key data dihapuskan dari struktur tsb. Saat masuknya data baru ke dalam tabel, key data dan referensi data dalam tabel disimpan dalam node leaf struktur B+Tree. Terdapat kapasitas maksimum setiap node sehingga saat key baru dimasukan sementara node sudah mencapai kapasitas maksimum, akan terjadi mekanisme “split”. Demikian pula, saat terjadi penghapusan data yang berakibat key pada node berkurang, apabila jumlah key melalui batas minimal kapasitas, maka akan terjadi mekanisme “merge” atau kalau tidak “redistribusi” isi node. Mekanisme-mekanisme itu memaintain struktur B+Tree tetap memenuhi kaidah sebagai suatu B+Tree agar setiap operasi dapat dilakukan secara O(log n) dengan basis logaritma bilangan yang besar.

Slide materi ini dapat di download di sini.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s