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.
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
No comments:
Post a Comment