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