HALAMAN JUDUL
SKRIPSI B-TREE DALAM BASIS DATA FIREBIRD
Sulistyo Sudarmono 01/147005/PA/08465
Sebagai salah satu syarat untuk memperoleh derajat sarjana S1 Program Studi Ilmu Komputer pada Jurusan Matematika
Departemen Pendidikan Nasional Universitas Gadjah Mada Fakultas Matematika Dan Ilmu Pengetahuan Alam Yogyakarta 2006
i
HALAMAN PENGESAHAN
SKRIPSI B-TREE DALAM BASIS DATA FIREBIRD
Sulistyo Sudarmono 01/147005/PA/08465 Telah dipertahankan di depan Tim Penguji dan dinyatakan lulus oleh Tim Penguji Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Gadjah Mada Pada tanggal 29 Maret 2006
Tim Penguji Nama
Tanda Tangan
1. Drs. Y Suyanto, M.Kom ( Dosen Pembimbing )
1.
2. Nur Rokhman, S.Si., M.Kom ( Dosen Penguji )
2.
3. Drs. Suprapto, M.Kom ( Dosen Penguji )
3.
ii
HALAMAN PERSEMBAHAN
“Tiada
hal yang tidak mungkin ”
Ku persembahkan karya ini Kepada Allah SWT Kepada Bapak Ibu Simun di Yogyakarta Kepada Bapak Ibu Asmawi Hasan di Dukuhseti, Pati Kepada Mbak Santi dan Mas Atek Kepada Dek Laila Fitriyah
iii
KATA PENGANTAR Segala puji dan syukur bagi Allah SWT yang senantiasa memberikan kekuatan, rahmat, petunjuk serta ridho-Nya kepada penyusun sehingga tugas akhir yang berjudul “B-tree Dalam Basis Data Firebird” dapat diselesaikan. Tugas akhir ini dibuat untuk memenuhi persyaratan guna memperoleh derajat sarjana S-1 pada Program Studi Ilmu Komputer, Jurusan Matematika dan Ilmu Pengetahuan Alam, Universitas Gadjah Mada. Penyusun mengucapkan terima kasih yang sebesar-besarnya kepada semua pihak yang telah mendukung penyusunan dalam penyelesaian tugas akhir ini, baik moril maupun materil, diantaranya : 1. Bapak dan Ibu tercinta, mbak Santi sekeluarga dan seluruh anggota keluarga besar Wongsotaruno yang selalu memberikan semangat, doronga n dan doa selama ini. 2. Bapak Drs. Y. Suyanto, M.Kom, sebagai dosen pembimbing yang selalu sabar dan bersedia membimbing penyusun dalam penyusunan tugas akhir ini. 3. Bapak Nur Rokhman, S.Si, M.Kom, sebagai dosen wali yang telah memberikan bimbingan kepada penyusun selama kuliah di Universitas Gadjah Mada. 4. Seluruh dosen FMIPA UGM yang telah mendidik penyusun selama belajar dalam bangku perkuliahan. 5. Dek Laila yang memberikan perhatian, bantuan, dukungan, dan semangat untuk menyelesaikan tugas akhir ini.
iv
6. Teman-teman di GIM: Joe, Mastris, Hepiw, Arsad, Brem, Vita dan Lia. Terima kasih atas semua referensi, akses internet dan support yang telah kalian berikan. 7. Rekan-rekan di PPTIK UGM: Pak Bambang Prastowo, Bunda Susie Daryanti, Pak Danang Lelono, Pak Ahmad Azhari, Pak Ilham, Pak Basuki, Mas Sidoe, Mas Dendi, Mas Mardhani dan lainnya atas segala bantuan dan dukungan dalam penyusunan tugas akhir ini. 8. Teman-teman di PPTIK UGM dan ex-nya: mas Andri, Rendy, Niknok, Mundi, Acil, Yudi, Dino, Ajoe, Yudho, Adjie, Rini, Mas Bayu, Mas Yoga, Mas Wahyu dan lainnya yang telah memberikan banyak masukan yang berharga kepada penyusun. 9. Seluruh kru Pahlevi: Didit Ucul, SuperBeben, Wida, Untung, David, Windu, Cecep, Kotem dan Ami. 10. Seluruh teman-teman di Ilmu Komputer UGM dan Teknik Elektro UGM. Terimakasih banyak atas bantuan yang diberikan baik secara langsung maupun tak langsung. 11. Pihak lain yang namanya tidak dapat disebutkan satu per satu tapi telah banyak membantu penyusun.
Semoga Allah SWT membalas seluruh amal kebaikan dan dukungan untuk semuanya dengan sebaik-baik balasan-Nya.
v
Penyusun menyadari bahwa tugas akhir ini masih jauh dari sempurna, untuk itu penyusun sangat terbuka untuk semua saran dan kritikan yang bertujuan untuk perbaikan di masa yang akan datang.
Yogyakarta, Maret 2006
Penyusun
vi
DAFTAR ISI HALAMAN JUDUL.................................................................................................i HALAMAN PENGESAHAN ..................................................................................ii HALAMAN PERSEMBAHAN ..............................................................................iii KATA PENGANTAR.............................................................................................iv DAFTAR ISI..........................................................................................................vii DAFTAR TABEL...................................................................................................ix DAFTAR GAMBAR ...............................................................................................x INTISARI ..............................................................................................................xiii BAB I PENDAHULUAN .......................................................................................1 1.1 Latar Belakang Masalah...........................................................................1 1.2 Rumusan Masalah....................................................................................3 1.3 Batasan Masalah.......................................................................................3 1.4 Tujuan Penulisan Tugas Akhir .................................................................4 1.5 Hipotesis ...................................................................................................4 1.6 Tinjauan Pustaka ......................................................................................4 1.7 Metodologi Penyusunan Tugas Akhir......................................................5 BAB II DASAR TEORI..........................................................................................7 2.1 Basis Data.................................................................................................7 2.1.1 Pengertian Basis Data.......................................................................7 2.1.2 Kegunaan Basis Data .......................................................................8 2.2 B-tree ......................................................................................................11 2.2.1 Struktur Data B+-tree .....................................................................11 2.3 Sistem Basis Data Firebird .....................................................................20 2.3.1 Arsitektur Firebird ..........................................................................21 2.3.2 Struktur Berkas Page Firebird ........................................................29 2.3.3 Indeks dalam Firebird.....................................................................38 2.4 Diagram Alir (Flowchart).......................................................................42 2.5 Diagram Arus Data.................................................................................43 BAB III RANCANGAN SISTEM ........................................................................45 3.1 Rancangan Struktur Data .......................................................................47 3.2 Rancangan Diagram Alir........................................................................48 3.2.1 Diagram Alir Utama .......................................................................48 3.2.2 Diagram Alir Proses Penambahan Data .........................................49 3.2.3 Diagram Alir Proses Penghapusan Data ........................................58 3.2.4 Diagram Alir Proses Pencarian Data..............................................62 3.3 Rancangan Diagram Arus Data ..............................................................62 3.4 Rancangan Antarmuka ...........................................................................64 3.4.1 Form Utama ....................................................................................64 3.4.2 Form Setting Orde B-tree ...............................................................65 3.4.3 Form Input Data Awal....................................................................66 3.4.4 Form Tambah Data.........................................................................66 3.4.5 Form Hapus Data ...........................................................................67 3.4.6 Form Pencarian Data ......................................................................68 3.4.7 Form Statistik Proses......................................................................68
vii
3.4.8 Form Log Proses ............................................................................69 3.4.9 Form Preview Visual......................................................................69 3.4.10 Form ODS ......................................................................................70 BAB IV IMPLEMENTASI DAN PEMBAHASAN SISTEM .............................71 4.1 Implementasi Program Simulasi ............................................................71 4.1.1 Implementasi Struktur Data ...........................................................71 4.1.2 Implementasi Proses Inisialisasi....................................................72 4.1.3 Implementasi Proses Penambahan Data.........................................73 4.1.4 Implementasi Proses Penghapusan Data ........................................82 4.1.5 Implementasi Proses Pencarian Data .............................................93 4.1.6 Implementasi Antarmuka Program Simulasi .................................95 4.2 Analisis dan Pembahasan Hasil............................................................101 4.2.1 Struktur Indeks Pada Basis Data Firebird ....................................101 4.2.2 Struktur Indeks Pada Program Simulasi.......................................102 4.2.3 Struktur Berkas Pada Basis Data Firebird....................................102 4.2.4 Struktur Berkas Pada Program Simulasi......................................103 4.2.5 Proses Pemasukkan Data Pada Basis Data Firebird.....................104 4.2.6 Proses Pemasukkan Data Pada Program Simulasi.......................106 4.2.7 Proses Pencarian Data Pada Basis Data Firebird .........................107 4.2.8 Proses Pencarian Data Pada Program Simulasi............................109 4.2.9 Proses Penghapusan Data Pada Basis Data Firebird ....................110 4.2.10 Proses Penghapusan Data Pada Program Simulasi ......................111 4.2.11 Pengaruh Orde dan Ukuran Page .................................................112 BAB V PENUTUP ..............................................................................................114 5.1 Kesimpulan...........................................................................................114 5.2 Saran.....................................................................................................115 DAFTAR PUSTAKA ..........................................................................................116
viii
DAFTAR TABEL Tabel 2.1 Algoritma Penambahan Rekaman pada b+-tree ....................................13 Tabel 2.2 Algoritma Penghapusan Rekaman pada b+-tree ...................................17 Tabel 2.3 Simbol dan fungsi diagram alir ..............................................................42 Tabel 2.4 Simbol dan fungsi DAD.........................................................................44
ix
DAFTAR GAMBAR Gambar 2.1 Sebuah b+-tree dengan 4 key pada setiap page .................................12 Gambar 2.2 Key 28 dimasukkan ke dalam leaf page yang tidak penuh.................14 Gambar 2.3 Key 70 dimasukkan ke dalam leaf page yang penuh..........................14 Gambar 2.4 Key 95 dimasukkan ke dalam leaf page dan index page yang penuh 15 Gambar 2.5 Kondisi sebelum Key 70 dimasukkan ke dalam leaf page .................16 Gambar 2.6 Kondisi setelah terjadi rotasi..............................................................16 Gambar 2.7 Kondisi sebelum terjadi penghapusan................................................17 Gambar 2.8 Kondisi setelah key 70 dihapus ..........................................................18 Gambar 2.9 Kondisi setelah key 25 dihapus ..........................................................19 Gambar 2.10 Kondisi setelah key 60 dihapus ........................................................19 Gambar 2.11 Arsitektur komponen utama (Chan dan Yaskhir, 2002)...................22 Gambar 2.12 Modul remote connection system.....................................................23 Gambar 2.13 Modul SQL translator.......................................................................23 Gambar 2.14 Arsitektur dari relational database engine (JRD) .............................24 Gambar 2.15 Modul lock manager.........................................................................26 Gambar 2.16 Berkas single- file dan multi- file basis data Firebird (Harrison, 2005).................................................................................................30 Gambar 2.17 Header standar setiap page ...............................................................31 Gambar 2.18 Informasi header page dari sebuah berkas basis data Firebird .........32 Gambar 2.19 Page inventory page (PIP) ................................................................33 Gambar 2.20 Transaction inventory page (TIP).....................................................33 Gambar 2.21 Pointer page sebagai penunjuk data page .........................................34 Gambar 2.22 Data page sebagai media penyimpan data........................................35 Gambar 2.23 Index root page (IRT) sebagai penyimpan indeks root ....................36 Gambar 2.24 B-tree page atau index page .............................................................37 Gambar 2.25 Binary large object (BLOB) page ....................................................37 Gambar 2.26 Generator page .................................................................................38 Gambar 3.1 Node dalam sebuah b-tree ..................................................................47 Gambar 3.2 Susunan indeks dalam basis data Firebird..........................................48 Gambar 3.3 Susunan page dalam basis data Firebird.............................................48 Gambar 3.4 Diagram alir proses program simulasi b-tree dalam Firebird.............49 Gambar 3.5 Diagram alir algoritma penambahan data dalam b+-tree ..................50 Gambar 3.6 Diagram alir pembuatan page baru ....................................................51 Gambar 3.7 Diagram alir pencarian leaf page yang sesuai untuk pemasukan data ...................................................................................................52 Gambar 3.8 Diagram alir pemasukan data dalam leaf page ..................................53 Gambar 3.9 Diagram alir proses rotasi dengan sibling kiri....................................54 Gambar 3.10 Diagram alir proses rotasi dengan sibling kanan..............................54 Gambar 3.11 Diagram alir proses pembagian leaf page ........................................55 Gambar 3.12 Diagram alir pemasukan data dalam index page..............................56 Gambar 3.13 Diagram alir proses pembagian index page .....................................57 Gambar 3.14 Diagram alir algoritma penghapusan data dalam b+-tree................58 Gambar 3.15 Diagram alir pencarian leaf page yang sesuai untuk penghapusan data ...................................................................................................59
x
Gambar 3.16 Diagram alir penghapusan data dalam leaf page..............................60 Gambar 3.17 Diagram alir penggabungan page.....................................................61 Gambar 3.18 Diagram alir algoritma pencarian data dalam b+-tree .....................62 Gambar 3.19 Rancangan DAD tingkat ke-0 ..........................................................63 Gambar 3.20 Rancangan DAD tingkat ke-1 ..........................................................63 Gambar 3.21 Rancangan DAD tingkat ke-2 proses cari........................................63 Gambar 3.22 Rancangan DAD tingkat ke-2 proses tambah ..................................63 Gambar 3.23 Rancangan DAD tingkat ke-2 proses hapus.....................................64 Gambar 3.24 Form utama .......................................................................................65 Gambar 3.25 Form setting orde b-tree ...................................................................65 Gambar 3.26 Form input data awal........................................................................66 Gambar 3.27 Form tambah data .............................................................................67 Gambar 3.28 Form hapus data ...............................................................................67 Gambar 3.29 Form pencarian data .........................................................................68 Gambar 3.30 Form statistik proses.........................................................................69 Gambar 3.31 Form log proses................................................................................69 Gambar 3.32 Form preview visual.........................................................................70 Gambar 3.33 Form ODS ........................................................................................70 Gambar 4.1 Potongan kode program tipe data yang digunakan ............................72 Gambar 4.2 Potongan kode program proses inisialisasi indeks.............................72 Gambar 4.3 Potongan kode program prosedur dan variabel yang digunakan .......73 Gambar 4.4 Potongan kode program jika newTree merupakan index node ..........74 Gambar 4.5 Potongan kode program jika newTree merupakan leaf node .............74 Gambar 4.6 Potongan kode program pencarian rekursif........................................75 Gambar 4.7 Potongan kode program pencarian posisi data yang sesuai dalam node ..................................................................................................76 Gambar 4.8 Potongan kode program pemasukan data dalam indeks jika node tidak penuh .......................................................................................76 Gambar 4.9 Potongan kode program pembagian indeks jika node penuh.............77 Gambar 4.10 Potongan kode program pemasukan data dalam leaf jika node tidak penuh .......................................................................................78 Gambar 4.11 Potongan kode program rotasi sibling kiri jika node penuh.............79 Gambar 4.12 Potongan kode program rotasi sibling kanan jika node penuh.........80 Gambar 4.13 Potongan kode program pembagian leaf jika node penuh ...............82 Gambar 4.14 Potongan kode program prosedur dan variabel yang digunakan .....83 Gambar 4.15 Potongan kode program pencarian rekursif......................................84 Gambar 4.16 Potongan kode program penghapusan data dalam indeks jika jumlah data di atas orde ....................................................................85 Gambar 4.17 Potongan kode program proses penggabungan sibling kiri index node ..................................................................................................86 Gambar 4.18 Potongan kode program proses penggabungan sibling kanan index node.........................................................................................88 Gambar 4.19 Potongan kode program penghapusan data dalam indeks jika jumlah data di bawah orde................................................................89 Gambar 4.20 Potongan kode program penghapusan data dalam leaf jika jumlah data di atas orde ................................................................................90
xi
Gambar 4.21 Potongan kode program proses penggabungan sibling kiri leaf node ..................................................................................................91 Gambar 4.22 Potongan kode program proses penggabungan sibling kanan leaf node ..................................................................................................92 Gambar 4.23 Potongan kode program penghapusan data dalam leaf jika jumlah data dibawah orde .............................................................................93 Gambar 4.24 Potongan kode program prosedur dan variabel yang digunakan .....93 Gambar 4.25 Potongan kode program pencarian rekursif......................................94 Gambar 4.26 Potongan kode program pencarian posisi data yang sesuai dalam node ..................................................................................................94 Gambar 4.27 Implementasi Form Utama ...............................................................95 Gambar 4.28 Implementasi Form Inisialisasi Indeks.............................................95 Gambar 4.29 Implementasi Form Input Data Awal...............................................96 Gambar 4.30 Implementasi Form Tambah Data ....................................................97 Gambar 4.31 Implementasi Form Hapus Data.......................................................97 Gambar 4.32 Implementasi Form Input Data Awal...............................................98 Gambar 4.33 Implementasi Form Statistik Proses.................................................99 Gambar 4.34 Implementasi Log Proses .................................................................99 Gambar 4.35 Implementasi Form Preview Visual...............................................100 Gambar 4.36 Implementasi Form ODS................................................................100 Gambar 4.37 Struktur berkas indeks dalam sistem basis data Firebird ...............103 Gambar 4.38 Struktur berkas indeks dalam program simulasi ............................104 Gambar 4.39 Grafik jumlah rekaman dan waktu eksekusi insert pada sistem basis data Firebird dengan page 1024 KB......................................105 Gambar 4.40 Grafik jumlah rekaman dan waktu eksekusi insert pada sistem basis data Firebird dengan page 8192 KB......................................105 Gambar 4.41 Grafik jumlah rekaman dan waktu eksekusi insert pada orde 2.....106 Gambar 4.42 Grafik jumlah rekaman dan waktu eksekusi insert pada orde 20...107 Gambar 4.43 Grafik jumlah rekaman dan waktu eksekusi select pada sistem basis data Firebird dengan page 1024 KB......................................108 Gambar 4.44 Grafik jumlah rekaman dan waktu eksekusi select pada sistem basis data Firebird dengan page 8192 KB......................................108 Gambar 4.45 Grafik jumlah rekaman dan waktu eksekusi select pada orde 2.....109 Gambar 4.46 Grafik jumlah rekaman dan waktu eksekusi select pada orde 20...109 Gambar 4.47 Grafik jumlah rekaman dan waktu eksekusi delete pada sistem basis data Firebird dengan page 1024 KB......................................110 Gambar 4.48 Grafik jumlah rekaman dan waktu eksekusi delete pada sistem basis data Firebird dengan page 8192 KB......................................111 Gambar 4.49 Grafik jumlah rekaman dan waktu eksekusi delete pada orde 2 ....112 Gambar 4.50 Grafik jumlah rekaman dan waktu eksekusi delete pada orde 20 ..112 Gambar 4.51 Grafik jumlah rekaman dan waktu eksekusi delete pada orde 2 dengan 65535 data ..........................................................................113
xii
INTISARI
B-TREE DALAM BASIS DATA FIREBIRD
Oleh Sulistyo Sudarmono 01/147005/PA/8465
Sistem basis data merupakan suatu kumpulan data yang saling terkait. Sistem basis data menggunakan indeks untuk mempercepat pencarian data. Firebird merupakan salah satu sistem basis data yang menggunakan salah satu jenis b-tree untuk menangani indeks. Skripsi ini bertujuan untuk mengetahui cara kerja indeks pada sistem basis data Firebird. Skripsi ini menggunakan indeks jenis b+-tree. B+-tree adalah salah satu jenis b-tree yang mirip dengan struktur indeks pada basis data Firebird. Keluaran dari simulasi dalam skripsi ini adalah bentuk visualisasi dari proses yang dilakukan oleh indeks saat menambah, menghapus dan mencari rekaman. Simulasi dalam skripsi ini diuji menggunakan data acak dan menunjukkan bahwa proses pemasukan data dan proses penghapusan data lebih kompleks daripada proses pencarian data. Orde indeks juga mempengaruhi tingkat kepadatan dan kecepatan. Indeks dengan orde besar menyebabkan jumlah node menjadi sedikit dan tingkat indeks menjadi dangkal. Jumlah node yang sedikit serta tingkat yang dangkal menyebabkan waktu eksekusi. Jumlah data yang ada juga mempengaruhi waktu eksekusi. Waktu yang dibutuhkan semakin bertambah secara logaritmik seiring dengan bertambahnya data. Waktu ekseskusi rata-rata mendekati O(log n).
xiii
1BAB I PENDAHULUAN 1.1 Latar Belakang Masalah Sistem basis data mempunyai beberapa metode untuk menyimpan dan mengelompokkan record (rekaman data). Data disimpan dengan cara langsung ke dalam indeks atau dikelompokkan menggunakan key (nilai yang dapat digunakan untuk mengidentifikasi baris rekaman). Sistem basis data lebih cenderung menggunakan indeks primary key (indeks pada key utama) untuk menyimpan data. Indeks primary key membuat pencarian dalam sistem basis data sangat efisien. Indeks (struktur data yang memungkinkan pencarian sublinier) dengan seluruh rekaman tersimpan di dalamnya membuat tingkat kedalaman sangat dalam dan tidak mudah untuk melintas. Indeks yang padat membuat tingkat kedalaman indeks menjadi dangkal dan mudah dilintasi (Harrison 2005). Sistem basis data mengunakan beberapa macam metode untuk membentuk indeks. B-tree merupakan salah satu metode untuk membentuk indeks. B-tree merupakan metode penyusunan data berbentuk tree (struktur data seperti pohon yang merupakan kumpulan dari node) yang secara umum dapat ditemukan pada sistem basis data dan sistem berkas. B-tree bergerak secara bottom-up ketika terjadi perubahan data di dalamnya. B-tree mempunyai keunggulan pada waktu penjangkauan data pada setiap node (unit terkecil dalam pembentukan tree). B-tree digunakan pada ruang simpan sekunder yang memiliki waktu penjangkauan antar node melebihi waktu penjangkauan dalam node.
1
2
Jumlah child node atau subtree (elemen didalam node) dalam setiap node mempengaruhi efisiensi dan tinggi suatu B-tree. Jumlah child node yang semakin banyak menjadikan tinggi B-tree berkurang dan efisiensi pencarian meningkat. Makalah yang berjudul “Binary B-Trees for Virtual Memory” oleh Prof. Rudolf Bayer Ph. D mengawali metode B-tree. Makalah tersebut dipaparkan pada suatu workshop “ACM-SIGFIDET” tahun 1971 di San Diego, California. Inner node (sebuah node dalam struktur data B-tree) merupakan dasar pemikiran B-tree. Inner node mempunyai jumlah child node yang bervariasi dan telah terdefinisi terlebih dahulu. Inner node mengurangi frekuensi penyeimbangan ulang pada B-tree (Anonim 2005a). Interbase merupakan sistem basis data relasional komerisal yang sudah dipakai lebih dari 15 tahun. Borland menjadikan Interbase sebagai produk open source pada Desember 1999. Borland melepas versi Interbase terbaru untuk lisensi komersial pada Desember 2001. Interbase komersial mematikan produk Interbase open source dan menyisakan arsitekturnya. Mark O'Donohue dan para mantan pengembang Interbase mengembangkan sisa arsitektur dari Interbase. Firebird merupakan proyek sistem basis data pengembangan arsitektur Interbase yang ditulis dengan bahasa C++. Firebird menggunakan metode B-tree untuk membentuk indeks. Indeks Firebird merupakan indeks sangat padat karena kedua prefik dan sufik pada setiap key menggunakan kompresi. Penyimpanan yang padat pada indeks memungkinkan kedalaman B-tree menjadi kecil (Harrison 2005).
3
Indeks primer dan indeks sekunder mempengaruhi waktu penjangkauan data pada suatu sistem basis data. Primary key yang mempunyai kelompok data memiliki waktu penjangkauan data sangat cepat. Indeks sekunder yang menggunakan primary key sebagai penunjuk record membutuhkan waktu penjangkauan data lebih lambat dibandingkan indeks sekunder yang terpecah menjadi dua indeks pencarian (Harrison 2005). Struktur yang berbeda dari sistem basis data lain digunakan dalam proses penjangkauan indeks Firebird. Proses penjangkauan indeks Firebird menghasilkan waktu pencarian indeks primer dan indeks sekunder yang sama. 1.2 Rumusan Masalah Masalah yang dapat dirumuskan dalam tugas akhir ini sebagai berikut : 1. Menganalisis cara kerja indeks b-tree dalam sistem basis data Firebird. 2. Mengimplementasikan proses manipulasi data pada indeks b-tree dalam sistem basis data Firebird dalam bentuk visualisasi. 1.3 Batasan Masalah Batasan masalah yang perlu diberikan berdasarkan permasalahan yang telah dikemukakan diatas adalah sebagai berikut : 1. Indeks pada program simulasi menggunakan jenis b+-tree. 2. Basis data acuan yang dipakai adalah sistem basis data Firebird 1.5 3. Proses manipulasi data meliputi proses pemasukan data, proses penghapusan data, dan proses pencarian data. 4. Waktu simulasi merupakan waktu yang diperoleh dari eksekusi perintah pada setiap data.
4
5. Data yang dimasukkan ke dalam indeks merupakan tipe integer. 6. Program simulasi mengeluarkan log proses, visualisasi bentuk indeks, dan waktu eksekusi. 7. Waktu ekseskusi proses manipulasi data dipengaruhi oleh proses visualisasi dan pencatatan log. 1.4 Tujuan Penulisan Tugas Akhir 1. Membuat program simulasi penggunaan metode B-tree dan proses manipulasi data. 2. Mengetahui waktu pembentukan indeks pada struktur B-tree. 1.5 Hipotesis Kesimpulan awal yang diperoleh tentang penyusunan tugas akhir ini antara lain: 1. Waktu eksekusi berbanding banyak data digambarkan dalam bentuk logaritmik. 2. Data page pada Firebird merupakan leaf node dari modul B-tree pada Firebird. 3. Orde b-tree mempengaruhi kepadatan dan tinggi tingkat indeks. 4. Proses pencarian dalam indeks b-tree membutuhkan waktu O(log n). 1.6 Tinjauan Pustaka Penelitian terdahulu yang membahas sistem indeks pada basis data Firebird telah dipaparkan oleh Harrison (2005) dalam makalah yang berjudul “Firebird for the Database Expert ”. Harrison menjelaskan bahwa sebuah basis data Firebird memiliki page yang berurutan dan berukuran sama yang secara normal terletak
5
pada satu berkas. Sejarah basis data Firebird beserta penjelasan dan kelebihannya dipaparkan oleh Harrison (2002) dalam konferensi open source di Tokyo, Jepang. Chan dan Yashkir (2002) dalam makalah yang berjudul “Conceptual Architecture for InterBase/Firebird” menjelaskan tentang identifikasi dari komponen utama dari sistem basis data Interbase/Firebird beserta interaksinya. Setiap komponen dari Interbase/Firebird memiliki arsitektur sendiri. Berbagai bentuk beserta algoritma struktur data untuk sistem pengorganisasian berkas dibahas oleh Tharp (1988). Stuktur data B-tree merupakan salah satu bentuk struktur data untuk sistem pengorganisasian berkas yang berjenis tree. Struktur data jenis tree beserta analisis algoritma dijelaskan oleh Brassard dan Bratley (1996). Model B+-tree beserta algoritma modifikasi data dibahas oleh Anderson (1998). 1.7 Metodologi Penyusunan Tugas Akhir Metode yang digunakan dalam penyusunan tugas akhir ini adalah 1. Tinjauan pustaka Mempelajari jurnal, hasil penelitian, buku yang terkait dengan metode Btree, sistem basis data Firebird 1.5, sistem indeks dan struktur data. 2. Desain sistem Melakukan pembuatan alur proses yang tergambar dalam bentuk Data Flow Diagram dan merancang struktur datanya. 3. Implementasi Mengimplementasi suatu simulasi sistem yang telah terdisain ke dalam program komputer dengan bantuan Borland Delphi 6. 4. Verifikasi
6
Meneliti simulasi sistem yang telah dibuat dengan metode yang digunakan dan mencocokan hasilnya. 5. Penulisan tugas akhir Penulisan tugas akhir dimulai dari pembuatan proposal sampai dengan kesimpulan dari simulasi sistem yang dibuat.
2BAB II DASAR TEORI 2.1 Basis Data Basis data (database) merupakan suatu bentuk pengorganisasian sekumpulan data yang saling terkait sehingga memudahkan aktivitas untuk memperoleh informasi. 2.1.1 Pengertian Basis Data Suatu sistem basis data secara dasar dapat didefinisikan sebagai suatu sistem pengarsipan berbasis komputer yang bertujuan untuk merekam dan menangani informasi. Informasi yang direkam sistem basis data meliputi segala sesuatu yang termasuk dalam pelayanan sistem tersebut. Sebuah sistem basis data mempunyai empat komponen utama yaitu (Date, 1981) : 1. Data Data yang tersimpan dalam sistem secara terpartisi dalam satu atau lebih basis data. Data dalam sistem basis data dapat berupa data tergabung atau dalam bentuk data terbagi. Data dalam bentuk tergabung jika sistem basis data merupakan sebuah satu kesatuan dari beberapa berkas berbeda dengan beberapa atau seluruh berkas tersebut terdapat redudansi. Data dalam bentuk terbagi jika bagian data dalam basis data dibagi kepada beberapa pengguna yang memungkinkan seorang pengguna dapat menjangkau bagian data yang sama.
7
8
2. Perangkat keras Perangkat keras yang digunakan sistem basis data berupa media penyimpan sekunder yang dapat menyimpan susunan data dalam sistem tersebut. 3. Perangkat lunak Perangkat lunak dalam sistem basis data berfungsi sebagai jembatan antara basis data fisik yang dikelola oleh perangkat keras dengan pengguna. Perangkat lunak dalam suatu sistem basis data dikenal dengan sebutan Database Manage ment System (DBMS). 4. Pengguna Suatu sistem basis data membagi pengguna dalam tiga bagian dasar pengguna. Bagian application programmer merupakan pengguna yang menulis program aplikasi yang menggunakan basis data. Aplikasi program dapat memanipulasi informasi dalam basis data dan dapat bekerja secara on-line maupun batch. Bagian end-user merupakan bagian pengguna yang melakukan manipulasi terhadap informasi dalam sistem basis data dengan cara menjalankan aplikasi program. Bagian database administrator (DBA) merupakan bagian pengguna yang menentukan dan mengidentifikasi entitas dari suatu kebutuhan basis data dan mengidentifikasi informasi yang dapat dimasukkan untuk memenuhi entitas yang sesuai. 2.1.2 Kegunaan Basis Data Basis data merupakan sebuah bahan dari komputasi bisnis pada awal dari era digital. Basis data relasional lahir pada tahun 1970 ketika E. F. Codd menulis
9
makalah tentang garis besar proses relasi pada suatu basis data. Basis data relasional berkembang dan menjadi standar seiring dengan kemajuan teknologi (Anonim, 2005b). Sebuah sistem basis data menyediakan kontrol terpusat pada data yang sedang dioperasikan. Beberapa keuntungan yang didapat dari penggunaan basis data yang menggunakan sistem kontrol terpusat antara lain (Date, 1981): 1. Redudansi dapat dikurangi Sebuah sistem yang tidak menggunakan basis data menyimpan berkas pada berkas privat. Berkas privat dapat menimbulkan terjadinya redudansi data yang berakibat pada pembuangan ruang pada media penyimpan. Sistem basis data dapat mengurangi redudansi data dengan mengatur data yang terduplikasi menjadi sebuah data. Redudansi tidak dapat dihilangkan sepenuhnya karena basis data tetap menangani data yang terduplikasi dalam kondisi teknis atau ketentuan tertentu. 2. Menghindari data tidak konsisten Basis data dapat mengirimkan pesan tidak konsisten ketika terjadi konflik informasi di dalamnya. Data inkonsisten dalam basis data harus dirubah agar konsistensi tetap terjaga. Basis data terdapat perintah update untuk menjaga data agar tetap konsisten. 3. Data dapat dibagi Tidak hanya sebuah aplikasi yang telah ada yang dapat membagi data dalam sistem basis data kepada para pengguna. Aplikasi yang baru dikembangkan
10
dapat menggunakan basis data yang sama dan tidak perlu menyimpan berkas baru. 4. Standarisasi data Representasi data secara standar dapat dilakukan oleh DBA pada basis data yang menggunakan kontrol terpusat. Standarisasi format data yang tersimpan merupakan sebuah alat bantuk untuk melakukan sebuah migrasi antar sistem (data interchange). 5. Keamanan Sistem keamanan basis data memungkinkan pengguna tertentu untuk menggunakan basis data dan melakukan operasi sesuai dengan hak akses pengguna tersebut. 6. Kesatuan data terjaga Inkonsistensi antara dua masukan merupakan suatu gambaran tentang kekurangan kesatua n dalam kumpulan data. Kesatuan data dalam sistem basis data dijaga dengan cara mengurangi redudansi dan inkonsistensi data. Basis data memungkinkan DBA untuk melakukan validasi data. 7. Keperluan dapat seimbang Keperluan setiap pengguna basis data tidak sama. DBA dapat mengelola struktur sebuah basis data untuk menyeimbangkan pelayanan sesuai dengan keperluan pengguna. DBA dapat memberikan akses yang cepat pada aplikasi yang dinilai sangat penting dan mengurangi performa pada aplikasi yang lain.
11
2.2 B-tree B-tree merupakan sebuah struktur data berbentuk tree yang secara umum dapat ditemukan pada sistem berkas dan basis data. B-tree menjaga data tetap terurut dan memungkinkan pengisian dan penghapusan data dilakukan dengan waktu yang logaritmik. B-tree secara umum berkembang dari bawah ke atas sesuai dengan elemen yang diisikan. B-tree mempunyai inner node yang fleksibel dan mempunyai jumlah child node yang berbeda pada batas yang telah ditentukan. B-tree tidak perlu melakukan penyeimbangan secara sering yang biasa dilakukan oleh struktur data tree yang lain. Sebuah node dalam keadaan ilegal apabila mempunyai jumlah child node yang salah (Anonim, 2005a). Rudolf Bayer merupakan pencipta b-tree dan tidak menjelaskan tentang kepanjangan dari huruf b pada kata “b-tree”. Secara umum huruf pada kata “btree” dapat berarti balance atau bayer atau boeing karena setiap leaf node b-tree seimbang dan Rudolf Bayer bekerja pada Boeing Scientific Research Labs (Anonim, 2005a). 2.2.1 Struktur Data B+-tree B+-tree merupakan sebuah b-tree yang rekaman datanya diletakkan pada terminal node dan pada nonterminal node hanya berisi nilai key yang membentuk sebuah indeks ke dalam node data (Tharp, 1988). Anderson (1998) menjelaskan bahwa sebuah b+-tree memuat fitur Indexed Sequential Access Method (ISAM) dan fitur b-tree. B+-tree terdiri dari index page dan data page. Data page terdapat dalam bentuk leaf node(terminal node). Root node dan node tingkat menengah
12
selalu membentuk index page. Fitur indeks dan data mirip dengan fitur pada ISAM tetapi fitur overflow page tidak digunakan dalam b+-tree. Index page dalam b+-tree dibuat melalui proses pengisian dan penghapusan rekaman. B+tree dan b-tree menggunakan sebuah faktor pengisi untuk mengontrol perkembangan dan penyusutan. Sebuah faktor pengisi bernilai 50% menjadi nilai minimum b+-tree atau b-tree. B+-tree dengan 4 key pada setiap page mempunyai 5 pointer tiap page. Key minimal pada setiap page sebanyak 2 key jika faktor pengisi sebesar 50%. Aturan faktor pengisi telah ditetapkan tetapi root page dapat melanggar aturan faktor pengisian. Gambar 2.1 menggambarkan data dan indeks dari sebuah b+-tree dengan dengan 4 key pada setiap page.
Gambar 2.1 Sebuah b+-tree dengan 4 key pada setiap page 2.2.1.1 Penambahan Rekaman pada Sebuah B+-tree Nilai dari key pada indeks menunjukkan letak rekaman pada sebuah b+-tree. Leaf page dipelihara secara sekuensial dan terdapat senarai berantai yang menghubungkan antar leaf page. Algoritma penambahan rekaman dipengaruhi keadaan leaf page dan index page (Anderson, 1998). Tabel 2.1 menunjukkan aksi yang harus dijalankan ketika terjadi penambahan rekaman pada suatu b+-tree.
13
Tabel 2.1 Algoritma Penambaha n Rekaman pada b+-tree Leaf Page Index Page Aksi Tidak penuh Tidak penuh Letakkan rekaman pada posisi terurut di leaf page yang tepat. Penuh Tidak penuh 1. Membagi leaf page. 2. Meletakkan middle key pada index page dengan posisi terutut. 3. Leaf page kiri berisi rekaman dengan key kurang dari middle key. 4. Leaf page kanan berisi rekaman dengan key yang lebih dari atau sama dengan middle key. Penuh Penuh 1. Membagi leaf page. 2. Rekaman dengan key kurang dari middle key ke sebelah kiri dari leaf page. 3. Rekaman dengan dengan key yang lebih dari atau sama dengan middle key ke sebelah kanan dari leaf page. 4. Membagi index page. 5. Key lebih kecil dari pada middle key ke sebelah kiri index page. 6. Key lebih besar dari pada middle key ke sebelah kanan index page. 7. Middle key naik ke tingkat yang lebih tinggi. Teruskan membagi index page jika tingkat index page selanjutnya penuh. Penambahan sebuah rekaman dalam sebuah leaf page yang tidak penuh pada sebuah b+-tree dapat dilihat dalam Gambar 2.2. Rekaman secara langsung dimasukkan ke dalam leaf page secara berurutan jika dalam leaf page tersebut masih terdapat ruang (Anderson, 1998). Gambar 2.2 menjelaskan ketika rekaman dengan key 28 dimasukan ke dalam leaf page maka key tersebut akan menggeser posisi key 30 sehingga key 28 terletak pada posisi yang telah terurut.
14
Gambar 2.2 Key 28 dimasukkan ke dalam leaf page yang tidak penuh Penambahan sebuah rekaman dalam sebuah leaf page yang penuh pada sebuah b+-tree dapat dilihat dalam Gambar 2.2 dan Gambar 2.3. Leaf page dibagi menjadi dua bagian ketika rekaman dimasukkan ke dalam sebuah leaf page yang penuh. Middle key dinaikkan ke dalam indeks setelah proses pembagian leaf page (Anderson, 1998). Gambar 2.2 menunjukan posisi awal sebelum key 70 dimasukkan ke dalam b+-tree. Gambar 2.3 menjelaskan ketika rekaman dengan key 70 dimasukan ke dalam leaf page dan kondisi leaf page dalam keadaan penuh. Key 60 menjadi middle key dan leaf node dibagi menjadi dua bagian dan middle key diletakkan pada indeks.
Gambar 2.3 Key 70 dimasukkan ke dalam leaf page yang penuh Penambahan sebuah rekaman dalam sebuah leaf page dan index page yang penuh pada sebuah b+-tree dapat dilihat dalam Gambar 2.3 dan Gambar 2.4. Leaf page dibagi menjadi dua bagian ketika rekaman dimasukkan ke dalam sebuah leaf page yang penuh. Middle key dinaikan ke dalam indeks setelah pembagian leaf
15
page. Index page dibagi menjadi dua bagian dan middle key indeks dinaikkan ketika index page penuh (Anderson, 1998). Gambar 2.3 menunjukan posisi awal sebelum key 95 dimasukkan ke dalam b+-tree. Gambar 2.4 menjelaskan ketika rekaman dengan key 95 dimasukan ke dalam leaf page dan kondisi leaf page dalam keadaan penuh. Key 85 menjadi middle key dan leaf node dibagi menjadi dua bagian dan middle key diletakkan pada indeks. Key 85 dimasukkan ke dalam indeks dan kondisi indeks dalam keadaan penuh. Key 60 pada indeks menjadi middle key indeks dan membagi indeks menjadi dua bagian dan menaikkan key 60 ke tingkat yang lebih tinggi dalam index page.
Gambar 2.4 Key 95 dimasukkan ke dalam leaf page dan index page yang penuh 2.2.1.2 Rotasi pada b+tree Anderson (1998) menjelaskan bahwa sebuah b+-tree dapat menjalankan proses rotasi untuk mengurangi jumlah pembagian page dan mengurangi kedalaman level. Sebuah rotasi terjadi jika terdapat page yang penuh dan terdapat sibling yang tidak penuh. Rotasi tidak membagi leaf page tetapi memindahkan
16
rekaman ke sibling- nya dan mengatur indeks sesuai dengan susunan rekaman. Pemeriksaan dimulai dari sibling di sebelah kiri terlebih dahulu. Gambar 2.5 menjelaskan kondisi b+tree ketika key 70 belum dimasukkan kedalam leaf page. Leaf page yang akan dimasuki key 70 dalam keadaan penuh tetapi terdapat sibling yang tidak dalam keadaan penuh pada sibling kiri.
Gambar 2.5 Kondisi sebelum Key 70 dimasukkan ke dalam leaf page Rekaman digeser dengan key terendah ke sibling- nya dan memodifikasi index page (Anderson, 1998). Gambar 2.6 menunjukan kondisi b+tree ketika key 70 telah dimasukkan ke dalam leaf page dan rotasi telah dijalankan tanpa membagi leaf page.
Gambar 2.6 Kondisi setelah terjadi rotasi 2.2.1.3 Penghapusan Rekaman pada Sebuah B+-tree Algoritma penghapusan rekaman dipengaruhi oleh keadaan jumlah key dan faktor pengisi dari leaf page dan index page (Anderson, 1998). Tabel 2.2
17
menunjukkan aksi yang harus dijalankan ketika terjadi penghapusan rekaman pada suatu b+-tree. Tabel 2.2 Algoritma Penghapusan Rekaman pada b+-tree Jumlah Key Jumlah Key Aksi Leaf Page Index Page Tidak di Tidak di bawah Rekaman dihapus dalam leaf page bawah faktor faktor pengisi kemudian key diurutkan untuk mengisi pengisi kekosongan. Key berikutnya akan digunakan untuk key indeks jika rekaman yang dihapus merupakan key pada indeks. Di bawah Tidak di bawah Leaf page dan sibling digabungkan faktor pengisi faktor pengisi kemudian mengubah index page. Di bawah Di bawah faktor 1. Leaf page dan sibling digabungkan. faktor pengisi pengisi 2. Mengubah index page. 3. Index page dan sibling digabungkan. Index page dan sibling digabungkan sampai mendapatkan faktor pengisi yang benar atau jika sudah sampai pada root page.
Gambar 2.7 Kondisi sebelum terjadi penghapusan Penghapusan sebuah rekaman dengan kondisi leaf page dan index page yang tidak di bawah faktor pengisi pada sebuah b+-tree dapat dilihat dalam Gambar 2.7 dan Gambar 2.8. Gambar 2.7 menunjukan kondisi awal b+-tree sebelum
18
dilakukan penghapusan rekaman. Faktor pengisi dihitung ketika key 70 dihapus dari leaf page. Kondisi leaf page setelah key 70 dihapus tidak di bawah faktor pengisi. Key didalam leaf page diurutkan. Gambar 2.8 menujukkan kondisi setelah key 70 di dalam b+-tree dihapus.
Gambar 2.8 Kondisi setelah key 70 dihapus Penghapusan sebuah rekaman dengan kondisi key pada leaf page dipakai sebagai indeks dapat dilihat dalam Gambar 2.8 dan Gambar 2.9. Gambar 2.8 menunjukan kondisi awal sebelum key 25 dihapus. Key di dalam leaf page diurutkan setelah key 25 dihapus dari leaf page. Index page dengan key 25 harus diganti dengan key yang baru. Key 28 menggantikan posisi key 25 pada index page. Gambar 2.25 menujukkan kondisi setelah key 25 di dalam b+-tree dihapus.
19
Gambar 2.9 Kondisi setelah key 25 dihapus Penghapusan sebuah rekaman dengan kondisi leaf page dan index page dibawah faktor pengisi dapat dilihat dalam Gambar 2.9 dan Gambar 2.10. Gambar 2.9 menunjukan kondisi awal sebelum rekaman dengan key 60 dihapus. Faktor pengisi lebih besar dari jumlah key dalam leaf page ketika key 60 dihapus. Sibling digabung dengan leaf page ketika faktor pengisi lebih besar. Kondisi setelah penggabungan sibling dengan leaf page menyebabkan pengurangan sebuah key pada index page . Jumlah key dalam index page lebih kecil daripada faktor pengisi menyebabkan index page harus digabung. Key dalam index page diubah sesuai dengan key pada leaf page. Gambar 2.10 menujukkan kondisi setelah key 60 di dalam b+-tree dihapus.
Gambar 2.10 Kondisi setelah key 60 dihapus
20
2.3 Sistem Basis Data Firebird Borland Software Corp. mengeluarkan Interbase 6.0 versi beta sebagai open source pada bulan Juli 2000. Source code Interbase dikeluarkan oleh Borland dibawah lisensi InterBase Public Licence(IPL) jenis lain dari lisensi Mozilla Public Licence (MPL). Sebuah sistem inti dari beberapa pengembang yang terpisah membentuk sebuah proyek open source dan memasangnya di SourceForge. Proyek open souce pengembangan dari Interbase 6.0 memilih logo Phoenix dan mengadopsi nama “Firebird” (Anonim, 2005c). Borland kembali mengembangkan produk komersial yang tertutup karena upaya open source pada Interbase 6.0 tidak secara murni terlaksana. Firebird menjadi versi open source Interbase setelah Borland menutup versi open sourcenya. Firebird menjadi sebuah produk yang berdiri sendiri dan hampir sesuai dengan Interbase (Anonim, 2005c). Penyesuaian terhadap Interbase tetap dilakukan tetapi tidak menjadi jaminan bahwa Firebird akan mendukung semua fitur Interbase versi 6.0 keatas. Jalan migrasi yang aman atau fasilitas pendukung masih terus dicari agar komunitas pengguna Firebird dan Interbase tidak saling tumpang tindih. Sistem basis data Firebird dikembangkan dengan sukses dan telah berjalan pada sejumlah besar platform (Anonim, 2005c). Firebird digunakan pada Windows, Linux , MacOS X (Darwin), FreeBSD, OpenBSD, HP-UX dan AIX. Anonim (2005c) menjelaskan bahwa sistem inti Firebird 1.5 terdapat beberapa fungsi signifikan yang ditambahkan di dalamnya dan sistem tersebut diluncurkan
21
pada bulan Oktober 2003. Proses pengembangan Firebird dapat dilihat oleh semua orang seperti proyek open source lainnya. Semua orang dapat memberikan pengaruh pada proses pengembangan dengan memberi masukan atau donasi meskipun beberapa bug ditemukan dan diperbaiki oleh tim pengembang. Tim pengembang Firebird tidak hanya berkonsentrasi dalam memecahkan bug, tetapi juga menambah fitur-fitur baru dan meningkatkan kemampuan Firebird. Penambahan fitur dan peningkatan kemampuan disesuaikan pada kebutuhan karena para pengembang Firebird merupakan pengguna Firebird itu sendiri. 2.3.1 Arsitektur Firebird Chan dan Yaskhir (2002) menjelaskan bahwa Firebird/InterBase dapat dibagi menjadi empat komponen subsistem dan pengaturannya digambarkan seperti sebuah pipa. Susunan komponen-komponen subsistem
arsitektur utama
Firebird/Interbase dapat dilihat dalam Gambar 2.11. Komponen subsistem yang menyusun arsitektur utama meliputi: 1. Remote Connection System. Subsistem yang menghubungkan klien dengan server. 2. SQL Translator. Subsistem yang mengubah SQL (structured query language) menjadi BLR (binary language representation). 3. Relational Database Engine. Subsistem yang melakukan pengambilan data secara aktual. 4. Lock Manager. Subsistem yang berfungsi sebagai alat kontrol konkurensi.
22
Gambar 2.11 Arsitektur komponen utama (Chan dan Yaskhir, 2002) 2.3.1.1 Remote Connection System (REMOTE): Subsistem REMOTE memungkinkan klien-klien untuk berkomunikasi dengan server melalui jaringan atau lokal. Komunikasi dari klien dengan server melewati berbagai protokol-protokol jaringan. TCP/IP, MS LanManager, dan SPX merupakan protokol-protokol jaringan yang menghubungkan klien dengan server. Subsistem ini terdiri dari dua buah bagian yaitu sisi klien dan sisi server. Sisi klien dan sisi server tersusun dari beberapa kode generik dan kode protokol spesifik untuk berkomunikasi. Gambar 2.12 menjelaskan susunan dari modul REMOTE. Klien mengirim permintaan kepada server melalui sebuah layer komunikasi generik. Layer komunikasi generik berkomunikasi melalui sebuah layer protokol spesifik. Layer protokol spesifik berkomunikasi melalui jaringan yang ditangani oleh sistem operasi. Model jaringan klien-server Firebird/Interbase hampir mirip dengan sebuah versi dua layer dari model jaringan OSI Layer. Firebird/Interbase memungkinkan klien dapat berkomunikasi secara lokal melalui modul emulasi koneksi jaringan menggunakan memori terbagi (shared memory).
23
Gambar 2.12 Modul remote connection system 2.3.1.2 SQL Translator (DSQL) Subsistem DSQL menerjemahkan permintaan dari SQL ke dalam BLR. BLR merupakan bahasa asli dari basis data. Arsitektur DSQL mirip dengan kompiler sederhana yang terdiri dari sebuah lexer, parser, tabel simbol, dan pembangkit kode. Susunan bagian-bagian DSQL dapat dilihat dalam Gambar 2.13.
Gambar 2.13 Modul SQL translator Lexer, parser, dan pembangkit kode tersusun secara pipeline seperti pada setiap kompiler. Lexer membagi masukan menjadi token-token. Parser menentukan arti dari masukan. Pembangkit kode menghasilkan kode BLR yang ekuivalen dengan kode SQL yang dimasukkan. 2.3.1.3 Relational Database Engine (JRD) JRD (Jim's Relational Database) merupakan subsistem yang melakukan pengambilan data secara aktual. Subsistem JRD mengeksekusi permintaan dan
24
mengembalikan hasil eksekusi tersebut. JRD menangani akses ke dalam ruang penyimpan melalui sebuah subsistem virtual IO. JRD melakukan verifikasi keamanan dan memastikan bahwa transaksi data ditangani secara otomatis. JRD mempunyai beberapa subsistem pendukung yang masing- masing berfungsi untuk menangani dan memproses permintaan. Susunan dari subsistem pendukung JRD dapat dilihat dalam Gambar 2.14. Chan dan Yaskhir (2002) menjelaskan bahwa di dalam JRD sebuah permintaan ditangani oleh sebuah kompiler. Kompiler menterjemahkan BLR menjadi sebuah representasi internal dari permintaan yang masuk. Representasi internal memanggil subsistem metadata (MET). MET menghasilkan metadata sesuai dengan permintaan dan memastikan tabel yang diminta terdapat dalam basis data.
Gambar 2.14 Arsitektur dari relational database engine (JRD)
25
Permintaan diproses oleh subsistem Exec dan B-tree ketika permintaan tersebut terkait dengan proses indeks. Hak akses pengguna diperiksa oleh subsistem-subsistem exec dan security. Eksekusi atom dari beberapa permintaan diperiksa oleh subsistem exec dan transaction. Subsistem exec dan sort digunakan ketika terdapat permintaan untuk mengurutkan. Konkurensi data ditangani oleh subsistem exec dan lock handler. Subsistem virtual IO merupakan sebuah sistem layer dengan tiga buah layer di dalamnya. Layer teratas memuat metode abstrak untuk mengakses data pada ruang penyimpan. Layer kedua merupakan cache manager yang menangani proses cache. Proses cache bertujuan mempercepat akses data. Layer kedua merupakan layer terakhir yang menggunakan konsep struktur data basis data. Layer terakhir merupakan layer physical IO. Layer terakhir berhubungan dengan sistem operasi pada mesin yang digunakan dan membuat system call untuk pengaksesan data ke ruang penyimpan. 2.3.1.4 Lock Manager (LOCK) Subsistem LOCK menangani proses sinkronisasi transaksi. Fungsi utama subsistem LOCK adalah alat kontrol konkurensi bila terdapat banyak pengguna yang mengakses satu berkas basis data yang sama secara bersamaan. Situasi konkurensi biasa terjadi dalam operasi normal setiap DBMS. LOCK terdiri dari dua komponen utama yaitu submodul lock handler pada JRD dan lock table diluar JRD. Susunan komponen utama LOCK dapat dilihat pada Gambar 2.15.
26
Gambar 2.15 Modul lock manager Permintaan yang memerlukan mekanisme penguncian dapat dibagi menjadi dua kategori utama yaitu permintaan modifikasi metadata dan permintaan data biasa. Mekanisme penguncian terjadi ketika permintaan menggunakan lock handler. Sebuah mekanisme penguncian pada data yang diinginkan akan masukan pada permintaan ketika terdapat permintaan
modifikasi metadata. Mekanisme
penguncian dilepaskan kembali setelah proses modifikasi dilakukan. Sebuah lock handler dapat menunggu beberapa saat jika masih terdapat mekanisme penguncian yang belum dilepaskan. Lock handler melakukan eksekusi normal setelah mekanisme penguncian yang lain telah dilepaskan pada data yang diinginkan. LOCK menunggu permintaan dari beberapa lock handler dan melakukan modifikasi ke lock table untuk mendaftarkan mekanisme penguncian yang ada. 2.3.1.5 Operasi Firebird/Interbase Chan
dan
Firebird/Interbase.
Yaskhir
(2002)
Firebird/Interbase
mengeksekusi setiap permintaan.
menjelaskan terdapat
proses
operasi
dalam
berbagai
langkah
untuk
27
Proses penambahan sebuah tabel baru sesuai dengan perintah SQL pada Interbase membutuhkan langkah- langkah seperti berikut: 1. Permintaan berawal dari aplikasi pengguna di sisi klien. 2. Permintaan dikemas dan dikirim melalui jaringan yang dipakai ke sisi server. 3. Memanggil DSQL untuk mengubah permintaan SQL menjadi BLR. 4. Memanggil JRD dan CMP untuk kompilasi permintaan BLR. 5. Memanggil Exec untuk mengeksekusi permintaan dan memanggil MET. 6. Eksekusi dilakukan di MET ketika terdapat permintaan untuk memodifikasi metadata dalam basis data. 7. Memanggil lock handler untuk memperoleh sebuah mekanisme penguncian pada metadata yang digunakan. 8. Lock handler memanggil LOCK untuk menambah mekanisme penguncian yang diinginkan ke dalam lock table. 9. MET memanggil virtual IO library untuk melakukan perubahan pada ruang penyimpan. 10. Rutin penanganan ruang penyimpan dijalankan tergantung dari sistem berkas yang digunakan. 11. MET memanggil lock handler untuk melepaskan mekanisme penguncian dan melepasnya dari lock table ketika eksekusi selesai. 12. JRD memanggil modul REMOTE untuk mengembalikan pesan sukses atau gagal kepada pengguna.
28
13. Modul REMOTE meneruskan pesan dari JRD melalui jaringan dan sampai pada aplikasi pengguna. Proses pencarian baris pada suatu tabel menggunakan perintah SQL dalam Interbase membutuhkan langkah- langkah sebagai berikut: 1. Permintaan dibuat pada aplikasi pengguna di sisi klien. 2. Modul REMOTE mengirim permintaan ke sisi server dan memanggil DSQL. 3. DSQL mengubah permintaan SQL menjadi BLR 4. Memanggil JRD dan CMP mengkompilasi permintaan. 5. EXEC mulai mengeksekusi permintaan. 6. Memanggil virtual IO untuk mendapatkan tabel yang sesuai. 7. Memeriksa cache untuk data yang diminta. 8. Rutin pencarian dilakukan didalam modul b-tree untuk mencari baris menggunakan indeks yang sesuai. 9. Memanggil modul REMOTE untuk mengembalikan hasil pencarian kepada aplikasi pengguna. 2.3.1.6 Pengembangan Firebird/InterBase Chan dan Yaskhir (2002) menjelaskan bahwa sebuah sistem yang dapat memberikan pengubahan di masa depan dan beberapa ekspansi sistem merupakan sebuah arsitektur sistem yang bagus. Interbase berkembang sejak tahun 1985 dibawah nama yang berbeda. Interbase berkembang dengan berbagai perubahan yang besar dan beberapa penyempurnaan sampai sekarang. Konsep arsitektur utama sistem Interbase tidak berubah walau mengalami beberapa perubahan dan
29
penyempurnaan. Perubahan pada Interbase terjadi berdasarkan kemajuan teknologi. Perubahan pada modul REMOTE Interbase terjadi seiring dengan banyak standar LAN baru yang bermunculan. Modul REMOTE dimodifikasi agar Interbase dapat bekerja dengan standar yang ada (Chan dan Yaskhir, 2002). Perubahan modul REMOTE tidak mempengaruhi konsep arsitektur Interbase karena semua yang berhubungan dengan rutin komunikasi jaringan tertampung dalam satu modul. 2.3.2 Struktur Berkas Page Firebird Sebuah basis data Firebird secara normal tersimpan di dalam satu berkas. Sebuah basis data Firebird merupakan sebuah urutan dari beberapa page yang mempunyai panjang tertentu. Setiap page di dalam basis data Firebird mempunyai fungsi yang berbeda. Susunan page basis data Firebird diawali sebuah header page, diikuti dengan Page Inventory Page (PIP), informasi Write Ahead Log (WAL), pointer page, index root page (IRT), data page, dan index page (Harrison, 2005). Harrison (2005) menjelaskan bahwa jumlah page dapat bertambah jumlah seiring dengan banyak data yang tersimpan dalam basis data Firebird. Basis data yang menggunakan multi-file mempunyai susunan urutan yang terpecah menjadi beberapa berkas dengan sebuah header page pada masing- masing berkas. Susunan page dalam basis data Firebird dapat dilihat pada Gambar 2.16. Tidak
30
terdapat perbedaan struktur page antara multi-file dan single file dalam basis data Firebird.
Gambar 2.16 Berkas single- file dan multi- file basis data Firebird (Harrison, 2005) Harrison (2005) menjelaskan bahwa setiap page mempunyai sebuah header yang berfungsi untuk mengenali tipe page dan menyediakan informasi yang berguna untuk semua page. Informasi tambahan dimiliki oleh sebagian besar header antar tipe page. Byte pertama header standar merepresentasikan tipe dari tiap-tiap page. Byte kedua berisi flag yang spesifik dan digunakan pada binary large object (BLOB) page dan index page. Flag pada page lain terletak pada area khusus. Dua byte selanjutnya merupakan checksum yang berisi angka 12345. Empat byte selanjutnya merupakan informasi penulisan page. Delapan byte selanjutnya merupakan informasi urutan dan ofset page dalam log. Sebuah header standar digambarkan dalam Gambar 2.17.
31
Gambar 2.17 Header standar setiap page Page-page dalam suatu sistem basis data Firebird meliputi (Harrison, 2005): 1. Header Page. Page yang berisi tentang informasi dari sebuah basis data. 2. Page Inventory Page. Page yang berisi daftar page yang ada dalam basis data 3. Transaction Inventory Page. Page yang berisi tentang informasi transaksi. 4. Pointer Page. Page yang berisi tentang key penunjuk data fisik. 5. Data Page. Page yang berisi data fisik. 6. Index Root Page. Page yang berisi daftar root indeks dari setiap tabel. 7. B-tree Page. Page yang berisi susunan indeks. 8. Blob Page. Page yang berisi data BLOB. 9. Generator Page. Page yang berisi daftar generator. 2.3.2.1 Header Page Tipe page 1 merupakan sebuah header page. Setiap berkas basis data Firebird mempunyai satu header page yang terletak pada awal berkas. Header page mempunyai ukuran sebesar 1024 byte. Header page dibuka sesuai format on disk structure (ODS) basis data Firebird. Gambar 2.18 menunjukkan format ODS pada basis data Firebird. Header page memberikan informasi tentang ukuran tiap page,
32
mengetahui status read/only suatu berkas, mengetahui status force write dan berbagai informasi penting yang dibutuhkan. Berkas berkas multi-file memiliki header page yang berisi tentang panjang berkas, banyaknya page dan nama berkas selanjutnya.
Gambar 2.18 Informasi header page dari sebuah berkas basis data Firebird 2.3.2.2 Page Inventory Page (PIP) Tipe page 2 merupakan sebuah page inventory page. PIP memetakan semua page isi dan page kosong yang berada dalam basis data. Bagian kepala dari sebuah PIP terdapat ofset yang menunjukkan page pertama yang tersedia. Bagian tubuh PIP berisi sebuah larik yang mencerminkan bit keadaan page dalam basis data. Page tidak dipakai atau kosong jika keadaan bernilai 1. Page telah digunakan jika keadaan bernilai 0. Struktur PIP dapat dilihat pada Gambar 2.19. PIP dimulai dari page 1 dan alamat terakhir merupakan PIP selanjutnya.
33
Gambar 2.19 Page inventory page (PIP) 2.3.2.3 Transaction Inventory Page (TIP) Tipe page 3 merupakan sebuah transaction inventory page. Bagian kepala TIP terdapat alamat TIP selanjutnya. Tubuh TIP terdiri dari sebuah larik dari sepasang bit yang mencerminkan keadaan dari transaksi. Transaksi aktif atau tidak sedang dijalankan jika kedua bit bernilai 0. Transaksi dilakukan (commit) jika kedua bit bernilai 1. Transaksi dibatalkan (rollback) jika bit pertama bernilai 1 dan bit kedua bernilai 0. Transaksi dalam keadaan limbo jika bit pertama bernilai 0 dan bit kedua bernilai 1. Keadaan limbo merupakan keadaan yang terjadi ketika terdapat salah satu transaksi sempurna pada dua fase transaksi. Struktur TIP dapat dilihat pada Gambar 2.20.
Gambar 2.20 Transaction inventory page (TIP)
34
2.3.2.4 Pointer Page Tipe page 4 merupakan sebuah pointer page. Setiap pointer page dimiliki oleh sebuah tabel tertentu dan mempunyai sebuah urutan tersendiri dalam tabel. Bagian kepala mempunyai informasi tambahan yang berisi urutan pointer page untuk tabel, nomor pointer page selanjutnya, informasi tempat kosong pada page, jumlah tempat yang telah digunakan, identitas relasi dari tabel yang memiliki, ofset tempat pertama page yang menunjukkan sebuah page tidak penuh dan ofset tempat terakhir page yang menunjukkan sebuah data page tidak penuh. Tubuh pointer page berisi sebuah larik integer 32-bit yang berisi nomor data page. Sebuah larik pada dasar pointer page menunjukkan tingkat pengisian page. Gambar 2.21 menunjukan sebuah pointer page.
Gambar 2.21 Pointer page sebagai penunjuk data page 2.3.2.5 Data Page Tipe page 5 merupakan sebuah data page. Setiap data page dimiliki oleh sebuah tabel tertentu. Bagian kepala mempunyai informasi tambahan yang berisi tentang posisi page dalam daftar data page, identitas relasi dari tabel yang
35
memiliki dan jumlah isi page. Bagian tubuh diawali dengan sebuah larik word 16bit yang berfungsi sebagai penunjuk data. Sepasang byte pertama merupakan ofset sebuah rekaman atau pecahan rekaman pada page. Sepasang byte kedua merupakan panjang data. Gambar 2.22 menunjukkan struktur dari data page. Penunjuk data akan berkembang dari atas ke bawah dan rekaman data berkembang dari bawah ke atas ketika data dimasukkan ke dalam page.
Gambar 2.22 Data page sebagai media penyimpan data 2.3.2.6 Index Root Page (IRT) Tipe page 6 merupakan sebuah index root page. Setiap tabel mempunyai sebuah IRT yang menyimpan indeks- indeks root pada tabel. Bagian kepala terdapat informasi tambahan yang berisi tentang identitas relasi dari tabel yang mempunyai dan jumlah indeks dalam tabel. Bagian tubuh berisi sebuah larik yang terdiri dari beberapa index descriptor yang terletak dari atas ke bawah dan larik yang terdiri dari field descriptor yang terletak dari bawah ke atas. Setiap index descriptor memuat nilai indeks jika telah dibuat atau transaksi jika indeks sedang dibuat. Nomor page indeks root dari indeks tersebut terletak pada 32 bit
36
selanjutnya. Ofset dari field descriptor yang berada di bawah page terletak pada 32 bit selanjutnya. Byte selanjutnya merupakan jumlah field dan flag dalam indeks. Larik dari field descriptor berisi identitas field dan tipe field. Gambar 2.23 menunjukkan struktur dari IRT.
Gambar 2.23 Index root page (IRT) sebagai penyimpan indeks root 2.3.2.7 B-tree Page Tipe page 7 merupakan sebuah indeks atau b-tree page. Semua indeks pada Firebird merupakan sebuah jenis lain dari b-tree. Urutan indeks dimulai dari sebuah page paling atas yang biasa disebut root. Istilah root pada b-tree page berbeda dengan IRT. Bagian kepala tambahan pada b-tree page terdapat nomor page di atas nilai terbesar, nomor page di bawah nilai terendah, jumlah kompresi prefix, identitas relasi dari tabel yang menggunakan, jumlah ruang yang telah terpakai, nomor identifikasi dari indeks tersebut dan level dari page tersebut. Bagian tubuh dari b-tree page merupakan isian dari indeks. Gambar 2.24 menunjukkan struktur dari b-tree page.
37
Gambar 2.24 B-tree page atau index page 2.3.2.8 Blob Page Tipe page 8 merupakan BLOB page. BLOB kecil dimasukkan kedalam data page. BLOB dimasukan ke dalam sebuah urutan BLOB page jika ukuran sebuah BLOB lebih besar daripada ukuran sebuah page. Bagian kepala merupakan nomor page dari urutan yang terdepan, posisi urutan dari page tersebut, jumlah data yang tersimpan dalam page, dan sebuah pad word untuk memulai penulisan data. Bagian tubuh dari BLOB page menyimpan data BLOB. Gambar 2.25 menunjukkan struktur dari BLOB page
Gambar 2.25 Binary large object (BLOB) page
38
2.3.2.9 Generator Page Tipe page 9 merupakan sebuah generator page. Informasi tambahan tidak terdapat dalam bagian kepala generator page. Terdapat ruang yang tidak digunakan dalam bagian kepala generator page. Generator page yang asli merupakan sebuah subset dari pointer page dan tidak memiliki tipe sendiri. Pemisahan generator menjadi page sendiri dilakukan ketika generator dinaikkan dari 32 bit menjadi 64 bit. Sebuah generator page terdiri dari sebuah larik yang berisi integer 64 bit yang setiap elemen dari larik tersebut berisi nilai dari sebuah generator. Gambar 2.26 menunjukkan struktur dari generator page
Gambar 2.26 Generator page 2.3.3 Indeks dalam Firebird Harrison (2005) menjelaskan bahwa tipe indeks dalam basis data Firebird merupakan jenis lain dari b-tree. Indeks dapat bersifat unik atau memungkinkan duplikasi data, juga dapat terdiri dari satu field atau banyak field dan dapat diakses secara ascending atau descending. Firebird menyimpan rekaman pada data page menggunakan ruang yang cukup dan page yang dapat diakses dengan mudah.
39
Indeks disimpan dalam index page yang berisi penunjuk rekaman pada bagian leaf node. Banyak sistem basis data membaca sebuah index node kemudian mengambil data secara langsung. Teknik pengambilan secara langsung dapat memicu terjadinya lompatan di antara index page dan data. Lompatan di antara index page dan data dapat diatasi dengan kontrol peletakan data yang baik. Teknik pengambilan secara langsung mengakibatkan terjadinya proses pembacaan berulang pada data page untuk indeks yang tidak terkluster. Firebird memungut penunjuk rekaman untuk mengkualifikasi rekaman dari indeks. Firebird membuat sebuah bitmap dari penunjuk rekaman dan membaca rekaman pada ruang penyimpan fisik (Harrison, 2005). Pengoptimasi basis data harus memilih salah satu indeks per tabel sebagai sebuah jalur untuk mendapatkan data karena terjadi ikatan akses indeks dan akses rekaman secara kua t. Harrison (2005) menjelaskan bahwa Firebird dapat menggunakan beberapa indeks pada sebuah tabel dengan cara meng-AND-kan dan meng-OR-kan bitmap yang telah dibuat sebelum mengakses suatu data. Basis data non-versioning memecahkan pengambila data dengan cara membaca indeks tanpa membaca rekaman data secara aktual. Indeks yang terdapat dalam Firebird berisi catatan yang tak terlihat ke transaksi yang lain. Catatan yang berada dalam indeks tidak relevan dengan beberapa transaksi aktif. Membaca rekaman merupakan satu-satunya jalan untuk mengetahui sebuah catatan indeks yang merepresentasikan data tampak ke sebuah bagian transaksi. Firebird
40
termasuk basis data versioning (Harrison, 2005). Tanda dari transaksi diberikan ketika Firebird menyimpan sebuah rekaman baru. Rekaman versi baru dibuat dan tanda dari transaksi diberikan ketika terjadi modifikasi pada sebuah rekaman. Rekaman versi baru menunjuk versi rekaman yang lama. Semua transaksi akan menunjuk ke versi rekaman yang lama sebelum transaksi yang membuat rekaman versi baru dilakukan (commit). Jumlah panjang dari sebuah key indeks harus kurang dari 252 byte pada Firebird versi 1.x. melarang indeks dengan banyak key dan indeks dengan isi nonbinary. Firebird 2 mampu menampung key sampai seperempat dari ukuran page atau sebesar 4 Kb. Firebird mengubah semua key indeks ke dalam sebuah format yang dapat di bandingkan secara byte per byte (Harrison, 2005). Semua field numerik dan tanggal disimpan sebagai key double precision integer, kecuali field integer 64 bit. Angka double precision dimanipulasi untuk membandingkan secara byte per byte. Firebird mengubah nilai masukan ke format yang sama dengan key yang disimpan ketika menjalankan sebuah pencarian indeks. Indeks pada string, numerik dan tanggal mempunyai kecepatan yang sama. Semua key dibandingkan secara bit per bit tanpa memperhatikan aturan dari tipe data yang asli. Key indeks Firebird disimpan dengan kompresi prefik dan sufik (Harrison, 2005). Kompresi sufik menghilangkan ruang kosong di belakang field string dan menghilangkan angka nol dibelakang field numerik. Angka nol di belakang field numerik tidak terlalu signifikan karena sebagian besar nilai numerik tersimpan
41
dalam bentuk double precision. Kompresi sufik dilakukan pada setiap key field pada sebuah gabungan key dengan memperhatikan batas dari key field. Kode kompresi indeks melandaskan field pada sebuah empat byte penanda dan memasukan penanda sebagai penujuk posisi field dalam key ketika ruang kosong dan angka nol dalam field telah dihilangkan. Kompresi yang terjadi dapat digambarkan seperti indeks dengan tiga buah field dengan set “ abc “, “def “, “ghi “ dan “abcdefghi “, “ “, “ “. Firebird menghapus ruang kosong di belakang field agar kedua set seimbang dan mengubah set menjadi “abc 1def 2ghi 3” dan “abcd1efgh1i 1 2 3”. Firebird versi 1.x mengkompresi prefik dari key indeks seperti pada waktu menyimpan ke dalam page. Firebird menyimpan key pertama pada sebuah page tanpa kompresi prefik (Harrison, 2005). Key berikutnya disimpan dengan kompresi prefik yang mengganti awalan byte yang sama dengan awalan key sebelumnya dengan sebuah byte yang menandakan jumlah byte yang dipotong. Set field yang telah terkompresi prefik dapat digambarkan seperti set “0abc 1def 2ghi 3” dan “3d1efgh1i 1 2 3”. Sebuah masukan indeks yang sama dengan masukan sebelumnya tersimpan sebagai satu byte yang berisi panjang masukan tersebut. Firebird 2 melakukan kompresi prefik menggunakan representasi yang padat. Kombinasi dari teknik kompresi menghilangkan beberapa aturan tentang pembangunan key. Sebuah field varchar yang panjang harus ditempatkan pada daerah logikal pada sebuah gabungan key dan kompresi tidak dipaksakan sampai akhir karena kompresi sufik terjadi pada semua segmen sebuah key. Sebuah
42
gabungan key yang memuat banyak duplikasi harus ditempatkan pada awal key karena dapat mengambil keuntungan dari kompresi prefik (Harrison, 2005). 2.4 Diagram Alir (Flowchart) Diagram alir merupakan diagram yang menunjukkan alir di dalam program atau prosedur sistem secara logika. Diagram alir digunakan terutama untuk alat bantu komunikasi dan untuk dokumentasi. Simbol-simbol pada diagram alir serta fungsinya dapat dilihat pada Tabel 2.3.
No 1
Tabel 2.3 Simbol dan fungsi diagram alir Simbol Fungsi Simbol input/output
2
Simbol proses digunakan untuk mewakili suatu proses
3
Simbol garis alir digunakan untuk menunjukkan arus dari proses
4
Simbol penghubung digunakan untuk menunjukkan sambungan dari bagan alir yang terputus di halaman selanjutnya. Simbol keputusan digunakan untuk suatu penyeleksian kondisi di dalam program
5
6
7 8
Simbol proses terdefinisi digunakan untuk menunjukkan suatu operasi yang rinciannya ditunjukkan di tempat lain. Simbol penyisipan digunakan untuk memberi nilai awal suatu besaran. Simbol titik terminal digunakan untuk menunjukkan awal dan akhir dari suatu proses.
43
No 9
Simbol
10
Fungsi Menunjukkan dokumen input dan output baik untuk proses manual, mekanik, atau komputer Menunjukkan input/output yang menggunakan kartu plong
11
Menunjukkan proses pengurutan data di luar proses komputer.
12
Menunjukkan input yang menggunakan on- line keyboard / input manual.
13
Menunjukkan output yang ditampilkan di monitor.
14
Menunjukkan data tersimpan (stored data).
15
Menunjukkan input/output menggunakan pita magnetik.
16
Menunjukkan pekerjaan manua l
17
Menunjukkan operasi yang dilakukan di luar proses operasi komputer.
18
Menunjukkan input/output menggunakan kertas berlubang.
2.5 Diagram Arus Data Diagram arus data merupakan alat untuk pengembangan sistem yang terstruktur. DAD digunakan untuk menggambarkan secara logika tanpa mempertimbangkan hubungan fisik tentang aliran data atau penyimpanan data. DAD merupakan bagan yang digunakan untuk mewakili arus data suatu sistem. DAD menggambarkan masukan, proses dan keluaran sistem yang berhubungan
44
dengan masukan, proses dan keluaran dari model sistem umum. Simbol-simbol pada DAD serta fungsinya dapat dilihat pada Tabel 2.4.
No 1
3 3
4
Tabel 2.4 Simbol dan fungsi DAD Simbol Fungsi Merepresentasikan objek sistem yang dapat mengirim data atau menerima data dari sistem Menunjukkan perpindahan data dari satu titik ke titik yang lain Menunjukkan adanya proses transformasi Menunjukkan tempat penyimpanan data
3BAB III RANCANGAN SISTEM Rancangan sistem menjelaskan tentang rancangan struktur data, rancangan diagram alir, rancangan diagram arus data, dan rancangan antarmuka. Rancangan struktur data menggunakan tipe pointer. Racangan diagram alir menggambarkan proses yang terjadi di dalam program simulasi. Rancangan antarmuka menggambarkan antarmuka yang dipakai program simulasi untuk memudahkan pengguna program menjalankan fungsi- fungsi yang telah disediakan program simulasi dan mendapatkan informasi yang diperlukan. Struktur data program simulasi menggunakan record yang dikemas dalam bentuk pointer sehingga dapat menunjuk satu sama lain. Sebuah node digambarkan dalam sebuah record yang mempunyai informasi yang unik. Diagram alir menjelaskan proses utama program simulasi, proses penambahan data, proses penghapusan data, dan proses pencarian data. Diagram alir utama menggambarkan alur proses umum program simulasi dan proses yang dilakukan oleh antarmuka. Diagram alir proses penambahan data menggambarkan proses yang terjadi di dalam program simulasi ketika sebuah data dimasukkan ke dalam indeks. Diagram alir proses penambahan terdiri dari beberapa diagram alir yang menjelaskan subproses dari proses penambahan. Subproses yang dijelaskan meliputi proses pembuatan page baru, proses pencarian leaf page yang sesuai untuk penambahan, proses pemasukan data dalam leaf page, proses pembagian leaf page, proses pemasukan data dalam index page, dan proses pembagian index page. Diagram alir proses penghapusan data menggambarkan proses yang terjadi
45
46
di dalam program sumulasi ketika sebuah data dalam indeks dihapus. Diagram alir proses penghapusan terdiri dari beberapa diagram alir yang menjelaskan subproses dari proses penghapusan. Subproses yang dijelaskan meliputi proses pencarian leaf page yang sesuai untuk penghapusan, proses penghapusan data, dan proses penggabungan page.
Diagram
alir
proses
pencarian
data
menggambarkan proses yang terjadi di dalam program simulasi ketika mencari data dalam indeks. Antarmuka dalam program simulasi terdiri dari beberapa form. Form utama merupakan antarmuka utama dari program simulasi yang terdiri dari beberapa pilihan
fungsi.
Form
setting orde b-tree
merupakan
antarmuka
yang
memungkinkan pengguna untuk menentukan orde indeks yang digunakan dalam program simulasi. Form input data awal merupakan antaramuka yang berfungsi untuk menentukan kondisi awal sebuah indeks. Form tambah data merupakan antarmuka yang berfungsi untuk melakukan proses penambahan data pada indeks. Form hapus data merupakan antarmuka yang berfungsi untuk melakukan proses penghapusan data pada indeks. Form pencarian data merupakan antarmuka yang berfungsi untuk melakukan proses pencarian pada indeks. Form statistik proses merupakan antarmuka yang menyediakan informasi proses yang telah dijalankan. Form log proses merupakan antarmuka yang menyediakan daftar dari keseluruhan proses yang telah dilakukan. Form preview visual merupakan antarmuka yang menggambarkan bentuk indeks secara visual. Form ODS merupakan antarmuka yang menggambarkan bentuk indeks seperti struktur yang ada pada media penyimpan.
47
3.1 Rancangan Struktur Data Struktur data yang digunakan dalam program simulasi menggunakan tipe pointer. Page dalam basis data firebird digambarkan oleh sebuah node dalam pointer yang akan digunakan. Pointer yang digunakan sebagai sebuah node berisi sebuah paket data yang terdiri dari identitas paket, jumlah data yang tersimpan, larik data, larik yang berisi pointer ke node yang lain di bawahnya, pointer yang menujuk ke sibling-nya dan pembeda leaf page dengan index page. Paket data yang menjadi sebuah node dalam program simulasi dapat dilihat pada Gambar 3.1.
Gambar 3.1 Node dalam sebuah b-tree Setiap node dirangkai sehingga menyerupai susunan indeks dalam basis data Firebird. Program simulasi hanya menggunakan susunan index page dan leaf page untuk membentuk susunan indeks. Data page tidak digunakan dalam program simulasi. Gambar 3.2 menjelaskan bentuk dari indeks b+-tree yang akan diimplementasikan dalam program simulasi. Gambar 3.3 menjelaskan page dalam b+-tree Firebird yang akan diimplementasikan dala m bentuk node.
48
Gambar 3.2 Susunan indeks dalam basis data Firebird
Gambar 3.3 Susunan page dalam basis data Firebird 3.2 Rancangan Diagram Alir Rancangan diagram alir merupakan rancangan alur proses yang ada dalam program simulasi. Diagram alir menjelaskan proses utama, proses penambahan data, proses penghapusan data dan proses pencarian data pada struktur b+-tree dalam program simulasi. 3.2.1 Diagram Alir Utama Algoritma secara umum semua proses yang ada dalam program simulasi penggunaan b-tree dalam Firebird digambarkan dalam diagram alir utama ini. Proses diawali dengan penentuan orde b-tree yang akan digunakan. Inisialisasi dilakukan setelah penentuan orde b-tree. Proses manipulasi dan pencarian data dilanjutkan dengan penyajian hasil dari proses sebelumnya. Algoritma proses utama ini dapat dilihat pada Gambar 3.4.
49
Gambar 3.4 Diagram alir proses program simulasi b-tree dalam Firebird 3.2.2 Diagram Alir Proses Penambahan Data Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses penambahan data dalam b+-tree. Gambaran umum algoritma pada proses penambahan data ini dapat dilihat pada Gambar 3.5. Proses penambahan data ini merupakan proses penambahan rekaman pada suatu b+-tree dan meletakkan rekaman tersebut pada posisi yang tepat sehingga susunan dan struktur dari b+tree masih terjaga.
50
Gambar 3.5 Diagram alir algoritma penambahan data dalam b+-tree 3.2.2.1 Diagram Alir Proses Pembuatan Page Baru Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses pembuatan sebuah page baru dalam b+-tree. Gambaran umum algoritma pada proses pembuatan page baru dapat dilihat pada Gambar 3.6. Proses pembuatan
51
page baru dimulai dari pemesanan ruang memori, mengisi identitas pembuatan page dan menentukan panjang larik data dan panjang larik pointer. Panjang larik data pada sebuah page merupakan dua kali dari orde indeks b+-tree tersebut. Panjang larik pointer pada sebuah page merupakan dua kali orde ditambah sebuah pointer.
Gambar 3.6 Diagram alir pembuatan page baru 3.2.2.2 Diagram Alir Proses Pencarian Leaf Page Yang Sesuai Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses pencarian posisi page oleh probe pada sebuah b+-tree. Gambaran umum algoritma pada proses pencarian posisi page dapat dilihat pada Gambar 3.7. Proses pencarian page memungkinkan probe untuk berpindah dari page satu ke page yang lain. Pencarian tidak sesuai jika sudah terdapat data yang akan dimasukan pada salah satu page dalam susunan b+-tree. Pencarian akan sesuai jika terdapat ruang kosong pada salah satu page atau jika data yang dimasukkan
52
lebih kecil dari data yang ada. Pencarian dimulai dari index page dan dilanjutkan sampai pada leaf page. Pencarian akan berakhir jika data tidak sesuai atau telah ditemukan tempat yang sesuai untuk penambahan data.
Gambar 3.7 Diagram alir pencarian leaf page yang sesuai untuk pemasukan data 3.2.2.3 Diagram Alir Proses Pemasukan Data Dalam Leaf Page Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses pemasukan data dalam sebuah leaf page. Gambaran umum algoritma pada proses pemasukan data dalam sebuah leaf page dapat dilihat pada Gambar 3.8. Data dimasukan secara langsung dan terurut pada page jika leaf page yang digunakan tidak penuh. Rotasi dilakukan untuk menjaga faktor pengisi setiap page dalam susunan b+-tree agar level b+-tree tidak terlalu dalam. Rotasi dilakukan ketika sebuah leaf page yang akan dimasuk i data sudah penuh dan terdapat sibling yang
53
masih terdapat ruang untuk penambahan data. Sibling kiri diperiksa terlebih dahulu sebelum sibling kanan.
Gambar 3.8 Diagram alir pemasukan data dalam leaf page Pemindahan data ke-0 dari page yang penuh ke data terakhir sibling kiri dilakukan ketika terjadi rotasi sibling kiri. Pemindahan data terakhir dari page yang penuh ke data ke-0 dari sibling kanan dilakukan ketika terjadi rotasi sibling kanan. Rotasi sibling kiri mengakibatakan index page dari page yang penuh harus diubah. Rotasi sibling kanan mengakibatkan index page dari sibling kanan harus diubah. Gambar 3.9 dan Gambar 3.10 menunjukan algoritma proses rotasi.
54
Gambar 3.9 Diagram alir proses rotasi dengan sibling kiri
Gambar 3.10 Diagram alir proses rotasi dengan sibling kanan
55
3.2.2.4 Diagram Alir Proses Pembagian Leaf Page Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses pembagian sebuah leaf page. Gambaran umum algoritma pada proses pembagian sebuah leaf page dapat dilihat pada Gambar 3.11. Pembagian leaf page terjadi apabila ada penambahan data pada sebuah leaf page penuh dan tidak terdapat sibling yang tidak penuh. Data yang dimasukan secara terurut pada page mengakibatkan overflow. Leaf page dibagi menjadi dua bagian. Leaf page diisi data yang lebih kecil dari data tengah dan leaf page baru diisi data yang lebih besar atau sama dengan data tengah. Perbaikan taut sibling dilakukan setelah terjadi pembagian leaf page. Page baru menghasilkan key baru pada index page. Index page mengalami penambahan key setelah terjadi pembagian leaf page.
Gambar 3.11 Diagram alir proses pembagian leaf page 3.2.2.5 Diagram Alir Proses Pemasukan Data Dalam Index Page Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses pemasukan data dalam sebuah index page. Gambaran umum algoritma pada
56
proses pemasukan data dalam sebuah index page dapat dilihat pada Gambar 3.12. Data dimasukan secara langsung dan terurut pada page jika leaf page yang digunakan tidak penuh.
Gambar 3.12 Diagram alir pemasukan data dalam index page 3.2.2.6 Diagram Alir Proses Pembagian Index Page Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses pembagian sebuah index page. Gambaran umum algoritma pada proses pembagian sebuah index page dapat dilihat pada Gambar 3.13. Pembagian index page terjadi apabila ada penambahan data pada sebuah index page penuh. Data yang dimasukan secara terurut pada page mengakibatkan overflow. Index page dibagi menjadi dua bagian. Index page diisi data yang lebih kecil dari data tengah dan Index page baru diisi data yang lebih besar atau sama dengan data tengah. Page baru menghasilkan key baru. Index page pada level di atasnya mengalami penambahan key setelah terjadi pembagian index page. Pembagian index page
57
pada level berikutnya akan terus terjadi jika index page pada level berikutnya penuh.
Gambar 3.13 Diagram alir proses pembagian index page
58
3.2.3 Diagram Alir Proses Penghapusan Data Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses penghapusan data dari sebuah b+-tree. Gambaran umum algoritma pada proses penghapusan data ini dapat dilihat pada Gambar 3.14.
Gambar 3.14 Diagram alir algoritma penghapusan data dalam b+-tree
59
Proses penghapusan data ini merupakan proses penghapusan rekaman pada suatu b+-tree dan menjaga tingkat kepadatan b+-tree. 3.2.3.1 Diagram Alir Proses Pencarian Leaf Page Yang Sesuai Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses pencarian posisi page oleh probe pada sebuah b+-tree untuk melakukan proses penghapusan. Gambaran umum algoritma pada proses pencarian posisi page dapat dilihat pada Gambar 3.15. Proses pencarian page memungkinkan probe untuk berpindah dari page satu ke page yang lain. Pencarian tidak sesuai jika tidak terdapat data yang akan dihapus susunan b+-tree. Pencarian akan sesuai jika terdapat data yang akan dihapus ada dalam susunan b+-tree.
Gambar 3.15 Diagram alir pencarian leaf page yang sesuai untuk penghapus an data
60
3.2.3.2 Diagram Alir Proses Penghapusan Data Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses penghapusan data dari sebuah leaf page. Gambaran umum algoritma pada proses penghapusan data dari sebuah leaf page dapat dilihat pada Gambar 3.16.
Gambar 3.16 Diagram alir penghapusan data dalam leaf page Data dihapus secara langsung dalam page jika jumlah data dalam leaf page di atas orde indeks. Penggabungan (merge) dilakukan untuk menjaga faktor pengisi setiap page dalam susunan b+-tree agar level b+-tree tidak terlalu dalam. Penggabungan dilakukan ketika sebuah leaf page mempunyai jumlah data di bawah orde indeks. Sibling kiri diperiksa terlebih dahulu sebelum sibling kanan.
61
3.2.3.3 Diagram Alir Proses Penggabungan Page Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses penggabungan sebuah page. Gambaran umum algoritma pada proses pembagian sebuah index page dapat dilihat pada Gambar 3.17. Penggabungan page terjadi apabila sebuah page mempunyai jumlah data di bawah orde indeks. Page dan sibling-nya digabungkan dan page yang tidak terpakai dihapus beserta key dalam index page pengacunya. Penggabungan page dilakukan dalam index page pengacu jika penghapusan key pada index page pengacu mengakibatkan jumlah data dalam index page pengacu di bawah orde indeks. Pemeriksaan jumlah data dan orde indeks dilakukan dari leaf page sampai root indeksnya.
Gambar 3.17 Diagram alir penggabungan page
62
3.2.4 Diagram Alir Proses Pencarian Data Diagram alir ini berfungsi untuk menggambarkan algoritma untuk proses pencarian data dalam b+-tree. Gambaran umum algoritma pada proses pencarian data dapat dilihat pada Gambar 3.18.
Gambar 3.18 Diagram alir algoritma pencarian data dalam b+-tree 3.3 Rancangan Diagram Arus Data Rancangan aliran data pada tingkat ke-0 yang digunakan dalam program simulasi digambarkan oleh Gambar 3.19. Gambar 3.20 menggambarkan DAD pada tingkat ke-1. Gambar 3.21 menjelaskan aliran data tingkat ke-2 pada proses cari. Gambar 3.22 menjelaskan aliran data tingkat ke-2 pada proses tambah. Gambar 3.23 menjelaskan aliran data tingkat ke-2 pada proses hapus.
63
Gambar 3.19 Rancangan DAD tingkat ke-0
Gambar 3.20 Rancanga n DAD tingkat ke-1
Gambar 3.21 Rancangan DAD tingkat ke-2 proses cari
Gambar 3.22 Rancangan DAD tingkat ke-2 proses tambah
64
Gambar 3.23 Rancangan DAD tingkat ke-2 proses hapus
3.4 Rancangan Antarmuka Antarmuka program simulasi digambarkan dalam bentuk form yang di dalamnya terdapat berbagai objek berbentuk grafis untuk simbol-simbol perintah, pesan, dan pemilihan menu 3.4.1 Form Utama Form utama digunakan untuk menampilkan menu utama dalam program simulasi. Dalam form utama juga ditampilkan informasi indeks secara tekstual, data yang dibaca indeks secara sekuensial ascending dan descending pada leaf node. Rancangan form utama dapat dilihat pada Gambar 3.24.
65
Gambar 3.24 Form utama 3.4.2 Form Setting Orde B-tree Form setting orde digunakan untuk menentukan orde indeks yang digunakan dalam program simulasi. Dalam form setting orde juga ditampilkan informasi sebuah node sesuai dengan orde yang dipilih. Program keluar jika orde indeks belum ditentukan. Form utama terbuka jika orde telah terinisialisasi. Rancangan form setting orde dapat dilihat pada Gambar 3.25.
Gambar 3.25 Form setting orde b-tree
66
3.4.3 Form Input Data Awal Form input data awal digunakan untuk memasukan sekelompok data. Input data awal untuk membentuk susunan indeks digunakan ketika data dalam indeks dalam keadaan kosong. Susunan data yang akan diproses merupakan data yang ditentukan secara manual atau beberapa data acak. Proses pemasukan data ke dalam indeks terekam oleh log. Tidak terdapat animasi dalam proses pemasukan data melalui form input data awal. Data terproses ketika tombol proses ditekan. Rancangan form input data awal dapat dilihat pada Gambar 3.26.
Gambar 3.26 Form input data awal
3.4.4 Form Tambah Data Form tambah data digunakan untuk memasukan data. Data yang akan diproses merupakan data yang ditentukan secara manual. Proses pemasukan data ke dalam indeks terekam oleh log dan statistik proses. Penjelasan proses menjelaskan animasi dan proses yang sedang terjadi. Data terproses ketika tombol masukkan ditekan. Rancangan form tambah data dapat dilihat pada Gambar 3.27.
67
Gambar 3.27 Form tambah data 3.4.5 Form Hapus Data Form hapus data digunakan untuk menghapus data. Data yang akan diproses merupakan data yang ditentukan secara manual. Proses penghapusan data dalam indeks terekam oleh log dan statistik proses. Penjelasan proses menjelaskan animasi dan proses yang sedang terjadi. Proses dijalankan ketika tombol hapus ditekan. Rancangan form hapus data dapat dilihat pada Gambar 3.28.
Gambar 3.28 Form hapus data
68
3.4.6 Form Pencarian Data Form pencarian data digunakan untuk mencari data. Data yang akan diproses merupakan data yang ditentukan secara manual. Proses pencarian data dalam indeks terekam oleh log dan statis tik proses. Penjelasan proses menjelaskan animasi dan proses yang sedang terjadi. Proses dijalankan ketika tombol cari ditekan. Rancangan form pencarian data dapat dilihat pada Gambar 3.29.
Gambar 3.29 Form pencarian data 3.4.7 Form Statistik Proses Form statistik proses digunakan untuk memberikan informasi tentang jumlah proses yang telah dilakukan dan daftar proses beserta waktu eksekusinya. Waktu ekseskusi
diambil
dari
CPU
berdasarkan
pengambilan
frekuensi
dan
penghitungnya. Rancangan form statistik proses dapat dilihat pada Gambar 3.30.
69
Gambar 3.30 Form statistik proses 3.4.8 Form Log Proses Form log proses digunakan untuk memberikan informasi tentang rekaman proses yang telah dilakukan secara keseluruhan. Rancangan form log proses dapat dilihat pada Gambar 3.31.
Gambar 3.31 Form log proses 3.4.9 Form Preview Visual Form preview visual digunakan untuk menggambarkan bentuk indeks secara visual. Rancangan form preview visual dapat dilihat pada Gambar 3.32.
70
Gambar 3.32 Form preview visual 3.4.10 Form ODS Form ODS digunakan untuk menggambarkan bentuk page dari indeks yang tersusun secara visual maupun secara urutan bit informasi dalam berkas. Rancangan form ODS dapat dilihat pada Gambar 3.33.
Gambar 3.33 Form ODS
4BAB IV IMPLEMENTASI DAN PEMBAHASAN SISTEM 4.1 Implementasi Program Simulasi Implementasi program simulasi penggunaan b-tree dalam basis data Firebird dibuat dengan menggunakan bahasa pemrograma n Delphi 6.0. 4.1.1 Implementasi Struktur Data Struktur data dibuat menggunakan tipe data pointer. Sebuah pointer menunjukan sebuah paket data. Paket data dikemas dalam tipe data record. Sebuah paket data terdiri dari identitas node,
D
ID
dengan tipe data integer yang berfungsi sebagai
dengan tipe data integer yang menginformasikan jumlah data
yang tersimpan dalam node tersebut,
Data
dengan tipe data
untuk menyimpan key dalam larik bertipe data integer,
P
TData
yang berfungsi
dengan tipe data
TPNode
yang berfungsi untuk menyimpan penunjuk node di bawahnya dalam larik bertipe data
PNode , Next
dengan tipe data
sebelah kanan dari leaf node,
PNode
Prev
yang berfungsi sebagai penunjuk sibling
dengan tipe data
penunjuk sibling sebelah kir i dari leaf node dan
PNode
isLeaf
yang berfungsi sebagai
dengan tipe boolean yang
berfungsi sebagai pembeda node. Node merupakan sebuah index node jika isLeaf bernilai false dan merupakan sebuah leaf node jika isLeaf bernilai true. Deklarasi node dalam program simulasi digambarkan dalam potongan kode program pada Gambar 4.1.
71
72
type PNode = ^TNode; //index TData = array of integer; TPNode = array of PNode; TNode = record ID : integer; //creation ID D: integer; //jumlah entri Data : TData; //data dalam node (-1 = kosong) P: TPNode; //pointer ke childnode Next, Prev : PNode; //penunjuk ke sibling isLeaf : Boolean; //pembeda leaf dan indeks end; var Index : PNode; OrdeIndex, Create : integer;
Gambar 4.1 Potongan kode program tipe data yang digunakan 4.1.2 Implementasi Proses Inisialisasi Sebuah root indeks digambarkan oleh sebuah variabel bernama
Index . Index
merupakan sebuah pointer utama yang mengarahkan node berikutnya dan membentuk suatu susunan tree.
Index
merupakan sebuah leaf node pada awal
inisialisasi dan tidak berubah jika jumlah data yang dimasukkan tidak melebihi jumlah daya tampung sebuah node.
Index
menjadi sebuah index node ketika data
yang dimasukkan melebihi daya tampung sebuah node dan telah terjadi pembagian leaf node. Variabel
create
yang merupakan identitas pembuatan node
diisi 0 ketika proses inisialisasi. Potongan kode inisialisasi dapat dilihat pada Gambar 4.2. OrdeIndex := InttoStrDef(edtOrde.Text,2); Create := 0; NodeBaru(Index); //root = Index Index^.isLeaf := True;
//default orde = 2
Gambar 4.2 Potongan kode program proses inisialisasi indeks Proses inisialisasi indeks merupakan proses penentuan orde indeks yang digunakan. Orde menentukan panjang node dan kedalaman level. Jumlah data yang dapat ditampung dalam tiap node sebesar berikutnya sebesar
(2*Orde)+1 .
2*Orde
dan jumlah pointer ke node
Level indeks akan sangat dalam jika indeks
73
mempunyai orde yang kecil dan diisi banyak data. Level indeks tidak akan dalam jika indeks mempunyai orde yang besar. 4.1.3 Implementasi Proses Penambahan Data Proses penambahan data pada program simulasi menggunakan metode rekursif.
Metode
rekursif
mempermudah
proses
pencarian
dan
dapat
mengembalikan nilai yang akan digunakan jika terjadi pembagian node. Prosedur insert
merupakan
prosedur
membutuhkan parameter ChildNode
Node
rekursif dan
Data.
yang
digunakan.
Prosedur
insert
Prosedur
insert
mengembalikan nilai
yang berarti alamat pointer node baru hasil dari proses pembagian node
pada level di bawahnya. Prosedur utama penambahan data beserta prosedur rekursif dapat dilihat pada Gambar 4.3. procedure InputData(Data: integer); var DataTemp, i : integer; newIndex, newTree : PNode; //prosedur pemasukan rekursif procedure Insert(var Node:PNode; Data:integer; var ChildNode:PNode); begin ... {pemasukan data ke leaf node dan index node} ... end; begin Insert(Index,Data, newTree); ... {jika ada newTree} ... end;
Gambar 4.3 Potongan kode program prosedur dan variabel yang digunakan Variabel
newIndex
merupakan pointer yang berfungsi sebagai indeks baru jika
terdapat sebuah root indeks penuh dan terjadi pembagian root indeks. Variabel newTree
merupakan pointer hasil dari eksekusi prosedur insert. Variabel
newTree
merupakan pecahan sebelah kanan dari root indeks jika terjadi pembagian root indeks dan newTree tidak nil.
74
4.1.3.1 Proses Modifikasi Root Indeks Modifikasi root indeks terjadi apabila terjadi penambahan key pada root indeks yang penuh. Root indeks dapat berupa sebuah index node atau sebuah leaf node. Root indeks berupa sebuah leaf node ketika jumlah data dalam b-tree kurang dari atau sama dengan kapasitas sebua h leaf node. Root indeks yang berupa leaf node berubah menjadi sebuah index node ketika sebuah leaf node tersebut mempunyai data yang melebihi kapasitas. Program akan memindah pointer penunjuk node lain beserta datanya ke node baru jika sebuah root indeks yang terbagi merupakan sebuah index node. Gambar 4.4 menunjukkan potongan kode program jika sebuah root indeks merupakan index node. NodeBaru(newIndex); newIndex^.Data[0] := newTree^.Data[0]; newIndex^.D := 1; newIndex^.P[0] := Index; newIndex^.P[1] := newTree; i:=0; while i
Gambar 4.4 Potongan kode program jika newTree merupakan index node Program akan memindah data ke node baru jika sebuah root indeks yang terbagi merupakan sebuah leaf node. Gambar 4.5 menunjukkan potongan kode program jika sebuah root indeks merupakan index node. NodeBaru(newIndex); newIndex^.Data[0] := newTree^.Data[0]; newIndex^.D := 1; newIndex^.P[0] := Index; newIndex^.P[1] := newTree; Index := newIndex;
Gambar 4.5 Potongan kode program jika newTree merupakan leaf node
75
4.1.3.2 Proses Pencarian Rekursif Proses pencarian posisi untuk memasukan data pada prosedur
insert
menggunakan metode rekursif. Probe berpindah antar node dan menuju ke level berikutnya jika posisi data yang akan diletakkan belum tepat. Pencarian dihentikan dan keluar dari proses rekursif jika data sudah ada dalam indeks. Indeks probe digambarkan oleh variabel Data>Node^.data[i]
i.
Posisi tepat ditemukan jika
dan indeks probe tidak melebihi kapasitas data dari node.
Rekursif berakhir pada leaf node jika posisi node yang sesuai sudah ditemukan. Gambar 4.6 menjelaskan potongan kode program tentang proses pencarian yang menggunakan metode rekursif. i:=0; while ((i
Node^.data[i])) do begin inc(i); //mencari posisi yang tepat untuk penambahan end; if ((inil} ... end;
Gambar 4.6 Potongan kode program pencarian rekursif 4.1.3.3 Proses Pencarian Posisi Data Dalam Node Node mempunyai sebuah larik data. Pencarian posisi yang tepat untuk melakukan pemasukan data di dalam sebuah node dapat dilihat pada Gambar 4.7. Pencarian posisi dalam node dijalankan setelah pencarian rekursif menemukan sebuah node yang sesuai untuk memasukan data. Indeks probe digambarkan oleh variabel i. Posisi data yang sesuai mempunyai keadaan
Data
atau
76
jika terdapat ruang kosong pada larik data yang diakses oleh probe. Pencarian dihentikan dan keluar dari prosedur jika data sudah ada dalam indeks. i:=0; while (i<=Node^.D) do begin //jika posisi sesuai maka keluar dari perulangan, i sebagai indeks posisi if (Data
Gambar 4.7 Potonga n kode program pencarian posisi data yang sesuai dalam node 4.1.3.4 Proses Pemasukan Data Jika Index Node Tidak Penuh Pemasukan data pada node yang mempunyai larik data tidak penuh dilakukan dengan memasukan langsung data pada larik data. Pencarian posisi data terlebih dahulu dilakukan sebelum memasukan data ke dalam larik data untuk menjaga urutan data yang telah ada. Data dan pointer digeser ke kanan jika terdapat data baru yang disisipkan di antara larik data. Potongan kode program yang menjelaskan proses pemasukan data dalam index node jika node tersebut tidak penuh digambarkan pada Gambar 4.8. Data := ChildNode^.Data[0]; P := ChildNode; ... {cari posisi yang sesuai} ... inc(Node^.D); while i
Gambar 4.8 Potongan kode program pemasukan data dalam indeks jika node tidak penuh 4.1.3.5 Proses Pemasukan Data Jika Index Node Penuh Pemasukan data pada node yang mempunyai larik data penuh dilakukan dengan membagi node menjadi dua bagian dan menaikkan data tengah ke index
77
node level di atasnya. Pencarian posisi data dilakukan sebelum memasukan data ke dalam larik data untuk menjaga urutan data yang telah ada. Data dan pointer digeser ke kanan jika terdapat data baru yang disisipkan di antara larik data. Pemasukan data pada node yang penuh menyebabkan overflow. Node dibagi menjadi dua agar data yang overflow dapat ditampung dalam larik data. Data di tengah node dinaikkan ke level di atasnya untuk menjadi key baru yang menujukkan node baru. Node baru disimpan dalam variabel
ChildNode.
Node baru
dihubungkan ke sibling. Potongan kode program yang menjelaskan proses pemasukan data dalam index node jika node tersebut penuh digambarkan pada Gambar 4.9. Data := ChildNode^.Data[0]; P := ChildNode; ... {cari posisi yang sesuai} ... while (i
Gambar 4.9 Potongan kode program pembagian indeks jika node penuh 4.1.3.6 Proses Pemasukan Data Leaf Node Jika Tidak Penuh Pemasukan data pada sebuah leaf node yang mempunyai larik data tidak penuh dilakukan dengan memasukan langsung data pada larik data. Pencarian
78
posisi data terlebih dahulu dilakukan sebelum memasukan data ke dalam larik data untuk menjaga urutan data yang telah ada. Data digeser ke kanan jika terdapat data baru yang disisipkan di antara larik data. Variabel
Childnode
diisi nil
karena tidak terdapat proses pembagian node. Potongan kode program yang menjelaskan proses pemasukan data dalam index node jika node tersebut tidak penuh digambarkan pada Gambar 4.10. ... {cari posisi yang sesuai} ... inc(Node^.D); while i
Gambar 4.10 Potongan kode program pemasukan data dalam leaf jika node tidak penuh 4.1.3.7 Proses Rotasi Sibling Kiri Jika Leaf Node Penuh Rotasi sibling kiri dilakukan jika leaf node penuh dan terdapat ruang pada sibling kirinya. Rotasi dilakukan untuk mengefisienkan faktor pengisi pada sebuah indeks b+-tree. Variabel
IndexRotasi
berfungsi sebagai pointer index node
yang akan dirubah jika terjadi Rotasi. Rotasi kiri memindahkan data ke-0 leaf node yang penuh ke sibling kirinya. Pemindahan data ke-0 menyebabkan key indeks untuk node ya ng penuh berubah. Data ke-0 yang baru menggantikan key indeks pada index node yang menunjuk leaf node yang penuh. ... {jika ada data sama maka keluar dari prosedur} ... {cari node yang menujuk ke Node } DataRotasi := Node^.Data[0]; i:=0; while i<=Node^.Prev^.D do begin if (DataRotasi
79
Node^.Prev^.Data[i] := DataRotasi; Node^.Data[0] := -1; i:=0; dec(Node^.D); while i
Gambar 4.11 Potongan kode program rotasi sibling kiri jika node penuh Potongan kode program yang membahas tentang rotasi sibling kiri pada leaf node digambarkan dalam Gambar 4.11. Proses rotasi diawali dengan pencarian posisi yang sesuai untuk memasukan data. Pemasukan data pada leaf node yang penuh berakibat terjadinya overflow. Data ke-0 dikeluarkan dari node yang penuh dan data digeser ke kiri sehingga overflow masuk dalam node. Probe mencari posisi yang sesuai pada sibling kiri node untuk meletakkan data ke-0 dari node. Data dimasukkan ke dalam sibling kiri node jika posisi yang sesuai telah ditemukan. Penggantian key dilakukan pada index node yang menunjuk leaf node yang penuh.
80
4.1.3.8 Proses Rotasi Sibling Kanan Jika Leaf Node Penuh Rotasi sibling kanan pada sebuah leaf node dilakukan jika leaf node penuh, sibling kiri node penuh dan terdapat ruang pada sibling kanannya. Rotasi dilakukan untuk mengefisienkan faktor pengisi pada sebuah indeks b+-tree. ... {jika ada data sama maka keluar dari prosedur} ... {cari node yang menujuk ke Node^.Next} DataRotasi := Node^.Next^.Data[0]; i:=0; while i<=Node^.D do begin if (Data0 do begin {pindah data dari i+1 ke i pada Node^.Next} dec(i); end; Node^.Next^.Data[0] := Data; inc(Node^.Next^.D); inFound := False; i:=0; while i
Gambar 4.12 Potongan kode program rotasi sibling kanan jika node penuh Variabel
IndexRotasi
berfungsi sebagai pointer index node dari sibling kanan
yang akan dirubah jika terjadi Rotasi. Rotasi kanan memindahkan data overflow dari node yang penuh ke sibling kanannya. Pemindahan data ke sibling kanan menyebabkan key indeks pada sibling kanan node yang penuh berubah. Data ke-0 yang baru menggantikan key indeks pada index node yang menunjuk sibling
81
kanan node yang penuh. Potongan kode program yang membahas tentang rotasi sibling kanan pada leaf node digambarkan dalam Gambar 4.12. Proses rotasi diawali dengan pencarian posisi yang sesuai untuk memasukan data. Pemasukan data pada leaf node yang penuh berakibat terjadinya overflow. Sibling kanan menggeser data ke kanan sehingga terdapat ruang pada data ke-0. Data overflow dimasukkan pada posisi data ke-0 dari sibling kanan node. Penggantian key dilakukan pada index node yang menunjuk sibling kanan node yang penuh. 4.1.3.9 Proses Pemasukan Data Jika Leaf Node Penuh Pemasukan data pada leaf node dengan cara membagi node dilakukan jika leaf node tersebut penuh, sibling kiri node penuh dan sibling kanan node penuh. Pemasukan data pada leaf node dilakukan dengan membagi node menjadi dua bagian dan menaikkan data tengah ke index node level di atasnya. Pencarian posisi data terlebih dahulu dilakukan sebelum memasukan data ke dalam larik data untuk menjaga urutan data yang telah ada. Data digeser ke kanan jika terdapat data baru yang disisipkan di antara larik data. Pemasukan data pada node yang penuh menyebabkan overflow. Node dibagi menjadi dua agar data yang overflow dapat ditampung dalam larik data. Data di tengah node dinaikkan ke level di atasnya untuk menjadi key baru yang menujukkan node pecahan dari node yang penuh. Node baru disimpan dalam variabel
ChildNode.
pada urutan sekuensial dari leaf node. Kode program Node^.Next
:=
tempr,
tempr^.Prev
tempr^.Next^.Prev := tempr
:=
Node
dan
Node baru disisipkan
tempr^.Next := Node^.Next , if
tempr^.Next<>nil
then
menunjukkan proses penyisipan node dalam urutan leaf
node. Sibling kanan node baru diganti dengan sibling kanan node. Sibling kiri dari
82
sibling kanan node diganti node baru. Sibling kanan node diganti dengan node baru. Sibling kiri node baru diganti dengan node. Model leaf node sekuensial dengan taut pada sibling-nya dapat dilihat pada Gambar 3.3 pada bab III. Potongan kode program yang menjelaskan proses pemasukan data dalam leaf node jika node tersebut penuh digambarkan pada Gambar 4.13. ... {cari posisi yang sesuai} ... i:=0; while (i<=Node^.D) do begin {cari letak data yang sesuai} inc(i); end; while (i
Gambar 4.13 Potongan kode program pembagian leaf jika node penuh 4.1.4 Implementasi Proses Penghapusan Data Proses penghapusan data pada program simulasi menggunakan metode rekursif.
Metode
rekursif
mempermudah
proses
pencarian
dan
dapat
mengembalikan nilai yang akan digunakan jika terjadi penggabungan node. Prosedur
delete
merupakan prosedur rekursif yang digunakan. Prosedur
delete
83
membutuhkan
parameter
mengembalikan nilai
Node ,
integer
Data
dan
ParentNode .
Prosedur
delete
yang berarti data dalam level berikutnya yang akan
dihapus. Prosedur utama penghapusan data beserta prosedur rekursif dapat dilihat pada Gambar 4.14. procedure InputData(Data: integer); function Delete(Node:PNode;Data:integer;ParentNode:PNode):integer; var i,j, Datatemp, iFound:integer; Found : boolean; IndexTemp : PNode; begin ... {penghapusan data di leaf node dan index node} ... end; begin Delete(Index,Data,nil); end;
Gambar 4.14 Potongan kode program prosedur dan variabel yang digunakan 4.1.4.1 Proses Pencarian Rekursif Proses pencarian posisi untuk penghapusan data pada prosedur
delete
menggunakan metode rekursif. Probe berpindah antar node dan menuju ke level berikutnya jika data tidak ditemukan. Indeks probe digambarkan oleh variabel i. Posisi tepat ditemukan jika
Data>=Node^.data[i]
dan indeks probe tidak melebihi
kapasitas data dari node. Rekursif berakhir pada leaf node jika posisi node yang sesuai sudah ditemukan. Gambar 4.15 menjelaskan potongan kode program tentang proses pencarian yang menggunakan metode rekursif. i:=0; while ((i=Node^.data[i])) do begin inc(i); end; if (i=0) and (Node<>Index) then Datatemp := Delete(Node^.p[i],Data, ParentNode) else Datatemp := Delete(Node^.p[i],Data, Node); if Datatemp<>-1 then begin ... {proses pegnhapusan di index node} ...
84
end;
Gambar 4.15 Potongan kode program pencarian rekursif 4.1.4.2 Proses Penghapusan Data Jika Index Node Diatas Orde Penghapusan data pada node yang mempunyai jumlah larik data di atas orde indeks dilakukan dengan menghapus data secara langsung dalam larik data. Data dihapus dan diurutkan kembali jika data ditemukan dalam larik. Pointer digeser mengganti posisi pointer yang dihapus. Proses ini menghasilkan nilai -1 yang berarti tidak terdapat key indeks pada level berikutnya yang akan dihapus. Potongan kode program yang menjelaskan proses penghapusan data dalam index node jika jumlah data dalam node tersebut di atas orde digambarkan pada Gambar 4.16. ... {pencarian data} ... i := iFound; if Node^.P[0]^.Data[0]=Datatemp then begin {Next dan Prev sibling pointer disesuaikan} NodeDelete(Node^.P[i]); Node^.P[i] := nil; while inil) then begin i:=0; found := false; while i<ParentNode^.D do begin {Cari posisi yang cocok dengan Data} inc(i); end; if found then ParentNode^.Data[i] := Node^.P[0]^.Data[0]; end; Result := -1; end else begin {Next dan Prev sibling pointer disesuaikan}
85
NodeDelete(Node^.P[i+1]); Node^.P[i+1] := nil; Dec(Node^.D); while i
Gambar 4.16 Potongan kode program penghapusan data dalam indeks jika jumlah data di atas orde 4.1.4.3 Proses Penggabungan Sibling Kiri Index Node Penggabungan antara node dengan sibling kiri dilakukan jika jumlah data dalam index node di bawah orde dan terdapat ruang pada sibling kirinya. Penggabungan dilakukan untuk mengefisienkan faktor pengisi pada sebuah indeks b+-tree. Penggabungan dilakukan jika
ParentNode
sama. Variabel
iFound
merupakan indeks yang menunjukkan posisi data yang akan dihapus. Penggabungan dilakukan dengan cara memindahkan data dan pointer pada node ke sibling kirinya. Pemindahan data tidak menyebabkan key indeks pada sibling berubah. Penggabungan menghapus node yang telah dipindah ke sibling-nya. Potongan kode program yang menjelaskan proses penggabungan sibling kiri digambarkan pada Gambar 4.17. ... {pencarian data} ... i := iFound; if Node^.P[0]^.Data[0]=Datatemp then begin {Next dan Prev sibling pointer disesuaikan} NodeDelete(Node^.P[i]); Node^.P[i] := nil; while i
86
begin {Next dan Prev sibling pointer disesuaikan} NodeDelete(Node^.P[i+1]); Node^.P[i+1] := nil; Dec(Node^.D); while inil then begin i:=0; while i<=ParentNode^.D do begin {Cari posisi yang cocok dengan Node} inc(i); end; Result := ParentNode^.Data[i-1]; Node^.Prev^.Data[Node^.Prev^.D] := ParentNode^.Data[i-1]; Inc(Node^.Prev^.D); end; i:=0; j:=Node^.Prev^.D; Node^.Prev^.P[j] := Node^.P[i]; while i
Gambar 4.17 Potongan kode program proses penggabungan sibling kiri index node Proses penggabungan diawali dengan menghapus data di dalam node. Larik data beserta pointer diurutkan kembali setelah data terhapus. Variabel
IndexTemp
merupakan index node yang mengacu sibling. Nilai dikembalikan untuk menghapus key pada
ParentNode
jika index node yang mengacu node sama dengan
index node yang mengacu sibling. Proses pemindahan data dan pointer ke node sibling dilakukan jika
ParentNode
sama. Proses pemindahan data dan pointer
diikuti dengan modifikasi pointer penunjuk sibling kiri dan kanan.
87
4.1.4.4 Proses Penggabungan Sibling Kanan Index Node Penggabungan antara node dengan sibling kanan dilakukan jika jumlah data dalam index node di bawah orde, sibling kiri penuh dan terdapat ruang pada sibling kanannya. Penggabungan dilakukan jika
ParentNode
sama. Variabel
iFound
merupakan indeks yang menunjukkan posisi data yang akan dihapus. Penggabungan dilakukan dengan cara memindahkan data dan pointer dari sibling kanan ke node. Pemindahan data tidak menyebabkan key indeks node berubah. Penggabungan menghapus sibling yang telah dipindah ke node. Potongan kode program yang menjelaskan proses penggabungan sibling kanan digambarkan pada Gambar 4.18. ... {pencarian data} ... i := iFound; if Node^.P[0]^.Data[0]=Datatemp then begin {Next dan Prev sibling pointer disesuaikan} NodeDelete(Node^.P[i]); Node^.P[i] := nil; while inil then begin i:=0;
88
while i<=IndexTemp^.D do begin {Cari posisi yang cocok dengan Node^.Next} inc(i); end; Result := IndexTemp^.Data[i-1]; Node^.Data[Node^.D] := IndexTemp^.Data[i-1]; Inc(Node^.D); end; i:=0; j:=Node^.D; Node^.P[j] := Node^.Next^.P[i]; while i<=Node^.Next^.D do begin {Pindah data dan pointer Node^.Next[i] ke Node[j]} inc(i); inc(j); dec(Node^.Next^.D); inc(Node^.D); end; {Node^.Next dan Node^.Prev sibling disesuaikan}
Gambar 4.18 Potongan kode program proses penggabungan sibling kanan index node Proses penggabungan diawali dengan menghapus data di dalam node. Larik data beserta pointer diurutkan kembali setelah data terhapus. Key pengacu pada ParentNode
akan diganti jika data ke-0 dalam node berubah. Variabel
IndexTemp
merupakan index node yang mengacu sibling. Nilai dikembalikan untuk menghapus key pada index node yang mengacu sibling jika index node yang mengacu node sama dengan index node yang mengacu sibling. Proses pemindahan data dan pointer dari node sibling dilakukan jika
ParentNode
sama.
Proses pemindahan data dan pointer diikuti dengan modifikasi pointer penunjuk sibling kiri dan kanan. 4.1.4.5 Proses Penghapusan Data Jika Index Node Dibawah Orde Penghapusan secara langsung pada node yang mempunyai jumlah larik data di bawah orde indeks dilakukan jika kedua sibling dalam keadaan penuh. Data dihapus dan diurutkan kembali jika data ditemukan dalam larik. Pointer digeser mengganti posisi pointer yang dihapus. Proses ini menghasilkan nilai -1 yang
89
berarti tidak terdapat key indeks pada level berikutnya yang akan dihapus. Potongan kode program yang menjelaskan proses penghapusan data dalam index node jika jumlah data dalam node tersebut di bawah orde digambarkan pada Gambar 4.19. ... {pencarian data} ... i := iFound; if (Node^.P[0]^.Data[0]=Datatemp) or (Node^.P[0]^.Data[OrdeIndex+1]=Datatemp) then begin {Next dan Prev sibling pointer disesuaikan} NodeDelete(Node^.P[i]); Node^.P[i] := nil; while i
Gambar 4.19 Potongan kode program penghapusan data dalam indeks jika jumlah data di bawah orde 4.1.4.6 Proses Penghapusan Data Jika Leaf Node Diatas Orde Penghapusan data pada node yang mempunyai jumlah larik data di atas orde indeks dilakukan dengan menghapus data secara langsung dalam larik data. Data dihapus dan diurutkan kembali jika data ditemukan dalam larik. Proses ini menghasilkan nilai -1 yang berarti tidak terdapat key indeks pada level berikutnya
90
yang akan dihapus. Potongan kode program yang menjelaskan proses penghapusan data dalam index node jika jumlah data dalam node tersebut di atas orde digambarkan pada Gambar 4.20. ... {pencarian data} ... Result := -1; i := iFound; Dec(Node^.D); while inil) and (iFound=0) then begin i:=0; found := false; while i<ParentNode^.D do begin if ParentNode^.Data[i]=Data then begin found := true; break; end; inc(i); end; if found then ParentNode^.Data[i] := Node^.Data[0]; end;
Gambar 4.20 Potongan kode program penghapusan data dalam leaf jika jumlah data di atas orde 4.1.4.7 Proses Penggabungan Sibling Kiri Leaf Node Penggabungan antara node dengan sibling kiri dilakukan jika jumlah data dalam leaf node di bawah orde dan terdapat ruang pada sibling kirinya. Variabel iFound
merupakan indeks yang menunjukkan posisi data yang akan dihapus.
Penggabungan dilakukan dengan cara memindahkan data dalam node ke sibling kirinya. Pemindahan data tidak menyebabkan key indeks pada sibling berubah. Penggabungan menghapus node yang telah dipindah ke sibling-nya dengan mengembalikan nilai key dari node. Potongan kode program yang menjelaskan proses penggabungan sibling kiri digambarkan pada Gambar 4.21.
91
... {pencarian data} ... Result := Node^.Data[0]; i := iFound; Dec(Node^.D); while i
Gambar 4.21 Potongan kode program proses penggabungan sibling kiri leaf node 4.1.4.8 Proses Penggabungan Sibling Kanan Leaf Node Penggabungan antara node dengan sibling kanan dilakukan jika jumlah data dalam leaf node di bawah orde, sibling kiri penuh dan terdapat ruang pada sibling kirinya. Variabel
iFound
merupakan indeks yang menunjukkan posisi data yang
akan dihapus. Penggabungan dilakukan dengan cara memindahkan data dalam node ke sibling kanannya. Pemindahan data menyebabkan key indeks pada sibling berubah. Variabel
IndexTemp
digunakan untuk mengetahui index node yang
mengacu sibling kanan dan mengubah key. Penggabungan menghapus node yang telah dipindah ke sibling-nya dengan mengembalikan nilai key dari node. Potongan kode program yang menjelaskan proses penggabungan sibling kanan digambarkan pada Gambar 4.21. ... {pencarian data} ... Result := Node^.Data[0]; i := iFound; Dec(Node^.D); while i
92
inc(i); end; Node^.Data[i] := -1; IndexTemp := Index; IndexTemp := CariNode(IndexTemp, Node^.Next^.Data[0], nil); DataTemp := Node^.Next^.Data[0]; i:=Node^.D-1; while i>=0 do begin j:=Node^.Next^.D; while j>0 do begin Node^.Next^.Data[j] := Node^.Next^.Data[j-1]; dec(j); end; Node^.Next^.Data[j] := Node^.Data[i]; dec(i); inc(Node^.Next^.D); dec(Node^.D); end; if (IndexTemp<>nil) then begin i:=0; found := false; while i
Gambar 4.22 Potongan kode program proses penggabungan sibling kanan leaf node 4.1.4.9 Proses Penghapusan Data Jika Index Leaf Dibawah Orde Penghapusan secara langsung pada node yang mempunyai jumlah larik data di bawah orde indeks dilakukan jika kedua sibling dalam keadaan penuh. Data dihapus jika data ditemukan dalam larik. Pointer digeser mengganti posisi pointer yang dihapus. Proses ini menghasilkan nilai -1 yang berarti tidak terdapat key indeks pada level berikutnya yang akan dihapus. Potongan kode program yang menjelaskan proses penghapusan data dalam leaf node jika jumlah data dalam node tersebut di bawah orde digambarkan pada Gambar 4.23. ... {pencarian data} ...
93
i := iFound; Dec(Node^.D); while inil) and (iFound=0) then begin i:=0; found := false; while i<ParentNode^.D do begin if ParentNode^.Data[i]=Data then begin found := true; break; end; inc(i); end; if found then ParentNode^.Data[i] := Node^.Data[0]; end; Result := -1;
Gambar 4.23 Potongan kode program penghapusan data dalam leaf jika jumlah data dibawah orde 4.1.5 Implementasi Proses Pencarian Data Proses pencarian data pada program simulasi menggunakan metode rekursif. Metode rekursif mempermudah proses pencarian. Prosedur prosedur rekursif yang digunakan. Prosedur Node
dan
Data .
SearchRec
SearchRec
merupakan
membutuhkan parameter
Prosedur utama pencarian data beserta prosedur rekursif dapat
dilihat pada Gambar 4.3. procedure CariData(Data: integer); procedure SearchRec(Node:PNode;Data:integer); var i:integer; begin ... {pencarian dalam index dan leaf} ... end; begin SearchRec(Index,Data); end;
Gambar 4.24 Potongan kode program prosedur dan variabel yang digunakan
94
4.1.5.1 Proses Pencarian Rekursif Metode rekursif digunakan pada prosedur
SearchRec
untuk proses pencarian
data. Probe berpindah antar node dan menuju ke level berikutnya jika posisi data yang akan diletakkan belum tepat. Indeks probe digambarkan oleh variabel Posisi tepat ditemukan jika
Data>=Node^.data[i]
i.
dan indeks probe tidak melebihi
kapasitas data dari node. Rekursif berakhir pada leaf node jika posisi node yang sesuai sudah ditemukan. Gambar 4.15 menjelaskan potongan kode program tentang proses pencarian yang menggunakan metode rekursif. i:=0; while ((i=Node^.data[i])) do begin inc(i); end; SearchRec(Node^.p[i],Data);
Gambar 4.25 Potongan kode program pencarian rekursif 4.1.5.2 Proses Pencarian Posisi Data Dalam Node Node mempunyai sebuah larik data. Proses pencarian data di dalam sebuah node dapat dilihat pada Gambar 4.16. Pencarian posisi dalam node dijalankan setelah pencarian rekursif menemukan sebuah node yang sesuai untuk memasukan data. Indeks probe digambarkan oleh variabel Data=Node^.Data[i]
i.
Data ditemukan jika
pada larik data yang diakses oleh probe.
i:=0; while i
Gambar 4.26 Potongan kode program pencarian posisi data yang sesuai dalam node
95
4.1.6 Implementasi Antarmuka Program Simulasi Implementasi antarmuka program simulasi penggunaan b-tree dalam basis data Firebird dibuat dengan menggunakan bahasa pemrograman Delphi 6.0 dan komponen SuiPack 5. 4.1.6.1 Form Utama Form utama merupakan form yang berfungsi untuk menampilkan menu utama pada program simulasi dan berisi keterangan tentang indeks yang digunakan. Gambar 4.27 merupakan cuplikan dari form utama pada program simulasi.
Gambar 4.27 Implementasi Form Utama 4.1.6.2 Form Inisialisasi Indeks Form inisialisasi indeks merupakan form yang berfungsi untuk menentukan besar orde indeks dan menampilkan contoh sebuah node ke dalam layar. Gambar 4.28 merupakan cuplikan dari form inisialisasi indeks pada program simulasi.
Gambar 4.28 Implementasi Form Inisialisasi Indeks
96
4.1.6.3 Form Input Data Awal Form input data awal merupakan form yang berfungsi untuk menentukan data awal yang dapat dimasukkan ke dalam indeks. Data awal dapat berupa data acak atau data yang telah ditentukan nilainya. Gambar 4.29 merupakan cuplikan dari form input data awal pada program simulasi.
Gambar 4.29 Implementasi Form Input Data Awal 4.1.6.4 Form Tambah Data Form tambah data merupakan form yang berfungsi untuk menambahkan data pada struktur indeks dalam program simulasi. Data yang dimasukkan berupa data integer. Animasi proses pemasukan data dapat dilihat ketika data sedang dimasukkan dalam struktur indeks. Gambar 4.30 merupakan cuplikan dari form tambah data pada program simulasi.
97
Gambar 4.30 Implementasi Form Tambah Data 4.1.6.5 Form Hapus Data Form hapus data merupakan form yang berfungsi untuk menghapus data pada struktur indeks dalam program simulasi. Data yang dimasukkan berupa data integer. Animasi proses penghapusan data dapat dilihat ketika data sedang dihapus dalam struktur indeks. Gambar 4.31 merupakan cuplikan dari form hapus data pada program simulasi.
Gambar 4.31 Implementasi Form Hapus Data
98
4.1.6.6 Form Pencarian Data Form pencarian data merupakan form yang berfungsi untuk mencari data pada struktur indeks dalam program simulasi. Data yang dimasukkan berupa data integer. Animasi proses pencarian data dapat dilihat ketika data sedang dicari dalam struktur indeks. Gambar 4.32 merupakan cuplikan dari form pencarian data pada program simulasi.
Gambar 4.32 Implementasi Form Input Data Awal 4.1.6.7 Form Statistik Proses Form statistik proses merupakan form yang berfungsi untuk menjelaskan subproses yang terjadi pada proses penambahan, penghapusan dan pencarian data dalam struktur indeks pada program simulasi. Waktu eksekusi dari masing- masing subproses dapat dilihat pada form statistik proses. Gambar 4.33 merupakan cuplikan dari form statistik proses pada program simulasi.
99
Gambar 4.33 Implementasi Form Statistik Proses 4.1.6.8 Form Log Proses Form log proses merupakan form yang berfungsi untuk melihat histori dari proses dan subproses dari program simulasi yang telah dijalankan. Log proses dicatat sejak program simulasi dimulai sampai program simulasi selesai. Gambar 4.34 merupakan cuplikan dari form log proses pada program simulasi.
Gambar 4.34 Implementasi Log Proses
100
4.1.6.9 Form Preview Visual Form preview visual merupakan form yang berfungsi untuk melihat sturktur indeks pada program simulasi secara visual. Struktur indeks secara tekstual dapat dilihat dalam form utama. Gambar 4.35 merupakan cuplikan dari form preview visual pada program simulasi.
Gambar 4.35 Implementasi Form Preview Visual 4.1.6.10 Form ODS Form ODS (On Disk Structure) merupakan form yang berfungsi untuk melihat struktur indeks pada bentuk berkas. Gambar 4.29 merupakan cuplikan dari form ODS pada program simulasi.
Gambar 4.36 Implementasi Form ODS
101
4.2 Analisis dan Pembahasan Hasil Subbab ini membahas tentang analisis dan pembahasan hasil yang telah diimplementasikan dengan sistem basis data Firebird yang sebenarnya. Struktur sistem basis data Firebird dilihat dengan membaca source code Firebird versi 1.5.0.4290 dan menggunakan perangkat lunak IBSurgeon Viewer 1.0.2 dan IBAdmin 3.2.15.500. Program simulasi untuk analisis data menuliskan hasil eksekusi ke dalam sebuah berkas tanpa menjalankan animasi indeks dan tanpa menamp ilkan hasil ke dalam layar. Program analisis data untuk basis data Firebird menggunakan komponen IB pada program Delphi 6.0 yang menuliskan hasil eksekusi ke dalam sebuah berkas tanpa menggunakan antarmuka. Percobaan pada basis data Firebird menggunakan basis data dengan page 1024 Kbyte (KB) dan 8192 KB. Percobaan pada program simulasi menggunakan indeks dengan orde 2 dan orde 20. Basis data yang digunakan adalah basis data Firebird dengan 1 buah tabel dan 1 buah field yang terindeks. 4.2.1 Struktur Indeks Pada Basis Data Firebird Indeks pada sistem basis data Firebird tersimpan dalam b-tree page. Sebuah b-tree page merupakan sebuah node dalam struktur indeks pada sistem basis data Firebird. Susunan beberapa b-tree page membetuk indeks yang fungsional. Jumlah daya tampung b-tree page tergantung dari besar page yang ditentukan pada awal pembentukan basis data. Sistem basis data Firebird memberikan beberapa pilihan daya tampung tiap page yaitu sebesar 1024, 2048, 4096, dan 8192 KB. Semakin besar ukuran page berpengaruh pada jumlah data yang dapat
102
dimasukkan kedalamnya. Ukuran page yang umum pada sistem basis data Firebird adalah 1024 Kbyte. Data yang terdapat di dalam b-tree page terkompresi secara prefix dan suffix. 4.2.2 Struktur Indeks Pada Program Simulasi Indeks bertipe b+-tree digunakan dalam program simulasi. B+-tree merupakan tipe indeks yang mirip dengan indeks pada sistem basis data Firebird yang sebenarnya. Page dalam sistem basis data Firebird diwakili oleh sebuah node dalam program simulasi. Ukuran node yang digunakan dalam program simulasi ditentukan oleh orde b+-tree pada saat inisialisasi. Jumlah data yang tersimpan dalam sebuah node pada program simulasi adalah 2 x Orde b+-tree. Data yang tersimpan dalam indeks pada program simulasi tidak mengalami proses kompresi. 4.2.3 Struktur Berkas Pada Basis Data Firebird Perangkat lunak IBSurgeon Viewer 1.0.2 dapat menampilkan struktur berkas pada basis data Firebird. Sistem basis data Firebird menyimpan berkas dalam struktur yang telah ditentukan. Struktur berkas sebuah indeks yang berisi data 10, 11, 20, 40 dan 80 di dalam sistem basis data Firebird dapat dilihat dalam Gambar 4.37. Ruang pada sebuah page dalam sistem basis data Firebird akan terbuang jika sebuah basis data Firebird menggunakan ukuran page yang besar tetapi digunakan untuk menampung data yang sedikit.
103
Gambar 4.37 Struktur berkas indeks dalam sistem basis data Firebird 4.2.4 Struktur Berkas Pada Program Simulasi Program simulasi menulis struktur berkas menggunakan format yang terdapat pada sistem basis data Firebird. Program simulasi menuliskan header standar yang diikuti dengan data yang terdapat dalam susunan indeks. Data yang disimpan tidak mengalami proses kompresi. Struktur berkas pada program simulasi memerlukan ruang sebesar 1024 byte. Stuktur berkas sebuah indeks yang berisi data 10, 11, 20, 40 dan 80 di dalam program simulasi dapat dilihat dalam Gambar 4.38.
104
Gambar 4.38 Struktur berkas indeks dalam program simulasi 4.2.5 Proses Pemasukkan Data Pada Basis Data Firebird Proses pemasukan data dalam Firebird dilakukan ketika perintah insert dijalankan pada query. Perintah query insert memasukan data ke dalam tabel atau sebuah relation pada sistem basis data Firebird. Data dimasukkan ke dalam indeks jika query insert yang dieksekusi memasukan data ke dalam salah satu field yang terindeks. Gambar 4.39 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah insert pada basis data Firebird yang menggunakan ukuran page sebesar 1024 KB dan diisi 30000 data acak pada sebuah field yang terindeks.
105
Gambar 4.39 Grafik jumlah rekaman dan waktu eksekusi insert pada sistem basis data Firebird denga n page 1024 KB Gambar 4.40 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah insert pada basis data Firebird yang menggunakan ukuran page sebesar 8192 KB dan diisi 30000 data acak pada sebuah field yang terindeks.
Gambar 4.40 Grafik jumlah rekaman dan waktu eksekusi insert pada sistem basis data Firebird dengan page 8192 KB Gambar 4.39 dan Gambar 4.40 menjelaskan perbandingan waktu eksekusi perintah insert antara basis data Firebird dengan page 1024 KB dan 8192 KB. Basis data Firebird dengan page 1024 KB menjalankan query insert relatif sama dengan basis data Firebird dengan page 8192 KB.
106
4.2.6 Proses Pemasukkan Data Pada Program Simulasi Program simulasi menggambarkan proses pemasukan data ke dalam indeks. Program simulasi yang mempunyai orde indeks bernilai 2 akan mempunyai ruang data sebanyak 4 buah dan ruang pointer sebanyak 5 buah. Data acak sebanyak 30000 dimasukkan ke dalam indeks yang memiliki orde 2. Gambar 4.41 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah insert pada program simulasi dengan orde 2.
Gambar 4.41 Grafik jumlah rekaman dan waktu eksekusi insert pada orde 2 Program simulasi yang mempunyai orde indeks bernilai 20 akan mempunyai ruang data sebanyak 40 buah dan ruang pointer sebanyak 41 buah. Data sebanyak 30000 dimasukkan ke dalam indeks yang memiliki orde 20. Gambar 4.42 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah insert pada program simulasi dengan orde 20.
107
Gambar 4.42 Grafik jumlah rekaman dan waktu eksekusi insert pada orde 20 Gambar 4.41 dan Gambar 4.42 menjelaskan perbandingan waktu eksekusi perintah insert antara indeks dengan orde 2 dan orde 20. Indeks dengan orde 20 menjalankan query insert lebih cepat dari pada indeks dengan orde 2. 4.2.7 Proses Pencarian Data Pada Basis Data Firebird Proses pencarian data dalam Firebird dilakukan ketika perintah select dijalankan pada query. Perintah query select mengakses indeks ketika terdapat field yang terindeks turut terkesekusi. Gambar 4.43 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah select pada basis data Firebird dengan ukuran page 1024 KB. Eksekusi dijalankan pada sebuah field terindeks dengan 30000 data acak dan dilakukan perintah pencarian seiring dengan proses pemasukan data.
108
Gambar 4.43 Grafik jumlah rekaman dan waktu eksekusi select pada sistem basis data Firebird dengan page 1024 KB Gambar 4.44 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah select pada basis data Firebird dengan ukuran page 8192 KB. Eksekusi dijalankan pada sebuah field terindeks dengan 30000 data acak dan dilakukan perintah pencarian seiring dengan proses pemasukan data.
Gambar 4.44 Grafik jumlah rekaman dan waktu eksekusi select pada sistem basis data Firebird dengan page 8192 KB Gambar 4.43 dan Gambar 4.44 menjelaskan perbandingan waktu eksekusi perintah select antara basis data Firebird dengan page 1024 KB dan 8192 KB. Basis data Firebird dengan page 8129 KB me njalankan query select lebih cepat dari pada basis data Firebird dengan page 1024 KB.
109
4.2.8 Proses Pencarian Data Pada Program Simulasi Program simulasi menggambarkan proses pencarian data dalam indeks. Data acak sebanyak 30000 dimasukkan ke dalam indeks yang me miliki orde 2 dan dilakukan perintah pencarian seiring dengan proses pemasukan data. Gambar 4.45 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah select pada program simulasi dengan orde 2.
Gambar 4.45 Grafik jumlah rekaman dan waktu eksekusi select pada orde 2 Data acak sebanyak 30000 dimasukkan ke dalam indeks yang memiliki orde 20 dan dilakukan perintah pencarian seiring dengan proses pemasukan data. Gambar 4.46 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah select pada program simulasi dengan orde 20.
Gambar 4.46 Grafik jumlah rekaman dan waktu eksekusi select pada orde 20
110
Gambar 4.45 dan Gambar 4.46 menjelaskan perbandingan waktu eksekusi perintah select antara indeks dengan orde 2 dan orde 20. Indeks dengan orde 20 menjalankan query select lebih cepat dari pada indeks dengan orde 2. 4.2.9 Proses Penghapusan Data Pada Basis Data Firebird Proses penghapusan data dalam Firebird dilakukan ketika perintah delete dijalankan pada query. Perintah query delete mengakses indeks ketika terdapat field yang terindeks turut terkesekusi. Gambar 4.47 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah delete pada basis data Firebird dengan ukuran page 1024 KB. Eksekusi dijalankan pada sebuah field terindeks dengan 30000 data acak dan dihapus satu per satu.
Gambar 4.47 Grafik jumlah rekaman dan waktu eksekusi delete pada sistem basis data Firebird dengan page 1024 KB Gambar 4.48 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah delete pada basis data Firebird dengan ukuran page 8192 KB. Eksekusi dijalankan pada sebuah field terindeks dengan 30000 data acak dan dihapus satu per satu.
111
Gambar 4.48 Grafik jumlah rekaman dan waktu eksekusi delete pada sistem basis data Firebird dengan page 8192 KB Gambar 4.47 dan Gambar 4.48 menjelaskan perbandingan waktu eksekusi perintah delete antara basis data Firebird dengan page 1024 KB dan 8192 KB. Basis data Firebird dengan page 1024 KB menjalankan query delete relatif sama dengan basis data Firebird dengan page 8192 KB. 4.2.10 Proses Penghapusan Data Pada Program Simulasi Program simulasi menggambarkan proses penghapusan data dalam indeks. Data sebanyak 30000 dimasukkan ke dalam indeks yang memiliki orde 2 kemudian dihapus satu per satu. Gambar 4.49 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah delete pada program simulasi dengan orde 2.
112
Gambar 4.49 Grafik jumlah rekaman dan waktu eksekusi delete pada orde 2 Data sebanyak 30000 dimasukkan ke dalam indeks yang memiliki orde 20 kemudian dihapus satu per satu. Gambar 4.50 menjelaskan perbandingan antara waktu eksekusi dan jumlah data ketika menjalankan perintah delete pada program simulasi dengan orde 20.
Gambar 4.50 Grafik jumlah rekaman dan waktu eksekusi delete pada orde 20 Gambar 4.49 dan Gambar 4.50 menjelaskan perbandingan waktu eksekusi perintah select antara indeks dengan orde 2 dan orde 20. Indeks dengan orde 20 menjalankan query select lebih cepat dari pada indeks dengan orde 2. 4.2.11 Pengaruh Orde dan Ukuran Page Waktu eksekusi dipengaruhi oleh banyaknya data. Rata-rata waktu eksekusi hasil percobaan pada program simulasi dan pada basis data Firebird mendekati O(log n). Gambar 4.51 menujukkan terjadinya titik balik waktu ekseskusi terhadap 65535 data pada indeks dengan orde 2. Titik balik terjadi karena pencarian di dalam node merupakan pencarian sekuensial. Pencarian sekuensial lebih lama dibanding pencarian dengan susunan tree. Pemilihan orde yang optimal diperlukan untuk menjaga keseimbangan antara waktu akses sekuensial dan waktu akses tree dalam susunan indeks. Sistem basis data Firebird membatasi ukuran
113
page sampai dengan 8192 KB. Pembatasan ukuran page pada basis data Firebird berfungsi
untuk
mengoptimalkan
ruang
penyimpan
dalam
page
dan
mengoptimalkan waktu akses dalam page jika diakses secara sekuensial.
Gambar 4.51 Grafik jumlah rekaman dan waktu eksekusi delete pada orde 2 dengan 65535 data Orde dan ukuran page berpengaruh pada ruang penyimpan dalam berkas. Basis data Firebird dengan ukuan page kecil efektif pada data yang sedikit dan terdapat tabel yang banyak. Basis data Firebird dengan ukuran page besar efektif pada data yang banyak dengan tabel yang sedikit. Percobaan simulasi basis data Firebird dengan page 1024 KB menghasilkan ukuran berkas 6.285 KB dan simulasi basis data Firebird dengan page 8192 KB menghasilkan ukuran berkas 4.056 KB.
5BAB V PENUTUP 5.1 Kesimpulan Kesimpulan yang diperoleh dari penulisan skripsi dengan judul “B-tree Dalam Basis Data Firebird” ini adalah sebagai berikut : 1. Proses pemasukan data dan penghapusan data lebih kompleks daripada proses pencarian data. 2. Semakin besar orde menyebabkan indeks mempunyai sedikit node dan level yang dangkal dan sebaliknya untuk orde yang kecil. 3. Semakin besar orde indeks berakibat indeks menjadi dangkal dan waktu eksekusi menjadi semakin cepat. 4. Jumlah data dalam indeks mempengaruhi waktu eksekusi. Waktu yang dibutuhkan semakin bertambah secara logaritmik seiring dengan bertambahnya data. 5. Berdasarkan pengujian sistem, waktu eksekusi rata-rata dari proses pemasukan, penghapusan dan pencarian data pada program simulasi mendekati O(log n).
114
115
5.2 Saran Saran yang ingin disampaikan berdasarkan penulisan skripsi ini adalah sebagai berikut: 1. Diperlukan pengukur yang tepat untuk mengetahui waktu ekseskusi karena waktu yang diukur dibawah satu milidetik dan dipengaruhi proses lainnya. 2. Diperlukan banyak referensi tentang sistem berkas untuk pembelajaran lebih lanjut.
DAFTAR PUSTAKA Anderson, S, 1998, B+Trees, http://www.iwu.edu/~sander/C314Lectures/physicalDB/btree.html, diakses 15 September 2005. Anonim, 2005a, B-tree, http://wikipedia.org/wiki/B-tree, diakses 20 Juli 2005. Anonim, 2005b, What are Relational Databases, http://computer.howstuffworks.com/, diakses 20 Juli 2005 Anonim, 2005c, General Information, http://www.ibphoenix.com/main.nfs?a= ibphoenix&page=what_is_interbase, diakses 10 Oktober 2005 Brassard, G dan Bratley, P, 1996, Fundamentals of Algorithmics, Prentice-Hall, Inc. Chan, H dan Yashkir, D, 2002, Conceptual Architecture for InterBase/Firebird, IBPhoenix. Date, C. J., 1981, An Introduction to Database System, Addison-Wesley Publishing Company, Inc. Harrison, A, 2005, Firebird for the Database Expert, IBPhoenix. Harrison, A, 2002, Firebird (yet) another Open Source Database, IBPhoenix. Tharp, A L, 1988, File Organization And Processing, John Wiley & Sons.
116
