Apakah perbezaan antara indeks B-tree dan indeks B+-tree dalam MySQL?

Jika anda menggunakan pepohon sebagai struktur data indeks, setiap kali anda mencari data, satu nod pepohon akan dibaca daripada cakera, yang merupakan halaman Walau bagaimanapun, setiap nod pepohon perduaan hanya menyimpan satu bahagian data dan tidak dapat mengisi ruang storan halaman, bukankah ruang storan tambahan akan dibazirkan? Untuk menyelesaikan kekurangan pepohon carian seimbang binari ini, kita harus mencari struktur data yang boleh menyimpan lebih banyak data dalam satu nod, iaitu pepohon carian berbilang hala.

1. Pokok carian berbilang laluan

1. Lengkapkan ketinggian pokok perduaan: O(log2N), dengan 2 ialah logaritma, bilangan nod pada setiap peringkat

2. Lengkapkan Ketinggian pepohon carian M-way: O(logmN), dengan M ialah logaritma, bilangan nod pada setiap peringkat pepohon

Pokok carian M-way ialah sesuai untuk senario di mana jumlah data yang disimpan terlalu besar untuk dimuatkan ke dalam memori pada satu masa. Simpan lebih banyak data dalam satu lapisan dengan menambah bilangan nod setiap lapisan dan menyimpan lebih banyak data dalam setiap nod, dengan itu mengurangkan ketinggian pepohon dan mengurangkan bilangan akses cakera semasa carian data.

Oleh itu, jika bilangan kata kunci setiap nod mengandungi dan bilangan nod setiap tahap meningkat, ketinggian pokok akan berkurangan. Walaupun penentuan data setiap nod akan lebih memakan masa, fokus B-tree adalah untuk menyelesaikan kesesakan prestasi cakera, jadi kos mencari data pada satu nod boleh diabaikan.

2. B-tree - pokok carian seimbang berbilang hala

B-tree ialah pokok carian M-way digunakan terutamanya untuk menyelesaikan ketidakseimbangan carian M-way pokok menyebabkan perubahan ketinggian pokok, yang sama dengan masalah prestasi yang disebabkan oleh pokok binari merosot ke senarai terpaut. B-tree memastikan keseimbangan pepohon carian M-way dengan mengawal dan melaraskan nod setiap lapisan, seperti pemisahan nod, penggabungan nod, membelah nod induk ke atas apabila satu lapisan penuh untuk menambah lapisan baharu dan operasi lain.

Dalam pepohon B, setiap nod ialah blok cakera (halaman), dan urutan atau nombor laluan M menentukan bilangan maksimum nod anak dalam nod. Setiap nod bukan daun menyimpan kata kunci dan penunjuk kepada subpokok Nombor khusus ialah: M-order B-tree, setiap nod bukan daun menyimpan kata kunci M-1 dan M pointer kepada subtree. Gambar menunjukkan gambar rajah skema struktur pokok B 5 tertib:

3 indeks pokok B

Buat pengguna dahulu jadual:

create table user(
	id int,
	name varchar,
	primary key(id)
) ROW_FORMAT=COMPACT;

Andaikan kita menggunakan B-tree untuk mengindeks rekod pengguna dalam jadual:

Setiap nod daripada pokok-B menduduki satu blok cakera juga merupakan halaman Seperti yang dapat dilihat dari rajah di atas, berbanding dengan pokok binari seimbang, setiap nod pokok B menyimpan lebih banyak kunci dan data utama, dan setiap nod mempunyai lebih banyak nod anak. . Jika kita ingin mencari maklumat pengguna id=28, proses carian adalah seperti berikut:

1. Cari halaman 1 mengikut nod akar dan baca ke dalam memori. [Operasi I/O Cakera kali pertama]

2 Bandingkan nilai kunci 28 dalam selang (17,35), cari penunjuk p2 pada halaman 1; berdasarkan penunjuk p2 3. Baca ke dalam ingatan. [Kendalian I/O Cakera kali ke-2]

4. Bandingkan nilai kekunci 28 dalam selang (26, 35), dan cari penunjuk p2 halaman 3.

5. Cari halaman 8 mengikut penunjuk p2 dan baca ke dalam ingatan. [Kendalian I/O Cakera kali ke-3]

