Pertanyaan Bagaimana cara kerja pengindeksan basis data?


Mengingat bahwa pengindeksan sangat penting karena kumpulan data Anda bertambah dalam ukuran, dapatkah seseorang menjelaskan bagaimana pengindeksan bekerja pada tingkat basis data-agnostik?

Untuk informasi tentang kueri untuk mengindeks suatu bidang, periksa Bagaimana cara saya mengindeks kolom basis data.


1873
2017-08-04 10:07


asal


Jawaban:


Mengapa dibutuhkan?

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

Karena fakta bahwa sejumlah rekaman hanya dapat diurutkan pada satu bidang, kami dapat menyatakan bahwa penelusuran di bidang yang tidak diurutkan memerlukan Penelusuran Linier yang memerlukan N/2 memblokir akses (rata-rata), di mana N adalah jumlah blok yang dibentang oleh tabel. Jika bidang tersebut adalah bidang non-kunci (yaitu tidak berisi entri unik) maka seluruh tablespace harus dicari di N memblokir akses.

Sedangkan dengan bidang yang diurutkan, Pencarian Biner dapat digunakan, yang memiliki log2 N memblokir akses. Selain itu karena data diurutkan dengan bidang non-kunci, bagian lain dari tabel tidak perlu ditelusuri untuk nilai duplikat, setelah nilai yang lebih tinggi ditemukan. Dengan demikian peningkatan kinerja sangat besar.

Apa itu pengindeksan?

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

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

Bagaimana cara kerjanya?

Pertama, mari kita uraikan skema tabel contoh database;

Nama bidang Tipe data Ukuran pada disk
id (Kunci primer) Int 4 byte yang tidak ditandai
firstName Char (50) 50 byte
lastName Char (50) 50 byte
emailAddress Char (100) 100 bita

Catatan: char digunakan sebagai pengganti varchar untuk memungkinkan ukuran akurat pada nilai disk. Database sampel ini berisi lima juta baris dan tidak terindeks. Kinerja beberapa queri sekarang akan dianalisis. Ini adalah permintaan menggunakan id (bidang kunci yang diurutkan) dan satu menggunakan nama depan (bidang tidak disortir non-kunci).

Contoh 1 - disortir vs bidang yang tidak disortir

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

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

Sekarang nama depan bidang tidak diurutkan atau bidang kunci, sehingga pencarian biner tidak mungkin, begitu pula nilai-nilai unik, dan dengan demikian tabel akan memerlukan pencarian sampai akhir untuk sebuah eksak N = 1,000,000 memblokir akses. Situasi inilah yang ingin dikoreksi oleh pengindeksan.

Mengingat bahwa catatan indeks hanya berisi bidang yang diindeks dan penunjuk ke catatan asli, itu masuk akal bahwa itu akan lebih kecil dari catatan multi-bidang yang menunjuk ke. Jadi, indeks itu sendiri membutuhkan blok disk yang lebih sedikit daripada tabel asli, yang karenanya membutuhkan lebih sedikit akses blok untuk melakukan iterasi. Skema untuk indeks pada nama depan bidang diuraikan di bawah ini;

Nama bidang Tipe data Ukuran pada disk
firstName Char (50) 50 byte
(Perekam catatan) Khusus 4 byte

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

Contoh 2  - pengindeksan

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

Sekarang pencarian menggunakan nama depan bidang dapat memanfaatkan indeks untuk meningkatkan kinerja. Ini memungkinkan pencarian biner indeks dengan rata-rata log2 277778 = 18.08 = 19 memblokir akses. Untuk menemukan alamat dari rekaman yang sebenarnya, yang membutuhkan akses blok lebih lanjut untuk membaca, sehingga totalnya menjadi 19 + 1 = 20 memblokir akses, jauh dari akses 1.000.000 blok yang diperlukan untuk menemukan nama depan cocok dalam tabel yang tidak diindeks.

Kapan seharusnya digunakan?

Mengingat bahwa membuat indeks membutuhkan ruang disk tambahan (277.778 blok tambahan dari contoh di atas, peningkatan ~ 28%), dan bahwa 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, maka masuk akal bahwa bidang pengindeksan yang hanya digunakan untuk keluaran hanya akan membuang-buang ruang disk dan waktu pemrosesan ketika melakukan insert atau menghapus operasi, dan dengan demikian harus dihindari. Juga diberi sifat pencarian biner, kardinalitas atau keunikan data adalah penting. Mengindeks pada bidang dengan kardinalitas 2 akan membagi data menjadi setengahnya, sedangkan kardinalitas 1.000 akan mengembalikan sekitar 1.000 rekaman. Dengan kardinalitas rendah, efektivitasnya dikurangi menjadi semacam linier, dan pengoptimal kueri akan menghindari penggunaan indeks jika kardinalitas kurang dari 30% dari jumlah catatan, secara efektif membuat indeks membuang-buang ruang.


2848
2017-08-04 10:41



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

