Bagaimana cara kerja pengindeksan database? [Tutup]

Mengingat pengindeksan sangat penting karena kumpulan data Anda bertambah besar, dapatkah seseorang menjelaskan bagaimana pengindeksan bekerja pada tingkat database-agnostik?

Untuk informasi tentang kueri untuk mengindeks bidang, lihat Bagaimana cara mengindeks kolom database .

Mengapa itu dibutuhkan?

Ketika data disimpan pada perangkat penyimpanan berbasis disk, itu disimpan sebagai blok data. Blok-blok ini diakses secara keseluruhan, menjadikannya operasi akses disk atom. Blok disk disusun dengan cara yang hampir sama dengan daftar tertaut; keduanya berisi bagian untuk data, penunjuk ke lokasi simpul berikutnya (atau blok), dan keduanya tidak perlu disimpan secara bersamaan.

Karena kenyataan bahwa sejumlah catatan hanya dapat diurutkan pada satu bidang, kami dapat menyatakan bahwa pencarian di bidang yang tidak diurutkan memerlukan Pencarian Linear yang memerlukan N/2akses blok (rata-rata), di mana Njumlah blok yang bentang meja. Jika bidang itu adalah bidang non-kunci (yaitu tidak mengandung entri unik) maka seluruh tablespace harus dicari di Nblok akses.

Sedangkan dengan bidang yang diurutkan, Pencarian Biner dapat digunakan, yang memiliki log2 Nakses blok. Juga karena data diurutkan diberi bidang non-kunci, sisa tabel tidak perlu dicari untuk nilai duplikat, setelah nilai yang lebih tinggi ditemukan. Dengan demikian peningkatan kinerja sangat besar.

Apa itu pengindeksan?

Pengindeksan adalah cara menyortir sejumlah catatan pada berbagai bidang. Membuat indeks pada bidang dalam tabel membuat struktur data lain yang menyimpan nilai bidang, dan penunjuk ke catatan yang terkait dengannya. Struktur indeks ini kemudian disortir, memungkinkan Pencarian Biner dilakukan di dalamnya.

Kelemahan dari pengindeksan adalah bahwa indeks ini memerlukan ruang tambahan pada disk karena indeks disimpan bersama dalam tabel menggunakan mesin MyISAM, file ini dapat dengan cepat mencapai batas ukuran sistem file yang mendasarinya jika banyak bidang dalam tabel yang sama diindeks .

Bagaimana cara kerjanya?

Pertama, mari kita garis besar skema tabel database sampel;

Nama bidang Tipe data Ukuran pada disk
id (kunci utama) INT 4 byte
firstName Char (50) 50 byte
lastName Char (50) 50 byte
emailAddress Char (100) 100 byte

Catatan : char digunakan sebagai pengganti varchar untuk memungkinkan ukuran yang akurat pada nilai disk. Database sampel ini berisi lima juta baris dan tidak terindeks. Kinerja beberapa pertanyaan sekarang akan dianalisis. Ini adalah query menggunakan id (a diurutkan bidang kunci) dan satu menggunakan firstName (bidang non-key unsorted).

Contoh 1 - bidang yang diurutkan vs yang tidak disortir

Diberikan basis data sampel kami r = 5,000,000catatan ukuran tetap memberikan catatan panjang R = 204byte dan mereka disimpan dalam tabel menggunakan mesin MyISAM yang menggunakan B = 1,024byte ukuran blok standar . Faktor pemblokiran tabel adalah bfr = (B/R) = 1024/204 = 5rekaman per blok disk. Jumlah total blok yang diperlukan untuk memegang tabel adalah N = (r/bfr) = 5000000/5 = 1,000,000blok.

Pencarian linear pada bidang id akan memerlukan rata-rata N/2 = 500,000akses blok untuk menemukan nilai, mengingat bahwa bidang id adalah bidang kunci. Tetapi karena bidang id juga disortir, pencarian biner dapat dilakukan yang membutuhkan rata-rata log2 1000000 = 19.93 = 20akses blokir. Secara instan kita bisa melihat ini adalah peningkatan yang drastis.

