B-Tree dan Hard Disk (Secondary Storage)

Kali ini saya dapat tugas di matakuliah Analisis Desain Algoritma I. Tugasnya menjelaskan hubungan B-tree dan secondary storage. Saya sih menganggap salah satu secondary storage yaaa hardisk jadi... Mari kita bahas, hubungan b-tree dan hardisk. Sebelum masuk lebih dalam mengenai hubungan B-Tree dan harddisk, alangkah lebih baik jika kita mengenal satu per satu definisi dari kedua kata tersebut.

 

Apa itu B-Tree? B-Tree merupakan suatu bentuk generalisasi dari struktur data Binary Search Tree (BST), yaitu pohon yang dapat memiliki lebih dari dua buah simpul/node. B-Tree memiliki kompleksitas logaritmik O(log(n)) dalam proses pembacaan maupun pencarian record. Bagian node paling atas disebut root (akar) dan node paling bawah disebut leaf (daun) dimana diasumsikan setiap bagian record telah diberikan suatu nilai key berupa indeks tertentu. 

Apa itu Harddisk? Harddisk adalah salah satu media penyimpanan kedua (secondary storage) dimana jika kita menyimpan data pada hard disk maka data kita tidak akan hilang meskipun sumber daya-nya mati. Akan tetapi kecepatan akses membaca dan menulis (read-write) dari harddisk cukup lambat jika dibandingkan dengan RAM (Random Access Memory) yang merupakan media penyimpanan pertama (primary storage). Beberapa secondary storage lainnya adalah disket, CD (Compact Disc), DVD, flashdisk, memori card, dan lain sebagainya.

SEBENARNYA APA HUBUNGAN DIANTARA B-TREE DAN HARDISK?

Tentunya karena B-Tree yang mampu mengakses data dalam jumlah besar dan waktu yang cepat membuat penggunaannya sangat cocok untuk hard disk. B-Tree mampu mencari key secara 'cepat' pada data dalam jumlah besar seperti pada hard disk walaupun key tersebut berada pada node leaf/node terbawah.

Lama proses pencarian key dengan metode B-Tree sebenarnya sebanding dengan tingkat kedalaman atau dapat dituliskan sebagai O(h). Keuntungan penggunaan B-Tree adalah kita cukup mengakses blok yang menyimpan indeks dari masing-masing record (lihat gambar). Dikarenakan akses langsung dari harddisk jauh lebih lambat dibanding dengan mengakses/menyimpan indeks dari record yang tentunya memiliki memori lebih kecil, menyebabkan akses/proses pencariannya lebih cepat. 

Bisa dibayangkan jika data yang ada sebesar 1 TeraByte maka pohon yang terbentuk akan memiliki ketinggian yang sangat besar (pada kasus tree/pohon biasa, dimana pohon tidak boleh memiliki lebih dari dua simpul), sedang waktu yang dibutuhkan untuk mencari key pada satu ketinggian/height pohon adalah satu menit, maka bisa dipastikan pencarian key tersebut tidak akan berjalan cepat bahkan bisa berjam-jam lamanya 

Tetapi jika kita menggunakan B-Tree pada proses pencariannya maka waktu aksesnya dapat dipercepat. Sebagai contoh, data sebesar 1 TB harus diakses dalam waktu 3 menit dan waktu akses/pencarian di tiap ketinggian pohon adalah satu menit (kita anggap identik) maka B-Tree akan mengatur sehingga pohon tersebut memiliki ketinggian tiga (3 record) dan mencari key di tiap ketinggian/record (satu record ada banyak cabang/child) dengan waktu satu menit tiap recordnya. Jadi B-Tree akan dapat mengakses data tersebut dalam waktu 3 menit (sesuai target)

Salah satu contoh implementasi B-Tree pada harddisk (Secondary Storage) adalah misal kita ingin mencari "Algorithms_3rd.pdf" maka B-Tree akan mengaksesnya melalui indeks yang mengacu pada byte-byte file "Algorithms_3rd.pdf" tersebut, dimana byte-byte tersebut tidak semuanya berada pada directory yang sama. Jadi B-Tree akan mengakses indeks dari record yang telah ditentukan B-Tree dan menyebabkan aksesnya lebih cepat.

B-Tree biasanya digunakan pada database yang berukuran besar seperti harddisk sebab waktu akses dan pemindahan datanya dari/ke media penyimpanan berjalan efisisien dan cepat. Metode ini juga bisa diaplikasikan pada penyimpanan data-data karyawan maupun inventarisasi perusahaan dan pembuatan DBMS (DataBase Management System).

Referensi:

• Setiadi, Iskandar. Analisis B-Tree dan B+ Tree Indexed File. Sekolah Teknik Elektro dan Informatika ITB. 

• http://en.wikipedia.org/wiki/B-tree

• http://en.wikipedia.org/wiki/Computer_data_storage