1、B-Tree
叫B樹，記得不是B減，像iphone12-pro，不會是減pro

2、B+Tree（B+-Tree）
B加樹

有數(shù)據(jù)冗余，葉子節(jié)點存儲所有的數(shù)據(jù)

3、官方對Innodb的部分說明

4、提出疑問
創(chuàng)建一個表

然后無規(guī)律的插入數(shù)據(jù)并查詢

結(jié)果會變成 好像是根據(jù)a字段升序排序了

為什么會這樣？稍后說明

5、page？
我們先假設(shè)查詢select * from t1 where a=7;，就會先從磁盤讀取第一條數(shù)據(jù)放到內(nèi)存中，然后cpu判斷該條數(shù)據(jù)a是否等于7，不等于就要繼續(xù)讀取下一條，這樣會發(fā)生7次磁盤IO。
mysql為了提升速度，使用了page，通過show global status like 'Innodb_page_size';查看一頁的大小為16KB

所以存儲引擎每次取都會至少取一頁的數(shù)據(jù)，也就一次磁盤IO就把數(shù)據(jù)讀取到內(nèi)存中，然后CPU取第一條進行判斷，再取第二條進行判斷。

在數(shù)據(jù)插入的時候就已經(jīng)進行了排序

6、為什么插入的時候要排序
加快讀取。當查詢a=3的時候，第二條4已經(jīng)比3大了，證明數(shù)據(jù)不存在，不會再遍歷該頁的數(shù)據(jù)

所以建議主鍵是自增id。
上面這個只是一個小優(yōu)勢，當查詢a=300000的話，那還是需要遍歷這頁所有數(shù)據(jù)的一個長鏈表，性能差，需要用到頁目錄。

7、頁目錄
類似新華字典，要查某個漢字，根據(jù)他的拼音，得到在那一頁開始，然后再查詢。

頁目錄存的是主鍵，這樣查找速度就快很多了。
但如果頁目錄太多的時候，還是需要先判斷30000是否小于1，是否小于4，是否小于10....最后才得出它應(yīng)該在最后一頁

還可以用二分查找法提升查找在那一頁的速度。

8、
假設(shè)一頁存四條數(shù)據(jù)就滿了，后續(xù)數(shù)據(jù)就會存到下一頁。
（其實是雙向鏈表）

在非自增id的時候，例如第一頁存的是1，2，4，8，這時要插入5，就需要把5擠進第一頁，8退到第二頁，這樣速度就會很慢。所以主鍵自增是很有必要的

9、
當存了8條數(shù)據(jù)，第一頁1234，第二頁5678，這時要查a=6，就會先讀第一頁到內(nèi)存中，然后查找a=6沒有數(shù)據(jù)，再根據(jù)next指針在磁盤找到第二頁讀到內(nèi)存，再找a=6的數(shù)據(jù)。兩次磁盤IO，更多頁就會更多的IO（a=600000，變成了頁的長鏈表）效率會很低

10、
同樣的思想，為頁目錄再做一個管理目錄，存每頁的最小主鍵值

這樣就能更快定位到那一頁了?，F(xiàn)在這個圖就和B+Tree相同了

11、
現(xiàn)在為了方便查看，假設(shè)一頁兩條數(shù)據(jù)

B+Tree最主要的是主鍵，主鍵索引。
如果這時查b=7，就無法用主鍵索引了