Sekarang bidang firstName tidak diurutkan atau tidak bidang kunci, sehingga pencarian biner tidak mungkin, juga tidak ada nilai-nilai yang unik, dan dengan demikian tabel akan membutuhkan pencarian sampai akhir untuk N = 1,000,000akses blok yang tepat . Situasi inilah yang ingin diperbaiki pengindeksan.

Mengingat bahwa catatan indeks hanya berisi bidang yang diindeks dan penunjuk ke catatan asli, masuk akal bahwa itu akan lebih kecil daripada catatan multi-bidang yang ditunjuknya. Jadi indeks itu sendiri membutuhkan lebih sedikit blok disk daripada tabel aslinya, yang karenanya membutuhkan lebih sedikit blok akses untuk beralih melalui. Skema untuk indeks pada bidang firstName diuraikan di bawah ini;

Nama bidang Tipe data Ukuran pada disk
firstName Char (50) 50 byte
(rekam pointer) Spesial 4 byte

Catatan : Pointer di MySQL panjangnya 2, 3, 4 atau 5 byte tergantung pada ukuran tabel.

Contoh 2 - pengindeksan

Diberikan contoh basis data r = 5,000,000catatan kami dengan panjang catatan indeks R = 54byte dan menggunakan ukuran B = 1,024byte blok standar . Faktor pemblokiran indeks adalah bfr = (B/R) = 1024/54 = 18rekaman per blok disk. Jumlah total blok yang diperlukan untuk menahan indeks adalah N = (r/bfr) = 5000000/18 = 277,778blok.

Sekarang pencarian menggunakan bidang firstName dapat memanfaatkan indeks untuk meningkatkan kinerja. Ini memungkinkan pencarian indeks biner dengan rata-rata log2 277778 = 18.08 = 19akses blok. Untuk menemukan alamat catatan yang sebenarnya, yang membutuhkan akses blok lebih lanjut untuk membaca, sehingga total untuk 19 + 1 = 20blok akses, jauh menangis dari 1.000.000 blok pengaksesan diperlukan untuk menemukan firstName pertandingan dalam tabel non-diindeks.

Kapan itu harus digunakan?

Mengingat bahwa membuat indeks memerlukan ruang disk tambahan (277.778 blok tambahan dari contoh di atas, peningkatan ~ 28%), dan terlalu banyak indeks dapat menyebabkan masalah yang timbul dari batas ukuran sistem file, pemikiran yang cermat harus digunakan untuk memilih yang benar bidang untuk diindeks.

Karena indeks hanya digunakan untuk mempercepat pencarian bidang yang cocok dalam catatan, masuk akal bahwa bidang pengindeksan yang hanya digunakan untuk output hanya akan membuang-buang ruang disk dan waktu pemrosesan saat melakukan operasi penyisipan atau penghapusan, dan dengan demikian harus dihindari. Juga mengingat sifat pencarian biner, kardinalitas atau keunikan data adalah penting. Pengindeksan pada bidang dengan kardinalitas 2 akan membagi data menjadi dua, sedangkan kardinalitas 1.000 akan mengembalikan sekitar 1.000 catatan. Dengan kardinalitas yang rendah, keefektifannya dikurangi menjadi semacam linier, dan pengoptimal kueri akan menghindari penggunaan indeks jika kardinalitas kurang dari 30% dari jumlah catatan, secara efektif membuat indeks menjadi pemborosan ruang.

Contoh klasik "Indeks dalam Buku"

Pertimbangkan sebuah "Buku" 1000 halaman, dibagi dengan 10 Bab, masing-masing bagian dengan 100 halaman.

Sederhana ya

Sekarang, bayangkan Anda ingin menemukan Bab tertentu yang berisi kata " Alchemist ". Tanpa halaman indeks, Anda tidak memiliki pilihan lain selain memindai seluruh buku / Bab. yaitu: 1000 halaman.

