Hubungan B-Tree dan Hard disk

Pendahuluan

B-tree

is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.

Hard disk

is a data storage device used for storing and retrieving digital information using rapidly rotating disks (platters) coated with magnetic material.

Fisik Hard disk modern :

Perputaran Platters (piringan magnetik) dan Head disk modern :

Memori utama : 

Hubungan B-Tree dan Hard disk
Hard disk merupakan perangkat magnetik yang digunakan sebagai media penyimpanan kedua (secondary storage) setelah memori utama. Kapasitas penyimpanannya lebih besar dan lebih murah dibandingkan memori utama, namun 100.000 kali lebih lambat. Oleh karena memori utama tidak dapat menyimpan file dalam jumlah banyak dan besar maka digunakanlah hard disk sebagai penyimpanan yang non-volatile. Jika file tidak ada di memori utama maka CPU akan mengambilnya dari hard disk. Jika file tersebut dimisalkan x maka proses tersebut diwakili oleh Read(x). File tersebut berupa sekumpulan data dalam disk page (bagian atau wadah data pada hard disk). Biasanya berukuran kurang lebih 4 KB tiap page. Setelah file berhasil di-load ke memori utama, CPU dapat melakukan perubahan atau tidak. Jika terjadi perubahan maka file tersebut disimpan kembali dalam hard disk yang diwakili oleh Write(x). Proses tersebut (Read() dan Write()) umumnya menggunakan struktur data B-Tree yang dapat menangani file atau database dalam jumlah besar dengan cukup efisien. Node dalam struktur data B-Tree diwakili oleh disk page. Dengan branching factor yang besar maka worst case Read() maupun Write() dapat dihindari, sehingga lebih efisien. Biasanya digunakan branching factor sebesar 50 hingga 20.000.



Sumber: wikipedia.org, Introduction to Algorithm 3rd Edition, dan sumber online lainnya.