Sistem Berkas(Sekuential Berindeks)

1. Index Sequential File

         1.1 Pengertian Index Sequential File

               Index Sequential File merupakan perpaduan terbaik dari teknik Sequential dan random file. Teknik penyimpanan yang dilakukan, menggunakan suatu index yang isinya berupa bagian dari data yang sudah tersortir. Index ini diakhiri denga adanya suatu pointer (penunjuk) yang bisa menunjukkan secara jelas posisi data yang selengkapnya. Index yang ada juga merupakan record-key (kunci record), sehingga kalau recordkey ini dipanggil, maka seluruh data juga akan ikut terpanggil.

              Untuk membayangkan penyimpanan dan pembacaan data secara Sequential, kita bisa melihat rekaman lagu yang tersimpan pada kaset. Untuk mendengarkan lagu kelima, kita harus melalui lagu kesatu, dua, tiga dan empat terlebih dahulu. Pembacaan seperti inilah yang disebut sebagai Sequential atau berurutan. Untuk membayangkan penyimpanan data dengan menggunakan teknik index Sequential ini, kita bisa melihat daftar isi pada sebuah buku. Pada bagian disebelah kiri disebut sebagai index data yang berisi bagian dari data yang ada. Index data kemudian diakhiri dengan pointer yang menunjukkan posisi keseluruhan isi data.

       Sebuah data yang terdiri Nomor, Nama, NL1, Nl2, dan NL3 bisa disimpan dengan menggunakan Nomor sebagai Index. Apabila data tersebut dicetak, maka akan dihasilkan suatu data yang berurutan berdasar Nomor. Nomor yang ada akan tersusun dengan urutan dari kecil keurutan yang lebih besar. Dari data yang ada, juga bisa dibuat Nama sebagai Index. Apabila data tersebut dicetak, maka akan dihasilkan suatu data yang berurutan berdasar Nama. Nama yang ada akan tersusun dengan urutan dari kecil keurutan yang lebih besar. Peluang yang memiliki abjad terkecil, akan menempati posisi pertama dan Rino pada posisi terakhir.

      Sesuai dengan sifat media yang dimilikinya, maka pada sebuah pita magnetic tape, hanya bisa menyimpan data secara Sequential; Dengan demikian, cara pembacaan yang dilakukan juga hanya secara Sequential, yaitu berurutan satu persatu sampai nomor record yang dikehendaki diketemukan. Dengan menggunakan Direct Access Methode (metode pembacaan/penulisan secara langsung), maka, recordyang tersimpan didalam sebuah disket, Hard-disk, CD ROM ataupun Laser-Disk dapat di-access secara langsung dengan tanpa harus membaca seluruh data yang dimilikinya.

      Access dengan menggunakan methoda Index-Sequential juga dapat dilakukan oleh media ini. Dengan melakukan access pertama kali pada key-field yang ada, maka akan diketemukan recordyang dituju. Data yang sudah terekam dalam methoda index-Sequential juga dapat dilakukan pembacaan secara Sequential. Key-field akan dibaca pertama kali secara Sequential, dan untuk selanjutnya recordyang dituju akan diketemukan.


1.2 Keuntungan Index Sequential File
      Sangat cocok untuk digunakan menyimpan batch data ataupun individual data. Dibanding Sequential file, pemanggilan data menjadi lebih cepat.


1.3 Kerugian Index Sequential File
      Access (pemanggilan) data tidak bisa disamakan dengan random (direct access file). Memerlukan adanya ruangan extra didalam memory untuk menyimpan index data. Memerlukan adanya hardware dan software yang lebih kompleks.

Suatu Tape dengan Panjang 2400 feet, Density 1600 Bpi dan Panjang Gap ¾ inchi. Jika 1 record berukuran 80 karakter , berapa banyak data yang dapat disimpan jika blocking factornya 5 record / blok !

1.4 Jenis Acces yang di perbolehkan dalam Berkas Indeks Sequential

Akses SekuensialØ
Akses DirectØ
Sedangkan jenis prosesnya adalah :
BatchØ
InteractiveØ
Struktur Berkas Indeks sekuensial
Binary Search Tree® Indeks Ø
Sekuensial® Data Ø

Implementasi Organisasi Berkas Indeks Sequential