6 Cari nilai kunci 28 dalam senarai nilai kunci pada halaman 8. Maklumat pengguna yang sepadan dengan nilai kunci ialah (28,po); 🎜 >

mengurangkan bilangan nod berbanding

, supaya data yang diambil daripada memori setiap kali I/O cakera digunakan, dengan itu meningkatkan kecekapan pertanyaan.

4. Indeks pokok B+ B-TreeAVLTreeB+Tree ialah pengoptimuman berdasarkan B-Tree, menjadikannya lebih sesuai untuk melaksanakan struktur indeks storan luar Ciri-ciri pokok B+:

1. Penunjuk subpokok bagi nod bukan daun adalah sama dengan bilangan kata kunci; daun Nod muncul, dan kata kunci dalam senarai terpaut berada dalam urutan

4. Nod bukan daun adalah bersamaan dengan indeks nod daun dan nod daun adalah bersamaan dengan lapisan data yang menyimpan. (kata kunci) data;

Enjin storan InnoDB menggunakan B+Tree untuk melaksanakan struktur indeksnya.

Ia boleh dilihat dalam rajah struktur B-tree bahawa setiap nod juga mengandungi nilai data sebagai tambahan kepada nilai kunci data. Ruang storan setiap halaman adalah terhad Jika data data adalah besar, bilangan kunci yang boleh disimpan dalam setiap nod (iaitu satu halaman) akan menjadi sangat kecil Apabila jumlah data yang disimpan adalah besar, ia juga akan membawa ke B- Kedalaman Pokok lebih besar, yang meningkatkan bilangan I/O cakera semasa pertanyaan, sekali gus menjejaskan kecekapan pertanyaan. Dalam B+Tree, semua nod rekod data disimpan pada nod daun dalam lapisan yang sama mengikut urutan nilai kunci Hanya maklumat nilai kunci disimpan pada nod bukan daun Ini boleh meningkatkan bilangan nilai kunci yang disimpan dalam setiap satu nod. , kurangkan ketinggian B+Tree.

B+Tree mempunyai beberapa perbezaan berbanding dengan B-Tree:

1. Nod bukan daun hanya menyimpan maklumat nilai utama dan penunjuk kepada nombor halaman nod anak

2. Terdapat penunjuk pautan di antara semua nod daun;

Berdasarkan gambar di atas, mari kita lihat perbezaan antara pokok B+ dan B-tree:

(2) Dalam B+ pokok, Nod bukan daun hanya menyimpan nilai utama, manakala nod B-tree menyimpan kedua-dua nilai utama dan data.

Saiz halaman ditetapkan, saiz halaman lalai dalam InnoDB ialah 16KB. Jika data tidak disimpan, lebih banyak nilai kunci akan disimpan, susunan pokok yang sepadan akan menjadi lebih besar, dan pokok itu akan menjadi lebih pendek dan lebih gemuk Akibatnya, bilangan kali IO cakera yang kita perlukan untuk mencari data akan dikurangkan lagi Kecekapan pertanyaan data juga akan lebih cepat.

Selain itu, jika satu nod pokok B+ kami boleh menyimpan 1000 nilai utama, maka pokok B+ 3 lapisan boleh menyimpan 1000×1000×1000=1 bilion keping data. Secara amnya, nod akar bermastautin dalam ingatan (tidak perlu membaca cakera apabila mendapatkan semula nod akar buat kali pertama), jadi secara amnya kita hanya memerlukan 2 cakera IO untuk mencari 1 bilion data.

(2) Semua data dalam indeks pepohon B+ disimpan dalam nod daun dan data disusun mengikut tertib.

B+ Halaman dalam pepohon disambungkan melalui senarai terpaut dua hala dan data dalam nod daun disambungkan melalui senarai terpaut sehala Dengan cara ini, semua data dalam jadual boleh ditemui. Pepohon B+ membuat pertanyaan julat, pertanyaan mengisih, pertanyaan kumpulan dan pertanyaan penyahduplikasian sangat mudah. Dalam B-tree, kerana data bertaburan dalam pelbagai nod, tidak mudah untuk mencapai ini.

Atas ialah kandungan terperinci Apakah perbezaan antara indeks B-tree dan indeks B+-tree dalam MySQL?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!