Pemahaman mendalam tentang struktur indeks MySQL

Artikel ini membawa anda pengetahuan yang berkaitan tentang mysql, yang terutamanya memperkenalkan isu berkaitan tentang struktur indeks. Jadi, apakah struktur indeks? Mengapa pengindeksan boleh begitu pantas? Mari kita lihat di bawah, saya harap ia akan membantu semua orang.

Pembelajaran yang disyorkan: tutorial mysql

Unit storan pangkalan data

Pertama sekali, kita perlu tahu bahawa untuk mencapai kegigihan, indeks hanya boleh disimpan pada cakera keras Apabila membuat pertanyaan melalui indeks, operasi I/O pada cakera keras akan berlaku, apabila mereka bentuk indeks, adalah perlu untuk mengurangkan bilangan mencari sebanyak mungkin, dengan itu mengurangkan I/O memakan masa.

Selain itu, anda perlu mengetahui prinsip yang sangat penting: unit asas ruang penyimpanan pengurusan pangkalan data ialah 页(Page), dan rekod baris berbilang (Baris) disimpan dalam satu halaman.

Sistem komputer akan melakukan 预读 pengoptimuman untuk I/O cakera Apabila I/O dilakukan, sebagai tambahan kepada data pada alamat cakera semasa, data bersebelahan juga akan dibaca ke dalam penimbal memori. pool. , data yang dibaca oleh setiap I/O menjadi satu halaman dan saiz halaman lalai InnoDB ialah 16KB.
64 halaman berturut-turut membentuk 区(Extent), satu atau lebih takat membentuk 段(Segment) dan satu atau lebih segmen membentuk 表空间(Tablespace). InnoDB mempunyai dua jenis ruang jadual Ruang jadual yang dikongsi bermakna berbilang jadual berkongsi satu ruang jadual bebas bermakna data dan indeks setiap jadual disimpan dalam ruang jadual bebas.

Struktur halaman data adalah seperti berikut (Sumber: Geek Time "MySQL Must Know"):

7 kandungan struktur halaman data boleh dibahagikan secara kasar kepada berikut tiga kategori:

• Bahagian umum fail, digunakan untuk mengesahkan bahawa penghantaran halaman selesai
  • Tajuk Fail: menyatakan maklumat halaman FIL_PAGE_PREV dan FIL_PAGE_NEXT digunakan dalam pengepala fail untuk membentuk senarai terpaut berganda, masing-masing Menunjukkan ke halaman data sebelumnya dan seterusnya.
  • Pengepala Fail: Rekod maklumat status halaman
  • Treler Fail: Sahkan sama ada halaman itu lengkap
• Bahagian rekod , digunakan untuk menyimpan data rekod
  • Rekod maksimum dan minimum (Infimum/Supremum): rekod baris maya, mewakili rekod maksimum dan rekod minimum halaman data.
  • Rekod Pengguna dan Ruang Bebas: digunakan untuk menyimpan kandungan rekod baris data
• Bahagian indeks, digunakan untuk meningkatkan kecekapan mendapatkan semula rekod
  • Direktori Halaman: Kedai lokasi relatif rekod pengguna

Untuk butiran, sila rujuk laporan bulanan kernel pangkalan data Taobao

Struktur data indeks

Sememangnya, kami akan memikirkan beberapa struktur data biasa yang terlibat dalam algoritma carian, seperti pepohon carian binari, pepohon seimbang perduaan, dsb. Malah, indeks Innodb menggunakan B 树 Dilaksanakan, mari kita lihat mengapa struktur indeks ini dipilih.

Keterbatasan Pokok Binari

Mari kita semak secara ringkas definisi Pokok Carian Binari Dalam pepohon carian binari, jika kunci yang ditemui lebih besar daripada nod akar, maka dalam Carian dalam subpokok kanan Jika kunci lebih kecil daripada nod akar, cari dalam subpokok kiri sehingga kunci ditemui Kerumitan masa ialah O(logn). Sebagai contoh, jujukan [4,2,6,1,3,5,7] akan menjana pepohon carian binari berikut:

Walau bagaimanapun, dalam beberapa kes khas, kedalaman pepohon binari akan menjadi sangat besar. Contohnya, [1,2,3,4,5,6,7] akan menjana pokok berikut:

Dalam kes berikut, dalam kes yang paling teruk, ia memerlukan 7 kali untuk menyemak Hasil yang diingini boleh didapati, dan masa pertanyaan menjadi O(n).

Untuk mengoptimumkan keadaan ini, terdapat pepohon carian binari seimbang (pokok AVL merujuk kepada pokok yang perbezaan ketinggian antara subpokok kiri dan kanan tidak melebihi 1. Carian). kerumitan masa ialah O(logn) , ini sudah pun menjadi pepohon carian yang ideal, tetapi dalam pangkalan data dengan berpuluh-puluh juta baris rekod, kedalaman pokok itu akan tetap sangat tinggi, dan ia masih bukan struktur yang paling ideal.

Pokok B

Jadi, jika anda berkembang daripada pokok binari kepada pokok N-ary, mudah untuk membayangkan bahawa pokok N-ary boleh mengurangkan kedalaman pokok itu dengan banyak. Malah, struktur pokok 4 lapisan adalah Ia sudah boleh menyokong berpuluh-puluh terabait data.

B-tree (Pokok Imbangan) ialah pokok N-ary yang juga dipanggil B-pokok, yang memenuhi definisi berikut:
Biarkan k sebagai darjah B-pokok. mewakili setiap Bilangan maksimum nod anak yang boleh dimiliki oleh nod),

1. Setiap blok cakera mengandungi paling banyak k - 1 kata kunci dan k penunjuk ke nod anak
2. Dalam nod daun, hanya ada kata kunci dan tiada penunjuk nod anak
3. The kata kunci dalam setiap nod disusun dalam susunan menaik Semua kata kunci dalam subpokok kiri setiap kata kunci adalah lebih kecil daripadanya, dan semua kata kunci dalam subpokok kanan adalah lebih besar daripadanya.
4. Semua nod daun berada pada lapisan yang sama.

Seperti yang dinyatakan di atas, setiap I/O akan pra-membaca data blok cakera, yang bersaiz satu halaman Kandungan blok cakera digunakan untuk mewakili I/O. Struktur B-tree adalah seperti Gambar berikut (Sumber: Geek Time SQL mesti tahu):

B-tree juga dipesan Memandangkan penunjuk nod anak mestilah 1 lebih daripada kata kunci , ia boleh dibahagikan kepada sub-pokok menggunakan kata kunci Bahagian nod, seperti dalam contoh dalam rajah, setiap nod mempunyai 2 kekunci dan 3 nod anak, seperti blok cakera 2, kunci titik bait pertama ialah. 3, 5 adalah kurang daripada nod anak pertamanya sendiri 8 , nod anak kedua 9, 10 adalah antara 8 dan 12, nilai nod anak ketiga 13, 15 lebih besar daripada nod anak kedua 12 sendiri.

Andaikan kita ingin mencari 9 sekarang, langkah-langkahnya adalah seperti berikut:

1. Bandingkan dengan blok cakera nod akar 1 (17,35), kurang daripada 17, teruskan untuk mencari dalam penuding P1, sepadan dengan cakera Blok 2
2. dibandingkan dengan blok cakera 2 (8,12), terletak di antara keduanya, teruskan mencari di penunjuk P2, sepadan dengan blok cakera 6
3. dan blok cakera 6 (9, 10) Bandingkan dan cari 9

Anda dapat melihat bahawa walaupun banyak operasi perbandingan dilakukan, disebabkan prabacaan, perbandingan dalam blok cakera dilakukan dalam ingatan dan tidak menggunakan cakera I/O, operasi di atas hanya memerlukan 3 kali I/O untuk diselesaikan, yang merupakan struktur yang ideal.

Indeks B-tree

B-tree dipertingkatkan lagi berdasarkan B-tree Perbezaan antara B-tree dan B-tree adalah seperti berikut:

.
1. B-pokok dibina sedemikian rupa sehingga, untuk kata kunci dalam nod induk, semua kata kunci subpokok kiri adalah kurang daripadanya dan semua kata kunci subpokok kanan lebih besar daripada atau sama dengannya
2. Nod bukan daun hanya digunakan untuk pengindeksan, Tiada rekod data akan disimpan
3. Kata kunci nod induk juga akan muncul dalam nod anak, dan ia adalah nilai maksimum (atau nilai minimum) dalam nod anak
4. Semua kata kunci akan muncul dalam nod anak Antara nod daun, nod daun membentuk senarai terpaut tersusun, diisih dari kecil ke besar.

Contohnya adalah seperti berikut, kata kunci nod induk ialah nilai minimum di antara nod anak (Sumber: Geek Time SQL mesti tahu):
Andaian Untuk mencari kata kunci 16, langkah carian adalah seperti berikut:

1. Bandingkan dengan cakera nod akar 1 (1,18,35), 16 antara 1 dan 18, dapatkan penunjuk P1 , menunjuk ke cakera 2
2. Cari cakera 2 (1,8,14), 16 lebih besar daripada 14, dapatkan penunjuk P3, tuding ke cakera 7
3. Cari cakera 7 (14,16, 17), cari 16

Kelebihan B-tree:

1. Nod dalaman tidak menyimpan data, jadi bilangan rekod yang boleh disimpan oleh setiap nod dalaman adalah lebih besar daripada B-tree, ketinggian pokok lebih rendah, dan I/O kurang, Halaman data dibaca setiap kali I/O mengandungi lebih banyak kandungan
2. Boleh menyokong pertanyaan julat, hanya melintasi senarai terpaut tersusun yang terdiri daripada nod daun secara langsung
3. Semua data disimpan dalam nod daun , jadi kecekapan pertanyaan lebih stabil

Indeks HASH

Struktur indeks lalai enjin storan memori MySQL ialah indeks Hash. Hash ialah fungsi yang dipanggil fungsi cincang, yang dihantar melalui Algoritma tertentu (seperti MD5, SHA1, SHA2, dll.) menukar input panjang sewenang-wenangnya kepada output dengan panjang tetap satu. Artikel ini tidak akan memberikan pengenalan yang mendalam kepada fungsi cincang Untuk butiran, sila rujuk kepada Baidu Encyclopedia.

Kecekapan carian hash ialah O(1), yang sangat cekap dict python, peta golang dan peta cincang java semuanya dilaksanakan berdasarkan pangkalan data Key-Value seperti Redis juga dilaksanakan Hash.

Untuk carian yang tepat, indeks Hash lebih cekap daripada indeks B-tree, tetapi indeks Hash mempunyai beberapa had dan oleh itu bukan struktur indeks paling arus perdana.

1. Oleh kerana data yang ditunjuk oleh indeks Hash tidak tertib, indeks Hash tidak boleh dipersoalkan dalam julat dan tidak menyokong ORDER BY sorting.
2. Memandangkan Hash ialah padanan tepat, pertanyaan kabur tidak boleh dilakukan.
3. Indeks cincang tidak menyokong prinsip padanan paling kiri bagi indeks bersama, dan indeks bersama hanya berkuat kuasa apabila terdapat padanan lengkap. Kerana indeks Hash mengira nilai Hash dengan menggabungkan indeks dan kemudian mengira nilai Hash bersama-sama, bukannya mengira nilai Hash berasingan bagi setiap indeks.
4. Jika medan diindeks mempunyai banyak nilai pendua, ia akan menyebabkan sejumlah besar konflik cincang dan pertanyaan akan menjadi sangat memakan masa.

Berdasarkan sebab di atas, enjin Mysql InnoDB tidak menyokong indeks Hash, tetapi terdapat fungsi indeks Hash adaptif dalam struktur memori Apabila nilai indeks digunakan dengan sangat kerap, ia akan menjadi dalam B Berdasarkan indeks pepohon, secara automatik mencipta indeks Hash untuk meningkatkan prestasi pertanyaan.

Indeks Adaptive Hash boleh difahami sebagai "indeks indeks". Indeks Hash digunakan untuk menyimpan alamat halaman dalam indeks B-tree dan mencari nod daun yang sepadan dengan cepat. Ia boleh dilihat melalui pembolehubah innodb_adaptive_hash_index.

Pembelajaran yang disyorkan: tutorial mysql

Atas ialah kandungan terperinci Pemahaman mendalam tentang struktur indeks MySQL. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!