1.5 Ada 2 pendekatan dasar untuk mengimplementasikan konsep dari organisasi berkas indeks sequential :
Blok Indeks dan Data (Dinamik)Ø
Prime dan Overflow Data Area (Statik)Ø
Kedua pendekatan tersebut menggunakan sebuah bagian indeks dan sebuah bagian data, dimana masing-masing menempati berkas yang terpisah.

Alasannya :
Karena mereka diimplementasikan pada organisasi internal yang berbeda. Masing-masing berkas tersebut harus menempati pada alat penyimpan yang bersifat Direct Access Storage Device (DASD).

Kinerja File Index  Sequential

Ukuran Record (R)

    R = a V + P

    a : Jumlah atribut

    V : Panjang rata – rata nilai atribut

    P : Ukuran field tambahan untuk tombstone

 Jumlah record file indexed sequential

    n = nm + o’

nm : Jumlah record di file utama

o’ : Jumlah record di overflow area

Jumlah entri index level pertama (i1)

  i1 = nm / Bfr

Jumlah entri index level berikutnya

I(level)=i(level)-1/y

Jumlah block yang dibutuhkan pada suatu level

Bi(level)=i(level)/y=i(level)+1

Total ruang index

SI = (bi1+ bi2+ ...+ 1) B = (i2+ i3+ ...+ 1) B

Total ruang per record

Rtotal= (nm.R + o’.R + SI) / n

Waktu fetch record tertentu (TF),ditentukan oleh :

–Akses index, TAn= x (s+ r + btt)

–Akses main file, TAq= s + r +btt

–Akses overflow, TAo=(o’/ n)(s+ r + btt)

dengan o = jumlah record yang di-insert

Jika overflow masih kosong, maka :

TF= TAn+ TAq

     = x(s+ r + btt) + (s+ r + btt)

     = (x+ 1) (s + r + btt)

Jika overflow telah terisi, maka :

TF= TAn+ TAq+ TAo

     = x (s+ r + btt) + (s + r + btt) + (o’ / n)(s + r + btt)

     = (x + 1 + o’ / n)(s + r + btt)

Waktu pembacaan Next Record (T)

–Jika next record di Main File :

  TN = (1 / Bfr) (s + r + btt)

–Jika next record di Overflow :

  TFo = (o’ / nm) (r + btt)

  TN = (1 / Bfr) (s + r + btt) + TFo

Waktu penyisipan record (TI)

–Baca dan tulis ulang record predesesor

–Baca  dan  tulis  ulang  block  overflow  untuk  record  yang di

push atau di-insert

  TI = TF + TRW + r + btt + TRW

    = TF + 5r + btt

Waktu update record (TU)

–Terhadap bukan kunci

TU= TF + TRW

–Terhadap kunci

•Record yang diubah, ditandai untuk dihapus

•Record baru disisipkan

TU = TF + TRW + TI

•Waktu pembacaan seluruh record (TX)

–File  dibaca  serial  mulai  dari  awal  hingga  akhir  file,  dengan

mengikuti rantai overflow jika ada.

TX= TF+ (n+ o’– 1) TN

     = [ (n + o’ . Bfr) / Bfr) ] (r + btt)

Reorganisasi dilakukan jika :

–        Telah terjadi overflow pada overflow area

–        Telah terjadi rantai yang panjang

–        Proses akses data lambat

Proses reorganisasi :

–        Baca file secara serial

–        Tulis kembali ke file baru tanpa menyertakan record yang ditandai untuk dihapus

–        Buat index

–        Buat index untuk tiap block index hingga block index terakhir selesai dibuat

–        Hapus main file dan index lama

Waktu reorganisasi (T_Y)

T_Y = [ (n + o’ . Bfr) / Bfr ] (r + btt) + (n + o’ – d) (R / t’) + (SI / t’)

Dengan :          n  = Jumlah record pada main file

                        o’ = Jumlah record pada overflow area

                        d  = Jumlah record yang ditandai untuk dihapus

[ (n + o’ . Bfr) / Bfr ] (r + btt) è Waktu pembacaan main file secara serial

(n + o’ – d) (R / t’) è Waktu penulisan kembali ke file baru

(SI / t’) è Waktu pembentukan index

