Mari kita bercakap secara mendalam tentang mengapa indeks mysql menggunakan struktur B-tree

Artikel ini adalah kajian lanjutan tentang mysql Ia memperkenalkan sebab mengapa mysql menggunakan B-tree sebagai struktur data indeks saya harap ia akan membantu semua orang.

Indeks meningkatkan kecekapan pertanyaan, sama seperti buku yang kita baca, jika kita ingin membelok terus ke bab tertentu, kita tidak perlu membelek halaman demi halaman, cuma bacalah Jadual kandungan, cuma cari nombor halaman di mana ia terletak mengikut jadual kandungan. [Cadangan berkaitan: tutorial video mysql]

Dalam komputer, kami memerlukan struktur data untuk menyimpan direktori ini Struktur data biasa termasuk jadual cincang, pepohon carian binari dan Pokok baki perduaan (AVL ), pokok merah-hitam, maka mengapa Innodb dan MyISAM memilih b-tree.

1. Jadual cincang

Jadual cincang ialah senarai terpaut tatasusunan, dengan subskrip 0, 1, 2, 3..... menunjukkan lokasi datanya. Jika anda ingin menyimpan data dalam jadual cincang, mula-mula gunakan algoritma cincang pada data (yang asas ialah operasi modulo Jika panjang tatasusunan ialah 13, selepas modulo 13, ia akan menjadi 0-12, yang sepadan dengan). bahagian bawah data Jika subskrip yang dikira adalah sama, senarai terpaut akan mengikut kedudukan subskrip.

Kelemahan:

1. Menggunakan storan cincang memerlukan penambahan semua fail data pada memori, yang menggunakan lebih banyak ruang memori.
2. Carian cincang ialah pertanyaan yang setara, yang sangat pantas, tetapi tiada peraturan julat antara setiap data Walau bagaimanapun, dalam kerja sebenar, lebih banyak pertanyaan julat digunakan dan cincang tidak sesuai.

Tidak boleh dikatakan secara langsung bahawa mysql tidak menggunakan jadual cincang, tetapi ia mesti ditentukan berdasarkan enjin storan Memori menggunakan jadual cincang

Menyebabkan nod pokok menjadi terlalu dalam, dengan itu meningkatkan IO carian, dan kini IO adalah kesesakan carian

3 >

Untuk mengekalkan keseimbangan pokok dan mengelakkan data condong, operasi putaran diperlukan Melalui putaran kiri atau kanan, panjang subpokok terpanjang dan subpokok terpendek tidak boleh melebihi 1. Jika melebihi. 1, ia bukan pokok AVL dalam erti kata yang ketat

Kelemahan:

1 Apabila jumlah data adalah besar, mengikut urutan untuk mengekalkan keseimbangan, putaran 1-n diperlukan Putaran ini adalah perbandingan. Ia adalah pembaziran prestasi, kecekapan pemasukan dan pemadaman adalah sangat rendah, dan kecekapan pertanyaan adalah sangat tinggi.

Hanya terdapat dua dahan, dan kedalaman pokok masih sangat dalam apabila jumlah data adalah besar.

4. Pokok merah-hitam

Sub pokok terpanjang tidak boleh melebihi 2 kali ganda subpokok terpendek Melalui perubahan warna dan putaran, sisipan dan pertanyaan adalah seimbang

Pokok merah-hitam ialah varian pokok avl, yang kehilangan sebahagian daripada prestasi pertanyaan untuk meningkatkan prestasi sisipan.

Kelemahan:

Terdapat juga hanya dua cabang, dan kedalaman akan tetap sangat mendalam apabila jumlah data adalah besar

Dengan peningkatan data, tiga jenis pokok binari di atas akhirnya akan mempunyai terlalu banyak nod, dan mereka hanya mempunyai 2 cabang, jadi bilangan IO juga banyak.

Cara menyelesaikannya Hanya ada 2 dahan dan kedalaman terlalu dalam, jadi ada B-tree, tambah dahan

5 🎜>Mula-mula jangan baca pokok tolak B, baca pokok B

Semua nilai utama diedarkan ke seluruh pokok.

Carian mungkin berakhir pada nod bukan daun dan carian dilakukan dalam keseluruhan set kata kunci dan prestasinya hampir dengan carian binari. Setiap nod mempunyai paling banyak m subpokok.

Nod akar mempunyai sekurang-kurangnya 2 subpokok.

Nod cawangan mempunyai sekurang-kurangnya m/2 subpokok (semua nod cawangan kecuali nod akar dan nod daun).

Semua nod daun berada pada lapisan yang sama, setiap nod boleh mempunyai sehingga kekunci m-1, dan disusun dalam tertib menaik

Seperti yang ditunjukkan dalam gambar di atas: (Hanya sebahagian daripada gambar yang dilukis. Malah, tiada sekatan, bukan hanya p1, p2, dan p3)

