1，索引到底是什麼
2，索引底層資料結構與算法
3，索引最左字首原理
索引到底是什麼
•索引是幫助MySQL高效擷取資料的排好序的資料結構
索引的本質
MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效擷取資料的資料結構。提取句子主幹，就可以得到索引的本質：索引是資料結構。
我們知道，資料庫查詢是資料庫的最主要功能之一。我們都希望查詢資料的速度能盡可能的快，是以資料庫系統的設計者會從查詢算法的角度進行優化。最基本的查詢算法當然是順序查找（linear search），這種複雜度為O(n)的算法在資料量很大時顯然是糟糕的，好在計算機科學的發展提供了很多更優秀的查找算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。如果稍微分析一下會發現，每種查找算法都隻能應用于特定的資料結構之上，例如二分查找要求被檢索資料有序，而二叉樹查找隻能應用于二叉查找樹上，但是資料本身的組織結構不可能完全滿足各種資料結構（例如，理論上不可能同時将兩列都按順序進行組織），是以，在資料之外，資料庫系統還維護着滿足特定查找算法的資料結構，這些資料結構以某種方式引用（指向）資料，這樣就可以在這些資料結構上實作進階查找算法。這種資料結構，就是索引。
•索引存儲在檔案裡
磁盤存取原理
上文說過，索引一般以檔案形式存儲在磁盤上，索引檢索需要磁盤I/O操作。與主存不同，磁盤I/O存在機械運動耗費，是以磁盤I/O的時間消耗是巨大的。
圖6是磁盤的整體結構示意圖。
圖6
一個磁盤由大小相同且同軸的圓形盤片組成，磁盤可以轉動（各個磁盤必須同步轉動）。在磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的内容。磁頭不能轉動，但是可以沿磁盤半徑方向運動（實際是斜切向運動），每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的（不過目前已經有多磁頭獨立技術，可不受此限制）。
圖7是磁盤結構的示意圖。
圖7
盤片被劃分成一系列同心環，圓心是盤片中心，每個同心環叫做一個磁道，所有半徑相同的磁道組成一個柱面。磁道被沿半徑線劃分成一個個小的段，每個段叫做一個扇區，每個扇區是磁盤的最小存儲單元。為了簡單起見，我們下面假設磁盤隻有一個盤片和一個磁頭。
當需要從磁盤讀取資料時，系統會将資料邏輯位址傳給磁盤，磁盤的控制電路按照尋址邏輯将邏輯位址翻譯成實體位址，即确定要讀的資料在哪個磁道，哪個扇區。為了讀取這個扇區的資料，需要将磁頭放到這個扇區上方，為了實作這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然後磁盤旋轉将目标扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
索引底層資料結構與算法
•索引結構
1，二叉樹 2，紅黑樹 3，HASH4，BTREE
二叉樹
圖中展示了一種可能的索引方式。左邊是資料表，一共有兩列七條記錄，最左邊的是資料記錄的實體位址（注意邏輯上相鄰的記錄在磁盤上也并不是一定實體相鄰的）。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分别包含索引鍵值和一個指向對應資料記錄實體位址的指針，這樣就可以運用二叉查找在O(log2n)的複雜度内擷取到相應資料。雖然這是一個貨真價實的索引，但是實際的資料庫系統幾乎沒有使用二叉查找樹或其進化品種紅黑樹（red-black tree）實作的
•B-Tree
•度(Degree)-節點的資料存儲個數
•葉節點具有相同的深度
•葉節點的指針為空
•節點中的資料key從左到右遞增排列 、
為了描述B-Tree，首先定義一條資料記錄為一個二進制組[key, data]，key為記錄的鍵值，對于不同資料記錄，key是互不相同的；data為資料記錄除key外的資料。那麼B-Tree是滿足下列條件的資料結構：
1. d為大于1的一個正整數，稱為B-Tree的度。
2. h為一個正整數，稱為B-Tree的高度。
3. 每個非葉子節點由n-1個key和n個指針組成，其中d<=n<=2d。
4. 每個葉子節點最少包含一個key和兩個指針，最多包含2d-1個key和2d個指針，葉節點的指針均為null 。
5. 所有葉節點具有相同的深度，等于樹高h。
6. key和指針互相間隔，節點兩端是指針。
7. 一個節點中的key從左到右非遞減排列。
8. 所有節點組成樹結構。
9. 每個指針要麼為null，要麼指向另外一個節點。
10. 如果某個指針在節點node最左邊且不為null，則其指向節點的所有key小于v(key1)，其中v(key1)為node的第一個key的值。
11. 如果某個指針在節點node最右邊且不為null，則其指向節點的所有key大于v(keym)，其中v(keym)為node的最後一個key的值。
12. 如果某個指針在節點node的左右相鄰key分别是keyi和keyi+1且不為null，則其指向節點的所有key小于v(keyi+1)且大于v(keyi)。
圖2是一個d=2的B-Tree示意圖。
圖2
由于B-Tree的特性，在B-Tree中按key檢索資料的算法非常直覺：首先從根節點進行二分查找，如果找到則傳回對應節點的data，否則對相應區間的指針指向的節點遞歸進行查找，直到找到節點或找到null指針，前者查找成功，後者查找失敗
關于B-Tree有一系列有趣的性質，例如一個度為d的B-Tree，設其索引N個key，則其樹高h的上限為logd((N+1)/2)，檢索一個key，其查找節點個數的漸進複雜度為O(logdN)。從這點可以看出，B-Tree是一個非常有效率的索引資料結構。
另外，由于插入删除新的資料記錄會破壞B-Tree的性質，是以在插入删除時，需要對樹進行一個分裂、合并、轉移等操作以保持B-Tree性質，本文不打算完整讨論B-Tree這些内容，因為已經有許多資料詳細說明了B-Tree的數學性質及插入删除算法
•B+Tree(B-Tree變種)
•非葉子節點不存儲data，隻存儲key，可以增大度
•葉子節點不存儲指針
•順序通路指針，提高區間通路的性能
B-Tree有許多變種，其中最常見的是B+Tree，例如MySQL就普遍使用B+Tree實作其索引結構。
與B-Tree相比，B+Tree有以下不同點：
1. 每個節點的指針上限為2d而不是2d+1。
2. 内節點不存儲data，隻存儲key；葉子節點不存儲指針。
圖3是一個簡單的B+Tree示意。
圖3
由于并不是所有節點都具有相同的域，是以B+Tree中葉節點和内節點一般大小不同。這點與B-Tree不同，雖然B-Tree中不同節點存放的key和指針可能數量不一緻，但是每個節點的域和上限是一緻的，是以在實作中B-Tree往往對每個節點申請同等大小的空間。
一般來說，B+Tree比B-Tree更适合實作外存儲索引結構，具體原因與外存儲器原理及計算機存取原理有關，将在下面讨論。
帶有順序通路指針的B+Tree
一般在資料庫系統或檔案系統中使用的B+Tree結構都在經典B+Tree的基礎上進行了優化，增加了順序通路指針。
圖4
如圖4所示，在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序通路指針的B+Tree。做這個優化的目的是為了提高區間通路的性能，例如圖4中如果要查詢key為從18到49的所有資料記錄，當找到18後，隻需順着節點和指針順序周遊就可以一次性通路到所有資料節點，極大提到了區間查詢效率。
這一節對B-Tree和B+Tree進行了一個簡單的介紹，下一節結合存儲器存取原理介紹為什麼目前B+Tree是資料庫系統實作索引的首選資料結構。
•B+Tree索引的性能分析
•一般使用磁盤I/O次數評價索引結構的優劣
•預讀：磁盤一般會順序向後讀取一定長度的資料(頁的整數倍)放入記憶體
•局部性原理：當一個資料被用到時，其附近的資料也通常會馬上被使用
•B+Tree節點的大小設為等于一個頁，每次建立節點直接申請一個頁的空間，這樣就保證一個節點實體上也存儲在一個頁裡， 就實作了一個節點的載入隻需一次I/O
•B+Tree的度d一般會超過100，是以h非常小(一般為3到5之間)
•MyISAM索引實作(非聚集)
MyISAM索引檔案和資料檔案是分離的
•InnoDB索引實作(聚集)
•資料檔案本身就是索引檔案
•表資料檔案本身就是按B+Tree組織的一個索引結構檔案
•聚集索引-葉節點包含了完整的資料記錄
•為什麼InnoDB表必須有主鍵，并且推薦使用整型的自增主鍵？
•為什麼非主鍵索引結構葉子節點存儲的是主鍵值？(一緻性和節省存儲空間)
•聯合索引的底層存儲結構長什麼樣？
這裡以MySql INNODB為例，MyISAM道理是一樣的。然後先從原文搬幾個圖過來：
這是一張表格，col1 是主建，col2和col3 是普通字段。那麼主索引 對應的 B+樹 結構是這樣子的：
也可以是這樣子的，這是我畫的：
現在呢，對col3 建立一個單列索引，原文圖：
看完這個圖也是可以了解的，那麼想法來了，如果對 col3 和 col2 建立 聯合索引，那麼 B+ 樹會是一個什麼樣子的呢？
首先可以肯定的是，肯定隻有一棵樹，又因為 最左原則的存在，那麼帶着這個想法自己試着畫了下：
建索引語句 CREATE INDEX IDX_XXX ON TABLE(COL3, COL2);
先根據col3 排序，在根據 col2 排序，如上圖。
原文例子中的資料沒有重複資料，為了更好的了解，我自己改了下：
紅色框是改動的地方，把col3 改成有重複資料了，然後 還是對 col3 ，col2建立聯合索引，那麼 B+樹 如下：
紅色框是和原來不一樣的地方。
聯合索引在查找的時候，比如要找 Alice，34 這條記錄 WHERE COL3 = 'Alice' AND COL2 = 34
先根據col3 查找 Alice ，找到了2條記錄，在根據col2 查找 34，然後擷取到主鍵 15 ，在根據主鍵去查找 主索引。
如果 是 WHERE COL2 = 34，由于隻有聯合索引 (col3, col2)，沒有col2 的單列索引。
那麼查找的時候，就沒法根據上面的這棵樹來查找 ，隻能全表掃描。
是以為什麼會有最左原則，就是因為 B+樹 是根據最左邊的字段建構的，我的想法是這樣子的。
片段截取引用來源：klchht 來源：CSDN 原文：https://blog.csdn.net/klchht/article/details/78146443?utm_source=copy
索引的最左字首原理：
通常我們在建立聯合索引的時候，也就是對多個字段建立索引，相信建立過索引的同學們會發現，無論是oralce還是mysql都會讓我們選擇索引的順序，比如我們想在a,b,c三個字段上建立一個聯合索引，我們可以選擇自己想要的優先級，a、b、c,或者是b、a、c 或者是c、a、b等順序。為什麼資料庫會讓我們選擇字段的順序呢？不都是三個字段的聯合索引麼？這裡就引出了資料庫索引的最左字首原理。
比如：索引index1:(a,b,c)有三個字段，我們在使用sql語句來查詢的時候，會發現很多情況下不按照我們想象的來走索引。
select * from table where c = '1' 這個sql語句是不會走index1索引的，select * from table where b =‘1’ and c ='2' 這個語句也不會走index1索引。
什麼語句會走index1索引呢？
答案是：
select * from table where a = '1'
select * from table where a = '1' and b = ‘2’
select * from table where a = '1' and b = ‘2’ and c='3'
我們可以發現一個共同點，就是所有走索引index1的sql語句的查詢條件裡面都帶有a字段，那麼問題來了，index1的索引的最左邊的列字段是a，是不是查詢條件中包含a就會走索引呢？
例如：select * from table where a = '1' and c= ‘2’這個sql語句，按照之前的了解，包含a字段，會走索引，但是是不是所有字段都走了索引呢？
答案：不會，隻會走a字段的索引，因為聯合索引執行是有順尋的，即 a->b->c，也就是說隻有走了a，才會走b，隻有走了b才會 走c；
是最左字首原理的一部分，索引index1:(a,b,c)，隻會走a、a,b、a,b,c 三種類型的查詢，其實這裡說的有一點問題，a,c也走，但是隻走a字段索引，不會走c字段。
另外還有一個特殊情況說明下，select * from table where a = '1' and b > ‘2’ and c='3' 這種類型的也隻會有a與b走索引，c不會走。
原因如下：
索引是有序的，index1索引在索引檔案中的排列是有序的，首先根據a來排序，然後才是根據b來排序，最後是根據c來排序，
像select * from table where a = '1' and b > ‘2’ and c='3' 這種類型的sql語句，在a、b走完索引後，c肯定是無序了，是以c就沒法走索引，資料庫會覺得還不如全表掃描c字段來的快。
參照片段位址：攻城小獅 -CSDN 原文：https://blog.csdn.net/zzx125/article/details/79678770?utm_source=copy