主要内容：
一、 主鍵索引
二、 二級索引
三、 數學分析
四、 索引的作用
一、主鍵索引：
作為資料庫的使用者，每天都需要跟資料庫打交道，避免不了接觸兩個概念，一個是表，一個是索引。日常思維中，表是用來存儲表中的資料，索引是用來加速查詢通路。下面來看一下RDS for MySQL在InnoDB引擎下面，資料的實體組織是如何組織？
如上圖所示這張表，它的主鍵是1個id、4個位元組、id作為主鍵，後面跟着一個單字元的C1，然後還有一個int類型的c2，然後單字元的c3，同時在 c1字段上有索引，這是很簡單的一張表。這個資料是如何組織？
在InnoDB引擎下，資料是存儲在主鍵中，就是指資料是通過主建進行實體組織，跟Oracle本身預設的堆表不一樣，Oracle本身預設建立的表如果不指定的話是一個堆表，真的有一個對象、實體結構、資料結構，一堆的資料結構來存儲資料，同時主建是另外一個資料結構，是兩份資料。對于MySQL在InnoDB引擎下面，本身資料是存儲在主鍵的葉子節點中，如下圖所示，“c1、c2、c3” 3列資料都存儲在主鍵的葉子節點。
整個組建的資料結構是B-Tree，B指的是Balance Tree多路平衡樹，而不是Binary tree二叉樹。多路平衡樹和二叉樹之間差別在于：
·二叉樹隻有左分支和右分支，而且不限定左分支的深度和右分支的深度，也可以指樹的高度，不限定左分支右分支的高度否是一緻。
·多路平衡樹指，從最上面的根節點到任何一個葉子節點是一緻的，樹高從任何一個次元來看，從任何一個葉子節點到根節點，從跟到任何一個業務節點，必須是一緻的。多路指是每一個節點，不論分支節點、跟節點，下面可以挂多個此子節點。
同時在整個的結構裡面，在Oracle的體系中，對于每個存儲資料的基礎單元叫塊“block”，再MySQL中做稱為頁。在MySQL裡面，如果不特意指定，預設都是16KB作為一頁，從磁盤上通路,不管是讀取一行資料，還是讀取一個位元組，都要讀16KB的資料到記憶體中。
資料組織結構有幾個關鍵點：
第一個關鍵點：資料是存儲在主鍵中，必須顯示定義主鍵，如果不顯示定義主鍵會出現兩種情況：
·第一種情況是在資料傳輸時，無法判斷資料是不是重複，是不是唯一的。主鍵的定義是非空、唯一。
·第二種情況是把RDS for MySQL的備份還原到線下的資料時，沒有主鍵的表，讀取時字段對不上。因為阿裡的SQL，為了避免出現沒有定義主鍵，導緻的問題，預設隐式的增加一個字段，把備份還原到實體備份或還原到本地時，這張表會多出一個字段，會導緻恢複時這張表不可通路。
第二個關鍵點：表的每個資料塊大小都是16KB，分支節點也是16KB，分支節點上的節點數越多，樹越扁，樹高越小，查詢的越快。因為根和分支節點都需要記憶體運作，樹高越高，需要讀的16KB的塊數就越多，導緻查詢會更慢。
第三個關鍵點：塊的尺寸一定的情況下，裡面帶的條目數越多，樹高越小，通路資料的代價越低。條目數取決于主鍵的資料類型，如下圖所示，int類型4個位元組，big int是8個位元組，如果使用的是字元串，在uti8字元集的情況下，是char類型，至少要3個位元組以上。是以關鍵點是主鍵盡量使int或者是big int這種整形，本身它很小，通常情況下一個16KB的塊能放幾百個int類型的條目，樹高很容易控制在很小。
第四個關鍵點：本身它是一棵平衡樹，平衡樹的要求就在于，從根到任何一個葉子節點高度都要一樣，樹高是固定值，這棵樹不斷的被增、删、改的情況下，為了保證根與分支節點與葉子節點的一緻性， 建議用auto_increment正向遞增或者使用sequence，如果在有drds或者sequence引擎的情況下，可以用savings或者outer equipment這種單向遞增，保證每次的寫入的操作，尤其是插入操作，性能一緻。
二、二級索引
除了主鍵以外的索引，其他都稱之為二級索引。二級索引跟的主鍵索引一樣，也是B-Tree。
二級索引在MySQL裡與Oracle在設計上不一樣，如下圖所示，對“c1”字段做了一個索引，但實際上資料存儲在主鍵中，是以資料尋址時，沒有必要放資料的真正實體位址，在Oracle裡，是資料的實體位址。在MySQL裡面直接放主鍵的值，因為知道主鍵的值，就能定位到這行記錄。雖然索引放的是“c1”，但是真正存儲時，節點中是把主鍵的值都要存起來，這種資料類型導緻主鍵的資料長度不能太長，否則會有問題。
補充一下，因為主鍵除了單項遞增資料類型要小以外，如uuid、Md5不建議用來做主鍵，因為長度太長。如果長度太長，磁盤塊裡頭放的會很小，樹結構會變得很臃腫，相同存儲相同的資料量，索引會占很大的空間。對于IO産生很大的影響，相同的硬體條件下,通路資料速度要慢，開銷大、成本高。
三、數學分析
假設一張表裡有一億行記錄，每一個磁盤頁存放16KB的塊，存放的條目數叫做平衡因子/分支因子（Balance factor）。
每個16KB分支節點可以存儲的索引字段個數，取兩個比較極限的情況，“b=2”每一個16KB的塊裡隻能放兩條記錄，類似于二叉樹,“b=100”每一個記錄裡能放100個條記錄，就每一個16KB的塊裡能放100條記錄。
樹高(h)，樹高影響實體IO，從磁盤上擷取資料到記憶體，需要花多少個物業取IO通路到資料，資料庫的增、删、改、查（select、interrupted，delete，replace），所有操作都是發生在記憶體。
索引B樹高度：從葉子節點到根節點的節點個數。樹高(h)固定的計算公式：
是跟 “b”和“n”相關的取兩個的對數，“b”是平衡因子，在“b=2”的情況下，樹高是27，在“b=100”的情況下，從定位1行記錄的開銷需要讀27個16KB的塊到記憶體，b定義成100，隻需讀4個16KB的塊到記憶體，開銷差異很明顯。
存儲空間的差異更明顯，隻說主鍵“b=2”情況下，需要花費781,250 MB的存儲容量；“b=100”的情況下，花費15,625 MB的存儲容量。
一般RDS記憶體正常情況下，最大的能到470GB記憶體，“b=100”時，770%~75%左右是配置設定給InnoDB用來緩存磁盤塊， 770%~75%是可以保證資料完全緩存在記憶體中，表的核心資料都儲存在記憶體裡，也不會超出記憶體最大值。“b=2”時，隻考慮了主健，不考慮任何二級索引，核心表資料也需要781GB，會需要出現實體IO換入換出資料，因為超出了記憶體空間。同樣的存儲，兩種情況的代價是完全不一樣，性能表現截然不同。
四、索引的作用
通過圖書館的模型介紹索引的作用，去圖書館内找一本書，正常的情況下，需要一個目錄的，通過查目錄，查詢到所需的書在哪個書架上面的哪個位置上面，這樣可以快速找到，這個目錄就相當于索引，它是一個從空間換時間，通過提前做準備好其他空間，來緩解通路時間。需要注意的是這裡隻是尋找一本書，通路一個資料，如果通路的資料量，需要擷取的資料量占總資料量的一定比例之後，就會引起質變。
優化是提高通路效率。
兩個概念：TR、TS。
TR是随機通路一個16KB的塊，TS是順序的去讀一個16KB的塊需要的時間。
通過user使用者表，(id int primary key, age int, fname char(1));
通過Select fname from users where age = 10進行一個簡單的查詢。
這裡我們忽略樹高，假設資料已經都在記憶體，因為不知道樹讀取的位置是在哪，那麼下一次對根來說就是一個随機讀，讀到根在忽略樹高且樹高合理的情況下，需要畫n減一個順序圖，把表編輯，因為沒有索引。
位次條件下建索引，首先考慮位次條件， where後的條件是什麼，根據什麼條件去通路資料，根據規則去優化通路，如上圖所示，age沒有索引，就全面掃描，但在不同的情況下
TR = 10 ms
TS = 0.01 ms
RT = TR * 1 + TS * (n - 1)
= 10 ms * 1 + 0.01 ms * (900K -1)
= 10 ms + 9000 ms
= 9.01 Sec
RT = TR * 1 + TS * (n - 1)
= 10 ms * 1 + 0.01 ms * (9000 -1)
= 10 ms + 90 ms
= 100 ms
= 10 ms * 1 + 0.01 ms * (9 -1)
= 10 ms + 0.08 ms
= 10.08 ms
全表掃描不一定不是好事，取決于通路、目的、還有資料量的多少。
如果表裡沒太大的資料量，沒有必要去通路索引，根據公式推理
結論就是通路的位次上面沒有索引，全表掃描來擷取資料，全面掃描不一定不好，不好的代價是在于表裡的資料量，随着資料量的上升，TS的通路的代價會快速的增加，會導緻時間快速增加。
随着資料量增加，上線時間加長，表的資料量越來越多，查詢越來越慢，可以看在a制字段上面加一個索引，如下圖所示：
由此推出，查詢慢，在位次條件對應的情況下建索引，前提是擷取的資料量是占總表的資料量很小的一部分，索引才是生效的。
實際上不管是oracle，還是MySQL的優化器也好，根據查詢，先估通路的資料量大概會占總表的資料量的多少，包括根據版本不一樣，會有略微變化。如果查詢擷取的資料量超過了總表資料量的一定比例之後，就不能再走這種索引通路形式，索引通路形式會帶來大量的回表通路，會引起大量的随機讀。
總結次位條件上面盡量建索引來加速通路，節省CPU，從時間來衡量，就是減少通路時間，減少查詢的處理時間。
建索引前提下是通路的資料要占總表資料量很小的一部分。
如何進行優化，如下表所示，公式内頭最大的開銷是在4個随機讀上面，來源于回表的3個随機讀，産生三個随機讀的原因是在于索引裡沒有fname，沒有需要的資料，把fname放到我的索引裡，Users (id int primary key, age int, fname char(1), key idx_age_fname (age,fname));這個時候通路就會變成了一個随機讀，通路的根，三個順序讀，找到三個資料，通過掃索引的三行資料，就滿足了查詢，公式就會變成1個随機讀加3個順序讀，出來是10個毫秒，這個索引叫做覆寫性索引，能夠完全滿足查詢，不用回表，是在對于查詢來說是最高效的一個通路形式。
如上圖所示，從9秒鐘優化到10 個毫秒，900倍的性能提升，最核心的表最頻繁的查詢建覆寫性索引。
建組合索引的時候，區分度越高的字段放在最前面，因為區分度越高，中間結果的索引片會越小越薄。目的就是隻有在選擇很小量的資料的時候，索引才是高效的。
反推就是中間生成的結果集或者中間的節點索引片越薄，包含的資料越小，索引對查詢的加速是越高的。
最左原則，要求能比對到的位次條件不能出現在第二個，位次條件一定要比對到第一個字段才可以，就是在比對索引跟查詢的位次的時候，按照從左到右來比對。如果已經有查詢在建組合索引的時候，一定要把幾個條件裡區分度最高的放在最左邊，其次，跟區分度類似的字段，盡量的往前放，經常被更新的字段盡量往後放，
最後，如果相同區分度都差不多，盡量把age看它的位次條件，如果是等值的，不管是等号大于等于小于等于都可以，隻要帶等号的盡量往前放，因為如果帶着等号，條件會被用來生成中間的臨時索引片或者中間的結果集。後面字段的條件依然能被用來生成中間的結果集。
fname是否能被用來生成結果集，需要看位次條件，第一個的位次條件，如果是等值帶等号，第二個字段肯定能被用來，隻要它後邊位次加減中有，肯定能用來生成中間的結果集，生成重量級結構機，第三個能不能被用，要看第二個是不是帶等值條件，就是說如果帶等值條件，盡量往前放，歸結起來就是：
1、 區分度越高的位次條件盡量往前放，如不是經常被更新的；
2、 帶等值條件的盡量往前放；
舉例，上圖如果寫的是不等于d那麼age可以用來生成中間結果索引片，lname也能用來生成中間索引片，如果這裡fname的位次條件，就不能用來生成索引片，隻能用來做引擎下推的過濾，或者是server層的過濾，通過已經存儲好的索引去生成中間結果集是基本上對CPU消耗是非常低的，但如果靠CPU去做過濾，生成結果集是非常耗CPU的，這是兩種完全不同的通路方式。
還有如果前面的等值全是等值條件，排序之前所有的索引前置的字段都是等值的情況下，就可以直接通過索引來避免它的排序。
覆寫性索引并排序例子：
RDS for MySQL資料庫的日常運維開發的使用的規範和建議