Sekumpulan field yang bergambung sebagai sebuah unit yang memiliki ukuran tertentu

@wisnu

UTS SBD 25 Oktober 2011 21:46

Soal2 UTS SBD 2011, terdiri dari: 1. Teori -teori 2. B-Tree dan B+ Tree (Plus) 3. Alt Query AR (Aljabar Relasional) 4. Hitung cost I/Os 5. Hashing 6. Indexing, Primary, Sekundary, Sparse, dan Dense 7. Blocking Factor 8. DDL/SQL ( dan BTreenya)

Introduction : -------------------------------------------------------Definisi : - Field ○ Elemet dasar dari suatu data , misal nama - Record ○ Sekumpulan field yang bergambung sebagai sebuah unit yang memiliki ukuran tertentu - File ○ Kumpulan dari record yang sama - Data ○ Kumpulan fakta yang memiliki arti atau informasi Struktur media penyimpanan : --------------------------------Hirarki media penyimpanan - Primari Storage ○ Chace memori ○ Main memori - Secondary Storage ○ Electrik disk ○ Magnetic disk - Tertiary Storage ○ Optical Storage ○ Tape Storage Istilah dalam Disk - Track ○ Merupakan suatu sisi melingkar pada disk yag digunakan sebagai bagian untuk menyimpan data - Sektor ○ Merupakan bagian dari track, dimana setiap sektor memiliki ukuran yang sama. - Block ○ Block merupakan pembagian dari sebuah track / kumpulan raceod yang memiliki ukuran yang fix sesuai dengan OS - Interblock Gaps ○ Bagian yang memisahkan antar block - Read/Write head ○ Bagian dari storage yang bertugas untuk membaca dan menulis - Cylinder ○ Merupakan sebuah piringan atau kumpulan track dalam sebuah disk Cara Akses Pada Disk SBD Page 1

Cara Akses Pada Disk - Waktu untuk akses ○ Seek time  Waktu yang dibutuhkan head untuk mencapai track ○ Rotational delay  Waktu yang diperlukan untuk menuju sektor/block yang dituju ○ Acces time  Waktu yang dibutuhkan menuju posisi disk yang akan dibaca/ditulis  Waktu yang diperlukan sebelum proses transfer berjalan  Seek + rotational ○ Transfer time  Waktu yang diperlukan untuk transfer dari/ke disk ○ Data transfer rate  Skala tranfer data yang dapat dilakukan disk misal 100mbps - RAID ○ Digunakan untuk meningkatkan reliablility, meningkatkan kemampuan untuk redudant arrays pada satu disk ○ Sistem RAID tersebut digunakan untuk kehandalan yang lebih tinggi dan kinerja yang lebih tinggi. ○ Ada 6 level dalam RAID

Blocking : ----------------------------------------

- Buffer management ○ Bla bla - Record ○ Merupakan sebuah unit struktur data ○ Sebuah record dapat memiliki ukuran yang fix maupun bebas ○ Misal  Tuple  Node pada tree - File ○ Adalah sekumpulan record yang tersimpan sebagai satu unit dalam disk - Blocking ○ Blocking adalah proses pemnyimpanan sejumlah record dalam sebuah block. Merujuk pada cara penempatan record dalam block ada 2 cara:  Spanning organization : dengan cara ini bisa dipastikan tidak ada ruang kosong dalam sebuah block dikarenakan semua record/ sebuah recod dapat disimpan dalam block-block yang berbeda.  Non-spanning organization : dengan cara ini dalam sebuah block bisa saja terdapat ruang kosong dikarenakan recod yang menempati block tersebut tidak sebesar block yang ada. - Blocking factor (bfr) ○ Jumlah rocord per block - Page ○ Adalah sebuah unit data transfer dari DBMS ke view side. ○ Disk block merupakan bagian terkecil dari page size. ○ Ukuran page biasanya : 1-10Kbytes ○ Page Transfer time : 1-10msec

- Record Blocking ○ Ukuran logic dari file adalah bytes/ record, dan ukuran fisik dari file adalah block Tipe Blocking SBD Page 2

