BERKAS SORT DAN MERGE

PENGERTIAN BERKAS SORT DAN MERGE

Dalam sistem penyortiran dikenal 2 metode yaitu;

  • Metode Sort Internal
  • Metode Sort Eksternal

Perbedaannya :

ü        Pada metode sort internal, semua record yang akan diproses dimuat ke dalam memori komputer lalu diproses sort (sortir).

ü        Pada metode sort eksternal, record-record yang diproses tidak semuanya dapat dimuat ke dalam memori komputer, karena keterbatasan memori komputer.

ü        Metode sort eksternal di dalam penerapannya nanti, menggunakan pula metode sort internal.

Contoh :

Sebuah file berisi 2000 record harus disortir ke dalam memori yang hanya dapat  menampung 1000 record sekaligus. Untuk itu digunakan metode sort eksternal.

Langkah-langkah penyortiran ini adalah :

v     Record-record dibagi ke dalam beberapa file agar dapat ditampung sekaligus di memori komputer, lalu masing-masing bagian disortir internal. Bagian-bagian file yang terlah tersortir ini disebut sorted sublist.

Maka didapat :

  • Sorted sublist 1 (record 1 – 1000) dan
  • Sorted sublist 2 (record 1001 – 2000)

v     Setelah itu kedua sorted sublist ini (RUN) digabung (merge), sehingga didapat berkas gabungan (merge file) yang record-recordnya telah disortir.

Maka dapat disimpulkan langkah-langkah untuk metode sort eksternal ini adalah :

  • Sort internal, dimana file dibagi menjadi beberapa bagian file, kemudian disortir.
  • Merge, dimana bagian-bagian file ini (sorted sublist) digabung menjadi satu atau lebih file gabungan. File-file gabungan kemudian digabung lagi sampai akhirnya didapatkan sebuah file gabungan yang berisi semua record-record yang telah disortir.
    • Output, yang menyalin file gabungan yang telah tersortir ke media storage terakhir.

Faktor-faktor yang mempengaruhi metode sort eksternal :

  • Jumlah record yang akan disortir
  • Ukuran record (panjang record)
  • Jumlah storage yang digunakan
  • Kapasitas internal memori
    • Distribusi nilai key dalam input file

Teknik sort/merge file ini berbeda satu dengan yang lainnya dalam hal :

  • Metode sort internal yang digunakan
  • Jumlah main memori yang disediakan untuk sort internal
  • Distribusi dari sorted sublist di secondary storage menjadi satu atau lebih file gabungan dalam satu langkah gabungan (merge pass)

Ada 4 teknik dalam sort/merge file, yaitu :

  • Natural Merge
  • Balanced Merge
  • Polyphase Merge
    • Cascade Merge

Natural Merge

Merge yang menangani 2 input file sekaligus disebut 2 way natural merge. Merge yang menangani M input file sekaligus disebut M way natural merge. M menunjukkan derajat merge.

Pada natural merge terbagi lagi menjadi :

2 way natural merge

3 way natural merge

:

:

M way natural merge

Pada M way natural merge, dapat didefinisikan sebagai merge dengan :

M input file dan hanya 1 output file.

Contoh :

Sebuah file yang terdiri dari 6000 record hendak disortir ke dalam memori komputer yang kapasitasnya 1000 record.

Buatlah dengan menggunakan 2 way natural merge !

Lihat pula contoh 3 way natural merge, yang ditunjukkan pada :

Lihat pula contoh 2 way natural merge dengan kapasitas memori 500 record.


Lihat pula contoh 3 way natural merge dengan kapasitas memori 500 record.

Balanced Merge

Dari metode natural merge kita lihat bahwa, jika kita gunakan M input file, maka file seluruhnya yang kita gunakan adalah M + 1 file.

Sedangkan pada balanced merge, jika kita gunakan M input file, maka file seluruhnya yang dipakai adalah 2 M file.

Pada balanced merge terbagi lagi menjadi :

2 way balanced merge

3 way balanced merge

:

:

M way balanced merge

Pada balanced merge, jumlah input file sama dengan jumlah output file, walaupun pada akhirnya tak ada lagi keseimbangan antara input dan output file.


Polyphase Merge

Pada M way polyphase merge digunakan 2 M-1 input file dengan 1 output file. Jadi kita menggunakan 2 way polyphase merge, maka banyaknya input file yang digunakan ada 3 input file.

Contoh :

