這篇文章我會分為以下部分進行講解，如果你懂了，那麼請繞行，別浪費你寶貴時間！
只有光頭才可以變強，如果你要繼續看，請保持空杯心態！
為什麼添加索引會提高查詢速度總結。索引提高了查詢速度對增刪改有影響嗎。索引常用的算法原理分析B樹和B+樹等。
為什麼添加索引會提高查詢速度
一句話回答：索引可以將無序內容轉換為有序的一個集合（相對），就如同新華字典，如果沒有目錄，那麼查詢一個漢字就需要很長時間了。
找到id=8的只需要這幾步
最後總結一點：如果沒有索引我們查詢數據是需要遍歷雙向鍊表來定位對應的page，現在通過索引創建的「目錄」就可以很快定位對應頁上了！
其實底層實現的結構就是B+樹，B+樹作為樹的一種實現能夠讓我們很快查找出對應內容。
索引可以提高查詢速度，但是會降低增刪改的速度，為什麼
任何事情都有有利有弊，在於你自己權衡利弊。
首先來說B+樹就是平衡樹的一種。
NOTE：平衡樹它就是一顆空樹或者說它左右兩個子樹的高度相差的絕對值不會超過1，並且左右兩個子樹都是一顆平衡二叉樹。
如果一棵普通B樹在極端情況下是有可能退化成鍊表的，這樣所謂的查詢提速也就不存在了
前面我們就說了B+樹本身就是平衡樹，所以它是不會退化成鍊表的，樹的高度都是比較低的（矮胖墩）【正因為這一點，我們的檢索時間複雜度為O】，在上面添加索引會提高查詢速度中我們介紹的建立索引，說白了就是建立一個B+樹。
B+樹是一顆平衡樹，如果我們對這棵樹增刪改的話，那肯定會破壞它的原有結構。要維持平衡樹，就必須做額外的工作。正因為這些額外的工作開銷，導致索引會降低增刪改的速度
索引常用的算法原理分析：B樹和B+樹等
和索引相關的算法：二分查找法、二叉查找樹、平衡二叉樹、B樹、B+樹，內容長，但很有用，如果看、耐心看，珍惜時間！
我們在這些數字中用不同算法（1、2、3、5、6、7、9）找出6。
二分查找法原理：先將記錄按順序排列，查找時先按序列的中點位置為比較對象，如果要找的元素值小於該中點元素，則將查詢範圍縮小為左半部分；如果要找的元素值大於該中點元素，則將查詢範圍縮小為右半部分。以此類推，直到查到需要的值。
比如我們要找6，用了 3 次就查找到 6 這個數字了。如果是順序查找，則需要查詢 5 次（從第一個數字 1 開始，如果發現不是 6，則繼續查找下一個，直到查詢到 6）。
我們來對比一下這個例子順序查找和二分查找法的平均查找次數：
順序查找：(1 + 2 + 3 + 4 + 5 + 6 + 7)/7 = 4 次
二分查找法：(3 + 2 + 3 + 1 + 3 + 2 + 3)/7 ≈ 2.4 次
顯然二分查找法相對順序查找平均效率更高。
二叉樹查找原理：二叉查找樹中，左子樹的鍵值總是小於根的鍵值，右子樹的鍵值總是大於根的鍵值，並且每個節點最多只有兩顆子樹。
還是找6，這組數字的平均查找次數為：(3 + 2 + 1 + 2 + 3 + 4 + 5)/7 ≈ 2.9 次
試想一下，如果 3 的右子樹後面拖更多的數字，那查詢效率得多低啊！
此時，平衡二叉樹出場了。
平衡二叉樹的定義：滿足二叉查找樹的定義，另外必須滿足任何節點的兩個子樹的高度差最大為 1。
如果要查值為 6 的記錄，先找到根（這裡是 5 ），這裡借用二分查找的思想，因為要找的值 6 大於中點元素 5，所以需要查找的是 5 的右子樹，而又因為 6 小於 7，則應該找 7 的左子樹，找到 6 這條記錄，一共查找了 3 次。如果查找記錄使用順序查找，找到 6 這個值需要查 5 次。
平衡二叉查找樹的平均查找次數：(3 * 4 + 2 * 2 + 1) /7 ≈ 2.4 次
計算方式：該平衡二叉查找樹中 4 個第三層的值需要查找 3 次，2 個第二層的值需要查找 2 次，第一層也就是根的值只需要查 1 次。
上面我們說了順序查找需要查找4次，比起來顯然平衡二叉查找樹的平均查找速度比順序查找更快。
但是平衡二叉樹有個缺點就是，每個節點最多只有兩個分支，如果數據量比較大，要經歷多層節點才能查詢在葉子節點的數據。
如果在平衡二叉樹的基礎上，每個節點可以有多個分支，那即使在葉子節點的數據，是不是查詢效率也比較高呢？這就引出了 B 樹結構。
B 樹可以理解為一個節點可以擁有多於 2 個子節點的多叉查找樹。B 樹中同一鍵值不會出現多次，要麼在葉節點，要麼在葉的子節點上。
比如用 1、2、3、5、6、7、9 這些數字構建一個 B 樹結構，其圖形如下：
與平衡二叉樹相比，B 樹利用多個分支（平衡二叉樹只有兩個分支）節點，減少獲取記錄時所經歷的節點數。
B 樹也是有缺點，因為每個節點都包含 key 值和 data 值，因此如果 data 比較大時，每一頁存儲的 key 會比較少；當數據比較多時，同樣會有：「要經歷多層節點才能查詢在葉子節點的數據」的問題。這時，B+ 樹站了出來。
B+ 樹是 B 樹的變體，定義基本與 B 樹一致
B樹和B+樹不同點：
所有葉子節點中包含了全部關鍵字的信息各葉子節點用指針進行連接非葉子節點上只存儲 key 的信息，這樣相對 B 樹，可以增加每一頁中存儲 key 的數量。B 樹是縱向擴展，最終變成一個「瘦高個」，而 B+ 樹是橫向擴展的，最終會變成一個「矮胖子」。在 B+ 樹中，所有記錄節點都是按鍵值的大小順序存放在同一層的葉子節點上。B+ 樹中的 B 不是代表二叉(binary) 而是代表（balance），B+ 樹並不是一個二叉樹。
B+與B樹最大的區別就是：B+樹它的鍵一定會出現在葉子節點上，同時也有可能在非葉子節點中重複出現。而 B 樹中同一鍵值不會出現多次。
總結
到此為止基本mysql查找算法就全部講完了，下一篇我們主要來看mysql的聚簇索引和非聚簇索引。
這篇文章重點知識：為什麼索引可以加速查詢，加速查詢算法的實現原理。