○ Tipe Blocking  Fixed Blocking  Variable-length spanned blocking  Variable-length unspanned blocking

 Fixed Blocking □ Merupakan metode penempatan record dimana pada metode ini semua record data dianggap memiliki ukuran yang sama □ Kelemahan  Ukuran record harus lebih kecil dari block  Boros tempat, karena ukuran record pasti tidak sama dengan blovk  Penghapusan yang suklit dimana posisi awal data yang dihapus harus diisi.  Blocking facornya :

 Variable-length spanned blocking □ Merupakan metode penempatan record dimana ukuran record boleh beda2 dan record dapat ditaruh pada 2 block yang berbeda/ displit □ Ukuran record >= block □ Tidak ada tempat yang terbuang □ Susah diimplementasikan □ Harus ada pointer (P) antar blok jika ada data yg displit □ Ukuran block efectif ( B - P) □ Ukuran Record + maker = (R + M) □ BFR = (B-P)/(R+M)  Variable-length unspanned blocking □ Ukuran record bisa berbeda namun tidak bisa displit □ Ukuran record <=block  Wasted Space (W) □ Merupakan tempat yang tidak bisa disimpan data □ Wg = tempat yang terbuang pada gap antar block □ Wr = tempat yang terbuang karenan blocking  Transfer rate □ Merupakan rate dimana data dapat diambil atau disimpan dalam disk □ Ada 2 transfer rate :  Record transfer time ◊ Waktu untuk transfer record dengan ukuranan R  Block transfer time ◊ Waktu untuk transfer block □ Bulk transfer  Waktu untuk transfer data yang banyak

○ Metode Alokasi File  Contiguous allocation □ Satu set block di alokasikan bersamaan dengan waktu pembuatan file tersebut □ Hanya ada satu entri dalam tabel alokasi  Block mulai dan panjang file □ Bisa terjadi ragmentasi external SBD Page 3

□ Bisa terjadi ragmentasi external  Chained allocation □ Alokasi pada block individu □ Setiap blok berisi pointer untuk block berikutnya dalam chain □ Hanya ada satu entri dalam tabel alokasi  Block mulai dan panjang file □ Tidak ada externa fragmentasi □ Bagus untuk sequential file

 Indexed Allocation □ Tabel alokasi file berisi salinan jumlah level index untuk setiap file □ Index memiliki satu entri untuk setiap porsi alokasi untuk file □ Tabel alokasi berisi number blok dan indexnya ○ Exercise :

Screen clipping taken: 27/10/2011 11:49


SBD Page 4


File Organization: -------------------------------------------------------------------------------------5 penglompokan umu : - Pile - Sequential file - Indexed sequential file - Indexed file - Direct (Hashed) file

- Pile / heap ○ Pile Juga disebut dengan Heap file ○ Data baru dapat dimasukkan begitu saj ake dalam file ○ Ukuran record dan urutan field boleh beraneka ragam ○ Biasanya digunakan exhausetive search ○ Tidak memiliki structure tertentu ○ Peng-insertan data sangat efesien ○ Search sangat tidak efesien karena linier search ○ Penghapusan juga kurang efesien

- Sequential/Ordered file ○ Ukuran dan urutan yang tetap ○ Satu field adalah key field / ID unik dari record ○ Record di simpan berurutan berdasarkan key ○ Nama file dan ukuran merupakan atribut dari file ○ Penanganan  Harus menggunakan sequential search (batch system)  Binary search bisa digunakan namun harus tau ukuran dan posisi tengah dari file  Susah untuk insert data baru ○ Komponen :  Master file  Log Transaction file ○ Performance kurang bagus ○ Data baru ditempatkan ke transaction log terlebih dahulu ○ Jika log full atau dilakukan update maka log file akan di merge dengan master file - Indexed Sequential File ○ Menambahkan index untuk meningkatkan kecepatan pencarian ○ Komponen :  Index  Main file  Overflow file Proses pencarian SBD Page 5

○ Proses pencarian  Pertama index disearch untuk mencari nilai yang mendekati nilai yang akan dicari  Setelah menemukan itu, maka aka dilanjutkan search di main file dengan indikasi pointer dari index.