2. Contoh Soal

Soal 1

Diketahui:

                P          =     2400 feet

                D         =     1600 Bpi

                IRG    =     3/4 inchi 

                           =     0.75 inchi

                C        =     80 character

                BF      =     5 record/block

JAWABAN :

Soal 2

Diketahui file indexed sequential disimpan pada

harddisk dengan parameter :

–        Putaran disk = 8000 rpm

–        Seek time (s) = 5 ms = 0,005 s

–        Transfer rate (t) = 2 KB / s

–        T_RW = 2r

–        Ukuran block (B) = 4096 byte

–        Ukuran pointer block (P) = 8 byte

–        IBG (G) = 1024 byte

–        Metode blocking = Fixed Blocking

Parameter file :

–        Jumlah record di main file (n_m) = 1.000.000 record

–        Jumlah field (a) = 8 field

–        Panjang nilai (V) = 25 byte

–        Jumlah record di overflow (o’) = 5000 record

–        Waktu pemrosesan block (c) = 2 ms = 0,002 s

Hitunglah :

Fan out (y), height (x), R_total, T_F, T_N, T_I, T_U, T_X, T_Y, dan W

Jawab:

y = B / (V + P) = 4096 / (25 + 8) = 4096 / 33 = 124

x = ^y log (n / Bfr)

R = a . V + P = 8 (25) + 8 = 208 byte

Bfr = B / R = 4096 / 208 = 19 record

n = n_m + o’ = 1000000 + 5000 = 1005000 record

x = ^y log (n / Bfr) = ¹²⁴ log (1005000 / 19) = ¹²⁴ log (52895) = 3

•          R_total = (n_m.R + o’.R + SI) / n

i₁ = n_m / Bfr = 1000000 / 19 = 52632

i₂ = i1 / y = 52632 / 124 = 425

i₃ = i2 / y = 425 / 124 = 4

i₄ = i3 / y = 4 / 124 = 1

SI   = (i2 + i3 + … + 1) B

      = (425 + 4 + 1) 4096 = (430) 4096 = 1761280

R_total = (n_m.R + o’.R + SI) / n = (n. R + SI) / n

                    = (1005000 . 208 + 1761280) / 1005000 = 209 byte

•          T_F = (x + 1 + o’ / n) (s + r + btt)

r = (60 . 1000) / (2 rpm) = 60000 / (2. 8000) = 3,75 ms = 0,00375 s

btt = B / t = 4096 / 2048 = 2 s

T_F  = (x + 1 + o’ / n) (s + r + btt)

      = (3 + 1 + 5000 / 1005000) (0,005 + 0,00375 + 2)

      = (4,00497) (2,00875) = 8,045 s

T_N = (1 / Bfr) (s + r + btt) + T_Fo

T_Fo = (o’ / n_m) (r + btt)

                  = (5000 / 1000000) (0,00375 + 2) = 0,01 s

T_N  = (1 / Bfr) (s + r + btt) + T_Fo

      = (1 / 19) (0,005 + 0,00375 + 2) + 0,01 = 0,116 s

T_I = T_F + 5r + btt = 8,045 + 5 (0,00375) + 2 = 10,06 s

T_U (Non Kunci) = T_F + T_RW = T_F + 2r

                           = 8,045 + 2 (0,00375) = 8,0525 s

T_U (Kunci) = T_F + T_RW + T_I = T_F + 2r + T_I

                  = 8,045 + 2 (0,00375) + 10,06 = 18,1125 s

T_X  = T_F + (n + o’ – 1) T_N

                  = 8,045 + (1005000 + 5000 – 1) 0,116

                  = 8,045 + 117159,884 = 117167,93 s

T_Y = [ (n + o’ . Bfr) / Bfr ] (r + btt) + (n + o’ – d) (R / t’) + (SI / t’)

W = G / Bfr = 1024 / 19 = 53 byte

t’    = (t / 2) (R / (R + W)) = (2048 / 2) (208 / (208 + 53)) = 816,06 s

T_Y  = ((n + o’ . Bfr) / Bfr) (r + btt) + (n + o’ – d) (R / t’) + (SI / t’)

      = ((1005000 + 5000 . 19) / 19) (0,00375 + 2) + (1005000 + 5000 – 0) (208 / 816,06) + (1761280 / 816,06)

      = (57894,74) 2,00375 + 1010000 (0,255) + 2158,273

      = 375714,86 s
