Apakah indeks dalam MySQL? Analisis ringkas model storan indeks

Lajur tutorial mysql berikut akan memberi anda analisis mendalam tentang indeks dalam MySQL dan memperkenalkan sedikit pengetahuan tentang indeks MySQL. Saya harap ia akan membantu anda!

Pangkalan data MySQL sepatutnya menjadi salah satu pangkalan data yang paling biasa digunakan dalam pelbagai syarikat besar dan kecil. Jika kita ingin menggunakannya dengan lebih baik, kita mesti memahaminya dahulu. Bak kata pepatah Seorang pekerja hendak menjalankan tugasnya dengan baik, dia harus mengasah alatnya dahulu.

Artikel ini akan membawa anda kepada analisis mendalam tentang beberapa pengetahuan tentang indeks MySQL Mula-mula, mari kita fahami apa itu indeks, potongan model storan indeks, dan mengapa struktur data asas dipilih sebagai. pokok B Sebabnya?

Apakah itu indeks?

Jadual mempunyai 5 juta keping data Jalankan pertanyaan tempat pada medan nama tanpa indeks:

select * from user_innodb where name ='小马';

Bagaimana jika terdapat indeks pada medan nama? Buat indeks pada medan nama dan laksanakan pertanyaan yang sama sekali lagi.

ALTER TABLE user_innodb DROP INDEX idx_name; 
ALTER TABLE user_innodb ADD INDEX idx_name (name);

Berbanding dengan pertanyaan tanpa indeks, kecekapan pertanyaan dengan indeks adalah berpuluh-puluh kali berbeza.

Melalui kes ini, anda seharusnya dapat merasakan secara intuitif bahawa pengindeksan boleh meningkatkan prestasi pengambilan data dengan banyak.

Jadi apakah sebenarnya indeks itu? Mengapakah ia boleh memberi kesan yang begitu besar pada pertanyaan kami? Apa yang berlaku apabila indeks dibuat?

Takrif indeks

Indeks pangkalan data ialah struktur data yang disusun dalam sistem pengurusan pangkalan data (DBMS) untuk membantu dalam membuat pertanyaan dan mengemas kini data dengan pantas dalam jadual pangkalan data .

Data disimpan pada cakera dalam bentuk fail, dan setiap baris data mempunyai alamat cakeranya. Jika tiada indeks, kami perlu mendapatkan sekeping data daripada 5 juta baris data, dan kami hanya boleh melintasi semua data dalam jadual ini sehingga kami menemui sekeping data ini.

Tetapi selepas kami mempunyai indeks, kami hanya perlu mendapatkan semula data ini dalam indeks, kerana ia adalah struktur data khas yang direka untuk mendapatkan semula dengan pantas Selepas kami mencari alamat cakera tempat data disimpan, , anda boleh dapatkan data.

Jenis indeks

Dalam InnoDB, terdapat tiga jenis indeks: indeks biasa, indeks unik (indeks kunci utama ialah indeks unik khas) dan penuh -indeks teks.

Biasa : Juga dipanggil indeks bukan unik, ia adalah indeks yang paling biasa tanpa sebarang sekatan.

Unik : Indeks unik memerlukan nilai kunci tidak boleh diulang. Selain itu, perlu diambil perhatian bahawa indeks kunci utama ialah indeks unik khas Ia juga mempunyai sekatan tambahan, yang memerlukan nilai kunci tidak boleh kosong . Indeks kunci utama dibuat menggunakan kunci utama.

Fulltext : Untuk data yang agak besar, sebagai contoh, jika kami menyimpan kandungan mesej dan beberapa KB data, jika kami ingin menyelesaikan masalah kecekapan rendah pertanyaan serupa , anda boleh mencipta indeks teks penuh. Indeks teks penuh hanya boleh dibuat untuk medan jenis teks, seperti char, varchar dan teks.

Indeks ialah struktur data, jadi apakah jenis struktur data yang harus dipilih untuk mencapai perolehan data yang cekap?

Potongan model storan indeks

Carian binari

Selepas Double Eleven, teman wanita anda bermain dengan anda permainan meneka Nombor. Cuba teka berapa banyak yang saya beli semalam dan beri anda lima peluang.

10000? rendah. 30,000? tinggi. Apa yang anda akan teka seterusnya? 20000. Mengapa anda tidak meneka 11,000 atau 29,000?

Ini adalah idea carian binari, juga dipanggil carian separuh Setiap kali, kami mengurangkan data calon sebanyak separuh. Kaedah ini lebih cekap jika data telah diisih.

Maka pertama, kita boleh mempertimbangkan untuk menggunakan tatasusunan tertib sebagai struktur data yang diindeks.

