Hei Habr! Untuk perhatian Anda, saya persembahkan terjemahan artikel tersebut
"Bagaimana cara kerja database relasional".

Ketika berbicara tentang database relasional, saya merasa ada sesuatu yang hilang. Mereka digunakan dimana-mana. Ada banyak database berbeda yang tersedia, mulai dari SQLite yang kecil dan berguna hingga Teradata yang kuat. Namun hanya ada sedikit artikel yang menjelaskan cara kerja database. Anda dapat mencari sendiri menggunakan "howdoesarelationaldatabasework" untuk melihat seberapa sedikit hasil yang ada. Apalagi artikel-artikel ini pendek. Jika Anda mencari teknologi menarik terbaru (BigData, NoSQL, atau JavaScript), Anda akan menemukan artikel lebih mendalam yang menjelaskan cara kerjanya.

Apakah database relasional terlalu tua dan membosankan untuk dijelaskan di luar mata kuliah, makalah penelitian, dan buku?

Sebagai seorang pengembang, saya benci menggunakan sesuatu yang saya tidak mengerti. Dan jika database sudah digunakan lebih dari 40 tahun, pasti ada alasannya. Selama bertahun-tahun, saya telah menghabiskan ratusan jam untuk benar-benar memahami kotak hitam aneh yang saya gunakan setiap hari. Database relasional sangat menarik karena mereka berdasarkan konsep yang berguna dan dapat digunakan kembali. Jika Anda tertarik untuk memahami database, namun belum pernah memiliki waktu atau keinginan untuk mempelajari topik luas ini, Anda harus menikmati artikel ini.

Meskipun judul artikel ini eksplisit, tujuan artikel ini bukan untuk memahami cara menggunakan database. Oleh karena itu, Anda seharusnya sudah tahu cara menulis permintaan koneksi sederhana dan pertanyaan dasar kasar; jika tidak, Anda mungkin tidak memahami artikel ini. Hanya itu yang perlu Anda ketahui, saya akan menjelaskan sisanya.

Saya akan mulai dengan beberapa dasar ilmu komputer, seperti kompleksitas waktu algoritma (BigO). Saya tahu beberapa dari Anda membenci konsep ini, tetapi tanpanya Anda tidak akan dapat memahami seluk-beluk di dalam database. Karena ini adalah topik yang sangat besar, Saya akan fokus pada apa yang menurutku penting: bagaimana database memprosesnya SQL pertanyaan. Saya hanya akan memperkenalkan konsep dasar basis datasehingga di akhir artikel Anda memiliki gambaran tentang apa yang terjadi.

Karena ini adalah artikel panjang dan teknis yang melibatkan banyak algoritme dan struktur data, luangkan waktu Anda untuk membacanya. Beberapa konsep mungkin sulit untuk dipahami; Anda dapat melewatinya dan tetap mendapatkan gambaran umum.

Bagi Anda yang lebih berpengetahuan, artikel ini dibagi menjadi 3 bagian:

• Ikhtisar komponen database tingkat rendah dan tingkat tinggi
• Ikhtisar Proses Pengoptimalan Kueri
• Ikhtisar Manajemen Transaksi dan Buffer Pool

Kembali ke dasar

Bertahun-tahun yang lalu (di galaksi yang sangat jauh...), pengembang harus mengetahui secara pasti jumlah operasi yang mereka kodekan. Mereka hafal algoritma dan struktur datanya karena mereka tidak mampu menyia-nyiakan CPU dan memori komputer mereka yang lambat.

Pada bagian ini, saya akan mengingatkan Anda tentang beberapa konsep yang penting untuk memahami database. Saya juga akan memperkenalkan konsepnya indeks basis data.

O(1) vs O(n2)

Saat ini, banyak pengembang tidak peduli dengan kompleksitas waktu dari algoritma... dan mereka benar!