4. Setiap nod menduduki blok cakera Terdapat dua kata kunci yang disusun dalam tertib menaik pada nod dan tiga penunjuk ke nod akar subpohon Penunjuk menyimpan alamat blok cakera di mana nod anak berada. Tiga medan julat dibahagikan dengan dua kata kunci sepadan dengan medan julat data subpokok yang ditunjuk oleh tiga penunjuk. Mengambil nod akar sebagai contoh, kata kunci ialah 16 dan 34. Julat data subpokok yang ditunjuk oleh penunjuk p1 adalah kurang daripada 16, julat data subpokok yang ditunjuk oleh penunjuk p2 ialah 16-34, dan data julat subpokok yang ditunjuk oleh penunjuk p3 adalah lebih besar daripada 34. .

   Proses mencari kata kunci 28:

   1. Cari blok cakera 1 berdasarkan nod akar dan bacakannya ke dalam ingatan. [Operasi I/O cakera pertama]
   2. Bandingkan kata kunci 28 dalam selang (16, 34) dan cari penunjuk p2 blok cakera 1.
   3. Cari blok cakera 3 mengikut penunjuk p2 dan baca ke dalam ingatan. [Operasi I/O cakera kedua]
   4. Bandingkan kata kunci 28 dalam selang (25, 31), dan cari penunjuk p2 blok cakera 3.
   5. mencari blok cakera 8 mengikut penunjuk p2 dan membacanya ke dalam ingatan. [Operasi I/O cakera ketiga]
   6. Cari kata kunci 28 dalam senarai kata kunci dalam blok cakera 8, hujung.

   Kelemahan:

   1. Setiap nod mempunyai kunci dan juga mengandungi data, dan ruang storan setiap halaman adalah terhad Jika data besar, ia akan menyebabkan setiap satu Bilangan kunci yang boleh disimpan oleh nod menjadi lebih kecil.
   2. Apabila jumlah data yang disimpan adalah besar, kedalaman akan meningkat, meningkatkan bilangan pertanyaan IO ke cakera, sekali gus menjejaskan prestasi pertanyaan.

   6. B-tree

   B-tree ialah pengoptimuman berdasarkan B-tree, dengan perubahan berikut:

   1. B Setiap nod pokok boleh mengandungi lebih banyak nod. Sebab pertama adalah untuk mengurangkan ketinggian pokok. Sebab kedua adalah untuk mengubah julat data menjadi berbilang selang ia adalah untuk mendapatkan semula data dengan lebih cepat.
   2. Nod bukan daun hanya menyimpan kunci dan nod daun menyimpan kunci dan data.
   3. Dua penunjuk nod daun disambungkan antara satu sama lain (selaras dengan ciri cakera baca-depan), dan prestasi pertanyaan berjujukan adalah lebih tinggi.

   

   Seperti yang ditunjukkan di atas: Terdapat dua penunjuk kepala pada pokok B, satu menunjuk ke nod akar, dan satu lagi menunjuk ke nod daun minimum kata kunci, dan terdapat struktur cincin rantai antara semua nod daun (dan nod data), jadi dua B-trees boleh Terdapat tiga operasi carian: satu ialah carian julat dan carian halaman untuk kunci utama, dan satu lagi ialah carian rawak bermula dari nod akar.

   Perbezaan dalam indeks antara InnoDB dan MyISAM

   1. Indeks kunci utama InnoDB

   Nod daun menyimpan data baris tertentu

   

   2. InnoDB-Indeks bukan kunci utama

   Nod daun indeks bukan kunci utama menyimpan nilai kunci utama (jadi data pertanyaan pada asasnya perlu dikembalikan ke jadual)

   

   3. MyISAM

   nod daun menyimpan alamat data baris, yang memerlukan pengalamatan tambahan dan satu lagi IO

   

   Ringkasan: Mengapa mysql menggunakan B-tree

   Pernyataan tepat: Mengapa indeks enjin storan InnoDB dan MyISAM mysql menggunakan B-tree

   • Jadual cincang, pertanyaan setara adalah sangat pantas, tetapi ia tidak memenuhi carian julat biasa dan tiada hubungan antara dua nilai bersebelahan, dan cincang menggunakan lebih banyak memori.

   • Pokok binari/pokok binari seimbang/pokok merah-hitam, dll semuanya ada dan cuma ada 2 dahan lebih mendalam apabila jumlah data adalah besar.

   • B-tree akan menyimpan data pada nod, jadi bilangan kekunci yang disimpan pada satu halaman akan dikurangkan dan kedalaman pokok akan ditingkatkan.

   • B Nod bukan daun dalam pepohon telah dialih keluar data, yang akan meningkatkan bilangan kekunci pada halaman dan nod daun disambungkan melalui terpaut senarai, dengan Mudah untuk carian julat dan halaman.

   Alamat asal: https://juejin.cn/post/6994810803643744269
   

   Pengarang: En. Ji

   Untuk lebih banyak pengetahuan berkaitan pengaturcaraan, sila lawati: Video Pengaturcaraan! !

Atas ialah kandungan terperinci Mari kita bercakap secara mendalam tentang mengapa indeks mysql menggunakan struktur B-tree. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!