"B-Tree"
B-tree adalah struktur data yang menjaga data tetap balanced atau seimbang terurut dan memungkinkan operasi pencarian, penambahan, dan penghapusan dengan mudah dalam waktu logaritmik. B-tree sangat sesuai untuk dipakai dalam basis data dan berkas sistem karena mampu menangani data yang berukuran sangat besar dan dapat membagi data ke 2 media penyimpanan. B-tree mempunyai sifat struktur yang sama dengan RBT (Red-Black Tree) dimana setiap n-node nya mempunyai tinggi (height) sejumlah O(lg n). Jenis struktur data pohon ini didesain untuk Penyimpanan Sekunder (Secondary Storage) serta digunakan dalam aspek database dan filesystem. Tidak seperti pohon biner, setiap simpul pada B-tree dapat memiliki sejumlah variabel Key dan Child. Key disimpan dalam urutan membesar. Setiap elemen simpul internal adalah nilai-nilai yang berbeda yang membagi subtree nya. Setiap Key memiliki Child yang berhubungan dengan Key tersebut tersebut, yaitu root dari subtree dengan semua simpulkey-key lebih kecil atau sama dengan key simpul root akan tetapi lebih besar dari nilai key sebelumnya. Sebuah simpul juga mempunyai Child tambahan paling kanan yaitu root dari subtree yang mengandung semua key lebih besar dari semua key pada simpul.
Berdasarkan pengertian mengenai B-tree berikut di atas, dapat diketahui pengimplementasian B-tree di dalam Secondary memory mempunyai nilai efisiensi yang kuat dibandingkan dengan tindakan pemindahan data ke Memori Utama sekaligus.
Implementasi B-Tree dalam Secondary Memory
Implementasi a B-Tree dalam media penyimpanan sekunder, media penyimpanan sekunder merupakan perangkat yang digunakan untuk membantu media penyimpanan Primer, media penyimpanan sekunder bersifat Non-volatile, berbeda dengan media penyimpanan Perimer yang bersifat volatile yang apabila daya dimatikan maka akan hilang/terhapus, contohnya adalah RAM.
Namun dalam media penyimpanan ekunderlah (RAM) yang mimiliki kinerja yang cepat, berbeda dengan media penyimpanan primer yang relatif lebih lambat. Dan dalam RAM lah B-Tree dapat diterapkan, dimana hanya cukup mengakses blok tertentu saja, yaitu blok yang menyimpan indeks dari masing-masing tuple. Adapun B-tree yang penyimpanan deletakan dalam satu indeks yang tersusun menjadi B- Tree atau B+ Tree yang bertujuan untuk memudahkan pencarian data dalam media penyimpanan sekunder.
Alasan mengapa B-Tree banyak digunakan adalah karena:
1. Memungkinkan akses acak ke blok mana pun pada sebuah berkas tertentu
2. B-Tree bisa mengatasi masalah dalam mengubah alamat blok berkas menjadi alamat blok fisik
Berikut beberapa file system yang menggunakan B-Tree:
1. HFS+ dari Apple
2. NTFS dari Microsoft
3. AIX (jfs2), btrfs, Ext4 dari Linux
Dalam filesystem, B-Tree digunakan untuk dimungkinkannya random akses yang cepat ke arbitrary block pada file. Masalah dasarnya adalah mengubah alamat blok file i menjadi sebuah alamat blok disk. Beberapa sistem operasi membutuhkan pengguna untuk mengalokasikan jumlah maksimum dari ukuran file ketika file dibuat. File tersebut kemudian dapat dialokasikan sebagai disk blok secara berkelanjutan. Sistem operasi lainnya hanya menambahkan alamat blok file pada blok file awal dari file. Skemanya sederhana, tetapi ukuran file tidak dapat melebihi ukuran saat file pertama kali dibuat. Sistem operasi lainnya mengijinkan ukuran sebuah file untuk terus membesar. Hasilnya adalah disk blok bisa jadi tidak berkelanjutan, sehingga pemetaan blok logical ke blok fisik lebih berperan.
Acuan :
http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2011-2012/Makalah2011/Makalah-IF2091-2011-029.pdf
http://lambda.csail.mit.edu/~chet/papers/others/l/log-structured/rtcsa03_btreeflash.pdf