Apa perbedaan antara algoritma yang menggunakan struktur data dan algoritma yang menggunakan basis data?

10

Pertanyaan Umum

Apa perbedaan antara algoritma yang menggunakan struktur data dan algoritma yang menggunakan basis data?

Beberapa konteks

Ini adalah pertanyaan yang telah mengganggu saya selama beberapa waktu, dan saya belum dapat memberikan jawaban yang meyakinkan untuk itu.

Saat ini, saya sedang berusaha memperkuat pemahaman saya tentang algoritma yang, tentu saja, sangat melibatkan struktur data. Ini adalah struktur dasar seperti Bag, Queue, Stack, Priority Queue, dan Heap.

Saya juga menggunakan basis data setiap hari untuk menyimpan data yang telah diproses dan dikirim oleh pengguna akhir atau diproses oleh program. Saya mengambil dan mengirimkan data melalui DAL, yang memiliki struktur data sendiri yang dihasilkan berdasarkan tabel dalam database.

Pertanyaan saya muncul ketika saya memiliki opsi untuk mengurutkan data menggunakan database untuk mengirimkannya kembali kepada saya yang dipesan dengan cara naik / turun atau mengambil dan memuat data ke dalam logika saya, memproses data ini dalam antrian prioritas, dan mengurutkan tumpukan semua itu. Atau yang lain akan mencari catatan menggunakan database daripada memuat subset dari catatan dan menggunakan sesuatu seperti pencarian biner untuk menemukan catatan atau catatan yang saya tertarik.

Dalam pikiran saya, saya akan mencoba untuk memiliki banyak operasi yang terjadi pada database-end sebelum mengirimkannya karena komunikasi itu mahal. Ini juga membuat saya bertanya-tanya kapan Anda menggunakan algoritma dan struktur data yang didefinisikan secara ketat dalam logika Anda sendiri daripada untuk memproses data daripada database?

Jadi inilah pertanyaannya ...

Pertanyaan

  1. Apa perbedaan antara struktur data dan database?
  2. Kapan kita menggunakan algoritma yang menggunakan struktur data yang ditentukan hanya dalam logika Anda sendiri dan bukan dari database?
  3. @ Posting Harvey: Kapan metode dalam database menjadi kurang efisien untuk digunakan daripada metode dalam logika Anda sendiri?
    • @mirculixx post: Apa yang membuat suatu metode efisien?
  4. @ Posting Harvey: Bagaimana memproses data dengan struktur data lebih cepat daripada melakukannya di basis data?

Klarifikasi

  1. @Grant post: Basis data yang biasanya saya gunakan adalah relasional, dan pertanyaan-pertanyaan ini muncul karena bekerja dengan mereka. Namun, saya pikir pertanyaan-pertanyaan ini berlaku untuk setiap kerangka kerja yang bertahan lama (ketika saya mengatakan kerangka kerja, saya maksudkan dalam pengertian yang paling umum).

Saya tahu jawaban tanpa konteks spesifik itu sulit. Pokok-pokok pemikiran, saran, atau poin diskusi terutama adalah apa yang saya cari dan akan sangat dihargai!

algorithms programming-practices database data-structures hulkmeister
sumber
The datomic.com database lebih dekat ke pengguna daripada yang relasional tradisional. Apakah Anda hanya melihat basis data tradisional?
Pekerjaan
@Job Tidak, database relasional bukan satu-satunya hal yang saya pertimbangkan di sini. Ini lebih lanjut tentang memahami perbedaan antara struktur data dalam logika versus struktur data dalam database / unit persistensi.
Hulkmeister
Sebagai aturan umum saya akan mengatakan - gunakan database jika Anda bisa, tetapi jika menjadi terlalu lambat, maka gunakan struktur data. Duplikasi data (misalnya caching) buruk karena Anda harus menjaga keduanya tetap sinkron, jadi hindari kecuali Anda tidak bisa.
Ayub
Kirim data ke database hanya untuk mengurutkannya? Suka mengemudi di sekitar blok untuk mengubah pikiran Anda?

Jawaban:

18

Struktur Data sebagian besar adalah:

  1. Residen memori,
  2. Sementara,
  3. Ukurannya terbatas,
  4. Tidak masuk kembali tanpa menambahkan mekanisme konkurensi seperti kunci atau imutabilitas,
  5. Tidak memenuhi ACID ,
  6. Cepat, jika dipilih dengan cermat.

Database sebagian besar adalah:

  1. Disk-terikat,
  2. Gigih,
  3. Besar,
  4. Bersamaan aman,
  5. ACID compliant, dengan transaksional kemampuan,
  6. Lebih lambat dari struktur data

Struktur data dimaksudkan untuk diteruskan dari satu tempat ke tempat lain, dan digunakan secara internal dalam suatu program. Kapan terakhir kali Anda mengirim data dari halaman web ke server web menggunakan database, atau melakukan perhitungan pada database yang sepenuhnya ada dalam memori?

