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.
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;
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 并没有采取哈希作为其底层算法，这是为什么呢？
因为考虑到数据检索有一个常用手段就是范围查找，比如以下这个 SQL 语句：
select * from user where id \>3;
针对以上这个语句，我们希望做的是找出 id>3 的数据，这是很典型的范围查找。如果使用哈希算法实现的索引，范围查找怎么做呢？一个简单的思路就是一次把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。但是这个范围查找的方法也太笨重了，没有一点效率而言。
所以，使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效范围查找，因此哈希索引是不适合作为 Mysql 的底层索引的数据结构。
二叉查找树(BST)
二叉查找树是一种支持数据快速查找的数据结构，如图下所示:
二叉查找树的时间复杂度是 O(lgn)，比如针对上面这个二叉树结构，我们需要计算比较 3 次就可以检索到 id=7 的数据，相对于直接遍历查询省了一半的时间，从检索效率上看来是能做到高速检索的。此外二叉树的结构能不能解决哈希索引不能提供的范围查找功能呢？
答案是可以的。观察上面的图，二叉树的叶子节点都是按序排列的，从左到右依次升序排列，如果我们需要找 id>5 的数据，那我们取出节点为 6 的节点以及其右子树就可以了，范围查找也算是比较容易实现。
但是普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表，二分查找也会退化为遍历查找，时间复杂退化为 O（N），检索性能急剧下降。比如以下这个情况，二叉树已经极度不平衡了，已经退化为链表了，检索速度大大降低。此时检索 id=7 的数据的所需要计算的次数已经变为 7 了。
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:
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:
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 
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:
Fail yang dijana oleh Myisam selepas mencipta jadual ialah
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:
Atas ialah kandungan terperinci Mengapa indeks mysql pantas?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
