Mengenal Flat Database, B-Tree, dan Linked list


Flat Database


1. Database

Apa itu database?
Database adalah sekumpulan data yang disimpan dengan tujuan tertentu dan susun sedemikian rupa sehingga dapat diakses, dikelola dan diperbaharui secara mudah. Walaupun definisi diatas mengungkapkan abstrak dari sebuah database seperti misalnya perpustakaan, file cabinet, dan address book, yang dimaksud disini adalah sekumpulan data yang disimpan dalam sebuah sistem komputer. Ada dua jenis utama database, yaitu transactional database dan analytical database. Transactional database digunakan untuk menyimpan data yang dinamis (mudah berubah), sedangkan analytical database digunakan untuk menyimpan data yang statis.

Sejarah singkat
Konsep penggunaan database diterapkan pada pertengahan abad 20 yang sebelumnya masih menggunakan konsep file. Sebuah file database sering dianggap sebagai suatu tabel karena strukturnya yang sama dengan tabel pada sebuah laporan yang dicetak di kertas. Dengan alasan yang sama, kolom pada dalam suatu tabel disebut sebagai field dan baris disebut dengan record.

Model-model database
Model database yang paling awal adalah berbasis model flat file (file datar), dimana semua record disimpan dalam betuk sebuah file biasa. Pada model ini, tidak ada hubungan (relationship) yang bisa didefinisikan atau dibuat diantara record-record tersebut. Dengan tidak adanya hubungan antar record, maka record-record tersebut hanya bisa diakses dengan cara berurutan (sekuensial). Sebagai contoh, jika ingin menemukan suatu record pelanggan ke 50, maka akan dilakukan pencarian dari record pertama sampai ke record 49 secara berurutan. Model ini sesuai dengan kondisi dimana semua record akan diproses secara keseluruhan, tapi tidak sesuai jika hanya ingin mencari record yang sesuai saja dalam suatu database.

Model selanjutnya adalah hierarchial model (model hirarki), yang secara luas digunakan dalam lingkungan komputer mainframe. Model ini diturunkan dari Information Management Systems pada tahun 1950an dan diadopsi oleh perusahaan-perusahaan seperti bank, asuransi dan masih digunakan hingga sampai hari ini. Model ini dirancang dengan hubungan yang terstruktur sehingga memungkinkan dan mempermudah akses terhadap suatu data atau record. Dengan menggunakan skema dari suatu pohon yang dibalik, hubungan yang terjadi dalam model hirarki ini adalah parent-child dan one-to-many. Setiap tabel parent bisa mempunyai beberapa child tabel, namun setiap child tabel hanya mempunyai satu parent tabel. Karena struktur datanya permanen, dan secara eksplisit terhubung antara satu sama lainnya, maka proses pengaksesan data akan lebih cepat. Meskipun demikian, model struktur yang bersifat kaku ini menyebabkan beberapa masalah. Penambahan child tabel tidak bisa dilakukan jika tidak terhubung dengan parent tabel. Misalnya, jika parent tabelnya adalah “Dokter” dan child tabelnya adalah “Pasien”, maka penambahan pasien akan bergantung dengan dokter. Dengan kata lain, penambahan record seorang pasien harus juga menambahkan record seorang dokter. Begitu juga jika sebuah parent tabel dihapus, maka child-child tabel dibawahnya juga akan terhapus.

Berdasarkan model hirarki pohon terbalik juga, pendekatan desain database selanjutnya dibuat yaitu network model. Model ini menerapkan hubungan yang lebih rumit dari model hirarki, sebagai contoh suatu pohon bisa memiliki cabang yang banyak. Pada model ini, tabel-tabel terhubung dalam sebuah himpunan, dimana sebuah record dalam tabel owner akan dihubungkan dengan beberapa record dalam tabel member. Seperti halnya model hirarki, pengaksesan data pada network model juga berlangsung sangat cepat. Namun demikian, model ini juga mempunyai beberapa masalah. Misalnya, seorang user harus paham betul secara menyeluruh struktur database yang ada untuk memperoleh sebuah data atau informasi. Jika strukturnya berubah, maka segala informasi yang berkaitan dengannya akan berubah juga.

Pada tahun 1970-an, hubungan antar database (database relational) dikembangkan dengan  pesat dan begitu rumit, dimana nantinya akan mendominasi penggunaan konsep ini dalam semua industri.

Apa itu database relational?
Pada model database relational, data disimpan dalam sebuah relations (relasi), biasanya disebut dengan tabel. Kumpulan dari tabel, record (atau tuples), dan fields (atau attributes) adalah komponen-komponen dasar yang membentuk suatu relasi database. Setiap data individual, disimpan dalam field di suatu tabel dan setiap record terdiri dari beberapa field yang membentuk suatu tabel.