Sistem basis data menggunakan struktur data sebagai bagian dari implementasi internal mereka. Ini masalah ukuran dan ruang lingkup; Anda menggunakan struktur data dalam program Anda, tetapi sistem database adalah program dengan sendirinya.

Robert Harvey
sumber
Mengenai komentar halaman web-ke-server web, saya setuju Anda tidak akan menggunakan database di sana, tapi saya melihat kemungkinan ada servlet untuk menangani atau menerjemahkan data untuk bertahan ke database. Itu adalah antara tingkat menengah dan tingkat data di mana hal-hal menjadi sedikit kacau. Untuk menyederhanakan pertanyaan, kapan metode dalam database menjadi kurang bermanfaat untuk digunakan daripada metode dalam logika?
Hulkmeister
1
Nah, itu roti dan mentega DAL, bukan? DAL ada untuk memudahkan transisi antara objek dan catatan database. DAL bagus untuk sekitar 80 hingga 90 persen dari apa yang ingin Anda lakukan dengan database tetapi, untuk 10 hingga 20 persen sisanya, Anda mungkin ingin kembali ke SQL mentah atau prosedur tersimpan, karena lebih efisien.
Robert Harvey
Dalam contoh Anda menyortir / memfilter, Anda benar bahwa Anda mungkin ingin melakukan pemrosesan semacam itu di server database. Tetapi Anda kemungkinan besar masih akan menerima hasil pemrosesan itu sebagai beberapa bentuk struktur data.
Robert Harvey
Poin yang Anda berikan benar-benar informatif. Namun, masih ada sesuatu yang mengganggu saya tentang metode (atau algoritma) yang bekerja dengan database secara langsung atau hanya dengan struktur data secara ketat dalam logika atau keduanya. Saya melihat item 6 dari kedua daftar yang Anda letakkan, dan pertanyaan yang muncul di benak saya adalah, bagaimana yang satu lebih cepat dari yang lain? Saya selalu merasa bekerja dengan data pada sumbernya adalah cara tercepat untuk mengerjakan berbagai hal. Anda dapat memperbarui dalam posting Anda - saya akan membacanya lagi.
Hulkmeister
1
Database lebih lambat karena beberapa alasan. Meskipun demikian, caching, Anda harus membaca data dari disk, menggunakan pernyataan SQL yang harus dikompilasi, memiliki rencana eksekusi yang sering melibatkan beberapa tabel. Prosesnya jauh lebih kompleks. Selain itu, Anda umumnya masih harus mentransfer hasilnya melalui kabel, tempat Anda menerjemahkan data ke dalam struktur data sehingga Anda dapat bekerja dengannya.
Robert Harvey
6

Apa perbedaan antara struktur data dan database?

Pada tingkat abstrak, tidak ada - basis data adalah struktur data.

Pada tingkat tertentu, basis data biasanya memiliki tujuan untuk mempertahankan data, biasanya dalam format yang dioptimalkan untuk penyisipan, pembaruan, pengambilan, bergabung atau tujuan lain (atau kombinasi).

Misalnya jika Anda membandingkan tabel dalam RDBMS untuk mengatakan sebuah array data, perbedaannya mungkin pada waktu proses algoritma, jumlah kode yang harus Anda tulis, jumlah memori yang Anda butuhkan untuk menjalankan algoritma, atau fleksibilitas untuk bekerja / mengakses data dari luar program / algoritma Anda.

Kapan kita menggunakan algoritma yang menggunakan struktur data yang ditentukan hanya dalam logika Anda sendiri dan bukan dari database?

Dalam kecenderungan saya berpendapat

a) untuk menggunakan database jika Anda perlu mempertahankan data dengan cara yang dapat diakses di luar run-time atau tujuan dari algoritma tertentu.

b) untuk menggunakan struktur data Anda sendiri (dalam memori) jika kecepatan run-time penting, atau kegigihan tidak diperlukan

Misalnya, jika algoritma Anda memproses catatan pelanggan, Anda mungkin ingin menyimpan catatan pelanggan tersebut (katakanlah untuk menemukan semua pelanggan di bidang tertentu) untuk digunakan nanti oleh beberapa program / algoritma lain dan untuk tujuan yang sama sekali berbeda (katakan untuk menemukan pelanggan yang paling berharga) ). Dalam hal menggunakan database untuk bertahan, data mungkin merupakan ide yang bagus.

Namun, perlu diketahui bahwa ada konsep basis data di dalam memori yang tidak selalu bertahan dengan data, karena alasan kinerja. Misalnya Redis atau HANA .

Kapan metode dalam database menjadi kurang efisien untuk digunakan daripada metode dalam logika Anda sendiri?