Setelah phase sort internal, misalkan kita mempunyai 17 subfile atau 17 run yang akan didistribusikan ke input file. Jika kita menggunakan 2 way polyphase merge, berarti 17 run tersebut harus didistribusikan ke dalam 3 input file.

Dari pendistribusian tersebut, maka diperoleh :

Lihat gambar 6

Cascade Merge

Jenis lain dari unbalanced merge yang berusaha mengurangi penyalinan/copy dari record-record disebut cascade merge.

Cascade merge dengan derajat M menggunakan :

2 M-1, 2 M-2, 2 M-3, … , kemudian 2 input file selama merge

Setiap merge pass dimulai dengan merge dari :

2 M-1 input file ke 1 output file

Pada cascade merge, pendistribusian run-nya sama dengan pendistribusian run pada polyphase merge, hanya berbeda pada phase merge-nya.


By muhamadtoni

ORGANISASI BERKAS DENGAN BANYAK KEY

PENGERTIAN ORGANISASI BERKAS DENGAN BANYAK KEY

Organisasi berkas yang memperbolehkan record diakses oleh lebih dari satu keyfield disebut organisasi berkas dengan banyak key. Ada banyak teknik yang dipakai untuk organisasi berkas dengan banyak key ini. Hampir semua pendekatan bergantung pada pembentukan indeks yang dapat memberi akses langsung dengan banyak nilai key.

Ada 2 teknik dasar untuk pemberian hubungan antara sebuah indeks dan data record dari berkas, yaitu :

_ Inversion

_ Multi-list

Organisasi berkas yang memperbolehkan record diakses oleh lebih dari satu key field disebut organisasi berkas dengan banyak key.

Ada banyak teknik yang dipakai untuk organisasi berkas dengan banyak key ini. Hampir semua pendekatan bergantung pada pembentukan indeks yang dapat memberi akses langsung dengan banyak nilai key.

Ada 2 teknik dasar untuk pemberian hubungan antara sebuah indeks dan data record dari berkas, yaitu :

  • Inversion
  • Multi-list

DEFINISI DAN APLIKASI BERKAS DENGAN BANYAK KEY

Banyak sistem informasi interaktif memerlukan dukungan dari berkas banyak key.

Contoh :

Sebuah sistem perbankan yang mempunyai beberapa pemakai (user), seperti kasir, pegawai kredit, manajer cabang, pegawai bank, nasabah dan lain-lain. Semuanya memerlukan akses data yang sama dengan format record :

Adanya pemakai yang berbeda memerlukan akses record-record ini dalam cara yang berbeda.

Kasir Mengidentifikasikan record account menurut nilai ID.
Kredit Akses semua record menurut nilai OVERDRAW LIMIT atau semua record account dengan nilai SOCNO.
Manajer Cabang Akses semua record menurut Branch dan Type.
Pegawai Bank Membuat laporan berkala untuk semua record ccount yang disortir berdasarkan ID.
Nasabah Memerlukan akses recordnya dengan memberikan ID yang dimilikinya atau kombinasi dari NAME, SOCNO dan Type.

Satu pendekatan yang dapat mendukung semua jenis akses adalah dipunyainya banyak berkas yang berbeda. Setiap berkas diorganisasi untuk melayani satu jenis keperluan.

Maka untuk contoh sistem perbankan di atas harus ada :

ü        File account yang organisasinya indeks sequential dengan nilai key

ID              untuk melayani kasir, pegawai bank dan nasabah.

ü        File account yang organisasinya sequential dengan record diurut menurut

OVERDRAW LIMIT             untuk melayani pegawai kredit.

ü        File account yang organisasinya relarif dengan nilai key

SOCNO              untuk melayani pegawai kredit.

ü        File account yang organisasinya sequential dengan record diurut menurut

GROUP-CODE            untuk melayani manajer cabang.

ü        File account yang organisasinya relatif dengan nilai key

NAME, SOCNO dan TYPE            untuk melayani nasabah.

Jadi kita mempunyai 5 file, semuanya mempunyai record yang sama. Kelima file itu hanya berbeda dalam organisasi dan cara aksesnya.

Pengulangan data dari beberapa file bukan merupakan cara yang baik untuk mengakses record dengan berbagai cara. Dan cara ini memerlukan space (ruang) yang besar di storage dan kesulitan pada waktu peng-update-an record secara serentak.

Untuk mengatasi masalah di atas, maka digunakan organisasi berkas banyak key yang umumnya diimplementasikan dengan pembentukan banyak indeks untuk memberikan akses yang berbeda terhadap record data.

