mysql btree索引概述
今天研究下，
mysql中的B-tree索引，通過這篇文章你可以了解到，mysql中的btree索引的原理，檢索數據的過程，innodb和myisam引擎中btree索引的不同，以及btree索引的好處和限制。
B-Tree 索引是 MySQL 數據庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。不僅僅在 MySQL 中是如此，實際上在其他的很多數據庫管理系統中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為B-Tree 索引的存儲結構在數據庫的數據檢索中有非常優異的表現，值得注意的是mysql中innodb和myisam引擎中的B-tree索引使用的是B+tree（即每一個葉子節點都包含指向下一個葉子節點的指針，從而方便葉子節點的范圍遍歷，并且除葉子節點外其他節點只存儲鍵值和指針）。
一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 B+tree的結構來存儲的，也就是所有實際需要的數據都存放于 Tree 的 Leaf Node，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，可能各種數據庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結構稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結構實際上是 B+Tree ，也就是在 B-Tree 數據結構的基礎上做了很小的改造，在每一個Leaf Node 上面出了存放索引鍵值和主鍵的相關信息之外，B+Tree還存儲了指向與該 Leaf Node 相鄰的后一個 LeafNode 的指針信息，這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。
一：下面重點講解下在mysql中innodb和myisam的b-tree索引的不同實現原理；
1）MyISAM索引實現
MyISAM引擎使用B+Tree作為索引結構，葉節點的data域僅僅存放的是指向數據記錄的地址（也叫行指針），在MyISAM中，主索引和輔助索引（Secondary key）在結構上沒有任何區別，只是主索引要求key是唯一的，而輔助索引的key可以重復。
2）InnoDB索引實現
雖然InnoDB也使用B+Tree作為索引結構，但具體實現方式卻與MyISAM截然不同。
前面說過了，MyISAM索引文件和數據文件是分離的，索引文件僅保存數據行記錄的地址（行指針）。但是在innodb引擎中，btree索引分為兩種，1，聚集索引（主鍵索引），2.二級索引，或者說叫輔助索引。InnoDB中的主鍵索引是聚集索引，表數據文件本身就是按B+Tree組織的一個索引結構，這棵樹的葉節點data域保存了完整的數據記錄（整行數據）。這個索引的key是數據表的主鍵，因此InnoDB表數據文件本身就是主鍵索引。但是innodb的二級索引，保存的是索引列值以及指向主鍵的指針，所以我們使用覆蓋索引的做優化處理就是針對mysql的innodb的索引而言的。
總結起來就是：
MyISAM引擎中leaf node存儲的內容:
主鍵索引 ：僅僅存儲行指針；
二級索引：存儲的也僅僅是行指針；
InnoDB引擎中leaf node存儲的內容
主鍵索引 ：聚集索引存儲完整的數據（整行數據）
二級索引：存儲索引列值+主鍵信息
下面這張圖顯示mysql中innodb和myisam引擎的索引實現的原理
二：接下來說下通過btree索引檢索數據的過程：
myisam和innodb引擎都是使用B+tree實現btree索引，檢索數據的過程中，從根節點到子節點，然后找到葉子節點，接著找到葉子節點中存儲的data的過程是一樣的，只不過因為myisam和innodb引擎中的葉子節點中的data中存儲的內容是不一樣的（前文介紹了），所以找到葉子節點中的data之后再找真正數據的過程是不一樣的，然后根據前文介紹的不同存儲引擎中葉子節點data中存儲的不同數據，例如innodb中的主鍵索引葉子節點存儲的是完整數據行，所以根據innodb中的主鍵索引遍歷數據時，找到了葉子節點的data，就可以找到數據，至于myisam中葉子節點data存儲的是行指針，也就是找到葉子節點的data后，再根據行指針去找到真正的數據行。
下面重點去說由根節點找葉子節點中的data域的過程：
為了對比，可以先看下B-tree實現原理：
B+tree實現原理如下圖：
通過兩張圖可以看出來，相對于B-tree來說，B+Tree根節點和子節點只保存了鍵值和指針，所有數據記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，這樣可以大大加大每個節點存儲的key值數量，降低B+Tree的高度，并且B+Tree中的葉子節點比B-tree多存儲了指向下一個葉子節點的指針，這樣更方便葉子節點的范圍遍歷。
每個節點占用一個磁盤塊的磁盤空間，一個節點上有n個升序排序的關鍵字和（n+1)個指向子樹根節點的指針，這個指針存儲的是子節點所在磁盤塊的地址（注意這里的n是創建索引的時候，根據數據量計算出來的，如果數據量太大了，三層的可能就滿足不了，就需要四層的B+tree，或者更多層）,然后n個關鍵字劃分成（n+1)個范圍域，然后每個范圍域對應一個指針，來指向子節點，子節點又從新根據關鍵字再次劃分，然后指針指向葉子節點。
針對下圖具體解釋下B+tree索引的實現原理（修改自網絡）：
針對上圖，每個節點占用一個盤塊的磁盤空間，一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針，兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數據的范圍域。以根節點為例，關鍵字為17和35，P1指針指向的子樹的數據范圍為小于17，P2指針指向的子樹的數據范圍為17~35，P3指針指向的子樹的數據范圍為大于35。
然后針對上圖模擬下 where id=29的具體過程：（首先mysql讀取數據是以塊（page）為單位的）。
首先根據根節點找到磁盤塊1，讀入內存。【磁盤I/O操作第1次】
比較關鍵字29在區間（17,35），找到磁盤塊1的指針P2。
根據P2指針找到磁盤塊3，讀入內存。【磁盤I/O操作第2次】
比較關鍵字29在區間（26,30），找到磁盤塊3的指針P2。
根據P2指針找到磁盤塊8，讀入內存。【磁盤I/O操作第3次】
在磁盤塊8中的關鍵字列表中找到關鍵字29。
分析上面過程，發現需要3次磁盤I/O操作，和3次內存查找操作。由于內存中的關鍵字是一個有序表結構，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個B-Tree查找效率的決定因素。B-Tree相對于AVLTree縮減了節點個數，使每次磁盤I/O取到內存的數據都發揮了作用，從而提高了查詢效率。
相對于B-tree來說，B+Tree根節點和子節點只保存了鍵值和指針，
查看mysql中的頁的大小：
MySQL [meminfo]> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)
InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT（占用4個字節）或BIGINT（占用8個字節），指針類型也一般為4或8個字節，也就是說一個頁（B+Tree中的一個節點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值，為方便計算，這里的K取值為〖10〗^3）。也就是說一個深度為3的B+Tree索引可以維護10^3 * 10^3 * 10^3 = 10億 條記錄。
實際情況中每個節點可能不能填充滿，因此在數據庫中，B+Tree的高度一般都在2~4層。MySQL的InnoDB存儲引擎在設計時是將根節點常駐內存的，也就是說查找某一鍵值的行記錄時最多只需要1~3次磁盤I/O操作。
三：下面說下mysql中innodb引擎中聚簇表和myisam中非聚簇表的遍歷數據的不同
如下圖（來自網絡）：
看上去聚簇索引的效率明顯要低于非聚簇索引，因為每次使用輔助索引檢索都要經過兩次B+樹查找，這不是多此一舉嗎？聚簇索引的優勢在哪？
1 由于行數據和葉子節點存儲在一起，這樣主鍵和行數據是一起被載入內存的，找到葉子節點就可以立刻將行數據返回了，如果按照主鍵Id來組織數據，獲得數據更快。
2 輔助索引使用主鍵作為"指針" 而不是使用行地址值作為指針的好處是，減少了當出現行移動或者數據頁分裂時輔助索引的維護工作，使用主鍵值當作指針會讓輔助索引占用更多的空間，換來的好處是InnoDB在移動行時無須更新輔助索引中的這個"指針"，使用聚簇索引可以保證不管這個主鍵B+樹的節點如何變化，輔助索引樹都不受影響。
四：最后說下mysql中的B+tree索引的好處和限制（摘自高性能mysql第三版）
（一）可以使用的情況：
可以使用btree索引的查詢類型，btree索引使用用于全鍵值、鍵值范圍、或者鍵前綴查找，其中鍵前綴查找只適合用于根據最左前綴的查找。前面示例中創建的多列索引對如下類型的查詢有效：
1）全值匹配
全值匹配指的是和索引中的所有列進行匹配，即可用于查找姓名和出生日期
2）匹配最左前綴
如：只查找姓，即只使用索引的第一列
3）匹配列前綴
也可以只匹配某一列值的開頭部分，如：匹配以J開頭的姓的人（like 'J%')，這里也只是使用了索引的第一列，且是第一列的一部分
4）匹配范圍值
如查找姓在allen和barrymore之間的人，這里也只使用了索引的第一列
5）精確匹配某一列并范圍匹配另外一列
如查找所有姓為allen，并且名字字母是K開頭的，即，第一列last_name精確匹配，第二列first_name范圍匹配
6）只訪問索引的查詢
btree通常可以支持只訪問索引的查詢，即查詢只需要訪問索引，而無需訪問數據行，即，這個就是覆蓋索引的概念。需要訪問的數據直接從索引中取得，這個是針對innodb中btree索引而言的。
因為索引樹中的節點是有序的，所以除了按值查找之外，索引還可以用于查詢中的order by操作，一般來說，如果btree可以按照某種方式查找的值，那么也可以按照這種方式用于排序，所以，如果order by子句滿足前面列出的幾種查詢類型，則這個索引也可以滿足對應的排序需求。
(二）下面是關于btree索引的限制：
1）如果不是按照索引的最左列開始查找的，則無法使用索引(注意，這里不是指的where條件的順序，即where條件中，不管條件順序如何，只要where中出現的列在多列索引中能夠從最左開始連貫起來就能使用到多列索引)
2）不能跳過索引中的列，如創建了多列索引（姓，名，出生日期）：查詢條件為姓和出生日期，跳過了名字列，這樣，多列索引就只能使用到姓這一列。
3）如果查詢中有某個列的范圍查詢，則其右邊所有列都無法使用索引優化查詢，如：where last_name=xxx and first_name like ‘xxx%’ and dob=’xxx’;這樣，first_name列可以使用索引，這列之后的dob列無法使用索引。
總結：mysql中常用的引擎有innodb和myisam,這兩個引擎中創建的默認索引都是B-tree索引，而都是B+tree結構實現的，并且innodb和myisam具體葉子節點存儲的內容有所不同，然后覆蓋索引是針對innodb引擎的索引而言的，因為myisam引擎中b-tree索引的葉子節點存儲的僅僅是行指針。
