i

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

ii

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.

iii

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

iv

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,

dorongan 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.

v

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.

vi

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

vii

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

viii

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

ix

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

x

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

xi

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

xii

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

xiii

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).

1

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.

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 B-

tree, 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.

7

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.

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 Management 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 kesatuan 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 “b-

tree” 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 Penambahan 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 Leaf Page

Jumlah Key Index Page

Aksi

Tidak di bawah faktor

pengisi

Tidak di bawah faktor pengisi

Rekaman dihapus dalam leaf page kemudian key diurutkan untuk mengisi kekosongan. Key berikutnya akan digunakan untuk key indeks jika rekaman yang dihapus merupakan key pada indeks.

Di bawah faktor pengisi

Tidak di bawah faktor pengisi

Leaf page dan sibling digabungkan kemudian mengubah index page.

Di bawah faktor pengisi

Di bawah faktor pengisi

1. Leaf page dan sibling digabungkan. 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 source-

nya. 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 Yaskhir (2002) menjelaskan proses operasi dalam

Firebird/Interbase. Firebird/Interbase terdapat berbagai langkah untuk

mengeksekusi setiap permintaan.

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 16-

bit 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 non-

binary. 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.

Tabel 2.3 Simbol dan fungsi diagram alir No Simbol Fungsi 1

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.

5

Simbol keputusan digunakan untuk suatu penyeleksian kondisi di dalam program

6

Simbol proses terdefinisi digunakan untuk menunjukkan suatu operasi yang rinciannya ditunjukkan di tempat lain.

7

Simbol penyisipan digunakan untuk memberi nilai awal suatu besaran.

8

Simbol titik terminal digunakan untuk menunjukkan awal dan akhir dari suatu proses.

43

No Simbol Fungsi 9

Menunjukkan dokumen input dan output baik untuk proses manual, mekanik, atau komputer

10

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.

Tabel 2.4 Simbol dan fungsi DAD No Simbol Fungsi 1

Merepresentasikan objek sistem yang dapat mengirim data atau menerima data dari sistem

3

Menunjukkan perpindahan data dari satu titik ke titik yang lain

3

Menunjukkan adanya proses transformasi

4

Menunjukkan tempat penyimpanan data

45

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

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 dalam 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 dimasuki 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 penghapusan

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 Rancangan 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

71

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 pemrograman 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 ID dengan tipe data integer yang berfungsi sebagai

identitas node, D dengan tipe data integer yang menginformasikan jumlah data

yang tersimpan dalam node tersebut, Data dengan tipe data TData yang berfungsi

untuk menyimpan key dalam larik bertipe data integer, P dengan tipe data TPNode

yang berfungsi untuk menyimpan penunjuk node di bawahnya dalam larik bertipe

data PNode, Next dengan tipe data PNode yang berfungsi sebagai penunjuk sibling

sebelah kanan dari leaf node, Prev dengan tipe data PNode yang berfungsi sebagai

penunjuk sibling sebelah kir i dari leaf node dan isLeaf 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.

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); //default orde = 2 Create := 0; NodeBaru(Index); //root = Index Index^.isLeaf := True;

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 2*Orde dan jumlah pointer ke node

berikutnya sebesar (2*Orde)+1. 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 rekursif yang digunakan. Prosedur insert

membutuhkan parameter Node dan Data. Prosedur insert mengembalikan nilai

ChildNode 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 sebuah 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<newTree^.D do begin {pindah data dan pointer dari i+1 ke i} inc(i); end; {kosongkan data dan pointer terakhir} dec(newTree^.D); Index := newIndex;

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 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.6 menjelaskan potongan kode program tentang proses pencarian yang

menggunakan metode rekursif.