Mungkin juga cara ini memakai banyak link-list terhadap record. Dan sebuah indeks dapat dibentuk dengan beberapa cara, misal sebagai tabel binary search tree atau B-tree.

ORGANISASI INVERTER  FILE

Satu pendekatan dasar untuk memberikan hubungan antara sebuah indeks dan data record dari file adalah inversi. Sebuah key pada indeks inversi mempunyai semua nilai key dimana masing-masing nilai key mempunyai penunjuk ke record yang bersangkutan. File yang demikian disebut inverted file.

Indeks inversi yang sederhana dibentuk sebagai sebuah tabel.

Contoh :

Inversi file ACCOUNT terhadap SOCNO menghasilkan indeks inversi.

SOCNO ADDRESS
001234123

123456789

213823456

299167305

399042131

411625331

412631467

426135447

445062681

459463001

513014265

612305116

626311660

692122222

713214622

798392289

821346211

912346789

923146154

987654321

6

5

14

16

4

13

7

20

17

1

8

9

18

12

3

15

2

19

11

10

Sebuah indeks inversi dapat dibuat bersama sebuah relatif file atau sebuah indeks sequential. Sebuah indeks inversi dengan key SOCNO untuk sebuah relatif file dengan nilai key  ID akan memberikan sebuah file yang dapat diakses langsung oleh sebuah ID atau SOCNO.

SOCNO ID
001234123

123456789

213823456

299167305

399042131

411625331

412631467

426135447

445062681

459463001

513014265

612305116

626311660

692122222

713214622

798392289

821346211

912346789

923146154

987654321

291821

208432

486212

534216

201431

415631

300123

696123

535218

111111

310103

324196

641230

387122

198121

511211

112131

686116

386132

335812

Jika sebuah key dipakai untuk menentukan struktur storage dari file disebut primary key, sedangkan key yang lainnya disebut secondary key.

File yang mempunyai indeks inversi untuk setiap data field disebut completely inverted. File yang bukan completely inverted tapi paling sedikit mempunyai satu indeks inversi disebut partialy inverted file.

Sebuah variasi dari struktur indeks inversi adalah pemakaian secondary key dan primary key dari indirect addressing. Pendekatan ini membiarkan file yang direorganisasi dan restructure secara fisik tanpa menyebabkan indeks file.

Pada contoh di atas, nilai SOCNO adalah unik. Setiap SOCNO dalam indeks inversi mempunyai record. Indeks inversi dapat juga dipakai dengan key yang bukan unik.

GROUP-CODE

BRANCH TYPE

ID
DT

DT

EA

NE

NE

NW

NW

WE

001

002

001

001

002

001

002

002

111111, 201431, 310103, 686116

198121, 335812, 486212, 641230

324196, 534216, 535218

415631

300123, 696123

112131, 208432, 511211

291821

386132, 387122

Satu hal yang baik dari inversi file adalah beberapa pertanyaan di bawah ini dapat dijawab tanpa akses data file, cukup dengan indeks inversinya.

  • Apakah ada indeks untuk SOCNO = ‘414556233’ ?
  • Berapa banyak account dengan GROUP-CODE = ‘EA001’ ?
  • Berapa banyak account dengann BRANCH = ‘NE’ ?
  • Apakah BRANCH = ‘NE’ mempunyai TYPE = ‘001’ ?

Organisasi Multi-List File

Suatu pendekatan lain yang memberikan hubungan antara sebuah indeks dan data record dari sebuah file disebut organisasi multi-list file.

Seperti sebuah inverted file, sebuah multi-list file mempunyai sebuah indeks untuk setiap secondary key.

Organisasi multi-list file berbeda dengan inverted file, dimana dalam indeks inversi mirip dengan organisasi relative yang satu tabel index-nya berisi key field yang terurut dan sebuah pointer yang menunjuk ke alamat di mana data disimpan. Bedanya, karena di sini dibutuhkan banyak kunci, maka di tabel tersebut disimpan pula kunci-kunci atribut lainnya yang dibutuhkan., sedangkan dalam indeks multi-list hampir sama dengan cara pertama, yaitu dibuat tabel index yang terurut key field-nya dan penunjuk ke nomor record (pertama) datanya, hanya di setiap record ditambahkan pointer (penunjuk) ke record-record berikutnya sesuai urutan key field yang ditentukannya. Tentu penunjuk itu akan berubah datanya bila akses dilakukan dengan key field lainnya.