Analogi ini dikenal sebagai "Pemindaian Tabel Penuh" di dunia basis data.

Tetapi dengan halaman indeks, Anda tahu ke mana harus pergi! Dan lebih lagi, untuk mencari Bab tertentu yang penting, Anda hanya perlu memeriksa halaman indeks, berulang kali, setiap waktu. Setelah menemukan indeks yang cocok Anda dapat secara efisien melompat ke bab itu dengan melewatkan sisanya.

Tapi kemudian, selain 1000 halaman yang sebenarnya, Anda akan membutuhkan ~ 10 halaman lain untuk menunjukkan indeks, sehingga benar-benar 1010 halaman.

Dengan demikian, indeks adalah bagian terpisah yang menyimpan nilai kolom + pointer yang diindeks ke baris yang diindeks dalam urutan diurutkan untuk pencarian efisien.

Segalanya sederhana di sekolah, bukan? : P

Pertama kali saya membaca ini sangat membantu saya. Terima kasih.

Sejak saat itu saya mendapatkan beberapa wawasan tentang kelemahan membuat indeks: jika Anda menulis ke dalam tabel ( UPDATEatau INSERT) dengan satu indeks, Anda sebenarnya memiliki dua operasi penulisan dalam sistem file. Satu untuk data tabel dan satu lagi untuk data indeks (dan penggunaannya (dan - jika dikelompokkan - penggunaan data tabel)). Jika tabel dan indeks terletak pada hard disk yang sama, ini membutuhkan lebih banyak waktu. Dengan demikian tabel tanpa indeks (heap), akan memungkinkan untuk operasi penulisan yang lebih cepat. (jika Anda memiliki dua indeks, Anda akan berakhir dengan tiga operasi penulisan, dan sebagainya)

Namun, mendefinisikan dua lokasi berbeda pada dua hard disk yang berbeda untuk data indeks dan data tabel dapat mengurangi / menghilangkan masalah peningkatan biaya waktu. Ini memerlukan definisi grup file tambahan dengan file yang sesuai pada hard disk yang diinginkan dan definisi tabel / lokasi indeks yang diinginkan.

Masalah lain dengan indeks adalah fragmentasi mereka dari waktu ke waktu ketika data dimasukkan. REORGANIZEmembantu, Anda harus menulis rutinitas untuk menyelesaikannya.

Dalam skenario tertentu tumpukan lebih berguna daripada tabel dengan indeks,

misalnya: - Jika Anda memiliki banyak tulisan yang bersaing tetapi hanya satu malam membaca di luar jam kerja untuk pelaporan.

Juga, perbedaan antara indeks berkerumun dan tidak berkerumun agak penting.

Membantu saya: - Apa arti sebenarnya dari indeks Clustered dan Non clustered?

Indeks hanyalah struktur data yang membuat pencarian lebih cepat untuk kolom tertentu dalam database. Struktur ini biasanya b-tree atau tabel hash tetapi bisa berupa struktur logika lainnya.

Sekarang, katakanlah kita ingin menjalankan kueri untuk menemukan semua detail karyawan yang bernama 'Abc'?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Apa yang akan terjadi tanpa indeks?

Perangkat lunak basis data harus benar-benar melihat setiap baris dalam tabel Karyawan untuk melihat apakah Employee_Name untuk baris itu adalah 'Abc'. Dan, karena kita ingin setiap baris dengan nama 'Abc' di dalamnya, kita tidak bisa berhenti mencari begitu kita menemukan hanya satu baris dengan nama 'Abc', karena mungkin ada baris lain dengan nama Abc . Jadi, setiap baris hingga baris terakhir harus dicari - yang berarti ribuan baris dalam skenario ini harus diperiksa oleh database untuk menemukan baris dengan nama 'Abc'. Inilah yang disebut pemindaian tabel penuh

Bagaimana indeks basis data dapat membantu kinerja