Namun ketika Anda berurusan dengan banyak data (saya tidak berbicara ribuan) atau jika Anda kesulitan dalam hitungan milidetik, memahami konsep ini menjadi penting. Dan seperti yang dapat Anda bayangkan, database harus menangani kedua situasi tersebut! Saya tidak akan memaksa Anda menghabiskan lebih banyak waktu daripada yang diperlukan untuk menyampaikan maksudnya. Ini akan membantu kita memahami konsep optimasi berbasis biaya nantinya (biaya berdasarkan optimasi).

Konsep

Kompleksitas waktu dari algoritma digunakan untuk melihat berapa lama waktu yang dibutuhkan suatu algoritma untuk menyelesaikan sejumlah data tertentu. Untuk menggambarkan kompleksitas ini, kami menggunakan notasi matematika O besar. Notasi ini digunakan dengan fungsi yang menjelaskan berapa banyak operasi yang diperlukan suatu algoritma untuk sejumlah input tertentu.

Misalnya, ketika saya mengatakan "algoritma ini memiliki kompleksitas O(some_function())", itu berarti algoritma tersebut memerlukan operasi some_function(a_certain_amount_of_data) untuk memproses sejumlah data tertentu.

Dalam hal ini, Yang penting bukanlah jumlah data**, jika tidak **bagaimana jumlah operasi meningkat seiring dengan peningkatan volume data. Kompleksitas waktu tidak memberikan jumlah operasi yang pasti, namun merupakan cara yang baik untuk memperkirakan waktu eksekusi.

Dalam grafik ini Anda dapat melihat jumlah operasi versus jumlah data masukan untuk berbagai jenis kompleksitas waktu algoritma. Saya menggunakan skala logaritmik untuk menampilkannya. Dengan kata lain, jumlah data meningkat dengan cepat dari 1 menjadi 1 miliar, kita dapat melihat bahwa:

• O(1) atau kompleksitas konstan tetap konstan (jika tidak maka tidak disebut kompleksitas konstan).
• O(mencatat(n)) tetap rendah bahkan dengan miliaran data.
• Kesulitan terburuk - O(n2), dimana jumlah operasi berkembang pesat.
• Dua komplikasi lainnya meningkat dengan cepat.

contoh

Dengan jumlah data yang sedikit, perbedaan antara O(1) dan O(n2) dapat diabaikan. Misalnya, Anda memiliki algoritme yang perlu memproses 2000 elemen.

• Algoritme O(1) akan dikenakan biaya 1 operasi
• Algoritme O(log(n)) akan dikenakan biaya 7 operasi
• Algoritme O(n) akan dikenakan biaya 2 operasi
• Algoritme O(n*log(n)) akan dikenakan biaya 14 operasi
• Algoritma O(n2) akan dikenakan biaya 4 operasi

Perbedaan antara O(1) dan O(n2) tampak besar (4 juta operasi) tetapi Anda akan kehilangan maksimal 2 ms, cukup mengedipkan mata. Memang benar, prosesor modern bisa memproses ratusan juta operasi per detik. Inilah sebabnya mengapa kinerja dan optimalisasi tidak menjadi masalah di banyak proyek TI.

Seperti yang saya katakan, penting untuk mengetahui konsep ini ketika bekerja dengan data dalam jumlah besar. Jika saat ini algoritme harus memproses 1 elemen (yang tidak terlalu banyak untuk sebuah database):

• Algoritme O(1) akan dikenakan biaya 1 operasi
• Algoritme O(log(n)) akan dikenakan biaya 14 operasi
• Algoritme O(n) akan dikenakan biaya 1 operasi
• Algoritme O(n*log(n)) akan dikenakan biaya 14 operasi
• Algoritme O(n2) akan dikenakan biaya 1 operasi

Saya belum menghitungnya, tapi menurut saya dengan algoritma O(n2) Anda punya waktu untuk minum kopi (bahkan dua!). Jika Anda menambahkan 0 lagi ke volume data, Anda akan punya waktu untuk tidur siang.

Mari kita masuk lebih dalam

Untuk informasi Anda:

• Pencarian tabel hash yang baik menemukan elemen di O(1).
• Mencari pohon yang seimbang menghasilkan hasil dalam O(log(n)).
• Mencari array menghasilkan hasil dalam O(n).
• Algoritme pengurutan terbaik memiliki kompleksitas O(n*log(n)).
• Algoritme pengurutan yang buruk memiliki kompleksitas O(n2).