Sejak itu saya memperoleh beberapa wawasan tentang kerugian dari pembuatan indeks: jika Anda menulis ke meja (UPDATE atau 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 berada di hard disk yang sama, ini akan menghabiskan lebih banyak waktu. Jadi tabel tanpa indeks (heap), akan memungkinkan operasi tulis lebih cepat. (jika Anda memiliki dua indeks, Anda akan berakhir dengan tiga operasi tulis, dan seterusnya)

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 lokasi tabel / indeks yang diinginkan.

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

Dalam skenario tertentu, tumpukan lebih bermanfaat 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 non-cluster agak penting.

Membantuku:- Apa artinya Clustered dan Non Clustered Index?


175
2018-04-30 14:31



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

Untuk informasi lebih lanjut, saya merekomendasikan: Bagaimana cara kerja indeks basis data? Dan, bagaimana indeks membantu?


130
2018-02-20 14:40



Sekarang, misalkan kita ingin menjalankan kueri untuk menemukan semua detail karyawan yang diberi nama ‘Abc’?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Apa yang akan terjadi tanpa indeks?

Perangkat lunak database benar-benar harus melihat setiap baris dalam tabel Karyawan untuk melihat apakah Employee_Name untuk baris itu adalah ‘Abc’. Dan, karena kami ingin setiap baris dengan nama ‘Abc’ di dalamnya, kami tidak bisa berhenti melihat begitu kami menemukan hanya satu baris dengan nama ‘Abc’, karena mungkin ada baris lain dengan nama Abc. Jadi, setiap baris hingga baris terakhir harus dicari - artinya ribuan baris dalam skenario ini harus diperiksa oleh database untuk menemukan baris dengan nama 'Abc'. Inilah yang disebut a scan meja 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 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 lookup, penghapusan, dan penyisipan semua dapat dilakukan dalam waktu logaritmik. Dan, alasan utama lainnya pohon B lebih sering digunakan adalah karena data yang disimpan di dalam B-tree dapat diurutkan. RDBMS biasanya menentukan struktur data mana yang sebenarnya digunakan untuk indeks. Namun, dalam beberapa skenario dengan RDBMS tertentu, Anda sebenarnya dapat menentukan struktur data mana yang ingin digunakan basis data Anda ketika Anda membuat indeks itu sendiri.

Bagaimana cara kerja indeks tabel hash?

Alasan indeks hash digunakan adalah karena tabel hash sangat efisien ketika hanya mencari nilai. Jadi, pertanyaan yang membandingkan untuk persamaan ke string dapat mengambil nilai dengan sangat cepat jika mereka menggunakan indeks hash.

Sebagai contoh, kueri yang kita diskusikan sebelumnya dapat mengambil manfaat dari indeks hash yang dibuat di kolom Employee_Name. Cara indeks hash akan bekerja adalah bahwa nilai kolom akan menjadi kunci ke dalam tabel hash dan nilai aktual yang dipetakan ke kunci itu hanya akan menjadi penunjuk ke data baris dalam tabel. Karena tabel hash pada dasarnya merupakan 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 pertanyaan yang indeks hash bahkan tidak dapat membantu. Misalnya, Anda ingin mengetahui semua karyawan yang berusia kurang dari 40 tahun. Bagaimana Anda bisa melakukannya dengan indeks tabel hash? Yah, itu tidak mungkin karena tabel hash hanya baik untuk mencari pasangan nilai kunci - yang berarti pertanyaan yang memeriksa persamaan

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

Bagaimana cara database tahu kapan menggunakan indeks? Ketika sebuah query seperti "SELECT * FROM Employee WHERE Employee_Name = 'Abc'" dijalankan, database akan memeriksa untuk melihat apakah ada indeks pada kolom yang sedang ditanyakan. Dengan mengasumsikan kolom Employee_Name memiliki indeks yang dibuat di atasnya, database harus memutuskan apakah itu 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 basis data , dan lebih efisien hanya untuk memindai seluruh tabel.

Berapa biaya untuk memiliki indeks basis data?

Ini memakan ruang - dan semakin besar meja Anda, semakin besar indeks Anda. Kinerja lain yang dipukul dengan indeks adalah fakta bahwa setiap kali Anda menambahkan, menghapus, atau memperbarui baris di tabel terkait, operasi yang sama harus dilakukan pada indeks Anda. Ingat bahwa indeks harus berisi data yang sama hingga menit seperti 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 bagus?
  2. Bagaimana cara kerja indeks basis data

93
2017-08-13 18:36



Contoh klasik "Indeks dalam Buku"

Pertimbangkan "Buku" 1000 halaman, dibagi dengan 100 bagian, setiap bagian dengan halaman X.

Sederhana, ya?

Sekarang, tanpa halaman indeks, untuk menemukan bagian tertentu yang dimulai dengan huruf "S", Anda tidak memiliki pilihan selain memindai seluruh buku. yaitu: 1000 halaman

Tetapi dengan halaman indeks di awal, Anda ada di sana. Dan lagi, untuk membaca bagian tertentu yang penting, Anda hanya perlu melihat halaman indeks, lagi dan lagi, setiap waktu. Setelah menemukan indeks yang cocok Anda dapat secara efisien melompat ke bagian dengan melewati bagian lain.

Tapi kemudian, selain 1000 halaman, Anda akan membutuhkan lagi ~ 10 halaman untuk menampilkan halaman indeks, jadi total 1010 halaman.

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

Hal-hal sederhana di sekolah, bukan? : P


82
2018-04-23 14:43



Uraian Sederhana !!!!!!!!!!

Indeks hanyalah struktur data yang menyimpan nilai untuk kolom tertentu dalam tabel. Indeks dibuat pada kolom tabel.

Contoh, kita memiliki tabel database yang disebut Pengguna dengan tiga kolom - Nama, Umur, dan Alamat. Asumsikan bahwa tabel Pengguna memiliki ribuan baris.

Sekarang, misalkan kita ingin menjalankan kueri untuk menemukan semua detail dari setiap pengguna yang diberi nama ‘John’. Jika kita menjalankan query berikut.

SELECT * FROM User 
WHERE Name = 'John'

Perangkat lunak database secara harfiah harus melihat setiap baris dalam tabel Pengguna untuk melihat apakah Nama untuk baris itu adalah ‘John’. Ini akan memakan waktu lama.
Di sinilah indeks membantu kami "indeks digunakan untuk mempercepat permintaan pencarian dengan pada dasarnya mengurangi jumlah catatan / baris dalam tabel yang perlu diperiksa".
Cara membuat indeks

CREATE INDEX name_index
ON User (Name)

Indeks terdiri dari nilai kolom (Misalnya: John) dari satu tabel, dan bahwa nilai-nilai tersebut disimpan dalam struktur data.
Jadi sekarang database akan menggunakan indeks untuk menemukan karyawan yang bernama John karena indeks mungkin akan diurutkan berdasarkan abjad berdasarkan nama Pengguna. Dan, karena disortir, artinya mencari nama jauh lebih cepat karena semua nama yang dimulai dengan "J" akan berada tepat di sebelah satu sama lain dalam indeks!


46
2017-08-02 01:30



Hanya saran cepat .. Karena biaya pengindeksan Anda menulis tambahan dan ruang penyimpanan, jadi jika aplikasi Anda memerlukan lebih banyak operasi insert / update, Anda mungkin ingin menggunakan tabel tanpa indeks, tetapi jika itu membutuhkan lebih banyak operasi pengambilan data, Anda harus pergi untuk diindeks meja.


21
2018-01-14 06:44



Bayangkan saja Indeks Basis Data sebagai Indeks sebuah buku.  Jika Anda memiliki buku tentang anjing dan Anda ingin mencari informasi tentang katakanlah, Gembala Jerman, tentu saja Anda dapat membalik semua halaman buku dan menemukan apa yang Anda cari tetapi ini tentu saja memakan waktu dan tidak terlalu cepat. Pilihan lainnya adalah, Anda bisa pergi ke bagian Indeks buku dan kemudian menemukan apa yang Anda cari dengan menggunakan Nama entitas yang Anda cari (dalam contoh 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. Dengan menggunakan analogi Gembala Jerman yang sama, kita dapat memiliki sesuatu seperti ini (“Gembala Jerman”, 0x77129) di mana 0x77129 adalah alamat pada disk tempat data baris untuk Gembala Jerman disimpan.

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


16
2017-12-21 17:16



Indeks SQL adalah sesuatu yang berhubungan dengan mempercepat pencarian di SQL Database. Indeks memungkinkan programmer untuk mengambil data dari basis data dengan sangat cepat. Misalkan Anda seorang siswa atau pembaca buku. Buku Anda berisi 50.000 halaman. Hari pertama Anda membaca beberapa topik "ABC" hari berikutnya Anda ingin membaca beberapa topik "xyz". Anda tidak akan pernah secara manual melalui halaman demi halaman. Apa yang akan Anda lakukan dalam situasi ini adalah menggunakan indeks Buku untuk melihat beberapa topik tertentu dan kemudian Langsung langsung ke topik Anda. Indeks menghemat banyak waktu Anda untuk mencari topik. Sama dalam indeks SQL, Indeks memungkinkan untuk mencari jutaan rekaman dengan sangat cepat dari basis data.


10
2018-02-15 10:17



Indeks basis data adalah struktur data yang meningkatkan kecepatan operasi pengambilan data pada tabel basis data dengan biaya penulisan tambahan dan ruang penyimpanan untuk mempertahankan struktur data indeks. Indeks digunakan untuk menemukan data dengan cepat tanpa harus mencari setiap baris dalam tabel basis data setiap kali tabel basis data diakses. Indeks dapat dibuat menggunakan satu atau lebih kolom dari tabel database, menyediakan dasar untuk kedua pencarian acak cepat dan akses efisien dari catatan yang dipesan.


0
2017-07-09 05:33