一、定義

索引定義：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。
本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)。

二、B-Tree

m階B-Tree滿足以下條件：
1、每個節(jié)點至多可以擁有m棵子樹。
2、根節(jié)點，只有至少有2個節(jié)點（要么極端情況，就是一棵樹就一個根節(jié)點，單細胞生物，即是根，也是葉，也是樹)。
3、非根非葉的節(jié)點至少有的Ceil(m/2)個子樹(Ceil表示向上取整，如5階B樹，每個節(jié)點至少有3個子樹，也就是至少有3個叉)。
4、非葉節(jié)點中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示該節(jié)點中保存的關(guān)鍵字個數(shù)，K為關(guān)鍵字且Ki<Ki+1，A為指向子樹根節(jié)點的指針。
5、從根到葉子的每一條路徑都有相同的長度（葉子節(jié)點在相同的層）

B-Tree特性：

1、關(guān)鍵字集合分布在整顆樹中；
2、任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個節(jié)點中；
3、每個節(jié)點存儲date和key；
4、搜索有可能在非葉子節(jié)點結(jié)束；
5、一個節(jié)點中的key從左到右非遞減排列；
6、所有葉節(jié)點具有相同的深度，等于樹高h。

B-Tree上查找算法的偽代碼如下：

三、B+Tree

B+Tree與B-Tree的差異在于：
1、B+Tree非葉子節(jié)點不存儲data，只存儲key；
2、所有的關(guān)鍵字全部存儲在葉子節(jié)點上；
3、每個葉子節(jié)點含有一個指向相鄰葉子節(jié)點的指針，帶順序訪問指針的B+樹提高了區(qū)間查找能力；
4、非葉子節(jié)點可以看成索引部分，節(jié)點中僅含有其子樹（根節(jié)點）中的最大（或最小）關(guān)鍵字；

四、B/B+樹索引的性能分析

依據(jù)：使用磁盤I/O次數(shù)評價索引結(jié)構(gòu)的優(yōu)劣
主存和磁盤以頁為單位交換數(shù)據(jù)，將一個節(jié)點的大小設(shè)為等于一個頁，因此每個節(jié)點只需一次I/O就可以完全載入。
根據(jù)B樹的定義，可知檢索一次最多需要訪問h個節(jié)點
漸進復雜度:O(h)=O(logdN)
dmax=floor(pagesize/(keysize+datasize+pointsize))
一般實際應用中，出度d是非常大的數(shù)字，通常超過100，因此h非常小（通常不超過3，3層可存大約一百萬數(shù)據(jù)）
B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點常駐內(nèi)存）
B+Tree內(nèi)節(jié)點不含data域，因此出度d更大，則h更小，I/O次數(shù)少，效率更高，故B+Tree更適合外存索引。

五、MySQL索引實現(xiàn)
1、MyISAM引擎使用B+Tree作為索引結(jié)構(gòu)，葉節(jié)點的data域存放的是數(shù)據(jù)記錄的地址；
MyISAM主索引和輔助索引在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復；

2、InnoDB的數(shù)據(jù)文件本身就是索引文件，葉節(jié)點包含了完整的數(shù)據(jù)記錄，這種索引叫做聚集索引。
因為InnoDB的數(shù)據(jù)文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統(tǒng)會自動選擇一個可以唯一標識數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含字段作為主鍵。
InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址；
輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄；

3、頁分裂問題

如果主鍵是單調(diào)遞增的，每條新記錄會順序插入到頁，當頁被插滿后，繼續(xù)插入到新的頁；

如果寫入是亂序的，InnoDB不得不頻繁地做頁分裂操作，以便為新的行分配空間。頁分裂會導致移動大量數(shù)據(jù)，一次插入最少需要修改三個頁而不是一個頁。

如果頻繁的頁分裂，頁會變得稀疏并被不規(guī)則地填充，所以最終數(shù)據(jù)會有碎片。

六、總結(jié)

了解不同存儲引擎的索引實現(xiàn)方式對于正確使用和優(yōu)化索引都非常有幫助

1、為什么不建議使用過長的字段作為主鍵？

2、為什么選擇自增字段作為主鍵？

3、為什么常更新是字段不建議建立索引？

4、為什么選擇區(qū)分度高的列作為索引？區(qū)分度的公式是count(distinct col)/count(*)

5、盡可能的使用覆蓋索引

七、優(yōu)化LIMIT分頁查詢

SELECT * FROM table  where condition LIMIT offset , rows ;

上述SQL語句的實現(xiàn)機制是：
1、從“table”表中讀取offset+rows行記錄。
2、 拋棄前面的offset行記錄，返回后面的rows行記錄作為最終的結(jié)果。
覆蓋索引：

select  a.id, sid, parent_s_id from cashpool_account_relationship a join (select id from cashpool_account_relationship LIMIT 1000000,10)b on a.id = b.id;
select  id, sid, parent_s_id from cashpool_account_relationship where id >=(select id from cashpool_account_relationship LIMIT 1000000,1) LIMIT 10;

八、Q&A

1、InnoDB支持hash索引嗎？--馬欣
InnoDB是支持hash索引的，不過其支持的hash索引是自適應的，InnoDB存儲引擎會根據(jù)表的使用情況自動為表生成hash索引，不能人為干預是否在一張表中生成hash索引。
2、InnoDB主鍵索引的葉節(jié)點含完整的數(shù)據(jù)記錄，那主鍵索引文件要比數(shù)據(jù)文件大嗎？--徐財厚
1）.在Innodb 引擎中，主鍵索引中的葉子結(jié)點包含記錄數(shù)據(jù)，主鍵索引文件即為數(shù)據(jù)文件。
2）.在 tables 表中統(tǒng)計的data_length數(shù)據(jù)為主鍵索引大小，index_length 為統(tǒng)計的這個表中所有輔助索引（二級索引）索引的大小。

以上就是mysql的索引底層之實現(xiàn)原理的詳細內(nèi)容，更多請關(guān)注php中文網(wǎng)其它相關(guān)文章！