Pertanyaan yang sama dan pertanyaan perbandingan bagi tatasusunan tersusun adalah sangat cekap, tetapi akan ada masalah apabila mengemas kini data Sebilangan besar data mungkin perlu dialihkan (tukar indeks), jadi ia hanya sesuai untuk disimpan data statik.

Untuk menyokong pengubahsuaian yang kerap, seperti memasukkan data, kami perlu menggunakan senarai terpaut. Bagi senarai terpaut, jika ia adalah senarai pautan tunggal, kecekapan cariannya masih tidak cukup tinggi.

Jadi, adakah senarai terpaut yang boleh menggunakan carian binari?

Untuk menyelesaikan masalah ini, BST (Binary [ˈbaɪnəri] Search Tree), iaitu apa yang kita panggil pokok carian binari, telah dilahirkan.

Pokok Carian Perduaan

Semua nod dalam subpokok kiri lebih kecil daripada nod induk dan semua nod dalam subpokok kanan lebih besar daripada nod induk . Selepas diunjurkan ke atas satah, ia menjadi jadual linear tertib.

二叉查找树既能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。

什么情况是最坏的情况呢？

还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、10、12、15、 21、28

这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。

造成它倾斜的原因是什么呢？

因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。

所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？

这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。

平衡二叉树（AVL Tree）

平衡二叉树的定义：左右子树深度差绝对值不能超过 1。

是什么意思呢？比如左子树的深度是 2，右子树的深度只能是 1 或者 3。

这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。

那 AVL 树的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？ 例如：插入 1、2、3。

当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。

那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。

同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。

所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？ 在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

第一个：索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。

第二个：数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。

第三个因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。

如果是这样存储数据的话，我们来看一下会有什么问题。

首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, 
CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len 
from information_schema.TABLES 
where table_schema='gupao' and table_name='user_innodb';

当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。

Kemudian, satu nod pokok bersaiz 16K. Jika kita hanya menyimpan satu rujukan data nilai kunci dalam nod, seperti medan integer, ia mungkin hanya menggunakan sedozen atau berdozen bait, yang jauh daripada kapasiti 16K, jadi mengakses nod Pokok membuang banyak ruang semasa melakukan IO.

Jadi jika setiap nod menyimpan terlalu sedikit data, untuk mencari data yang kami perlukan daripada indeks, kami perlu mengakses lebih banyak nod, yang bermaksud akan terdapat terlalu banyak interaksi dengan cakera.

Dalam era cakera keras mekanikal, setiap kali membaca data daripada cakera memerlukan masa pencarian kira-kira 10ms Semakin banyak interaksi, semakin banyak masa yang digunakan.

Sebagai contoh, dalam gambar di atas, kita mempunyai 6 keping data dalam satu jadual Apabila kita menanyakan id=37, untuk menanyakan dua nod anak, kita perlu berinteraksi dengan cakera tiga kali beratus-ratus Bagaimana pula dengan data 10,000? Kali ini lebih sukar untuk dianggarkan.

Jadi apakah penyelesaian kami?

Yang pertama ialah membenarkan setiap nod menyimpan lebih banyak data.

Kedua, lebih banyak kata kunci pada nod, lebih banyak penunjuk yang kita ada, yang bermakna terdapat lebih banyak garpu.

Oleh kerana semakin banyak dahan, kedalaman pokok akan berkurangan (nod akar ialah 0). Dengan cara ini, adakah pokok kita akan berubah dari rupa asal tinggi dan kurus kepada rupa pendek dan gemuk?

Pada masa ini, pokok kami tidak lagi bercabang dua, tetapi bercabang berbilang, atau berbilang hala.

Pokok carian seimbang berbilang hala (Pokok B)

Sama seperti pepohon AVL, pepohon B menyimpan nilai utama, alamat data dan rujukan nod dalam cawangan nod dan nod daun.

Ia mempunyai ciri: bilangan garpu (bilangan laluan) sentiasa 1 lebih daripada bilangan kata kunci. Sebagai contoh, dalam pepohon yang kami lukis, setiap nod menyimpan dua kata kunci, jadi akan ada tiga penunjuk yang menghala ke tiga nod anak.

Apakah peraturan carian untuk B Tree?

Sebagai contoh, kami ingin mencari 15 dalam jadual ini. Oleh kerana 15 adalah kurang daripada 17, pergi ke kiri. Oleh kerana 15 lebih besar daripada 12, pergi ke kanan. 15 ditemui dalam blok cakera 7, dan hanya 3 IO digunakan.

Adakah ini lebih cekap daripada pokok AVL? Jadi bagaimana B Tree menyedari bahawa satu nod menyimpan berbilang kata kunci dan masih mengekalkan keseimbangan? Apakah perbezaan dengan pokok AVL?

