什麼是索引？
索引是幫助高效擷取資料的資料結構，避免全表掃描
mysql為什麼用B+TREE作索引？而不是其它樹形 結構?比如B樹？
盡量少地通路資源是資料庫設計的重要原則之一。
B樹不管葉子節點還是非葉子節點，都會儲存資料，這樣導緻在非葉子節 點中能儲存的指針數量變少（有些資料也稱為扇出），指針少的情況下要保 存大量資料，隻能增加樹的高度，導緻IO操作變多，查詢性能變低；
mysql索引如何實作？
我們先将資料記錄按主鍵進行排序，分别存放在不同的頁中（為了便于了解 我們這裡一個頁中隻存放3條記錄，實際情況可以存放很多），除了存放資料 的頁以外，還有存放鍵值+指針的頁，如圖中page number=3的頁，該頁存放 鍵值和指向資料頁的指針，這樣的頁由N個鍵值+指針組成。當然它也是排好 序的。這樣的資料組織形式，我們稱為索引組織表。
1、InnoDB存儲引擎的最小存儲單元是頁，頁可以用于存放資料也可以用于 存放鍵值+指針，在B+樹中葉子節點存放資料，非葉子節點存放鍵值+指針。
2、索引組織表通過非葉子節點的二分查找法以及指針确定資料在哪個頁中， 進而在去資料頁中查找到需要的資料；
什麼是回表？
現在，我們一起來看看這條SQL查詢語句的執行流程：
1. 在k索引樹上找到k=3的記錄，取得 ID = 300；
2. 再到ID索引樹查到ID=300對應的R3；
3. 在k索引樹取下一個值k=5，取得ID=500；
4. 再回到ID索引樹查到ID=500對應的R4；
5. 在k索引樹取下一個值k=6，不滿足條件，循環結束。
在這個過程中，回到主鍵索引樹搜尋的過程，我們稱為回表。
可以看到，這個查詢過程讀了k 索引樹的3條記錄（步驟1、3和5），回表了兩次（步驟2和4）。 在這個例子中，由于查詢結果所需要的資料隻在主鍵索引上有，是以不得不回表。
什麼是覆寫索引？
避免回表過程
如果執行的語句是select ID fromTwhere k between 3 and 5，這時隻需要查ID的值，而ID的值 已經在k索引樹上了，是以可以直接提供查詢結果，不需要回表。也就是說，在這個查詢裡面， 索引k已經“覆寫了”我們的查詢需求，我們稱為覆寫索引。
Msql5.6引入的索引下推優化
MySQL 5.6 引入的索引下推優化（index condition pushdown)， 可以在索引周遊過程中，對索 引中包含的字段先做判斷，直接過濾掉不滿足條件的記錄，減少回表次數。
無索引下推優化
索引下推優化
每個虛線箭頭表示一次回表
為什麼删除了表的部分記錄，它的索引還在？
alter table T engine=InnoDB
B+樹線上模拟
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
InnoDB一棵B+樹可以存放多少行資料？
在計算機中磁盤存儲資料最小單元是扇 區，一個扇區的大小是512位元組，而檔案系統（例如XFS/EXT4）他的最小單 元是塊，一個塊的大小是4k，而對于我們的InnoDB存儲引擎也有自己的最小 儲存單元——頁（Page），一個頁的大小是16K。
檔案系統中一個檔案大小隻有1個位元組，但不得不占磁盤上4KB的空間。
1、InnoDB存儲引擎的最小存儲單元是頁，頁可以用于存放資料也可以用于 存放鍵值+指針，在B+樹中葉子節點存放資料，非葉子節點存放鍵值+指針。
2、索引組織表通過非葉子節點的二分查找法以及指針确定資料在哪個頁中， 進而在去資料頁中查找到需要的資料；
單個葉子節點（頁）中的記錄數=16K/1K=16。（這裡假設 一行記錄的資料大小為1k，實際上現在很多網際網路業務資料記錄大小通常就 是1K左右）。
那麼現在我們需要計算出非葉子節點能存放多少指針，其實這也很好算，我 們假設主鍵ID為bigint類型，長度為8位元組，而指針大小在InnoDB源碼中設定 為6位元組，這樣一共14位元組，我們一個頁中能存放多少這樣的單元，其實就代 表有多少指針，即16384/14=1170。
那麼可以算出一棵高度為2的B+樹，能存 放1170*16=18720條這樣的資料記錄。 根據同樣的原理我們可以算出一個高度為3的B+樹可以存放： 1170*1170*16=21902400條這樣的記錄。是以在InnoDB中B+樹高度一般為1- 3層，它就能滿足千萬級的資料存儲。
在查找資料時一次頁的查找代表一次 IO，是以通過主鍵索引查詢通常隻需要1-3次IO操作即可查找到資料。