詳解B+樹及其正確打開方式

NO IMAGE

前言

hello,小可愛們,繼上篇長文的更新,我又又又來了。

前面我們長大了InnoDB數據頁的7個組成部分,各個數據頁組成了一個雙向鏈表,而每個數據頁中的記錄按照主鍵從小到大的順序組成一個單鏈表,每個數據頁中為這些記錄生成了一個目錄,可以採用二分法查找,提升查詢速度。

那麼問題來就來了,如果表中的記錄涉及多個數據頁,那又該如何查找呢?

沒有索引的查找

為了方便理解,咱先說一個SQL語句的情況,就是最簡單的精準查詢,如下:

select [列名列表] from [表名] where 列名=XXX

在一個頁中的查找

  • 以主鍵為搜索條件

可以直接使用數據頁中的目錄進行二分查找。

  • 以其他列為搜索條件

不可以使用數據頁中的目錄進行二分查找,只能順序查找,一列列的對比是否滿足條件。

在多個頁中的查找

不管是否以主鍵作為搜索提交,都不能使用數據頁中的目錄進行二分查找,只能順序查找,逐一對比。

結果:這樣查找速度肯定是慢的,我們得想一個提升速度的方法,那麼索引就出現了。

有索引的查找

索引是什麼?

我們先來創建一個表score,併為其新增三條語句,語句如下:

create table score(
id varchar(10),
name varchar(10),
score int,
primary key (id)
);
insert into score values('001','張三',100);
insert into score values('002','李四',90);
insert into score values('004','王五',70);

根據上篇我們說的,其在硬盤上的存儲結構如下(假設每一頁只存3條數據,其他不必要的信息都刪掉了)。

詳解B+樹及其正確打開方式

如果再新增一條數據,這一頁可以放不下了,需要新增一頁來存放數據啦,如下圖。

詳解B+樹及其正確打開方式

通過上圖,我們發現003比004小,卻排在了後面,不符合下一個數據頁中用戶記錄的主鍵值必須大於上一頁中用戶記錄的主鍵值這一標準,所以我們需要將003的這條記錄和004的這條記錄交換一下。

為什麼要符合這一標準呢?我們在頁內可以使用目錄進行二分查找,提升查詢速度,那麼我們在頁間是不是也可以採用二分查找呢?答案是肯定的,所以就要符合剛才的標準,因為二分查找的前提就是數據必須有序。

試想一下,如果有很多頁數據,我們每三頁合併一個大的頁,大的頁一共三條數據,分別對應著底下小頁的最小值,但是即使這樣,數據量還是很多,我們就再進行頁的合併,這樣就形成了下圖的形式,即為B+樹。

事實上,經他人統計(哈哈哈,錯了好甩鍋,鏈接見文章尾),600萬的數據也就3層,so,一般情況下B+樹不超過4層(包括3層目錄項頁和1層數據項頁)。

詳解B+樹及其正確打開方式

所以,索引是對按主鍵排列的數據進行速度提升的一種數據結構。我自己想的,非官方概念。

萬年面試題:索引為什麼是B+樹?而不是B樹?

在搞清楚這個問題前,我們先來看一下什麼是B樹,什麼是B+樹?(我就盜圖啦,不想自己畫了)

B樹:也就是B-樹,主要特點是非葉子節點上不僅有指針,也有data域。

詳解B+樹及其正確打開方式

B+樹:非葉子節點只有指針,沒有data域,InnoDB的默認索引存儲引擎。

詳解B+樹及其正確打開方式

那麼問題就來了,為什麼索引採用B+樹呢?

  1. B+樹的所有葉子節點都通過雙向鏈表關聯(不要問我截的圖為什麼沒有,因為是從人家那裡偷得,我已經用紅色的箭頭加上了),如果我想搜索範圍,比如數值從60到66的,就可以直接通過葉子節點的之間的指針來獲取,速度比較快。如果使用的B樹,得采用中序遍歷的方式,查詢速度慢。
  2. 之前我們有說到數據是有分成頁的,而InnoDB存儲引擎層是將數據頁分批讀取到內存,由內存對數據進行加工完返回給客戶端的。如果在讀取相同頁數的情況下,B+樹能存放的數據信息更多,因為其只有指針,沒有數據,所佔的內存更小。所以B+樹單次磁盤IO信息大於B樹,所以B+樹比B樹的IO次數少,當然速度也就更快。

聚簇索引

上面說的就是聚簇索引,包括兩個特點:

  1. 使用表中定義的主鍵建立樹形結構。頁中的記錄是按照主鍵的大小順序排列,呈現單鏈表的形式,頁與頁之間是通過雙向鏈表的形式相關聯的。比如上面的score表主鍵是id,那麼他的聚簇索引就是按照id從小到大的順序排放。如果我要查id=XXX的記錄,就可以直接通過該聚簇索引來採用類二分的方法查詢,可以明顯的提升查詢速度。
  2. 聚簇索引的葉子節點存儲的是完整的用戶記錄,也就是說score表中除了主鍵id外,name和score都存儲在葉子節點中。

注意:這一點我們在輔助索引(二級索引)說,因為聚簇索引存儲的是完整的用戶記錄,總有什麼索引存儲的不是完整的用戶記錄。

輔助索引(二級索引)

噹噹噹,輔助索引(二級索引)到了。