Model database relational dikembangkan dari proposal oleh Dr. E.F. Codd yang berjudul “A Relational Model of Data for Large Shared Databanks” pada tahun 1970. Codd adalah seorang peneliti ilmiah di IBM, yang menjelaskan cara yang baik untuk mengelola data yang ada dalam jumlah besar. Model hirarki dan network pada waktu itu cenderung bermasalah dengan redundansi dan integritas data. Dengan menggabungkan disiplin ilmu aljabar, kalkulus dan lojik ke suatu data, Codd membangun suatu model yang lebih komplek.

2. Flat Database

Apa itu flat database
Sebuah flat-file database adalah database yang hanya memiliki sebuah tabel. Tabel tersebut terdiri dari sekumpulan field (kolom) dan record (baris). Sebagai contoh adalah pada tabel kartu nama berikut ini:


Gambar 1. Tabel kartu nama

Flat database bisa digunakan secara luas dalam berbagai aplikasi yang berbeda, misalnya tabel dalam wordprocessor atau dokumen HTML, ataupun worksheet disebuah spreadsheet. Tabel didalamnya bisa diurutkan berdasarkan nilai yang ada dalam kolom. Dalam spreadsheet, tabel bisa juga diquery dan dimanipulasi dengan cara tertentu. Hal ini mencerminkan sifat-sifat sebuah database yang sederhana.

Sebuah field digunakan sebagai key field (atau index field) yang akan digunakan untuk mengindek database yang nantinya akan digunakan pada waktu operasi pencarian dan pengurutan. Nilai dari primary key field haruslah unik untuk setiap record. Contohnya adalah daftar tabel kartu nama dibawah ini:


 Gambar 2. Tabel kartu nama yang diindex

Semua database bisa di index untuk menambah aksesnya. Index dalam database merupakan sebuah daftar berurutan yang berisi beberapa kolom dari sebuah tabel dengan penunjuk (pointer) yang berhubungan dengan sebuah nilai. Sebuah index memungkinkan sebuah kriteria pencarian akan dicari secara cepat dan akurat. Berbagai macam metode index yang digunakan adalah b-tree, hashes, dan linked lists.

Suatu database yang bersifat relasional (RDBMS) akan lebih menguntungkan jika diiindex, karena tidak akan mengubah aplikasi yang berhubunga dengannya. Hal ini disebabkan karena aplikasi tersebut tidak menggunakan data yang terindex secara langsung.

B-Trees (Balanced Tree Data)
B-tree adalah suatu metode untuk menyimpan dan menemukan suatu file (disebut juga records atau keys) dalam suatu database. Algoritma b-tree meminimalkan jumlah dari media yang harus dilalui untuk mencapai suatu record database yang diinginkan sehingga akan mempercepat proses.


        Gambar 3. Struktur dari sebuah tree 

B-tree lebih dianjurkan ketika pengaksesan ke nodes adalah menggunakan media harddisk bukan RAM (Random Access Memory). Dibutuhkan waktu seribu kali lebih lambat untuk mengakses elemen data dari harddisk dibanding RAM, karena struktur harddisk yang memiliki bagian-bagian mekanik yang bergerak. Metode b-tree sangat menghemat waktu dimana setiap nodes bisa mempunyai beberapa cabang (disebut dengan children) jika dibanding dengan binary-tree yang hanya mempunyai dua children. Ketika terdapat beberapa children dalam suatu nodes, maka suatu record dapat ditemukan dengan hanya melewati beberapa nodes saja dibandingkan dengan node yang hanya mempunyai dua children.

Gambar 4. Struktur dari sebuah b-tree
          
Dalam sebuah tree (pohon), record disimpan dalam suatu lokasi yang disebut leaves (cabang). Suatu record dalam b-tree selalu berada pada titik akhir. Jumlah maksimal dari children setiap node disebut order. Jumlah dari disk access yang dibutuhkan disebut depth. Pada gambar diatas (kanan) menunjukkan sebuah b-tree dengan 3 buah order untuk menuju suatu record yang ada dalam 8 leaves. Pada gambar kiri adalah binary-tree dengan depth 4 dan b-tree dengan depth 3. Jelas terlihat bahwa metode b-tree memungkinkan pengaksesan record lebih cepat dengan asumsi semua sistem parameter adalah sama.

Dalam prakteknya b-tree bisa memiliki ribuan atau jutaan record. Tidak harus semua leaves memiliki suatu record, namun paling tidak adalah separuhnya harus memiliki. Perbedaan depth antara skema b-tree dan binary-tree adalah dalam penggunaan di sebuah sistem database dimana b-tree bisa memiliki order yang lebih tinggi, misalnya 32,64,128 atau lebih. Penambahan sejumlah record dalam database akan menambah depth, begitu juga sebaliknya. Struktur tree mendukung berbagai operasi dasar termasuk search, predecessor, successor, minimu, maximum, insert dan delete dalam sebuah tree.

Hashing
      Hashing adalah perubahan string dari suatu karakter kedalam nilai dengan panjang yang tetap atau key yang merepresentasikan string aslinya. Hashing digunakan untuk mengindex dan mengambil suatu nilai pada sebuah database, dimana akan berlangsung lebih cepat jika dibanding dengan data yang asli (sebelum diindex). Metode ini juga menggunakan beberapa algoritma enkripsi.