Maka terdapat sebuah linked-list dari data record untuk setiap nilai dari secondary key.

Nilai key harus diurut, struktur indeks adalah tabel dengan indirect addressing dan mempunyai hubungan data record yang disusun menurut ID secara ascending.Informasi tentang banyak record dalam link-list juga berguna untuk mendapatkan cara yang terbaik dalam pengaksesan.

MULTI-LIST ORGANIZATION

GROUP-CODE

BRANCH TYPE

ID
DT

DT

EA

NE

NE

NW

NW

WE

001

002

001

001

002

001

002

002

111111

198121

324196

415631

300123

112131

291821

386132

Multi-List indeks untuk GROUP-CODE secondary key

OVERDRAW

LIMIT

ID
0.

100.

200.

250

111111

112131

198121

511211

Multi-List indeks untuk OVERDRAW-LIMIT secondary key

GROUP-CODE

BRANCH TYPE

ID LENGTH
DT

DT

EA

NE

NE

NW

NW

WE

001

002

001

001

002

001

002

002

111111

198121

324196

415631

300123

112131

291821

386132

4

4

3

1

2

3

1

2

Variasi pada index untuk GROUP-CODE dengan banyak record dalam link list

OVERDRAW

LIMIT

ID LENGTH
0.

100.

200.

250

111111

112131

198121

511211

7

8

1

4

Variasi pada Index untuk OVERDRAW-LIMIT, dengan banyak record dalam link list

Contoh :

Ada 3 cara akses yang potensial dalam menjawab pertanyaan :

Daftar nilai ID untuk account dengan GROUP-CODE = ‘EA001’ dan OVERDRAW-LIMIT = 100 ?

Data file dapat dicari secara sequential, indeks GROUP-CODE atau dengan memakai OVERDRAW-LIMIT.

Mana cara yang terbaik ?

Pencarian secara sequential memerlukan akses sampai 20 data record, menggunakan indeks GROUP-CODE berarti akses sampai 3 data record dan memakai indeks OVERDRAW-LIMIT berarti akses sampai 8 data record.

Dari ketiga cara di atas, yang terbaik adalah menggunakan indeks GROUP-CODE.

111111, 201431, 310103, 686116 dt

324196, 534216, 535218 ea

415631NE

112131, 208432, 511211

nw

Record

Address

ID Name Group-Code

Branch

Type SOCNO Balance Overdraw Limit
Last First
1 111111 Dean John DT 001 45946301 100.50 0.
2 112131 Amore Carol NW 001 821346211 2311.20 100.
3 198121 Rice Bess DT 002 713214622 -191.87 200.
4 201431 Parker Ola DT 001 399042131 3142.93 100.
5 208432 Anderson Barbara NW 001 123456789 95.26 0.
6 291821 Anderson Brent NW 002 001234123 146.92 0.
7 300123 Hart Allison NE 002 412631467 3000.00 100.
8 310103 Tahoe Serena DT 001 513014265 243.63 0.
9 324196 Bones Igor EA 001 612305116 0.02 0.
10 335812 Bee Vera DT 002 987654321 88.72 0.
11 386132 Arc Jean WE 002 923146154 -89.98 100.
12 387122 Ells Joshua WE 002 692122222 10.95 0.
13 415631 Belle Ellie NE 001 411625331 426.86 100.
14 486212 Matthers Ann DT 002 213823456 893.92 100.
15 511211 Snuggs John NW 001 798392289 2814.12 250.
16 534216 Loomin Tim EA 001 299167305 296.12 250.
17 535218 Ellsworth Nancy EA 001 445062681 2814.12 250.
18 641230 Wells Chuck DT 002 626311660 -98.14 100.
19 686116 Sworth Lauren DT 001 912346789 3216.16 100.
20 696123 Gunness Marion NE 002 426135447 95.93 25.

CONTOH FILE DATA

Record

Address

ID Name Group-Code Next SOCNO Balance Overdraw

Limit