Index File : --------------------------------------------------------------------------------------------- Index File ○ Dengan mengindexkan atribut2 yang ada, kita bisa mempercepat proses pencarian. Seacara konsep sama dengan metode index pada buku - Klasifikasi Index File : ○ Dense Index :  Memiliki index untuk setiap search key value yang berhubungan dengan data pada file utma  Contoh :


○ Sparse (Nondense)  Hanya memiliki index untuk beberapa search key value, tidak semuanya memiliki index  Contoh :

SBD Page 6


○ Primary index  Digunakan untuk pengurutan key field di data records  adalah indeks yang didefinisikan terlebih dahulu untuk memesan sebuah kata kunci pada data.

○ Clustering Index  Merupakan index yang merupakan search key yang juga mendefinisikan sequential order dari file.  Pada clustering Index terdapat satu entri indeks untuk setiap nilai yang berbeda dari setiap field, titik entri indeks ke blok data pertama yang berisi catatan dari nilai field. Pada metode clustering index aktifitas insert dan delete relatif lebih mudah.  Contoh :

SBD Page 7


○ Secondary Index  Sebuah indeks sekunder menyediakan sarana sekunder untuk mengakses sebuah file dimana akses utama file tersebut sudah ada.  Indeks sekunder mungkin terdapat pada bidang yang merupakan candidate key dan memiliki nilai unik dalam setiap catatan, atau non-kunci dengan nilai-nilai duplikat.  Secondary Indeks adalah file yang terurut menjadi dua bidang, dimana bidang pertama adalah tipe data yang sama seperti beberapa bidang tidak terurut. Sedangkan bidang kedua adalah pointer blok atau pointer record.  Dalam Secondary indexes terdapat satu entri untuk setiap record dalam file data, oleh karena itu secondary indexes merupakan dense  Contoh :

SBD Page 8

Contoh :



SBD Page 9


○ Multi-Level Index  Menambahkan index untuk memperkecil / mepersempit jarak pencarian dari dense / undense index.  Contoh :

SBD Page 10


Tree Access Structure : ------------------------------------------------------------------------------ ISAM ○ ISAM = Indexed Sequential Access Method ○ Memiliki struktur statis. ○ Tidak mendukung bulk loading ○ Memiliki overflow ○ Search :  Dimulai dari root dan melakukan perbandingan untuk mendapat leaf( tempat data) ○ Insert :  Mencari leaf posisi yang tepat dari data ○ Delete  Mencari posisi data pada leaf ○ Strukture :

SBD Page 11


- B+Tree ○ Merupakan yang paling bnyak digunakan ○ Minimal harus terdapat 50% field dari node terisi, kecuali root ○ Mendukung Bulk Loading load data yang banyak ○ Search sama seperti ISAM namun perbedaanya B+tree memiliki struktur yang dynamic ○ Insert data pada B+tree  Mencari posisi leaf yang pass  Jika pasisi masi tersisa maka selesai  Jika tempat pada leaf sudah full maka lakukan split  Bawa ke atas nilai yang berada pada posisi yang ditengah ○ Split pada root membuat tingkat/tinggi tree bertambah ○ Pertambahan tree membuat ree menjadi  Melebar  Atau bertambah tinggi/level ke atas ○ Contoh :


Atau download di : http://www.ceng.metu.edu.tr/~karagoz/ceng302/302-B+treeind-hash.pdf - B-Tree Bisa dilihat contohnya di : SBD Page 12

○ Bisa dilihat contohnya di :  http://www.scribd.com/doc/18210/B-TREE-TUTORIAL-PPT  http://www.youtube.com/watch?v=coRJrcIYbF4

Hashing : -------------------------------------------------------------------------------------------

- Hashing adalah sebuah teknik dimana tempat peletakan data ditentukan oleh nilai pada hash field. - Pendekatan Hashing: ○ Setiap halaman disebut dengan bucket ○ Bucket di beri nomor 0 sampai N-1 ○ Jika bucket telah penuh, sebuah overflow page harus dirangkai pada bucket tersebut - Contoh Hash Index :


Query Processing : -------------------------------------------------------------------------

SBD Page 13

Sekumpulan field yang bergambung sebagai sebuah unit yang memiliki ukuran tertentu

Recommend Documents