如果當要查詢name=XXX的記錄時,我們只能通過主鍵id聚簇索引的葉子節點來一個個遍歷,然後比對哪一個name=XXX,這樣的方式就是一個遍歷單鏈表查詢,不用說了,這肯定賊慢。那有沒有更好一點的方法呢?

答案肯定是有的,那就是再為name列建一個索引,根據name從小到大的順序排列,這個就可以和主鍵id一樣,採用類二分的形式快速查出數據。

那我們就先在name上建一個索引index_name,語句如下:

alter table score add index index_name(name)
索引已經建立好了,那麼輔助索引是如何存放數據的?簡易版的,講究看看吧,哈哈哈。

詳解B+樹及其正確打開方式

從上圖中我們可以發現輔助索引的葉子節點並沒有分數score字段,但是卻有主鍵id字段,也就是他的葉子節點的數據並不完整。那麼如果我們要查看李四的id,name,score這三個字段,我們就可以使用基於name的所有index_name,採用類二分法找到李四這條記錄的主鍵id,再通過主鍵id去主鍵構成的聚簇索引查找這條記錄的完整信息,這個過程叫做回表

注意:為什麼要採用回表的形式呢?因為如果輔助索引的葉子節點存放的也是完整的記錄,列存放的數據越大,對內存的消耗就越明顯,越浪費空間。採用回表的方式,可以節省下空間,多浪費了一些時間。那麼問題就來了,如果我採用輔助索引得出來的數據量很大,已經接近於所有數據,然後再根據各自的主鍵id去查看完整的記錄,這樣的時間消耗可以比我直接採用主鍵索引一個個遍歷對比的時間消耗來的大,那麼MySQL還會選擇輔助索引嗎?這個問題就是查詢優化器的事情,下篇說,先立個flag,等著以後打臉。哈哈哈。。。。

聯合索引

比如我想找name=張三,score=100的這條記錄,如果使用基於主鍵id的聚簇索引,只能一個個遍歷並且對比,這樣的速度是很慢的。或者採用基於name的輔助索引,但是輔助索引裡面沒有分數score字段,所以還要通過回表的方式,找到score字段,但如果name=張三的記錄有100條,那我們只能找到100條數據,再挨個通過回表的方式,找到score=100的這條記錄。這樣看來,不管是基於主鍵id的聚簇索引還是基於name的輔助索引,都不是最好的方案。

所以可以創建聯合索引,語句如下,他其實就是當name一樣的時候,再按score進行排序,索引包括name,score,和主鍵id。其所對應的索引圖如下,簡單點啦,將就看看吧。我已經努力畫了(為了測試,我多加了兩條數據,005和006)。

create index name_and_score_index on score (name,score); 

詳解B+樹及其正確打開方式

注意:因為這邊就只有三個字段,如果字段量多的話,也是需要回表,通過主鍵id得到其他字段信息。

索引的正確打開方式

基於上面的理論知識,我們來實踐一下(上面的弄得明明白白就可以)。

再介紹下背景,score表有三個字段,分別是id,name,score。其還有兩個索引,一個是聚簇索引,一個是基於name和score的聯合索引。

先看下面的語句,判斷是不是能使用索引進行查詢。如果能準確說出下面是不是有使用索引,那麼下面就不要看了,就說的這些內容。

select * from score where id=XXX;  聚簇索引

select * from score where name=XXX;聯合索引

select * from score where score=XXX;不使用索引

select * from score where name=XXX and score=XXX; 聯合索引

select * from score where score=XXx and name=XXX; 聯合索引(經他人糾正,已改)

select * from score order by name; 聯合索引

select * from score order by score;不使用索引

前五個語句主要是最左前綴原則的使用。第一個不用說了,如果where後面的查詢條件是id,那麼他直接根據聚簇索引,採用類二分法,也就是從樹的根節點開始,能很快的查詢到相應的記錄。第二個where後面的查詢條件是name,那麼也可以根據聯合索引來查詢。(因為聯合索引是根據先name後score的方式來排序的,所以通過name查出一系列數據)。第三個where後面的查詢條件是score,那就不能用聯合索引了,因為有可能不同的name有著相同的score,那麼數據就是分散在各個頁上的,所以只能使用聚簇索引來一個個遍歷,並對比字段。第四個和第五個都能命中聯合索引,最左前綴原則是針對索引的順序,和SQL語句的前後順序無關。

後面兩個主要是用於排序的,如果SQL語句中有根據某個字段排序,儘量讓其在索引層面完成排序。如果在索引層面沒有完成排序,那麼就會在內存中就會浪費時間和空間來進行一系列排序算法來實現排序功能,這肯定對性能有影響。回到剛才的SQL語句,如果按name排序,則可以使用索引,因為索引是先按name排序,再按score索引的。但是如果按score排序,則不可以使用索引,因為score是後面排序的,也就是隻有name一樣才會按score排序,但是SQL語句需要的是全量的按照score排序。

結語

碼字不易,請多多關注偶。

詳解B+樹及其正確打開方式

參考書籍

InnoDB一棵B+樹可以存放多少條數據?

為什麼 MongoDB (索引)使用B-樹而 Mysql 使用 B+樹

MySQL是怎樣運行的

相關文章

面試官:“談談分庫分表吧?”

全網最全最詳細的ShardingJDBC入門

ShardingJDBC掃盲篇

不要為了“分庫分表”而“分庫分表”