Next
Last First Branch Type
1 111111 Dean John DT 001 201431 45946301 100.50 0. 208432
2 112131 Amore Carol NW 001 208432 821346211 2311.20 100. 201431
3 198121 Rice Bess DT 002 335812 713214622 -191.87 200. 0.
4 201431 Parker Ola DT 001 310103 399042131 3142.93 100. 300123
5 208432 Anderson Barbara NW 001 511211 123456789 95.26 0. 291821
6 291821 Anderson Brent NW 002 0 001234123 146.92 0. 310103
7 300123 Hart Allison NE 002 696123 412631467 3000.00 100. 386132
8 310103 Tahoe Serena DT 001 686116 513014265 243.63 0. 324196
9 324196 Bones Igor EA 001 534216 612305116 0.02 0. 335812
10 335812 Bee Vera DT 002 486212 987654321 88.72 0. 387122
11 386132 Arc Jean WE 002 387122 923146154 -89.98 100. 415631
12 387122 Ells Joshua WE 002 0 692122222 10.95 0. 0.
13 415631 Belle Ellie NE 001 0 411625331 426.86 100. 486212
14 486212 Matthers Ann DT 002 641230 213823456 893.92 100. 641230
15 511211 Snuggs John NW 001 0 798392289 2814.12 250. 534216
16 534216 Loomin Tim EA 001 535218 299167305 296.12 250. 535218
17 535218 Ellsworth Nancy EA 001 0 445062681 2814.12 250. 696123
18 641230 Wells Chuck DT 002 0 626311660 -98.14 100. 686116
19 686116 Sworth Lauren DT 001 0 912346789 3216.16 100. 0.
20 696123 Gunness Marion NE 002 0 426135447 95.93 25. 0.

CONTOH FILE DATA DENGAN STRUKTUR ORGANISASI MULTI-LIST

By muhamadtoni

index sequential

Organisasi berkas indeks sequential adalah Berkas/file yang disusun sedemikian rupa sehingga dapat diakses secara sequential maupun secara direct (langsung) atau kombinasi keduanya, direct dan sequential Data merupakan segala sesuatu yang masih dalam bentuk bahan mentah yang akan diproses. Data yang sudah diproses tersebut dan berguna bagi orang yang menerimanya ini disebut sebagai informasi. 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.

Adapun jenis akses yang diperbolehkan, yaitu :

-Akses Sekuensial

-Akses Direct

Sedangkan jenis prosesnya adalah :

-Batch

-Interactive
Struktur Berkas Indeks sekuensial

Indeks : Binary Search Tree

Data : Sekuensial

Ada beberapa tahapan dalam organisasi berkas secara sequential, yaitu :
1. Pengumpulan data
Proses dimana data yang ada dikumpulkan secara berurut berdasarkan klasifikasi yang membedakannya.
Pada tahap pengumpulan data ini, semua data akan diurutkan secara bertahap dan terorganisir dengan
baik.

2. Pemasukkan data ( input data )
Pada tahap ini, data-data yang telah dibedakan dan dikumpulkan tersebut akan secara permanent
dimasukkan ( di input ) kedalam suatu device penyimpanan. Device ( media ) penyimpanan ini dapat berupa
memori atau device penyimpanan lainnya.

3. Pengeditan data
Tahap selanjutnya yang harus dilakukan dalam proses secara sequential adalah pengeditan data. Setelah
data yang ada dikumpulkan dan proses input data juga telah dilakukan maka proses selanjutnya adalah
editing. Dalam tahap ini data yang telah di input akan diubah ( edit ).

4. Penyortiran data yang telah di edit
Tahap terakhir dalam tahap sequential ini adalah penyortiran. Setelah user melakukan pengeditan pada
data-data yang ada, maka selanjutnya data yang telah di edit tersebut kan di sortir.

Struktur Pohon

Sebuah pohon (tree) adalah struktur dari sekumpulan elemen, dengan salah satu elemennya merupakan akarnya atau root dan sisanya yang lain merupakan bagian-bagian pohon yang terorganisasi dalam susunan berhirarki dengan root sebagai puncaknya.

Pohon Biner

Salah satu tipe pohon yang paling banyak dipelajari adalah pohon biner. Pohon Biner adalah pohon yang setiap simpulnya memiliki paling banyak dua buah cabang / anak.

FILE ORGANIZATION : INDEX SEQUENTIAL
Selain organisasi berkas sequential dan relative yang telah dibahas sebelumnya, berikut akan dibahas mengenai organisasi berkas index sequential. Contoh sederhana dari organisasi ini adalah susunan data yang ada di sebuah buku kamus. Kita bisa mengakses buku kamus tersebut secara sequential (berurutan), maupun melalui index (daftar isi)nya. Jadi, file organization index sequential adalah file yang disusun sedemikian rupa sehingga dapat diakses secara sequential maupun secara direct (langsung), atau kombinasi keduanya, direct dan sequential.

By muhamadtoni