Inti dari memiliki indeks adalah untuk mempercepat permintaan pencarian dengan pada dasarnya mengurangi jumlah catatan / baris dalam tabel yang perlu diperiksa. Indeks adalah struktur data (paling sering B-tree) yang menyimpan nilai-nilai untuk kolom tertentu dalam tabel.

Bagaimana cara kerja indeks B-tree?

Alasan B-tree adalah struktur data yang paling populer untuk indeks adalah karena fakta bahwa mereka efisien waktu - karena pencarian, penghapusan, dan penyisipan semua dapat dilakukan dalam waktu logaritmik. Dan, alasan utama B-tree lebih umum digunakan adalah karena data yang disimpan di dalam B-tree dapat diurutkan. RDBMS biasanya menentukan struktur data mana yang sebenarnya digunakan untuk indeks. Tetapi, dalam beberapa skenario dengan RDBMS tertentu, Anda benar-benar dapat menentukan struktur data mana yang Anda ingin database Anda gunakan ketika Anda membuat indeks itu sendiri.

Bagaimana cara kerja indeks tabel hash?

Alasan mengapa indeks hash digunakan adalah karena tabel hash sangat efisien dalam hal mencari nilai saja. Jadi, kueri yang membandingkan kesetaraan dengan string dapat mengambil nilai dengan sangat cepat jika mereka menggunakan indeks hash.

Misalnya, kueri yang kita diskusikan sebelumnya dapat memanfaatkan indeks hash yang dibuat pada kolom Employee_Name. Cara indeks hash akan bekerja adalah bahwa nilai kolom akan menjadi kunci ke tabel hash dan nilai aktual yang dipetakan ke kunci itu hanya akan menjadi penunjuk ke data baris dalam tabel. Karena tabel hash pada dasarnya adalah array asosiatif, entri khas akan terlihat seperti “Abc => 0x28939 ″, di mana 0x28939 adalah referensi ke baris tabel di mana Abc disimpan dalam memori. Mencari nilai seperti "Abc" dalam indeks tabel hash dan mendapatkan kembali referensi ke baris dalam memori jelas jauh lebih cepat daripada memindai tabel untuk menemukan semua baris dengan nilai "Abc" di kolom Employee_Name.

Kerugian dari indeks hash

Tabel hash tidak diurutkan struktur data, dan ada banyak jenis permintaan yang indeks hash bahkan tidak bisa membantu. Misalnya, Anda ingin mengetahui semua karyawan yang berusia kurang dari 40 tahun. Bagaimana Anda bisa melakukan itu dengan indeks tabel hash? Yah, itu tidak mungkin karena tabel hash hanya baik untuk mencari pasangan nilai kunci - yang berarti pertanyaan yang memeriksa kesetaraan

Apa sebenarnya yang ada di dalam indeks basis data? Jadi, sekarang Anda tahu bahwa indeks basis data dibuat pada kolom dalam tabel, dan indeks menyimpan nilai dalam kolom tertentu. Tetapi, penting untuk dipahami bahwa indeks basis data tidak menyimpan nilai-nilai di kolom lain dari tabel yang sama. Misalnya, jika kita membuat indeks pada kolom Employee_Name, ini berarti bahwa nilai kolom Employee_Age dan Employee_Address juga tidak disimpan dalam indeks. Jika kita hanya menyimpan semua kolom lain dalam indeks, maka itu akan seperti membuat salinan lain dari seluruh tabel - yang akan memakan terlalu banyak ruang dan akan sangat tidak efisien.

Bagaimana basis data tahu kapan harus menggunakan indeks? Ketika kueri seperti "SELECT * FROM Employee WHERE Employee_Name = 'Abc'" dijalankan, database akan memeriksa untuk melihat apakah ada indeks pada kolom yang ditanyai. Dengan asumsi kolom Employee_Name memang memiliki indeks yang dibuat di atasnya, database harus memutuskan apakah benar-benar masuk akal untuk menggunakan indeks untuk menemukan nilai yang sedang dicari - karena ada beberapa skenario di mana sebenarnya kurang efisien untuk menggunakan indeks database , dan lebih efisien hanya dengan memindai seluruh tabel.