Sebagai contoh, apabila Darjah Maks (bilangan cara) ialah 3, kami memasukkan data 1, 2, dan 3. Apabila memasukkan 3, ia sepatutnya berada dalam blok cakera pertama, tetapi jika a nod mempunyai tiga Apabila kata kunci digunakan, ini bermakna terdapat 4 penunjuk, dan nod anak akan menjadi 4 hala, jadi ia mesti dipecahkan pada masa ini (sebenarnya Pokok B). Kemukakan data tengah 2 dan ubah 1 dan 3 menjadi nod anak 2.

Jika anda memadamkan nod, akan ada operasi cantum terbalik.

Perhatikan bahawa ini membelah dan bergabung, yang berbeza daripada pusingan kiri dan kanan pokok AVL.

Kami terus memasukkan 4 dan 5, dan B Tree akan berpecah dan bergabung semula.

Daripada ini, kita juga dapat melihat bahawa akan terdapat sejumlah besar pelarasan struktur indeks semasa mengemas kini indeks, yang menerangkan sebab kami tidak menambah lajur yang kerap dikemas kini. indeks di atas, atau mengapa tidak mengemas kini kunci utama.

Pemecahan dan penggabungan nod sebenarnya adalah pemisahan dan penggabungan halaman InnoDB.

B Tree (versi B Tree yang dipertingkatkan)

B Tree sudah sangat cekap Mengapa MySQL masih perlu menambah baik B Tree dan akhirnya menggunakannya ? Bagaimana dengan B Tree?

Secara umumnya, versi B-Tree yang dipertingkatkan ini menyelesaikan masalah yang lebih komprehensif daripada B-Tree.

Mari kita lihat struktur storan B-tree dalam InnoDB:

B-tree dalam MySQL mempunyai beberapa ciri:

1. Bilangan kata kuncinya adalah sama dengan bilangan laluan

2. B Tree tidak akan menyimpan data dalam nod akarnya; atau nod cawangan , hanya nod daun yang menyimpan data. Mencari kata kunci tidak akan kembali secara langsung, tetapi akan pergi ke nod daun lapisan terakhir. Sebagai contoh, jika kita mencari id=28, walaupun ia terkena terus pada lapisan pertama, semua data berada pada nod daun, jadi saya akan terus mencari ke bawah, sehingga ke nod daun.

3. Setiap nod daun Pokok B menambah penuding pada nod daun bersebelahan, dan data terakhirnya akan menghala ke data pertama nod daun seterusnya, membentuk struktur tersusun senarai terpaut.

4. Ia mendapatkan semula data berdasarkan selang [ ) yang ditutup di sebelah kiri dan terbuka di sebelah kanan.

Proses carian data B Tree:

1. Sebagai contoh, jika kita ingin mencari 28, kita telah menemui nilai kunci pada nod akar, tetapi kerana ia bukan nod anak halaman, kita akan terus mencari 28 adalah kiri, tertutup dan kanan [28,66) Nilai kritikal selang terbuka, jadi nod anak tengah akan berjalan, dan kemudian carian akan diteruskan Ia juga merupakan nilai kritikal bagi kiri-tutup dan kanan-. selang terbuka [28,34), jadi nod anak kiri akan berjalan, dan akhirnya nod daun Data yang diperlukan ditemui pada.

2. Kedua, jika ia adalah pertanyaan julat, contohnya, jika anda ingin menanyakan data dari 22 hingga 60, selepas mencari 22, anda hanya perlu melintasi nod dan penunjuk secara berurutan ke akses semuanya sekali gus ke semua nod data, yang meningkatkan kecekapan pertanyaan selang (tidak perlu kembali ke nod induk atas untuk melintasi carian berulang kali).

Ciri B Tree dalam InnoDB:

1. Ia adalah varian B Tree, yang boleh diselesaikan dengan B Masalah Pokok boleh diselesaikan. Apakah dua masalah utama yang diselesaikan oleh Pokok B? (Setiap nod menyimpan lebih banyak kata kunci; lebih banyak laluan); sudah cukup, tidak perlu melintasi seluruh B Tree untuk mendapatkan semua data;

2. Keupayaan membaca dan menulis cakera B Tree lebih kuat daripada B Tree (nod akar The branch). nod tidak menyimpan kawasan data, jadi nod boleh menyimpan lebih banyak kata kunci, dan lebih banyak kata kunci boleh dimuatkan ke dalam cakera pada satu masa); adalah Penunjuk ke kawasan data seterusnya, data membentuk senarai terpaut); adalah stabil).

3. Postskrip

Selepas melihat ini, saya percaya semua orang harus tahu mengapa MySQL memilih untuk menggunakan B-tree sebagai model struktur data indeks.

4. Untuk lebih banyak pengetahuan berkaitan pengaturcaraan, sila lawati:

   Pengenalan kepada Pengaturcaraan
! !

Atas ialah kandungan terperinci Apakah indeks dalam MySQL? Analisis ringkas model storan indeks. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!