Indeks diisih terlebih dahulu, supaya algoritma yang cekap seperti carian binari boleh digunakan semasa mencari. Kerumitan carian berurutan am ialah O(n), manakala kerumitan carian binari ialah O(log2n); apabila n adalah sangat besar, perbezaan kecekapan antara keduanya adalah besar.
Persekitaran pengendalian tutorial ini: sistem windows7, versi mysql8, komputer Dell G3.
Mysql ialah pangkalan data yang sangat popular di Internet Reka bentuk enjin storan asasnya dan enjin perolehan data adalah sangat penting, khususnya, bentuk penyimpanan data Mysql dan reka bentuk indeks menentukan keseluruhan data prestasi mendapatkan semula Mysql.
Kami tahu bahawa fungsi indeks adalah untuk mendapatkan semula data dengan cepat, dan intipati perolehan pantas ialah struktur data. Melalui pemilihan struktur data yang berbeza, pelbagai data boleh diperoleh dengan cepat. Dalam pangkalan data, algoritma carian yang cekap adalah sangat penting, kerana sejumlah besar data disimpan dalam pangkalan data, dan indeks yang cekap boleh menjimatkan masa yang besar. Sebagai contoh, dalam jadual data berikut, jika Mysql tidak melaksanakan algoritma indeks, maka untuk mencari data dengan id=7, anda hanya boleh menggunakan traversal berurutan yang ganas untuk mencari data Untuk mencari data dengan id=7, anda perlu membandingkannya 7 kali Jika jadual ini menyimpan 10 juta keping data Untuk mencari data dengan id=1000W, ia akan dibandingkan 1000W kali ini.
1. Indeks Mysql pemilihan struktur data asas
Jadual cincang (Hash)
Jadual cincang ialah alat yang berkesan untuk mendapatkan semula data yang pantas.
Algoritma cincang: Juga dipanggil algoritma cincang, ia menukar sebarang nilai (kunci) kepada alamat kunci panjang tetap melalui fungsi cincang dan menggunakan alamat ini untuk mencipta struktur data bagi data tertentu.
Pertimbangkan pengguna jadual pangkalan data ini. Kami perlu mendapatkan semula data dengan id= 7. Sintaks SQL ialah:
select * from user where id=7;
Salin selepas log masuk
Algoritma cincang terlebih dahulu mengira alamat fizikal addr=hash(7)=4231 untuk menyimpan data dengan id=7 dan alamat fizikal yang dipetakan oleh 4231 ialah 0x77 , 0x77 ialah id=7 Alamat fizikal data yang disimpan Data yang sepadan dengan user_name='g' boleh didapati melalui alamat bebas ini. Ini ialah proses pengiraan yang digunakan oleh algoritma cincang untuk mendapatkan semula data dengan cepat.
Walau bagaimanapun, algoritma cincang mempunyai masalah perlanggaran data, iaitu fungsi cincang mungkin mengira hasil yang sama untuk kunci yang berbeza Contohnya, cincang(7) mungkin mengira hasil yang sama seperti cincang(199). Iaitu, kunci yang berbeza dipetakan kepada hasil yang sama. Ini adalah masalah perlanggaran. Cara biasa untuk menyelesaikan masalah perlanggaran ialah kaedah alamat rantai, yang menggunakan senarai terpaut untuk menyambungkan data yang berlanggar. Selepas mengira nilai cincang, anda juga perlu menyemak sama ada nilai cincang mempunyai perlanggaran dalam senarai terpaut data, dan jika ya, rentas hingga ke penghujung senarai terpaut sehingga anda menemui data yang sepadan dengan kunci sebenar.
从算法时间复杂度分析来看，哈希算法时间复杂度为 O（1），检索速度非常快。比如查找 id=7 的数据，哈希索引只需要计算一次就可以获取到对应的数据，检索速度非常快。但是 Mysql 并没有采取哈希作为其底层算法，这是为什么呢？
Dalam pangkalan data, kenaikan automatik data ialah bentuk yang sangat biasa, contohnya, kunci utama jadual ialah id, dan kunci utama biasanya lalai kepada Peningkatan sendiri, jika struktur data seperti pokok binari digunakan sebagai indeks, maka masalah carian linear yang disebabkan oleh keadaan tidak seimbang yang diperkenalkan di atas pasti akan berlaku. Oleh itu, pepohon carian binari mudah mempunyai masalah penurunan prestasi perolehan yang disebabkan oleh ketidakseimbangan, dan tidak boleh digunakan secara langsung untuk melaksanakan indeks asas Mysql.
Pokok AVL dan pokok merah-hitam
Terdapat masalah ketidakseimbangan dalam pokok carian binari, jadi ulama telah mencadangkan automatik Nod pokok Dengan memutar dan melaraskan untuk mengekalkan pokok binari dalam keadaan seimbang pada asasnya, anda boleh mengekalkan prestasi carian terbaik bagi pokok carian binari. Pokok binari keadaan keseimbangan laras sendiri berdasarkan idea ini termasuk pokok AVL dan pokok merah-hitam.
Pertama sekali, kami memperkenalkan secara ringkas pokok merah-hitam Ini adalah struktur pokok yang melaraskan bentuk pokok secara automatik Sebagai contoh, apabila pokok binari berada dalam keadaan tidak seimbang, pokok merah-hitam akan memusingkan nod kiri dan kanan secara automatik dan nod akan bertukar warna Melaraskan bentuk pokok untuk mengekalkan keadaan seimbang asas (kerumitan masa ialah O(logn)) memastikan kecekapan carian tidak akan berkurangan dengan ketara. Sebagai contoh, jika nod data dimasukkan dalam tertib menaik dari 1 hingga 7, pokok carian binari biasa akan merosot menjadi senarai terpaut, tetapi pokok merah-hitam akan terus melaraskan bentuk pokok untuk mengekalkan keseimbangan asas, seperti yang ditunjukkan. dalam rajah di bawah. Bilangan nod yang hendak dibandingkan apabila mencari id=7 dalam pokok merah-hitam di bawah ialah 4, yang masih mengekalkan kecekapan carian yang baik bagi pokok binari.
Pokok merah-hitam mempunyai kecekapan carian purata yang baik, dan tiada situasi O(n) yang melampau Bolehkah pokok merah-hitam digunakan sebagai pelaksanaan indeks asas Mysql? Malah, pokok merah-hitam juga mempunyai beberapa masalah Lihat contoh berikut. Pokok merah-hitam memasukkan 1~7 nod secara berurutan, dan bilangan nod yang perlu dikira semasa mencari id=7 ialah 4.
Pokok merah-hitam memasukkan 1~16 nod secara berurutan, dan bilangan nod yang perlu dibandingkan dengan cari id=16 ialah 6 kali . Perhatikan bentuk pokok ini. Adakah benar apabila data dimasukkan secara berurutan, bentuk pokok itu sentiasa berada dalam arah aliran "miring ke kanan"? Pada asasnya, pokok merah-hitam tidak menyelesaikan sepenuhnya pepohon carian perduaan Walaupun arah aliran "bersandar ke kanan" ini jauh lebih kecil daripada pepohon carian perduaan yang merosot menjadi senarai terpaut linear, operasi kenaikan automatik kunci utama asas dalam. pangkalan data, kunci utama biasanya Berjuta-juta dan berpuluh-puluh juta Jika pokok merah-hitam mempunyai masalah seperti ini, ia juga akan menggunakan sejumlah besar prestasi carian kami tidak boleh bertolak ansur dengan penantian yang tidak bermakna ini.
Sekarang pertimbangkan satu lagi pokok binari pengimbangan diri yang lebih ketat, pokok AVL. Oleh kerana pokok AVL ialah pokok binari yang seimbang, ia menggunakan lebih banyak prestasi dalam melaraskan bentuk pokok binari.
Pokok AVL memasukkan 1~7 nod secara berurutan, dan bilangan kali untuk membandingkan nod dengan id=7 ialah 3.
Pokok AVL secara berurutan memasukkan 1~16 nod, dan bilangan nod yang perlu dibandingkan untuk mencari id=16 ialah 4. Dari segi kecekapan carian, kelajuan carian pokok AVL adalah lebih tinggi daripada pokok merah-hitam (pokok AVL ialah 4 perbandingan, pokok merah-hitam ialah 6 perbandingan). Jika dilihat dari bentuk pokok, pokok AVL tidak mempunyai masalah "condong yang betul" seperti pokok merah-hitam. Dalam erti kata lain, sejumlah besar sisipan berurutan tidak akan membawa kepada penurunan dalam prestasi pertanyaan, yang secara asasnya menyelesaikan masalah pokok merah-hitam.
Untuk meringkaskan kelebihan pokok AVL:
Prestasi carian yang baik (O(logn)), tiada situasi carian tidak cekap yang melampau.
boleh merealisasikan carian julat dan pengisihan data.
Nampaknya pokok AVL sangat bagus sebagai struktur data untuk carian data, tetapi pokok AVL tidak sesuai untuk struktur data indeks pangkalan data Mysql, kerana pertimbangkan masalah ini :
Halangan data pertanyaan pangkalan data ialah cakera IO, setiap nod pokok hanya boleh menyimpan satu data pada satu nod dan memuatkannya ke dalam memori dengan satu cakera IO. Contohnya, pertanyaan ID =7 Kita perlu melakukan cakera IO tiga kali untuk data ini, yang memakan masa. Oleh itu, apabila mereka bentuk indeks pangkalan data, kita perlu terlebih dahulu mempertimbangkan cara mengurangkan bilangan IO cakera sebanyak mungkin.
Satu ciri cakera IO ialah masa yang diperlukan untuk membaca data 1B dan data 1KB dari cakera pada asasnya adalah sama Berdasarkan idea ini, kita boleh membaca seberapa banyak data yang mungkin pada nod pokok. Simpan data dengan cekap, dan muatkan lebih banyak data ke dalam memori dalam satu cakera IO Ini adalah prinsip reka bentuk B-tree dan B+ tree.
B-tree
B-tree berikut terhad untuk menyimpan sehingga dua kekunci setiap nod dua Kunci akan terbelah secara automatik. Sebagai contoh, B-tree berikut menyimpan 7 data Anda hanya perlu menanyakan dua nod untuk mengetahui lokasi tertentu data dengan id=7 Iaitu, anda boleh menanyakan data yang ditentukan dengan dua IO cakera, yang lebih baik daripada pokok AVL.
Berikut ialah pokok B yang menyimpan 16 keping data Setiap nod juga menyimpan sehingga 2 kekunci. Pertanyaan Data dengan id=16 perlu disoal dan dibandingkan pada 4 nod, yang bermaksud 4 kali IO cakera. Nampaknya prestasi pertanyaan adalah sama dengan pepohon AVL.
Tetapi memandangkan masa yang digunakan oleh cakera IO untuk membaca satu keping data pada asasnya sama seperti membaca 100 keping data, kemudian pengoptimuman kami Idea ini boleh ditukar kepada: membaca sebanyak mungkin data ke dalam memori dalam satu cakera IO. Ini secara langsung dicerminkan dalam struktur pokok, iaitu kunci yang boleh disimpan oleh setiap nod boleh ditingkatkan dengan sewajarnya.
Apabila kami menetapkan had nombor kunci untuk satu nod kepada 6, untuk pokok B yang menyimpan 7 keping data, cakera IO yang diperlukan untuk menanyakan data dengan id=7 ialah 2 kali.
Pokok B yang menyimpan 16 keping data IO cakera yang diperlukan untuk menanyakan data dengan id=7 ialah 2 Kadar kedua. Berbanding dengan pokok AVL, bilangan IO cakera dikurangkan kepada separuh.
Jadi dari segi pemilihan struktur data indeks pangkalan data, B-tree adalah pilihan yang sangat baik . Ringkasnya, B-tree mempunyai kelebihan berikut apabila digunakan sebagai indeks pangkalan data:
Kelajuan mendapatkan semula yang sangat baik, kerumitan masa: Prestasi carian B-tree adalah sama dengan O (h*logn), Di mana h ialah ketinggian pokok, n ialah bilangan kata kunci dalam setiap nod; 🎜> boleh menyokong julat Cari.
Pokok B+
Apakah perbezaan antara pokok B dan pokok B+?
Pertama, B tree menyimpan data dalam satu nod, manakala B+ tree menyimpan indeks (alamat), jadi satu nod dalam B tree tidak boleh menyimpan banyak data, tetapi satu nod daripada pokok B+ boleh menyimpan banyak indeks, dan nod daun pokok B+ menyimpan semua data.
Kedua, Nod daun pokok B+ disambungkan secara bersiri dengan senarai terpaut dalam peringkat data untuk memudahkan carian julat.
2. Pelaksanaan enjin Innodb dan enjin Myisam Enjin data asas MySQL direka bentuk dalam bentuk pemalam Yang paling biasa ialah enjin Innodb dan Myisam enjin. Pengguna boleh menyesuaikannya mengikut keperluan peribadi mereka adalah perlu untuk memilih enjin yang berbeza sebagai enjin asas jadual data Mysql. Kami baru sahaja menganalisis bahawa pokok B+ sangat sesuai sebagai struktur data indeks Mysql, tetapi cara menyusun data dan indeks juga memerlukan beberapa reka bentuk Konsep reka bentuk yang berbeza juga membawa kepada kemunculan Innodb dan Myisam, masing-masing membentangkan prestasi yang unik.
Walaupun MyISAM mempunyai prestasi carian data yang sangat baik, ia tidak menyokong pemprosesan transaksi. Ciri terbesar Innodb ialah ia menyokong fungsi transaksi yang serasi dengan ACID dan ia menyokong kunci peringkat baris. Anda boleh menentukan enjin apabila Mysql mencipta jadual Contohnya, dalam contoh berikut, Myisam dan Innodb ditetapkan sebagai enjin data untuk jadual pengguna dan jadual pengguna2.
Selepas melaksanakan kedua-dua arahan ini, sistem muncul seperti berikut Fail menunjukkan bahawa data dan indeks kedua-dua enjin disusun secara berbeza.
Fail yang dijana oleh Innodb selepas mencipta jadual ialah:
frm: Pernyataan untuk mencipta jadual
idb: data + fail indeks dalam jadual
Fail yang dijana oleh Myisam selepas mencipta jadual ialah
frm: Penyata untuk mencipta jadual
MYD: Fail data dalam jadual (data myisam)
MYI: Fail indeks dalam jadual (indeks myisam)
Berdasarkan fail yang dijana, data asas dan indeks kedua-dua enjin disusun secara berbeza Enjin MyISAM memisahkan data dan mengindeks kepada satu fail bagi setiap orang . Ini dipanggil kaedah indeks bukan Berkelompok; Enjin Innodb meletakkan data dan indeks dalam fail yang sama, yang dipanggil kaedah indeks berkelompok. Berikut akan menganalisis cara kedua-dua enjin ini bergantung pada struktur data pokok B+ untuk mengatur pelaksanaan enjin dari perspektif pelaksanaan asas.
Pelaksanaan asas enjin MyISAM (mod indeks bukan berkelompok)
MyISAM menggunakan mod indeks bukan berkelompok, iaitu data dan indeks jatuh kepada dua yang berbeza pada fail. Apabila MyISAM mencipta jadual, ia menggunakan kunci utama sebagai KEY untuk mencipta pokok indeks B+ utama Nod daun pokok menyimpan alamat fizikal data yang sepadan. Selepas kami mendapat alamat fizikal ini, kami boleh mencari terus rekod data tertentu dalam fail data MyISAM.
Apabila kita menambah indeks pada medan, kita juga akan menjana pokok indeks untuk medan yang sepadan nod pokok indeks juga merekodkan alamat fizikal data yang sepadan, dan kemudian gunakan alamat fizikal ini untuk mencari rekod data tertentu dalam fail data.
Pelaksanaan asas enjin Innodb (kaedah indeks berkelompok)
InnoDB ialah kaedah indeks berkelompok, jadi data dan indeks disimpan dalam yang sama fail. Mula-mula, InnoDB akan mencipta pepohon indeks B+ berdasarkan ID kunci utama sebagai KEY, seperti yang ditunjukkan dalam rajah di bawah, dan nod daun pepohon B+ menyimpan data yang sepadan dengan ID kunci utama Sebagai contoh, apabila melaksanakan pernyataan pilih * dari info_pengguna di mana id=15, InnoDB Ia akan menanyakan pepohon indeks B+ ID kunci utama dan mencari nama_pengguna='Bob' yang sepadan.
InnoDB akan membina pepohon indeks ID kunci utama secara automatik apabila mencipta jadual. Inilah sebab mengapa Mysql memerlukan kunci utama untuk ditentukan semasa membuat jadual. Bagaimanakah InnoDB membina pepohon indeks apabila kita menambah indeks pada medan dalam jadual? Sebagai contoh, jika kita ingin menambah indeks pada medan nama_pengguna, maka InnoDB akan mencipta pepohon indeks nama_pengguna B+ KUNCI nama_pengguna disimpan dalam nod, dan data yang disimpan dalam nod daun ialah KEY kunci utama. Ambil perhatian bahawa daun menyimpan kunci utama KEY! Selepas mendapat KEY kunci utama, InnoDB akan pergi ke pepohon indeks kunci utama untuk mencari data yang sepadan berdasarkan KEY kunci utama yang baru ditemui dalam pepohon indeks nama_pengguna.
Persoalannya, mengapa InnoDB hanya menyimpan data tertentu dalam nod daun pokok indeks kunci utama, tetapi tidak dalam yang lain pepohon indeks? Bagaimana dengan data khusus? Bagaimana jika kita perlu mencari kunci utama dahulu dan kemudian mencari data yang sepadan dalam pepohon indeks kunci utama?
Ia sebenarnya sangat mudah, kerana InnoDB perlu menjimatkan ruang storan . Mungkin terdapat banyak indeks dalam jadual InnoDB akan menghasilkan pepohon indeks untuk setiap medan yang diindeks Jika pepohon indeks setiap medan menyimpan data tertentu, maka fail data indeks jadual ini akan menjadi sangat besar (data Sangat berlebihan). Dari perspektif penjimatan ruang cakera, sebenarnya tidak perlu menyimpan data khusus dalam setiap pokok indeks medan Melalui langkah yang kelihatan "tidak perlu" ini, ruang cakera yang besar dijimatkan dengan mengorbankan prestasi pertanyaan yang kurang.
Apabila membandingkan ciri-ciri InnoDB dan MyISAM, dikatakan bahawa MyISAM mempunyai prestasi pertanyaan yang lebih baik Sebabnya boleh dilihat dari reka bentuk fail data fail indeks di atas: MyISAM boleh mengesan alamat fizikal secara langsung selepas mencari. ia merekodkan Data, tetapi selepas InnoDB menanyakan nod daun, ia perlu menanya semula pokok indeks kunci utama untuk mencari data tertentu. Ini bermakna MyISAM boleh mencari data dalam satu langkah, tetapi InnoDB memerlukan dua langkah Sudah tentu, prestasi pertanyaan MyISAM lebih tinggi.
Artikel ini mula-mula membincangkan struktur data mana yang lebih sesuai sebagai pelaksanaan indeks asas Mysql, dan kemudian memperkenalkan pelaksanaan asas dua enjin data klasik Mysql, MyISAM dan InnoDB. Akhir sekali, mari kita ringkaskan apabila anda perlu mengindeks medan dalam jadual anda:
Medan yang lebih kerap digunakan sebagai syarat pertanyaan harus diindeks; dengan keunikan yang lemah tidak sesuai untuk mencipta indeks sahaja, walaupun medan itu kerap digunakan sebagai syarat pertanyaan;
[Cadangan berkaitan:
tutorial video mysql
]
Atas ialah kandungan terperinci Mengapa indeks mysql pantas?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