Berapa biaya memiliki indeks basis data?

Membutuhkan banyak ruang - dan semakin besar tabel Anda, semakin besar indeks Anda. Kinerja lain yang terkena indeks adalah fakta bahwa setiap kali Anda menambah, menghapus, atau memperbarui baris dalam tabel yang sesuai, operasi yang sama harus dilakukan untuk indeks Anda. Ingat bahwa indeks perlu memuat data yang sama hingga menit seperti apa pun yang ada di kolom tabel yang dicakup indeks.

Sebagai aturan umum, indeks hanya boleh dibuat di atas meja jika data dalam kolom yang diindeks akan sering ditanyakan.

Lihat juga

1. Kolom apa yang umumnya membuat indeks yang baik?
2. Bagaimana cara kerja indeks basis data

Deskripsi Sederhana!

Indeks tidak lain adalah struktur data yang menyimpan nilai untuk kolom tertentu dalam tabel. Indeks dibuat pada kolom tabel.

Contoh: Kami memiliki tabel database yang disebut Userdengan tiga kolom - Name, Agedan Address. Asumsikan bahwa Usertabel memiliki ribuan baris.

Sekarang, katakanlah kita ingin menjalankan kueri untuk menemukan semua detail dari setiap pengguna yang bernama 'John'. Jika kami menjalankan kueri berikut:

SELECT * FROM User 
WHERE Name = 'John'

Perangkat lunak basis data harus benar-benar melihat setiap baris dalam Usertabel untuk melihat apakah Namebaris itu adalah 'John'. Ini akan memakan waktu lama.

Di sinilah indexmembantu kami: indeks digunakan untuk mempercepat permintaan pencarian dengan secara esensial mengurangi jumlah catatan / baris dalam tabel yang perlu diperiksa .

Cara membuat indeks:

CREATE INDEX name_index
ON User (Name)

Sebuah indexterdiri dari nilai-nilai kolom (Misalnya: John) dari satu meja , dan nilai-nilai yang disimpan dalam struktur data .

Jadi sekarang database akan menggunakan indeks untuk menemukan karyawan bernama John karena indeks mungkin akan diurutkan berdasarkan abjad berdasarkan nama Pengguna. Dan, karena diurutkan, itu berarti mencari nama jauh lebih cepat karena semua nama yang dimulai dengan "J" akan berada tepat di sebelah satu sama lain dalam indeks!

Hanya saran cepat .. Karena pengindeksan akan menambah biaya penulisan dan ruang penyimpanan tambahan, jadi jika aplikasi Anda memerlukan lebih banyak operasi penyisipan / perbarui, Anda mungkin ingin menggunakan tabel tanpa indeks, tetapi jika memerlukan lebih banyak operasi pengambilan data, Anda harus menggunakan indeks meja.

Anggap saja Indeks Database sebagai Indeks buku.

Jika Anda memiliki buku tentang anjing dan Anda ingin mencari informasi tentang katakanlah, Gembala Jerman, Anda tentu saja dapat membolak-balik semua halaman buku dan menemukan apa yang Anda cari - tetapi ini tentu saja memakan waktu dan tidak sangat cepat.

Pilihan lain adalah bahwa, Anda bisa pergi ke bagian Indeks buku dan kemudian menemukan apa yang Anda cari dengan menggunakan Nama entitas yang Anda cari (dalam hal ini, Gembala Jerman) dan juga melihat nomor halaman untuk cepat temukan apa yang Anda cari.

Dalam Database, nomor halaman disebut sebagai pointer yang mengarahkan database ke alamat pada disk tempat entitas berada. Menggunakan analogi Gembala Jerman yang sama, kita bisa memiliki sesuatu seperti ini ("Gembala Jerman", 0x77129) di mana 0x77129alamat pada disk tempat data baris untuk Gembala Jerman disimpan.

Singkatnya, indeks adalah struktur data yang menyimpan nilai-nilai untuk kolom tertentu dalam tabel untuk mempercepat pencarian kueri.