開篇：

圖片是本人隨筆畫的，有點粗糙，望大家諒解，如有不妥之處，請聯系我們，感謝

一、索引到底是什么

.索引是幫助mysql高效獲取數據的排好序的數據結構

.索引是存儲在文件里的

.數據結構： 二叉樹 HASH BTREE

 

 

 

如果沒有索引的話，循環一條一條的找，找一次就是一次IO，這樣速度就會很慢

我們知道數據庫數據都是存在磁盤上的，當我們查找數據時，就會從磁盤上取數據,每取一次就是一次IO，IO是非常耗時的，為了速度快會把數據放到緩存里，然后在緩存里進行操作

 

二、磁盤存取原理

 

 

 

當查找數據的時候，就是磁頭循環找此道，就會一直循環查找，一次查找就是一次IO，IO是很耗時的

三、Mysql數據結構詳解

就拿上面的7條數據來說，如果沒有索引，當我們查找第7條數據時，就會循環7次，如果有百萬級別的數據，那么就會查找百萬次，顯然這樣是不行的，就需要數據結構算法來優化，那我們就從二叉樹----HASH---BTREE來一一說起

二叉樹：

二叉樹節點保存的都是單個索引，高度會隨著數據增大而增高，但是比一條一條的循環會快

 

 

 

 

 

 

不用二叉樹是因為的極端情況下會出現單邊增長，這樣在數量大的情況下，和一條一條查找沒有區別。

紅黑樹：

紅黑樹有自平衡性質，不會出現單邊增長，它會動態自旋轉，在性能上比二叉樹又高一點，但是mysql也沒有用這種數據結構，因為數據量超大的情況下，數據高度也會一直增大，在最終這個樹高度也非常大，解決不了根本問題

 

 

 

HASH:

hash算法一次就會定位到文件指針，速度快，但是還是沒有用，如果范圍查找的話就沒有辦法了，如果只是內存中的話，他的時間復雜度是O(1),速度會會很快，但是索引文件也是保存在磁盤上，而且hash是不連續的放在磁盤上的，這樣查詢起來也很慢，這才是不用hash的最根本原因

 

 

 

B-TREE:

相比上面的數據結構，b-tree增加了橫向大?。ǘ菵egree），那么在高度上就減小了，查找次數就少了

 

 

 

15，56，77.。。。。是索引，data就是對應的一行數據

那么在橫向的度上最大多少合適呢？？總不能橫向上一直擴展下呀，磁盤一次IO，就是取一個橫向的節點（度），把一個節點的數據放在緩存中，那么一次IO也不能把所用的數據全取出來，所以最好是一次io，就把這個節點全取處理，電腦操作系統從磁盤一次取數據到內存中一般是4K，而mysql取一次數據一般是16K，所以橫向節點一般設置為16K。因為一個節點設置成16K的話，這個節點保存了索引和索引對應行的數據，那么這個節點橫向保存不了太多的數據，所以，這種數據結構也不合適，引入新的數據結構

 

 

 

B+Tree

查找一次數據就是和磁盤一次IO，一次IO會把這個數據相鄰的數據一下全部查處理，這樣速度會更快，這樣的一頁就是咱們說的一個節點（4K），分配空間的時候也是一頁一頁分配的，這樣會更快，一頁就是一個節點

 

 

 

 

mysql 常用的引擎有MyISAM和InNoDb,兩種引擎得索引結構是不一樣的

MyISAM的數據結構：

.frm表結構文件 .myd表數據文件 .myi表索引文件

 

 

 

 

 

 

myisam引擎的主鍵索引數據結構是左上圖，普通索引是右上圖，葉子節點存的不是數據本身，是數據文件指針，和b_tree數據不一樣，注意：每類的索引，都是各自的樹，不是混合在一起的

 

.frm表結構文件 .ibd 表數據和索引文件

 

 

 

 

 

 

主鍵索引是聚集索引，因為葉子節點是所有的數據，就是一行數據，非主鍵索引葉子節點只包括索引和主鍵，再用主鍵找對應數據

非主鍵索引葉子節點只包括索引和主鍵，再用主鍵找對應數據，這樣是為了節省空間和數據一致性

 

聯合索引：

要滿足最左原則

聯合索引(col1, col2, col3)也是一棵B+樹，其非葉子節點存儲的是第一個關鍵字的索引，而葉子節點存儲的則是三個關鍵字col1、col2、col3三個關鍵字的數據，且按照col1-col2-col3的順序進行排序。

 

 

 

 

 

例如：

如果執行的是，SELECT * FROM T WHERE B=‘Tom’ AND C=4567;

那么無法使用索引，因為索引是用A字段先排序的，如果沒有先確定A，直接查找B和C，那么將會是全表查詢。

 

如果執行的是，SELECT * FROM T WHERE A=‘30’ ;

那么，會先找到A字段，再在A等于30的數據中（比如有很多條），找B等于Demi的數據。這樣是可以用到索引的。

 

如果執行的是，SELECT * FROM T WHERE A=‘18’ AND C=1234;

那么，A字段可以索引，而C不能索引。所以可以部分索引，也比全表查詢快。

 

如果執行 SELECT * FROM T WHERE B=Demi AND C=1234 and A=‘18’

是用到索引的，在and的情況下如果把第一個放到最后位置也是能用到索引的

 

現在我想大家應該了解了什么為什么是最左原則。因為，B+樹是按照最左邊的字段以此構建的。

作者：京東零售 韓航云

來源：京東云開發者社區 轉載請注明來源