Catatan: Pada bagian berikut kita akan melihat algoritma dan struktur data ini.

Ada beberapa jenis kompleksitas waktu algoritma:

• skenario kasus rata-rata
• skenario kasus terbaik
• dan skenario terburuk

Kompleksitas waktu seringkali merupakan skenario terburuk.

Saya hanya berbicara tentang kompleksitas waktu dari algoritma, tetapi kompleksitas juga berlaku untuk:

• konsumsi memori algoritma
• algoritma konsumsi I/O disk

Tentu saja ada komplikasi yang lebih buruk dari n2, misalnya:

• n4: ini mengerikan! Beberapa algoritma yang disebutkan memiliki kompleksitas ini.
• 3n: ini lebih buruk lagi! Salah satu algoritma yang akan kita lihat di tengah artikel ini memiliki kompleksitas ini (dan sebenarnya digunakan di banyak database).
• faktorial n: Anda tidak akan pernah mendapatkan hasil bahkan dengan jumlah data yang sedikit.
• nn: Jika Anda menghadapi kerumitan ini, Anda harus bertanya pada diri sendiri apakah ini benar-benar bidang kegiatan Anda...

Catatan: Saya tidak memberi Anda definisi sebenarnya dari sebutan O besar, hanya sebuah ide. Anda dapat membaca artikel ini di Wikipedia untuk definisi nyata (asimtotik).

Gabungkan Sortir

Apa yang Anda lakukan saat perlu mengurutkan koleksi? Apa? Anda memanggil fungsi sort()... Oke, jawaban bagus... Tapi untuk database, Anda harus memahami cara kerja fungsi sort() ini.

Ada beberapa algoritma pengurutan yang bagus, jadi saya akan fokus pada yang paling penting: menggabungkan semacam. Anda mungkin tidak memahami mengapa pengurutan data berguna saat ini, tetapi Anda harus memahaminya setelah bagian pengoptimalan kueri. Selain itu, memahami pengurutan gabungan akan membantu kita nantinya memahami operasi penggabungan database umum yang disebut bergabung ikut (asosiasi merger).

Menggabungkan

Seperti banyak algoritme yang berguna, pengurutan gabungan bergantung pada sebuah trik: menggabungkan 2 larik terurut berukuran N/2 ke dalam larik terurut N-elemen hanya membutuhkan N operasi. Operasi ini disebut penggabungan.

Mari kita lihat artinya dengan contoh sederhana:

Gambar ini menunjukkan bahwa untuk membuat larik 8 elemen yang diurutkan terakhir, Anda hanya perlu melakukan iterasi satu kali pada 2 larik 4 elemen. Karena kedua array 4 elemen sudah diurutkan:

• 1) Anda membandingkan kedua elemen saat ini dalam dua array (di awal saat ini = pertama)
• 2) kemudian ambil yang terkecil untuk dimasukkan ke dalam array 8 elemen
• 3) dan pindah ke elemen berikutnya dalam array tempat Anda mengambil elemen terkecil
• dan ulangi 1,2,3 hingga Anda mencapai elemen terakhir dari salah satu array.
• Kemudian Anda mengambil sisa elemen dari array lainnya untuk memasukkannya ke dalam array 8 elemen.

Ini berfungsi karena kedua array 4 elemen diurutkan sehingga Anda tidak perlu "kembali" ke array tersebut.

Sekarang setelah kita memahami triknya, inilah kodesemu saya untuk penggabungan:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Merge sort memecah suatu permasalahan menjadi permasalahan yang lebih kecil kemudian mencari hasil dari permasalahan yang lebih kecil tersebut untuk mendapatkan hasil dari permasalahan aslinya (catatan: algoritma jenis ini disebut dengan Divide and Conquer). Jika Anda tidak memahami algoritma ini, jangan khawatir; Saya tidak memahaminya saat pertama kali melihatnya. Jika ini dapat membantu Anda, saya melihat algoritma ini sebagai algoritma dua fase:

