一粱坤、基礎

1.1 索引

MySQL官方文檔對索引的定義：

Indexes are used to find rows with specific column values quickly.

在數據之外川背，數據庫系統(tǒng)維護著滿足特定查找算法的數據結構似扔，這些數據結構以某種方式引用（指向）數據扩然，這樣就可以在這些數據結構上實現(xiàn)高級查找算法辆毡。這種數據結構，就是索引异袄。

image.png

1.2 查找算法和數據結構

二分查找：O（logN）

二分查找法

二叉查找樹、平衡二叉樹

二叉查找樹

二玛臂、B樹烤蜕、B+樹

（平衡）二叉樹有一個缺陷，樹的高度會隨著數據量的增加而增高迹冤，由于數據存儲在磁盤讽营，從而導致IO開銷很大。

2.1 b-tree

B樹是由二叉樹和索引順序訪問方法演化而來的一種數據結構泡徙。它是一種自平衡的樹數據結構橱鹏，維護排序的數據，并允許在對數時間內進行搜索锋勺、順序訪問蚀瘸、插入和刪除操作。
相對于二叉樹庶橱，b樹的每個節(jié)點可以用的子節(jié)點的數目更多贮勃，這就意味著，在相同的數據量下苏章，樹的高度顯著降低寂嘉，查找更快，從而減少了磁盤的io枫绅。

b-tree

2.2 b+tree

現(xiàn)實使用中泉孩，基本是使用的b+樹，b+樹是B樹的變種并淋，它是一種專門為磁盤或其他讀取設備設計的一種平衡查找樹寓搬。不同于b樹，b+樹的非葉子節(jié)點只存儲索引县耽，不存儲數據句喷，所有數據都按照順序存儲在同一層的葉子節(jié)點镣典。

b+tree

2.3 帶有順序訪問指針的b+tree

一般在數據庫系統(tǒng)或文件系統(tǒng)中使用的B+Tree結構都在經典B+Tree的基礎上進行了優(yōu)化，增加了順序訪問指針唾琼。
特性：

• 1.單一節(jié)點存儲更多的元素兄春，使得查詢的IO次數更少；
• 2.所有查詢都要查找到葉子節(jié)點锡溯，查詢性能穩(wěn)定赶舆；
• 3.所有葉子節(jié)點形成有序鏈表，便于范圍查詢祭饭。

鏈表b+樹

三芜茵、MySQL B+樹索引

MySQL數據庫InnoDB存儲引擎的數據表，有兩種索引：聚集索引(cluster index)和輔助索引(secondary index)甜癞。每個表可以有多個輔助索引夕晓，但是有且只有一個聚集索引，一般說來悠咱，聚集索引和主鍵是同義詞：

• 如果表定義了主鍵蒸辆，那么InnoDB會使用主鍵作為聚集索引
• 如果表沒有定義主鍵，那么InnoDB會使用第一個唯一索引作為主鍵析既，這個唯一索引里的所有列必須都不能為null
• 如果以上兩點都不滿足躬贡，InnoDB會在一個包含行號（row id）的合成列上建立一個名為GEN_CLUST_INDEX 的聚集索引

3.1 聚集索引

InnoDB存儲引擎表是索引組織表，按照主鍵順序存放表中的數據眼坏。聚集索引按照表的主鍵順序組織一個B+樹拂玻，同時在葉子節(jié)點中存放完整的行數據，所以將聚集索引葉子節(jié)點稱為數據頁宰译，非葉子節(jié)點稱為索引頁檐蚜。索引組織表的這一特性決定了，數據頁也是聚集索引的一部分沿侈。并且所有的數據頁都通過鏈表來鏈接闯第。
葉子索引指向的是數據頁，進行查找時缀拭，會將對應行所在的數據頁加載到內存中咳短，在對相應的行進行二分查找，由于這一操作是在內存中進行蛛淋，所以速度很快咙好。

cluster index

3.2 輔助索引

同聚集索引一樣，輔助索引的底層實現(xiàn)也是b+樹褐荷，不同的是勾效，輔助索引的葉子節(jié)點存放的是輔助索引的索引列和主鍵。因此通過輔助索引進行查找分兩步，首先查到輔助索引對應的主鍵葵第，然后再去聚集索引中獲取主鍵對應的數據绘迁。

secondary index

3.3 B+樹索引分裂

如果數據的插入順序是隨機的，比如聚合索引是UUID的情況卒密，那么取頁的中間記錄作為分裂點；如果數據的插入是有順序的棠赛，那么分裂點定在中間就不是很合理哮奇。假設一個頁的記錄如下
p1 : 1 2 3 4 5 6 7 8 9
現(xiàn)要插入數字10，如果選擇中間的記錄作為插入點睛约，那么當前頁會分裂成下面兩列：
p1 : 1 2 3 4
p2 : 5 6 7 8 9 10
由于插入是按順序的鼎俘，p1這個頁里面不會有記錄插入，從而導致了空間的浪費辩涝，并且p2很快又會迎來一次分裂贸伐，導致頁分裂過于頻繁。
InnoDB存儲引擎會根據插入是否有序怔揩，來決定分裂點捉邢，當插入有序時，會根據插入的方向決定在尾端進行頁分裂商膊。

四伏伐、分區(qū)相關

MySQL支持的分區(qū)是局部索引分區(qū)，即一個分區(qū)中及存放了索引又存放了數據晕拆。全局分區(qū)是指藐翎，分區(qū)中只存放數據，而所有數據的索引放在一個對象中实幕。
如果對表進行了分區(qū)吝镣，那么所有的唯一索引都要帶上分區(qū)使用的所有列。

五昆庇、使用索引分區(qū)的一些意見

• 使用自增的主鍵（頁分裂和熱點數據）
  http://seanlook.com/2017/02/16/mysql-autoincrement/
  https://www.cnblogs.com/JiangLe/p/6362770.html
• 索引不宜太多
• 聯(lián)合索引的使用：最左前綴原則
  ICP http://blog.codinglabs.org/articles/index-condition-pushdown.html
  
  im多個鍵值的B+樹
• 分區(qū)表在查找時必須帶上分區(qū)字段
• 慢sql日志 和 explain命令（執(zhí)行計劃）