有兩個特點
使用主鍵值大小進行紀錄和頁的排序
包含三個方面
B+樹的葉子節點儲存的是完整的使用者紀錄。所謂的完整使用者紀錄就是指這個紀錄儲存了所有列的值(包含隱藏列)
這邊額外補充說明一下什麼是隱藏列(跟前文無關,知道的人可以略過)。就要提到Innodb的主鍵生成策略,它會優先使用使用者自訂的主鍵作為主鍵,如果使用者沒有定義主鍵,則選取一個不允許NULL的UNIQUE值作主鍵,如果連不允許NULL的UNIQUE值都沒有定義,則Innodb會為表預設增加一個名為row_id的隱藏列作為主鍵。
我們把具有這兩個特點的B+樹稱為聚簇索引,所有完整的使用者紀錄都存放在這個聚簇索引的葉子節點。聚簇索引不需要我們在Mysql敘述中顯性的使用INDEX敘述去創建(這邊不懂沒關係,後面會在介紹),Innodb儲存引擎會自動替我們創建聚簇索引。
大家是否發現,聚簇索引只能在搜尋條件是主鍵值時發揮作用,原因是B+樹中的資料都是按照主鍵排序的。那如果我們想以別的列作為搜尋條件該怎麼辦呢?難道只能從頭到尾沿著鏈結串列依次歷遍紀錄嗎?
當然不是!做法是我們可以多建幾棵B+樹,不同的B+樹採用不同的排序規則。
舉個例子:
我們可以只用c2列數值做資料頁
那這個B+樹跟前面聚簇索引的B+樹有那些不同呢?
變成使用c2列的大小進行紀錄和頁的排序
包含三個方面
B+樹的葉子節點儲存的並不是完整的使用者紀錄。只有c2列+c1列(主鍵)這兩個列的值
目錄項紀錄不再是主鍵+頁號的搭配,而是c2列+頁號
這邊搜尋的流程也會有些許的不同:
假設我們要找尋紀錄c2=4
我們由上而下透過c2=4,使用二分法先定位到目錄項,再定位到使用者紀錄。
發現使用者紀錄內只有c2列跟主鍵的值,並不是完整的使用者紀錄。
所以我們必須再拿主鍵值回到聚簇索引內去查詢完整的使用者紀錄,這個過程又叫做回表。
此外由於c2列的值並沒有唯一性(主鍵才有唯一性),可能會有很多筆紀錄符合c2=4,所以我們會從找到的第一筆紀錄(c2=4)開始沿著單向鏈結串列往下找,每找到一筆就進行回表操作。重複這個過程直到不滿足c2=4條件停止。
就是因為這種以非主鍵列的大小排序建立的B+樹需要執行回表操作才可以定位到完整的使用者紀錄,所以這種B+樹才稱為二級索引(輔助索引)。
我們也可以用多列作排序,就是為多個列建立索引。
比如我們想讓B+樹按照c2和c3列的大小進行排序,這裡面包含兩層含義:
這棵樹每筆目錄項紀錄就會是由c2列、c3列、頁號3個部分組成。
(補充說明一下:前面二級索引是c2列+頁號,一樣畫葫蘆,就是c2列、c3列、頁號)
而使用者紀錄(葉子節點)是由c2列、c3列、c1列(主鍵)3個部分組成。
這樣的B+樹就稱為聯合索引,也稱複合索引或多列索引。本質上也是個二級索引。
要特別注意的是
以c2和c3列為排序建立聯合索引和分別為c2和c3列建立索引是不同的概念唷!
不同點為
建立聯合索引是建立一棵B+樹(先按照c2排序,c2相同再用c3排序)
而分別為c2和c3列建立索引,則會分別以c2和c3列為排序建立兩棵B+樹
根頁面是萬年不動的
當我們為某表創建B+樹索引時,都會為索引創建一個根節點頁。最開始根節點沒有任何資料。
之後開始插入使用者紀錄會先把其儲存到根節點,當根節點的可用空間用完時,如還要繼續插入新紀錄,這時會把先根節點內的所有紀錄複製到新頁A,然後對這個頁面進行頁分裂(如果不清楚可以回前一篇複習)操作,得到另一個新頁B。然後再往下繼續插入,新紀錄會根據鍵值(聚簇索引中的主鍵值,或二級索引中對應索引列的值)大小插入到頁A或頁B中。此時根節點便升級為儲存目錄項紀錄的頁(還記得第一層是使用者紀錄層,第二層含以上都是目錄項紀錄層唷),此時也需把頁A和頁B對應的目錄項紀錄插入到根節點中。
這邊要注意的是B+樹索引根節點自創建日便再也不移動(頁號再也不改變)。
內節點中目錄項紀錄的唯一性
我們知道搜尋非主鍵值以外的列時,我們會建立二級索引,而二級索引的目錄項紀錄是索引列(c2)加頁號,但這樣會有問題。
舉個例子:
有一目錄項頁面,內有2筆目錄項紀錄( [c2:1,頁號:1] 跟 [c2:1,頁號:2] ),c2的值都為1,分別對應到第1頁與第2頁。
這時欲插入一筆新紀錄[c2:1]
原先我們透過二分法,用c2=1去查詢屬於那一目錄項,進而知道要插入到那頁(第1頁或第2頁)
但現在發現c2的值與原先的2筆紀錄一樣@@,我們就不知道要插入到那一頁了...
因此為了讓新插入的紀錄能找到自己屬於那一頁,我們就需要保證B+樹同一層內節點的目錄項紀錄,除了頁號這個欄位以外是唯一的。
二級索引內節點的目錄項紀錄從原先的索引列(c2)加頁號,追加主鍵值變成索引列(c2)加c1(主鍵值)加頁號
這樣即可確保搜尋到唯一一筆目錄項紀錄。
耶!take a break
接下來我們會具體說明該如何使用B+樹索引,敬請期待