• Fase pembagian, dimana array dibagi menjadi array yang lebih kecil
• Fase penyortiran adalah saat array kecil digabungkan (menggunakan penyatuan) untuk membentuk array yang lebih besar.

Fase pembagian

Pada tahap pembagian, array dibagi menjadi array kesatuan dalam 3 langkah. Banyaknya langkah formal adalah log(N) (karena N=8, log(N) = 3).

Bagaimana saya tahu ini?

Saya jenius! Singkatnya - matematika. Idenya adalah setiap langkah membagi ukuran array asli dengan 2. Jumlah langkah adalah berapa kali Anda dapat membagi array asli menjadi dua. Ini adalah definisi pasti dari logaritma (basis 2).

Fase penyortiran

Pada fase penyortiran, Anda memulai dengan array kesatuan (elemen tunggal). Selama setiap langkah Anda menerapkan beberapa operasi penggabungan dan total biayanya adalah N = 8 operasi:

• Pada tahap pertama Anda memiliki 4 penggabungan yang masing-masing memerlukan 2 operasi
• Pada langkah kedua Anda memiliki 2 penggabungan yang masing-masing memerlukan 4 operasi
• Pada langkah ketiga Anda memiliki 1 penggabungan yang membutuhkan 8 operasi

Karena ada langkah log(N), total biaya N * log(N) operasi.

Keuntungan dari pengurutan gabungan

Mengapa algoritma ini begitu kuat?

Karena:

• Anda dapat mengubahnya untuk mengurangi jejak memori sehingga Anda tidak membuat array baru tetapi langsung memodifikasi array input.

Catatan: algoritma jenis ini disebut in-tempat (menyortir tanpa memori tambahan).

• Anda dapat mengubahnya untuk menggunakan ruang disk dan sejumlah kecil memori secara bersamaan tanpa menimbulkan overhead I/O disk yang signifikan. Idenya adalah untuk memuat ke dalam memori hanya bagian-bagian yang sedang diproses. Hal ini penting ketika Anda perlu mengurutkan tabel multi-gigabyte dengan hanya buffer memori 100 megabyte.

Catatan: algoritma jenis ini disebut semacam eksternal.

• Anda dapat mengubahnya agar berjalan di banyak proses/utas/server.

Misalnya, pengurutan gabungan terdistribusi adalah salah satu komponen kuncinya Hadoop (yang merupakan struktur dalam data besar).

• Algoritma ini dapat mengubah timah menjadi emas (sungguh!).

Algoritma pengurutan ini digunakan di sebagian besar (jika tidak semua) database, namun ini bukan satu-satunya. Jika Anda ingin tahu lebih banyak, Anda bisa membaca ini pekerjaan penelitian, yang membahas pro dan kontra dari algoritma pengurutan database umum.

Array, Pohon dan Tabel Hash

Sekarang setelah kita memahami gagasan tentang kompleksitas waktu dan penyortiran, saya harus memberi tahu Anda tentang 3 struktur data. Ini penting karena mereka adalah dasar dari database modern. Saya juga akan memperkenalkan konsepnya indeks basis data.

Array

Array dua dimensi adalah struktur data yang paling sederhana. Sebuah tabel dapat dianggap sebagai sebuah array. Misalnya:

Array 2 dimensi ini adalah tabel dengan baris dan kolom:

• Setiap baris mewakili suatu entitas
• Kolom menyimpan properti yang mendeskripsikan entitas.
• Setiap kolom menyimpan data dengan tipe tertentu (integer, string, tanggal...).

Ini nyaman untuk menyimpan dan memvisualisasikan data, namun ketika Anda perlu menemukan nilai tertentu, ini tidak cocok.

Misalnya, jika Anda ingin mencari semua pria yang bekerja di Inggris, Anda perlu melihat setiap baris untuk menentukan apakah baris tersebut milik Inggris. Ini akan dikenakan biaya N transaksiDimana N - jumlah baris, mana yang lumayan, tapi mungkinkah ada cara yang lebih cepat? Sekarang saatnya kita berkenalan dengan pepohonan.