Contoh sederhana dari penggunaan hashing dalam database adalah berikut ini. Sebuah data flat dari sekumpulan orang adalah sebagai berikut:

Abernathy, Sara
Epperdingle, Roscoe        
Moore, Wilfred             
Smith, David
(dan seterusnya, diurut berdasarkan abjad)

Setiap nama depan dari data diatas akan menjadi key dari data nama lengkap mereka. Maka, dalam sebuah mekanisme pencarian, akan dicari karakter demi karakter terhadap semua data sehingga kriteria yang dicari ditemukan. Namun, jika setiap nama diatas dihash, maka dimungkinkan untuk menghasilkan nomor dengan sejumlah digit (misalnya empat digit) yang unik untuk setiap nama. Misalnya menjadi:

7864   Abernathy, Sara
9802   Epperdingle, Roscoe
1990   Moore, Wilfred
8822   Smith, David
(dan seterusnya)

Dalam sebuah pencarian, maka pertama kali nama akan dihash dengan fungsi hash yang sama pada waktu menyimpan data tersebut (mengindex) sehingga menghasilkan suatu nilai yang akan dibandingkan pada data terindex dengan nilai tersebut. Maka secara umum pencarian dengan 10 kemungkinan (digit 0-9) akan lebih cepat dibandingkan berdasarkan 26 kemungkinan (karakter a-z). Algoritma hashing yang digunakan disebut hash function. Sebagai tambahan, untuk mempercepat pengambilan suatu data, hashing juga menggunakan digital signature.
Fungsi hash juga digunakan untuk mengindex nilai asli atau key dan digunakan kemudian  setiap kali data yang berhubungan dengan nilai atau key tersebut diambil. Maka, metode hasing selalu merupakan operasi sekali jalan (one way operation). Tidak perlu melakukan teknik reverse engineering untuk metode ini dengan menganalisa nilai-nilai yang telah dihash. Fungsi hash yang baik tidak akan menghasilkan dua nilai yang sama untuk dua masukan yang berbeda. Jika iya, maka disebut collision.

Fungsi hash yang bekerja dengan baik untuk menyimpan dan mengambil data dari sebuah database mungkin tidak maksimal jika digunakan untuk cryptographic atau error-checking. Ada beberapa fungsi hash terkenal yang digunakan dalam cryptographic, misalnya fungsi hash message-digest MD2, MD4 dan MD4 yang digunakan untuk melakukan hash terhadap digital signature kedalam nilai yang lebih sederhana yang disebut message-digest, SHA (Secure Hash Algorithm), algoritma standar yang menggunakan sebuah message-digest lebih besar (60-bit) atau mirip dengan MD4.

Linked Lists
Sebuah linked list adalah sekumpulan data yang berurut yang hanya bisa diakses berdasarkan urutannya (dari depan ke belakang atau awal ke akhir). Setiap data yang disimpan disebut node dimana berisi penunjuk (pointer) ke node berikutnya. Bentuk dari linked list bisa digambarkan seperti dibawah ini. Node digambarkan dengan sebuah kotak sedangkan pointer digambarkan dengan sebuah anak panah. Pointer NULL digunakan untuk menandai akhir dari suatu list.

Gambar 5. Linked List

          List diatas merupakan nama yang disusun berdasarkan abjad. Perbedaan antara list yang berurutan dengan sebuah array adalah dalam pengaksesan datanya. Data dalam sebuah array bisa diakses secara acak dan langsung menunjuk secara tepat ke data yang dimaksud yang diwakili oleh sebuah angka index. Sedangkan dalam linked list, data diakses secara sekuensial (berurutan).

Meskipun pencarian data dalam bentuk array lebih cepat, namun akan mengalami kesulitan ketika sebuah data baru dimasukkan kedalamnya. Mungkin saja tidak cukup ruang pada array untuk dimasuki sebuah item baru, atau dengan menambahkan array yang baru. Sedangkan dalam linked list, penambahan record baru hanya mengubah sejumlah pointer saja.

Penghapusan sebuah record dari ordered list juga hanya dengan mengubah sebuah pointer. Jika dalam array, maka semua data disebelah kanan harus dipindah kekiri untuk mengisi ruang kosong pada saat penghapusan. Maka, sekali lagi linked list lebih cepat dan luwes. Secara umum, mungkin metode linked list lebih baik jika digunakan untuk operasi penambahan dan penghapusan yang dilakukan berulang-ulang. Jadi, linked list cenderung digunakan untuk tipe data yang dinamis, sedangkan array untuk tipe data yang statis.

Perbandingan yang lain adalah berdasarkan jumlah space yang digunakan. Dengan skema array, penggunaan space mungkin akan melebihi jumlah yang diperkirakan. Namun demikian, linked list juga membutuhkan space yang lumayan untuk menyimpan setiap pointer dari suatu node. Secara umum, agak sulit ditentukan metode mana yang membutuhkan space yang lebih besar.

Share this

Related Posts

Previous
Next Post »