i:=0; while ((i<Node^.d) and (Data>Node^.data[i])) do begin inc(i); //mencari posisi yang tepat untuk penambahan end; if ((i<Node^.d) and (Data=Node^.data[i])) then begin ChildNode :=nil; Exit; //jika data sudah ada maka keluar dari prosedur end else begin Insert(Node^.p[i],Data,ChildNode); //Rekursif ke node di lain level ... {jika ChildNode<>nil} ... 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<Node^.Data[i] 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<Node^.Data[i]) or (Node^.Data[i]=-1) then break else if Data=Node^.Data[i] then begin ChildNode :=nil; Exit; //jika data sudah ada maka keluar dari prosedur end; inc(i); end;

Gambar 4.7 Potongan 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<Node^.D do begin {masukan data baru dan geser data dan pointer sebelumnya} inc(i); end; ChildNode := nil;

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<Node^.D) do begin {masukan data baru dan geser data dan pointer sebelumnya} {Data dan P akhir berisi data dan pointer yang overflow} inc(i); end; NodeBaru(tempr); //node baru i:=OrdeIndex; j:=0; while (i<Node^.D) do begin {pindah sebagian data dari Node[i] ke tempr[j]} inc(i); inc(j); end; {data dan pointer overflow dimasukan ke tempr[j]} tempr^.D := j+1; Node^.D := OrdeIndex; {Node^.Next dan Node^.Prev sibling disesuaikan karena terdapat Node baru} ChildNode := tempr; //node baru menaikkan middle key ke index level berikutnya

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<Node^.D do begin {masukan data baru dan geser data sebelumnya} inc(i); end; ChildNode := nil; 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 yang 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<Node^.Prev^.Data[i]) or (Node^.Prev^.Data[i]=-1) then break; inc(i); end; inc(Node^.Prev^.D);

79

Node^.Prev^.Data[i] := DataRotasi; Node^.Data[0] := -1; i:=0; dec(Node^.D); while i<Node^.D do begin {pindah data dari i+1 ke i} inc(i); end; {kosongkan data ke i} i:=0; while i<=Node^.D do begin {cari posisi data yang tepat} inc(i); end; inc(Node^.D); while i<Node^.D do begin {masukan data baru dan geser data sebelumnya} inc(i); end; inFound := False; i:=0; while i<IndexRotasi^.D do begin {Cari posisi yang cocok dengan DataRotasi} inc(i); end; if inFound then IndexRotasi^.Data[i] := Node^.Data[0]; ChildNode := nil;

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 (Data<Node^.Data[i]) or (Node^.Data[i]=-1) then break; inc(i); end; while (i<Node^.D) do begin {masukan data baru dan geser data sebelumnya} inc(i); end; i:=Node^.Next^.D; while i>0 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<IndexRotasi^.D do begin {Cari posisi yang cocok dengan DataRotasi} inc(i); end; if inFound then IndexRotasi^.Data[i] := Data; ChildNode := nil;

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. Node baru disisipkan

pada urutan sekuensial dari leaf node. Kode program tempr^.Next := Node^.Next,

Node^.Next := tempr, tempr^.Prev := Node dan if tempr^.Next<>nil then

tempr^.Next^.Prev := tempr 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<Node^.D) do begin {masukan data baru dan geser data sebelumnya} inc(i); end; NodeBaru(tempr); tempr^.isLeaf := True; tempr^.Level := Node^.Level; inc(Levels[tempr^.Level]); i:=OrdeIndex; j:=0; while (i<Node^.D) do begin {pindah sebagian data dari Node[i] ke tempr[j]} inc(i); inc(j); end; {data dan pointer overflow dimasukan ke tempr[j]} tempr^.D := j+1; Node^.D := OrdeIndex; {Node^.Next dan Node^.Prev sibling disesuaikan karena terdapat Node baru} ChildNode := tempr; //Data[0] dinaikkan ke indeks untuk menjadi key

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 Node, Data dan ParentNode. Prosedur delete

