Implementasi B-Tree Pada Secondary Storage

Dalam penggunaannya pada database, sistem berbentuk B-tree digunakan dalam filesystem untuk membuat suatu akses data random secara cepat pada suatu block-block file. Ketika suatu database memiliki berjuta-juta record. Maka dibutuhkan penanganan yang cepat dalam hal pengambilan suatu data di database itu ataupun penyimpanan kembali ke dalam data base tersebut. Dengan penggunaan memory biasa pada database untuk melakukan pencarian data dan penyimpanan data akan membutuhkan waktu yang lama dan kurang efisien, sehingga bentuk data B-Tree sering digunakan untuk pengindeks-an data dan mempercepat waktu pengaksesan data.

             Struktur B-Tree : 

   

               Misal pada suatu contoh kita memiliki suatu data tanpa berindex dan tanpa terurut sebanyak n-key, pada proses pencarian data akan memiliki worst case running time yaitu O(n). Namun jika data itu sudah diberi indeks berbentuk B-tree, dengan operasi pencarian yang sama akan worst case running time akan menjadi O(log n). Untuk menjalankan suatu pencarian pada suatu set key yang berjumlah 1 juta, pencarian terurut akan membutuhkan waktu maksimal juga sebanyak 1 juta. Namun ketika sudah dibentuk suatu B-Tree dengan minimum degree 10, maka worst case akan didapatkan sebanyak 114. Dengan memaksimalkan jumlah key pada setiap node nya, maka tinggi dari suatu tree akan dapat di minimalkan sehingga jumlah akses ke tiap node nya akan berkurang. Banyaknya maksimum node child bergantung pada suatu informasi data yang akan disimpan dalam database dan juga pada jumlah total disk block dalam secondary storage. Meskipun struktur tree balance yang lain dapat digunakan, namuan B-Tree dapat mengoptimalkan suatu pencarian akses disk dalam jumlah data yang sangat banyak.