索引原理（B,B-,B+,紅黑樹）
① 非聚集索引和聚集索引的區別在於， 通過聚集索引可以查到需要查找的數據， 而通過非聚集索引可以查到記錄對應的主鍵值 ， 再使用主鍵的值通過聚集索引查找到需要的數據。然而， 有一種例外可以不使用聚集索引就能查詢出所需要的數據， 這種方法 稱之為「覆蓋索引」查詢， 也就是平時所說的複合索引或者多字段索引查詢。
② B樹（二叉搜索樹）：如果B樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那麼B樹的搜索性能逼近二分查找；但它比連續內存空間的二分查找的優點是，改變B樹結構（插入與刪除結點）不需要移動大段的內存數據，甚至通常是常數開銷；最差情況是B樹等同於線性的了，所以要儘量保持平衡，即“平衡二叉樹”。
③ B-樹：不是二叉。B-樹的性能總是等價於二分查找
④ B+樹（Innodb索引）：B+樹是B-樹的變體，也是一種多路搜索樹。B+的搜索與B-樹也基本相同，區別是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中），其性能也等價於在關鍵字全集做一次二分查找
⑤ 紅黑樹：紅黑樹（Red-Black Tree）是二叉搜索樹（Binary Search Tree）的一種改進。二叉搜索樹在最壞的情況下可能會變成一個鏈表（當所有節點按從小到大的順序依次插入後）。而紅黑樹在每一次插入或刪除節點之後都會花O（log N）的時間來對樹的結構作修改，以保持樹的平衡。也就是說，紅黑樹的查找方法與二叉搜索樹完全一樣；插入和刪除節點的的方法前半部分節與二叉搜索樹完全一樣，而後半部分添加了一些修改樹的結構的操作。
紅黑樹的每個節點上的屬性除了有一個key、3個指針：parent、lchild、rchild以外，還多了一個屬性：color。它只能是兩種顏色：紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質之外，還具有以下4點性質：
1. 根節點是黑色的。
2. 空節點是黑色的（紅黑樹中，根節點的parent以及所有葉節點lchild、rchild都不指向NULL，而是指向一個定義好的空節點）。
3. 紅色節點的父、左子、右子節點都是黑色。
4. 在任何一棵子樹中，每一條從根節點向下走到空節點的路徑上包含的黑色節點數量都相同。
什麼是回表，如何避免回表，什麼是索引覆蓋？
使用聯合索引，將查詢中的where 所有條件創建聯合索引可避免回表，實現索引覆蓋，效率更高。
不只是索引的全部定義，只要滿足最左前綴，就可以利用索引來加速檢索。這個最左前綴可以是聯合索引的最左 N 個字段，也可以是字符串索引的最左 M 個字符。
因此，基於最左前綴原則，我們在定義聯合索引的時候，考慮如何安排索引內的字段順序就至關重要了！評估的標準就是索引的複用能力，比如，當已經有了(a,b)字段的索引，一般就不需要再單獨在a上建立索引了。
如果沒有索引下推優化（或稱ICP優化），當進行索引查詢時，首先根據索引來查找記錄，然後再根據where條件來過濾記錄；在支持ICP優化後，MySQL會在取出索引的同時，判斷是否可以進行where條件過濾，也就是說提前執行where的部分過濾操作，在某些場景下，可以大大減少回表次數，從而提升整體性能。
閱讀更多 wendellFang 的文章