mengembalikan nilai integer 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^.d) and (Data>=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 i<Node^.D do begin {geser data dan pointer dari i ke i-1} inc(i); end; {kosongkan data dan pointer ke i-1} Dec(Node^.D); if (ParentNode<>nil) 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<Node^.D do begin {geser data dan pointer dari i+1 ke i} inc(i); end; {kosongkan data dan pointer ke i} Result := -1; end;

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<Node^.D do begin {geser data dan pointer dari i ke i-1} inc(i); end; {kosongkan data dan pointer ke i-1} Dec(Node^.D); end else

86

begin {Next dan Prev sibling pointer disesuaikan} NodeDelete(Node^.P[i+1]); Node^.P[i+1] := nil; Dec(Node^.D); while i<Node^.D do begin {geser data dan pointer dari i+1 ke i} inc(i); end; {kosongkan data dan pointer ke i} end; {cari node yang menujuk ke Node^.Prev}; if ParentNode<>nil 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<Node^.D do begin {Pindah data dan pointer Node[i] ke Node^.Prev[j]} inc(i); inc(j); dec(Node^.D); inc(Node^.Prev^.D); end; {Node^.Next dan Node^.Prev sibling disesuaikan}

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 i<Node^.D do begin {geser data dan pointer dari i ke i-1} inc(i); end; {kosongkan data dan pointer ke i-1} Dec(Node^.D); end else begin {Next dan Prev sibling pointer disesuaikan} NodeDelete(Node^.P[i+1]); Node^.P[i+1] := nil; Dec(Node^.D); while i<Node^.D do begin {geser data dan pointer dari i+1 ke i} inc(i); end; {kosongkan data dan pointer ke i} end; IndexTemp := Index; {cari node yang menujuk ke Node^.Next}; if IndexTemp<>nil 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<Node^.D do begin {geser data dan pointer dari i ke i-1} inc(i); end; {kosongkan data dan pointer ke i-1} Dec(Node^.D); Result := -1; end else begin {Next dan Prev sibling pointer disesuaikan} NodeDelete(Node^.P[i+1]); Node^.P[i+1] := nil; Dec(Node^.D); while i<Node^.D do begin {geser data dan pointer dari i+1 ke i} inc(i); end; {kosongkan data dan pointer ke i} Result := -1; end;

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 i<Node^.D do begin Node^.Data[i] := Node^.Data[i+1]; inc(i); end; Node^.Data[i] := -1; if (ParentNode<>nil) 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<Node^.D do begin Node^.Data[i] := Node^.Data[i+1]; inc(i); end; Node^.Data[i] := -1; i:=0; j:=Node^.Prev^.D; while i<Node^.D do begin Node^.Prev^.Data[j] := Node^.Data[i]; inc(i); inc(j); dec(Node^.D); inc(Node^.Prev^.D); end;

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<Node^.D do begin Node^.Data[i] := Node^.Data[i+1];

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<IndexTemp^.D do begin if IndexTemp^.Data[i]=Datatemp then begin found := true; break; end; inc(i); end; if found then IndexTemp^.Data[i] := Node^.Next^.Data[0]; end;

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 i<Node^.D do begin Node^.Data[i] := Node^.Data[i+1]; inc(i); end; Node^.Data[i] := -1; if (ParentNode<>nil) 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 SearchRec merupakan

prosedur rekursif yang digunakan. Prosedur SearchRec membutuhkan parameter

Node dan Data. 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 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^.d) and (Data>=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 i. Data ditemukan jika

Data=Node^.Data[i] pada larik data yang diakses oleh probe.

i:=0; while i<Node^.D do begin if Data=Node^.Data[i] then begin //DATA DITEMUKAN Exit; end; inc(i); end;

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

menampilkan 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 dengan 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 menjalankan 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 memiliki 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.

114

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).

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.

116

DAFTAR PUSTAKA

Anderson, S, 1998, B+Trees, http://www.iwu.edu/~sander/C314-Lectures/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.