作者 | 宋光璠
出品 | CSDN博客
B+樹索引介紹
什麼是索引
InnoDB 存儲引擎的最小儲存單元是頁（Page），一個頁的大小是 16K。InnoDB存儲引擎的所有數據文件（後綴為 .ibd 的文件），它的大小始終都是 16K的整數倍。頁的大小一般也是可以設置的，如下命令可以查看當前頁的大小。
數據表中的數據存儲在頁中，假設一行數據的大小是 1K，那麼一個頁可以存放 16 行這樣的數據。如果數據庫只按這樣的方式存儲，那麼查找數據將是一個問題，因為我們不知道數據存儲在哪個頁中，也不可能所有的頁都遍歷一遍。那樣做就太慢了。為了解決這個問題，數據庫系統維護了一種特殊的能夠滿足某種高級查找算法的數據結構，這個數據結構以某種方式指向具體的數據。我們把這個數據結構稱為索引。
索引的作用
創建索引可以加快數據的檢索速度，大大提高數據庫系統的性能。它會影響where後面的查找，和order by後面的排序，可以顯著減少排序的時間。但是不能為表的每個字段創建索引，因為增加索引也有些問題。比如索引本身就需要佔物理空間，除了數據表佔數據空間之外，每一個索引還要佔一定的物理空間，如果要建立聚簇索引，那麼需要的空間就會更大。當對錶中的數據進行增加、刪除和修改的時候，索引也要動態的維護，這樣就降低了數據的維護速度。
索引的分類
從存儲結構上：
B類索引（B-樹或者B+樹索引），哈希索引、全文索引（full-text index）, R樹索引
從應用上來分：
普通索引、唯一索引、複合索引
數據的物理順序與鍵值的順序關係：
聚簇索引、非聚集索引
在InnoDB存儲引擎支持三種常用索引
哈希索引
全文索引
B+樹索引
InnoDB會根據表的情況自動生成哈希索引，不能人為干預表生成哈希索引
全文索引是將存在數據庫的整本書的任意內容信息查找出來的技術，InnoDB從1.2.x版本支持。每張表只能有一個全文檢索的索引。
B+樹索引是傳統意義上的索引，關係型數據庫系統中查找最為常用也是最為高效的索引。它的構造類似於二叉樹，根據鍵值對（key, value）查找數據。其中的B不是Binary，而是Balance的意思。它的本質就是B+樹在數據庫中的實現。它有一個特點就是高扇出性，因此在數據庫中，B+樹的高度一般是2-4層，也就是說查找某一鍵值對應的行記錄只需要2-4次IO。
B+樹是為了磁盤及其他存儲輔助設備而設計的一種平衡查找樹，在B+樹中，所有記錄的節點按大小順序存放在同一層的葉節點中，各葉子節點用指針進行連接。還是來個例子有個直觀感受吧，下圖的B+樹，高度為2，每頁存放4條行記錄，扇出是5。
哈希索引的數據組織方式
哈希索引（Hash Index）基於哈希表實現，只有精確的匹配索引所有列的查詢才有效。對於每一行數據，存儲引擎都會對所有的索引列計算一個哈希碼（hash code），哈希碼是一個較小的值，並且不同鍵值的行計算出來的哈希碼也不一樣。哈希索引將所有的哈希碼存儲在索引中，同時在哈希表中保存指向每個數據行的指針。
對於hash相同的，採用鏈式的方式解決。這一點同hashmap比較相似。
舉個例子， 假設有一張customer表，有id、name、age三個字段，表結構如下圖所示：
create table customer(
id bigint NOT ,
name varchar(30) NOT ,
age int(11) NOT , KEY USING HASH(name),PRIMARY KEY(id))engine=innodb;
表結構如下：
假設現在執行select age from customer where name=‘song’,則是先計算‘song’的哈希值，並使用該值對應的記錄指針，比如f(‘song’)=2734,所以mysql在索引中查找2734，可以找到對應第1行的指針，最後再比較第1行的值是否為’song’。
所以通過分析，Hash 索引也有它的缺點
因為Hash索引比較的是經過Hash計算的值，所以只能進行等式比較，不能用於範圍查詢
由於哈希值是按照順序排列的，但是哈希值映射的真正數據在哈希表中就不一定按照順序排列，所以無法利用Hash索引來加速任何排序操作
不能用部分索引鍵來搜索，因為組合索引在計算哈希值的時候是一起計算的。
當哈希值大量重複且數據量非常大時，其檢索效率並沒有Btree索引高的。
B+樹的數據組織方式
B+樹索引分為聚集索引(cluster index)和輔助索引(secondary index)，聚集索引按表的主鍵構造的B+樹，葉子節點存放整張表的行記錄數據，每張表只能有一個聚集索引。一般優化器更傾向採用聚集索引，因為直接就能獲取行數據。下面我們以一個聚集索引的例子來理解B+樹的數據組織方式。
根絕customer表，那麼B+樹的數據方式組織如下圖所示：
現將數據記錄按主鍵進行排序，分別存放在不同頁中（這裡假設一個頁只存放3條記錄），可以看到，除了數據頁以外還有存放鍵值和指針的頁，比如圖中page number=3的頁，該頁存放鍵值和指向數據頁的指針。這樣的數據組織形式，一般稱為索引組織表。
那麼，假設現在要查找一條數據，該怎麼查，比如：
select * from where id=4;
在這裡選擇自增id來做主鍵，通過這課B+樹來查找，首先查找根頁。一般來說，每個表的根頁位置在表空間中都是不變的，在這裡也就是page number=3的頁。找到根頁後通過二分查找法，定位到id=4的頁應該在指針P5指向的頁中。將該頁讀入內存後，繼續去page number=5的頁中查找，即可查找到id=4的對應記錄了。
所以InnoDB中，B+樹組織及查詢數據總結起來，主要有以下兩點:
頁可以用來存放記錄，也可以用來存放鍵值+指針，所有記錄的節點按照大小順序存放在同一層葉子節點中，非葉子節點用來存放鍵值+指針，鍵值一般是頁面中的最小值(Low Key);
索引組織表只能通過非葉子節點的二分查找法以及指針確定數據在哪個頁中，然後通過把查找到的頁讀入內存後，再在內存中進行查找記錄行。
為什麼B+樹比B樹更適合做索引
B樹也是多叉樹結構，一種自平衡的樹，而且B+樹是從B樹演化而來的，那麼為什麼不使用B+樹的前身B樹呢？從結構比較來看，B樹相比B+樹的一個主要區別就在於B樹的分支節點上存儲著數據，而B+樹的分支節點只是葉子節點的索引而已。根據這個差別可以得出以下結論：
磁盤IO讀寫次數相比B樹降低了
在B+樹中，其非葉子的內部節點都變成了key值，因此其內部節點相對B 樹更小。如果把所有同一內部節點的key存放在同一盤塊中，那麼盤塊所能容納的key數量也越多。一次性讀內存中的需要查找的key值也就越多。相對來說IO讀寫次數也就降低了。
每次查詢的時間複雜度是固定的
在B+樹中，由於分支節點只是葉子節點的索引，所以對於任意關鍵字的查找都必須從根節點走到分支節點，所有關鍵字查詢路徑長度相同，每次查詢的時間複雜度是固定的。但是在B樹中，其分支節點上也保存有數據，對於每一個數據的查詢所走的路徑長度是不一樣的，所以查詢效率也不一樣。
遍歷效率更高
由於B+樹的數據都存儲在葉子節點上，分支節點均為索引，方便掃庫，只需掃一遍葉子即可。但是B樹在分支節點上都保存著數據，要找到具體的順序數據，需要執行一次中序遍歷來查找。所以B+樹更加適合範圍查詢的情況，在解決磁盤IO性能的同時解決了B樹元素遍歷效率低下的問題。
B+樹作為索引可以存放多少數據
有道面試題，問InnoDB中，一顆的B+樹可以存放多少行數據？
那麼我們該如何計算呢？假設我們定義一顆B+樹高度為2，即一個根節點和若干葉子節點。那麼這課B+樹的存放總行記錄數=根節點指針數*單個葉子記錄的行數。這裡先計算葉子節點，B+樹中的單個葉子節點的大小為16K，假設每一條目為1K，那麼記錄數即為16(16k/1K=16)，然後計算非葉子節點能夠存放多少個指針，假設主鍵ID為bigint類型，那麼長度為8字節，而指針大小在InnoDB中是設置為6個字節，這樣加起來一共是14個字節。那麼通過頁大小/(主鍵ID大小+指針大小），即16384/14=1170個指針，所以一顆高度為2的B+樹能存放18720條這樣的記錄。根據這個原理就可以算出一顆高度為3的B+樹可以存放1170*1170*16=21902400條記錄。所以在InnoDB中B+樹高度一般為2-3層，它就能滿足千萬級的數據存儲。
原文鏈接：
https://blog.csdn.net/songguangfan/article/details/102475002
閱讀更多 CSDN程序人生 的文章
