Organisasi dan akses file
| English | Bahasa Indonesia |
|---|---|
| file organisation/faɪl ˌɔːɡənaɪˈzeɪʃn/ | organisasi file |
| access method/ˈækses ˈmeθəd/ | metode akses |
| serial file/ˈsɪərɪəl faɪl/ | file serial |
| sequential file/siːˈkwenʃl faɪl/ | file berurutan |
| key field/kiː fiːld/ | bidang kunci |
| direct access/daɪˈrekt ˈækses/ | akses langsung |
| sequential access/siːˈkwenʃl ˈækses/ | akses berurutan |
| random file/ˈrændəm faɪl/ | file acak |
Mengapa pekerjaan malam bank memakan waktu sepanjang malam
- Hingga era 1980-an, akun bank tersimpan pada pita magnetik. Pita hanya dapat dibaca dari satu ujung ke ujung lainnya, sehingga transaksi harian diurutkan semalam dan seluruh file utama dibaca mulai dari awal hingga akhir, sekali, untuk menerapkan transaksi tersebut.
- Meminta saldo satu pelanggan di tengah sore dan jawabannya: belum sampai besok. Organisasi file, bukan kecepatan komputer, menentukan apa yang bisa ditawarkan bank.
- Disk memungkinkan organisasi berbeda: hitung di mana record berada berdasarkan kuncinya dan lompat ke sana. Itulah yang memungkinkan mesin ATM memberikan jawaban dalam satu detik.
- Pelajaran ini adalah organisasi file, dua metode akses, dan bagaimana memilih dari apa yang dilakukan program sebagian besar waktu.
Tiga organisasi
- File serial menyimpan record dalam urutan penambahan, tanpa pengurutan. Penambahan cepat; pencarian berarti membaca dari awal. Digunakan untuk log dan jejak audit.
- File sekuensial menyimpan record diurutkan berdasarkan bidang kunci. Pencarian lebih cepat, karena Anda dapat berhenti lebih awal atau menggunakan pencarian biner; penyisipan lambat, karena record selanjutnya harus bergeser. Digunakan untuk file master yang diperbarui secara batch.
- File acak, atau akses langsung, menyimpan setiap record pada posisi yang dihitung dari kunci recordnya, biasanya melalui hash. Pencarian berdasarkan kunci sangat cepat; membaca dalam urutan kunci sulit. Digunakan untuk tabel pencarian besar dan akun pelanggan.
Serial: urutan kedatangan, tidak lebih dari itu
Sekuensial: record yang sama, dalam urutan kunci
Dua metode akses
- Akses berurutan membaca dari awal file hingga rekaman yang diinginkan. Ini adalah satu-satunya akses yang memungkinkan file serial, dan demikian pula cara file berurutan diproses dalam batch.
- Akses langsung melompat langsung ke posisi yang diketahui tanpa membaca apa yang ada di sebelumnya. Ini adalah cara file acak dibaca, dan file berurutan juga dapat dibaca langsung ketika posisi kunci diketahui atau terindeks.
- Jadi pasangan silabusnya adalah: akses berurutan untuk file serial dan berurutan; akses langsung untuk file berurutan dan acak.
Acak: kunci memberi tahu Anda di mana harus melihat
Rute akses file
Ikuti alur file dari penyimpanan ke program dan kembali dengan aman.
File serial menyimpan rekaman:
File serial menjaga rekaman dalam urutan kedatangan — cepat untuk menambah, lambat untuk mencari. File sekuensial diurutkan berdasarkan kunci.
Cocokkan setiap organisasi file dengan cara ia menyimpan rekaman.
Serial = urutan kedatangan; sekuensial = terurut; acak = posisi terhash; indeks-sekuensial = terurut + indeks.
File acak (akses langsung) menempatkan setiap rekaman:
Kunci dikonversi (sering melalui hash) menjadi posisi, sehingga pencarian kunci tunggal sangat cepat.
Apa perbedaan antara file serial dan file sekuensial?
Urutan kedatangan versus diurutkan berdasarkan kunci. Perbedaan tunggal inilah yang membuat file sekuensial dapat dicari lebih awal dan lambat disisipkan.
Contoh kerja: pilih organisasi
- Program gaji membaca setiap rekaman karyawan sekali sebulan, sesuai urutan nomor karyawan, untuk menghasilkan slip gaji. Organisasi dan akses apa, serta alasannya?
- Organisasi berurutan dengan akses berurutan: semua rekaman diproses, jadi tidak ada keuntungan dari melompat-lompat, dan menyimpannya dalam urutan kunci berarti slip gaji keluar secara berurutan tanpa langkah pengurutan.
- Mesin ATM harus mengambil satu akun berdasarkan nomornya dalam waktu kurang dari satu detik. Organisasi acak dengan akses langsung: posisinya dihitung dari nomor rekening, sehingga hanya dibutuhkan satu pembacaan alih-alih pencarian melalui jutaan data.
- Aplikasi server web menambahkan satu baris per permintaan ke log. Serial: hanya penambahan yang penting, dan penambahan di akhir adalah hal tercepat yang bisa dilakukan file serial.
File sekuensial dapat dibaca dengan akses sekuensial maupun akses langsung.
Akses sekuensial melayani file serial dan sekuensial; akses langsung melayani file sekuensial dan acak. Hanya file serial yang terbatas pada satu metode.
Susun langkah-langkah mengambil satu akun dari file acak secara berurutan.
Tidak ada pencarian sama sekali: kunci diubah menjadi posisi dan dibaca sekali. Pengecekan terakhir menangkap tabrakan (collision).
Pertukaran, berdampingan
| serial | berurutan | acak | |
|---|---|---|---|
| urutan rekaman | saat ditambahkan | diurutkan oleh kunci | dihitung dari kunci |
| menambahkan rekaman | cepat, tambahkan | lambat, rekaman bergeser | cepat, jika slot kosong |
| menemukan satu rekaman | lambat, baca semua | lebih cepat, bisa berhenti dini | tercepat, satu baca |
| membaca dalam urutan kunci | butuh pengurutan | alami | butuh pengurutan |
- Jawaban yang benar selalu diperdebatkan dari operasi dominan: program ini melakukan apa paling banyak?
Organisasi file sekuensial sangat cocok untuk memproses setiap rekaman satu per satu.
Akses langsung cocok untuk melihat up satu rekaman.
Cocokkan setiap situasi dengan organisasi file yang sesuai.
Hanya menambah, memproses semua secara berurutan, atau melihat up satu rekaman: operasi dominan menentukan organisasi.
Contoh kerja: justifikasi perubahan
- File buku perpustakaan bersifat serial. Pencarian satu judul memakan waktu lama. Sarankan sebuah perubahan dan justifikasikan.
- Atur ulang menjadi file acak, mem-hash ISBN ke alamat, sehingga pencarian menjadi satu bacaan langsung alih-alih pemindaian seluruh file.
- Jika perpustakaan juga mencetak katalog dalam urutan judul, organisasi berurutan berdasarkan judul melayani keduanya dengan cukup baik: katalog tidak perlu diurutkan dan pencarian bisa berhenti dini atau menggunakan pencarian biner.
- Sebutkan organisasi, sebutkan metode akses, dan hubungkan keduanya dengan operasi yang disebutkan dalam soal.
Untuk menghasilkan laporan dalam urutan kunci, organisasi file terbaik adalah:
File sekuensial sudah dalam urutan kunci, sehingga membacanya secara sekuensial memberikan laporan berurutan.
Organisasi file dipilih dengan melihat operasi ____ program.
Setiap organisasi cepat pada sesuatu dan lambat pada hal lain, sehingga operasi yang paling sering dilakukan yang memutuskan.
Apa yang harus menjadi kunci, dan mengapa hashing rusak
- Akses langsung membutuhkan kunci, dan kunci harus unik untuk satu rekaman. Nama belakang bukan kunci; nomor pelanggan adalah.
- Hashing mengubah kunci tersebut menjadi alamat rekaman dalam satu perhitungan, sehingga satu bacaan mencapai rekaman terlepas dari seberapa besar filenya.
- Dua kunci berbeda dapat hash ke alamat yang sama. Itu adalah tabrakan, dan itu bukan kesalahan algoritma: itu tak terhindarkan begitu jumlah kemungkinan kunci melebihi jumlah alamat.
- Solusi yang disebut dalam skema nilai adalah area tumpukan, atau menyimpan penunjuk pada alamat menuju rantai rekaman yang membaginya. Tabrakan karena itu biaya satu bacaan ekstra, bukan kehilangan rekaman.
- Jadi perbandingan jujur adalah: hashing memberikan akses hampir konstan sampai file penuh, dan kinerjanya menurun seiring bertambahnya tabrakan. Akses berurutan tidak pernah menurun tetapi tidak pernah cepat.
Dua rekaman terhash ke alamat yang sama. Manakah yang benar? Pilih semua yang berlaku.
Tidak ada yang hilang; tabrakan memakan satu baca tambahan. Ini tidak dapat dihindari secara prinsip, karena selalu ada lebih banyak kemungkinan kunci daripada alamat.
⟦⟧ Nilai yang sering terlewat
- Serial adalah urutan kedatangan; berurutan adalah diurutkan oleh kunci. Mereka bukan sinonim, dan ujian menguji perbedaan ini secara spesifik.
- Organisasi adalah bagaimana rekaman tersusun; akses adalah bagaimana program menjangkau satu rekaman. Soal menyebutkan salah satu atau yang lain.
- File berurutan mendukung kedua metode akses; file serial hanya mendukung akses berurutan.
- Justifikasi dari operasi dominan, bukan dari "lebih cepat". Katakan lebih cepat dalam konteks apa, dan mengapa.
Anda telah memahaminya
- serial: urutan ditambahkan, tambah cepat, cari lambat, digunakan untuk log · sequential: diurutkan oleh bidang kunci, bagus untuk pemrosesan batch dan output berurutan · random: posisi dihitung dari kunci rekaman, satu baca untuk menemukan rekaman
- akses berurutan membaca dari awal; akses langsung melompat ke posisi
- akses berurutan melayani file serial dan berurutan; akses langsung melayani file berurutan dan acak
- pilih dari operasi dominan: proses semuanya, cari satu, atau hanya tambahkan