Jawabannya sangat tergantung pada keadaan dan (tipe) database yang digunakan. Saya akan mengubah pertanyaan menjadi "apa yang membuat suatu metode efisien?" Ini kemudian menjadi latihan menilai metode (= algoritma) yang akan Anda gunakan untuk struktur data Anda sendiri vs metode yang digunakan oleh database. Lihat juga poin selanjutnya.

Bagaimana memproses data dengan struktur data lebih cepat daripada melakukannya di database?

Sekali lagi, ini tergantung pada spesifikasinya. Secara umum, pemrosesan data yang ada dalam memori, dapat diakses langsung ke proses yang menjalankan algoritme Anda, lebih cepat daripada mengirim permintaan ke proses lain (di komputer yang sama atau melintasi jaringan) dan memintanya untuk mengirim kembali hasilnya . Namun jika data sudah berada dalam database, mengirimkannya perintah - katakan pernyataan SQL untuk bergabung dengan dua tabel dan menghitung beberapa fungsi agregat - dan hanya mengambil ringkasan kecil atau bagian dari data mungkin jauh lebih efisien daripada pertama-tama mentransfer semua data dan menghitung hasilnya secara lokal (menggunakan struktur data Anda sendiri).

miraculixx
sumber
1

Akses disk adalah yang paling mahal dalam operasi ini, lebih sering daripada akses jaringan (http://serverfault.com/questions/238417/are-networks-now-faster-than-disks). Kecuali jika basis data Anda tidak terletak di setidaknya jaringan 1 Gbps dan jaringan yang sama dengan server aplikasi web Anda, kinerja jaringan tidak akan sebanyak masalah kinerja disk untuk kumpulan data yang lebih besar. Atau jika data Anda berada pada disk solid state yang sangat cepat yang akan lebih cepat daripada akses jaringan biasa. Selain itu, database biasanya menyediakan mekanisme IPC seperti pipa bernama daripada menggunakan TCP / IP jika database berada di server yang sama dengan server aplikasi Anda.

Jika Anda dapat menyimpan sebagian besar struktur data dalam memori di antara permintaan, maka ini umumnya akan menjadi taruhan tercepat Anda. Jika Anda tidak bisa, maka sulit untuk mengalahkan struktur database yang baik dengan tabel yang dinormalisasi dan indeks yang tepat untuk mencari dan memperbarui kinerja pada apa pun selain set kecil catatan, terutama dalam sistem dengan jutaan catatan.

Database relasional biasanya menggunakan pohon B + atau varian daripadanya di bawah tenda dan memiliki banyak optimasi seperti penyelarasan data pada disk dan buffer pool untuk catatan yang sering diakses. Ini membuat mereka unggul dalam memproses dataset besar dengan cepat, terutama jika agregasi atau penyaringan terlibat.

Peter Smith
sumber
Tolong beri tahu saya apakah saya benar. Menerapkan apa yang Anda katakan, setiap kali saya berpikir tentang bekerja dengan data, jika saya dapat menyimpan set cache dalam memori, itu lebih cepat. Jika tidak, coba gunakan basis data untuk memberikan hasil tersebut atau temukan cara untuk melibatkan permintaan lebih banyak pada basis data?
Hulkmeister
@ Hulkmeister ya secara umum, kecuali dataset sangat kecil atau database jauh ke lokasi Anda di jaringan yang lambat.
Peter Smith
0

Apa yang Anda maksud dengan database? Maksud Anda database relasional seperti MySQL, atau SQL Server? Database relasional adalah struktur meta-data yang mendukung beberapa himpunan bagian dari operasi yang didefinisikan oleh model relasional . Teori model relasional yang sebagian besar dikerjakan oleh Edgar Codd di tahun 60an.

Model relasional adalah tujuan yang sangat umum dan fleksibel, tetapi itu berarti ia tidak dapat mengambil keuntungan dari struktur dalam data atau pola akses. Struktur data berguna ketika Anda mengetahui sesuatu tentang data dan bagaimana itu akan diakses. Misalnya, jika Anda tahu data terakhir yang Anda masukkan ke dalam struktur data akan menjadi data pertama yang Anda inginkan, Anda dapat menggunakan tumpukan.

Saya menyebut basis data relasional sebagai struktur meta-data karena secara umum cukup banyak peranti lunak yang menggunakan banyak struktur data seperti tumpukan, antrian, pohon, dan daftar untuk membuat struktur data abstrak dari tabel relasional.

Charles E. Grant
sumber
Maaf, hanya perlu klarifikasi tentang apa artinya "gumpalan kecil" dalam hal paragraf terakhir?
Hulkmeister
@ Hulkmeister, maaf itu seharusnya 'besar' bukan 'sedikit'. model relasional sangat abstrak dan cukup kompleks. Memberikan implementasi yang benar-benar berkinerja memadai, terutama yang menyediakan ACID ((Atomicity, Consistency, Isolasi, Durability) membutuhkan banyak kode yang cukup canggih yang berjalan di belakang layar.
Charles E. Grant