Catatan: Sebagian besar database modern menyediakan array yang diperluas untuk menyimpan tabel secara efisien: tabel yang diatur tumpukannya dan tabel yang disusun indeksnya. Namun hal ini tidak mengubah masalah pencarian kondisi tertentu dengan cepat dalam sekelompok kolom.

Pohon basis data dan indeks

Pohon pencarian biner adalah pohon biner dengan properti khusus, kunci pada setiap node harus:

• lebih besar dari semua kunci yang disimpan di subpohon kiri
• kurang dari semua kunci yang disimpan di subpohon kanan

Mari kita lihat apa artinya secara visual

Ide

Pohon ini memiliki N = 15 elemen. Katakanlah saya mencari 208:

• Saya mulai dari root yang kuncinya 136. Karena 136<208, saya melihat subpohon kanan dari node 136.
• 398>208 oleh karena itu saya melihat subpohon kiri dari node 398
• 250>208 oleh karena itu saya melihat subpohon kiri dari node 250
• 200<208, oleh karena itu saya mencari subpohon kanan dari node 200. Tetapi 200 tidak memiliki subpohon kanan, nilai tidak ada (karena jika ada maka akan berada di subpohon kanan 200).

Sekarang katakanlah saya mencari 40

• Saya mulai dari root yang kuncinya 136. Karena 136 > 40, saya melihat subpohon kiri dari node 136.
• 80 > 40, maka saya melihat subpohon kiri dari node 80
• 40= 40, simpul ada. Saya mengambil ID baris di dalam node (tidak ditampilkan dalam gambar) dan mencari ID baris yang diberikan di tabel.
• Mengetahui ID baris memungkinkan saya mengetahui secara pasti lokasi data dalam tabel, sehingga saya dapat mengambilnya secara instan.

Pada akhirnya, kedua pencarian tersebut akan membuat saya kehilangan jumlah level di dalam pohon. Jika Anda membaca bagian tentang pengurutan gabungan dengan cermat, Anda akan melihat bahwa ada level log(N). Ternyata, log biaya pencarian (N), tidak buruk!

Mari kita kembali ke masalah kita

Tapi ini sangat abstrak, jadi mari kita kembali ke masalah kita. Daripada bilangan bulat sederhana, bayangkan sebuah string yang mewakili negara seseorang pada tabel sebelumnya. Katakanlah Anda memiliki pohon yang berisi bidang "negara" (kolom 3) pada tabel:

• Jika Anda ingin tahu siapa yang bekerja di Inggris
• Anda melihat pohon untuk mendapatkan simpul yang mewakili Inggris Raya
• di dalam "UKnode" Anda akan menemukan lokasi catatan pekerja Inggris.

Pencarian ini akan memerlukan operasi log(N) daripada operasi N jika Anda menggunakan array secara langsung. Apa yang baru saja Anda sajikan adalah indeks basis data.

Anda dapat membuat pohon indeks untuk grup bidang apa pun (string, angka, 2 baris, angka dan string, tanggal...) selama Anda memiliki fungsi untuk membandingkan kunci (yaitu grup bidang) sehingga Anda dapat mengatur memesan di antara kunci-kunci itu (yang berlaku untuk semua tipe dasar dalam database).

B+Indeks Pohon

Meskipun pohon ini berfungsi dengan baik untuk mendapatkan nilai tertentu, ada masalah BESAR saat Anda membutuhkannya dapatkan banyak elemen di antara dua nilai. Ini akan memakan biaya O(N) karena Anda harus melihat setiap node di pohon dan memeriksa apakah node tersebut berada di antara dua nilai ini (misalnya dengan traversal pohon yang terurut). Selain itu, operasi ini tidak ramah I/O disk karena Anda harus membaca keseluruhan pohon. Kita perlu menemukan cara untuk mengeksekusi secara efisien permintaan jangkauan. Untuk mengatasi masalah ini, database modern menggunakan versi modifikasi dari pohon sebelumnya yang disebut B+Tree. Di pohon B+Tree:

• hanya simpul terbawah (daun) informasi toko (lokasi baris dalam tabel terkait)
• node lainnya ada di sini untuk perutean ke simpul yang benar selama pencarian.

Seperti yang Anda lihat, ada lebih banyak node di sini (dua kali). Memang benar, Anda memiliki node tambahan, "node keputusan", yang akan membantu Anda menemukan node yang benar (yang menyimpan lokasi baris dalam tabel terkait). Namun kompleksitas pencariannya masih O(log(N)) (hanya ada satu level lagi). Perbedaan besarnya adalah itu node di tingkat bawah terhubung ke penerusnya.

Dengan B+Tree ini, jika Anda mencari nilai antara 40 dan 100:

• Anda hanya perlu mencari 40 (atau nilai terdekat setelah 40 jika 40 tidak ada) seperti yang Anda lakukan pada pohon sebelumnya.
• Kemudian kumpulkan 40 ahli waris menggunakan tautan ahli waris langsung hingga Anda mencapai 100.

Katakanlah Anda menemukan M penerus dan pohon tersebut memiliki N node. Menemukan node tertentu membutuhkan log(N) seperti pohon sebelumnya. Namun begitu Anda mendapatkan node ini, Anda akan mendapatkan M penerus dalam operasi M dengan referensi ke penerusnya. Pencarian ini hanya dikenakan biaya M+log(N) operasi dibandingkan dengan N operasi pada pohon sebelumnya. Selain itu, Anda tidak perlu membaca pohon secara keseluruhan (hanya node M+log(N)), yang berarti penggunaan disk lebih sedikit. Jika M kecil (misalnya 200 baris) dan N besar (1 baris), maka akan terjadi perbedaan BESAR.

Namun ada masalah baru disini (lagi!). Jika Anda menambah atau menghapus baris dalam database (dan karenanya dalam indeks B+Tree terkait):

• Anda harus menjaga ketertiban antar node di dalam B+Tree, jika tidak, Anda tidak akan dapat menemukan node di dalam pohon yang tidak disortir.
• Anda harus menjaga jumlah level seminimal mungkin di B+Tree, jika tidak, kompleksitas waktu O(log(N)) menjadi O(N).

Dengan kata lain, B+Tree harus tertata sendiri dan seimbang. Untungnya, hal ini dapat dilakukan dengan operasi hapus dan penyisipan yang cerdas. Namun hal ini memerlukan biaya: penyisipan dan penghapusan pada pohon B+ memerlukan biaya O(log(N)). Itu sebabnya beberapa dari Anda pernah mendengarnya menggunakan terlalu banyak indeks bukanlah ide yang baik. Benar-benar, Anda memperlambat penyisipan/perbarui/penghapusan baris dalam tabel dengan cepatkarena database perlu memperbarui indeks tabel menggunakan operasi O(log(N)) yang mahal untuk setiap indeks. Selain itu, menambahkan indeks berarti menambah beban kerja manajer transaksi (akan dijelaskan di akhir artikel).

Untuk lebih jelasnya, Anda dapat melihat artikel Wikipedia di B+Pohon. Jika Anda ingin contoh penerapan B+Tree dalam database, lihatlah artikel ini и artikel ini dari pengembang MySQL terkemuka. Keduanya fokus pada bagaimana InnoDB (mesin MySQL) menangani indeks.

Catatan: Seorang pembaca mengatakan kepada saya bahwa, karena optimasi tingkat rendah, pohon B+ harus sepenuhnya seimbang.

tabel hash

Struktur data penting terakhir kami adalah tabel hash. Ini sangat berguna ketika Anda ingin mencari nilai dengan cepat. Selain itu, memahami tabel hash akan membantu kita nantinya memahami operasi gabungan database yang umum disebut hash join ( bergabung hash). Struktur data ini juga digunakan oleh database untuk menyimpan beberapa hal internal (mis. meja kunci или kolam penyangga, kita akan melihat kedua konsep ini nanti).

Tabel hash adalah struktur data yang dengan cepat menemukan elemen berdasarkan kuncinya. Untuk membuat tabel hash, Anda perlu mendefinisikan:

• petunjuk untuk elemen Anda
• fungsi hash untuk kunci. Hash kunci yang dihitung memberikan lokasi elemen (disebut segmen ).
• berfungsi untuk membandingkan kunci. Setelah Anda menemukan segmen yang benar, Anda harus menemukan elemen yang Anda cari dalam segmen tersebut menggunakan perbandingan ini.

Contoh sederhana

Mari kita ambil contoh yang jelas:

Tabel hash ini memiliki 10 segmen. Karena saya malas, saya hanya membayangkan 5 segmen, tapi saya tahu Anda pintar, jadi saya biarkan Anda membayangkan 5 segmen lainnya sendiri. Saya menggunakan fungsi hash modulo 10 dari kuncinya. Dengan kata lain, saya hanya menyimpan digit terakhir kunci elemen untuk menemukan segmennya:

• jika digit terakhirnya adalah 0, maka elemen tersebut masuk ke segmen 0,
• jika digit terakhirnya adalah 1, maka elemen tersebut masuk ke segmen 1,
• jika angka terakhirnya adalah 2, maka elemen tersebut masuk ke dalam area 2,
• ...

Fungsi perbandingan yang saya gunakan hanyalah persamaan antara dua bilangan bulat.

Katakanlah Anda ingin mendapatkan elemen 78:

• Tabel hash menghitung kode hash untuk 78, yaitu 8.
• Tabel hash melihat segmen 8, dan elemen pertama yang ditemukan adalah 78.
• Dia mengembalikan item 78 kepada Anda
• Pencarian hanya membutuhkan 2 operasi (satu untuk menghitung nilai hash dan yang lainnya untuk mencari elemen dalam segmen).

Sekarang katakanlah Anda ingin mendapatkan elemen 59:

• Tabel hash menghitung kode hash untuk 59, yaitu 9.
• Tabel hash mencari di segmen 9, elemen pertama yang ditemukan adalah 99. Karena 99!=59, elemen 99 bukan elemen yang valid.
• Dengan menggunakan logika yang sama, elemen kedua (9), elemen ketiga (79), ..., elemen terakhir (29) diambil.
• Elemen tidak ditemukan.
• Pencarian menelan biaya 7 operasi.

Fungsi hash yang bagus

Seperti yang Anda lihat, tergantung pada nilai yang Anda cari, biayanya tidak sama!

Jika sekarang saya mengubah fungsi hash modulo 1 kunci (yaitu, mengambil 000 digit terakhir), pencarian kedua hanya memerlukan 000 operasi karena tidak ada elemen di segmen 6. Tantangan sebenarnya adalah menemukan fungsi hash yang baik yang akan membuat keranjang berisi sejumlah kecil elemen.

Dalam contoh saya, menemukan fungsi hash yang baik itu mudah. Tapi ini adalah contoh sederhana, menemukan fungsi hash yang baik akan lebih sulit jika kuncinya adalah:

• string (misalnya - nama belakang)
• 2 baris (misalnya - nama belakang dan nama depan)
• 2 baris dan tanggal (misalnya - nama belakang, nama depan dan tanggal lahir)
• ...

Dengan fungsi hash yang baik, biaya pencarian tabel hash O(1).

Array vs tabel hash

Mengapa tidak menggunakan array?

Hmm, pertanyaan bagus.

• Tabel hashnya bisa sebagian dimuat ke dalam memori, dan segmen lainnya dapat tetap berada di disk.
• Dengan array Anda harus menggunakan ruang yang berdekatan di memori. Jika Anda memuat tabel besar sangat sulit untuk menemukan ruang kontinu yang cukup.
• Untuk tabel hash, Anda dapat memilih kunci yang Anda inginkan (misalnya, nama belakang negara dan orang).

Untuk lebih jelasnya anda dapat membaca artikel tentang JawaPeta Hash, yang merupakan implementasi tabel hash yang efisien; Anda tidak perlu memahami Java untuk memahami konsep yang dibahas dalam artikel ini.

Sumber: www.habr.com