SSoal 2

Parameter Harddisk
- Putaran Disk = 8000 RPM
- Seek Time (S) = 5 ms
- Transfer Rate (t) = 2048 byte/ms
- Waktu untuk pembacaan dan penulisan (TRw) = 2 ms

Parameter Penyimpanan
- Metode Blocking : Fixed Blocking
- Ukuran Block (B) : 4096 Byte
- Ukuran Pointer Block (P) : 8 byte
- Ukuran Interblock Gap (G) = 1024 byte

Parameter file
- Jumlah record di file (n) = 1.000.000 record
- Jumlah field (a) = 25 field
- Jumlah rata-rata nilai (V) = 8 byte

Parameter Reorganisasi
- Jumlah Penambahan Record (o) = 5000 record
- Jumlah Record ditandai sebagai dihapus (d) = 200 record


Hitung Y, X, R, Tf, Tn, Ti, Tu, Tx, Ty..!

Jawaban :

1. Y ?
   Y = (B) / (V+P)
   Y = 4096 / (25 + 8)
       = 4096 / 33
       = 124,12

2. X ?
   > R = a.V + P
          = 25 . 8 + 8
          = 208

   > Bfr = B / R
            = 4096 / 208
            = 19,69

  > X = ( ^yLog (n / Bfr))
           = ( ^124,12Log (1.000.000 / 19,69))
         = ^124,12Log 50.787,20
         =  log 50.787,20 

                log 124,12

         =  4,70

             2,09

         = 2,24

3. R ?

    R = a.V + P

          = 25 . 8 + 8
          = 208

4. Tf ?
    Btt = b / t
          = 4096 / 2048
          = 2

    r = 1/2 x ((60 x 1000) / RPM)
      = 1/2 x ((60 x 1000) / 8000)
      = 1/2 x 7,5
      = 3,75

   Tf = (x + 1 + o / n) x (s + r + btt)
       = (2,24 + 1 + 5000 / 1.000.000) x (5 + 3,75 + 2)
       = (3,24 + 0,005) x 10,75
       = 3,245 x 10,75
       = 34,883

5. Tn ?
    Tn = ((1 / Bfr) x (s + r + btt)) x ((o / n) x (r + btt))

         = ((1 / 19,69) x (5 + 3,75 + 2) x ((5000 / 1.000.000) x ( 3,75 + 2))

         = (0,05 x 10,75) x (0,005 x 5,75)

         = 10,8 x 0,02

         = 0,216

6. Ti ?

    Ti = Tf + TRw + r + btt + TRw

        = 34,883 + 2 + 3,75 + 2+ 2

        = 44,633

7. Tu ?

    Tu = Tf +TRw + Ti

         = 34,883 + 2 + 44,633

         = 81,516

8. Tx ?

    Tx = Tf + (n + o - 1) Tn

         = 34,833 + (1.000.000 + 5000 - 1) . 0,216

         = 34,833 + (1.004.999) . 0,216

         = 34,833 + 217 079,78

         = 217.114,61

9. Ty ?
     WG = G/Bfr
            = 1024 /  19,69
            = 52
     WR = B/Bfr

            = 4096 / 19,59

            = 208,02

     W   = WG + WR

            = 52,006 + 208,02

            = 260.02

     t' = (t/2) x {R/(R+W)}
       = (2048 / 2) x {208 / (208 + 260,02)}
       = 1024 x {208 / 468,02}
       = 1024 x 0,44
       = 450,56

    TY = (((n + (o x Bfr)) / Bfr) x (r + btt)) + (((n + o) - d) x (R / t')) + ((V + P) /r)
          = (((5000+(1.000.000x19,69))/19,69)x(3,75+2)+(((5000+1.000.000)-200)x(208/450,56))+((8+8/3,75)
            = (5000+19.690.000/19,69) x 5,75 + (1.004.800 x 0.46) + 10,13
          = 1.005.000 x 5.75 + 462.208 + 10,13
          = 5.778.750 + 462.218,13
          = 6.240.968,13

 

s