什么是數(shù)據(jù)庫的索引？

索引

當(dāng)數(shù)據(jù)庫中數(shù)據(jù)量比較少的時(shí)候，哪怕全部檢索也可以很快，但如果數(shù)據(jù)量達(dá)到了百萬，千萬，上億的時(shí)候，還是全表掃描，那么數(shù)據(jù)查詢的速度會(huì)慢的讓人無法忍受。

索引的作用，就是為了加快數(shù)據(jù)查詢，類似于我們查不認(rèn)識(shí)的字時(shí)，使用字典的目錄一樣，在字典里面快速查詢出不認(rèn)識(shí)的字。字典可以根據(jù)讀音的首字母，偏旁部首，筆畫來查詢。同樣的，索引也有Hash索引，B-Tree索引，GIN索引等不同索引類型，根據(jù)查詢的場景不同，可以選擇創(chuàng)建對(duì)應(yīng)的索引類型。

索引分類

數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)

Postgresql支持豐富的索引類型，并且根據(jù)索引框架支持用戶開發(fā)自定義的索引，下面列舉下常用的索引類型及適用范圍

mysql的索引類型和數(shù)據(jù)庫引擎相關(guān)性較強(qiáng)，不過最常用的B樹索引是支持的

聚簇索引與非聚簇索引

InnoDB 默認(rèn)創(chuàng)建的主鍵索引是聚族索引（Clustered Index），其它索引都屬于輔助索引（Secondary Index），也被稱為二級(jí)索引或非聚族索引。

聯(lián)合索引與單列索引

create index i1 on t2 (c1);
create index i2 on t2 (c1,c2);

pg的多列(聯(lián)合)索引僅支持b-tree、gist、gin、brin類型，其中b-tree的多列索引，僅在索引的第一個(gè)字段出現(xiàn)在查詢條件中才有效(最左匹配原則)，而其他類型的多列索引可以支持任意字段查詢 對(duì)于多字段查詢，多列索引要比單列索引的查詢速度快，可以避免回表查詢，但對(duì)于單字段查詢，多列索引就要比單列索引查詢速度慢了，這里需要根據(jù)表的實(shí)際查詢sql類型、頻率，綜合考慮是否需要使用多列索引。

部分索引

部分索引是指支持在指定條件的記錄上創(chuàng)建索引，通過where條件指定這部分記錄，比如：

postgres=# create table test(id int, c1 varchar(10));
CREATE TABLE
postgres=# insert into test select generate_series(100001,100100),'invalid';
INSERT 0 100
postgres=# create index i1 on test (c1) where c1 = 'invalid';
CREATE INDEX
postgres=# explain analyze select * from test where c1 = 'invalid';
                                                QUERY PLAN
----------------------------------------------------------------------------------------------------------
 Index Scan using i1 on t3  (cost=0.14..4.16 rows=1 width=11) (actual time=0.035..0.079 rows=100 loops=1)
 Planning Time: 0.485 ms
 Execution Time: 0.135 ms
(3 rows)

實(shí)際上對(duì)于數(shù)據(jù)分布不均的字段，創(chuàng)建正常的索引，在查詢占比較小值時(shí)也是可以走索引的，查詢占比較大值時(shí)無法走索引，如下所示，部分索引的優(yōu)勢(shì)在于索引體積小，維護(hù)代價(jià)也比較小

函數(shù)索引

函數(shù)索引指可以使用一個(gè)函數(shù)或者表達(dá)式的結(jié)果作為索引的字段，比如：

postgres=# create index i1 on test ((lower(c1)));
CREATE INDEX
postgres=# explain analyze select * from test where lower(c1) = 'xxx';
                                                  QUERY PLAN
--------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=20.29..783.05 rows=500 width=37) (actual time=0.063..0.063 rows=0 loops=1)
   Recheck Cond: (lower(c1) = 'xxx'::text)
   ->  Bitmap Index Scan on i1  (cost=0.00..20.17 rows=500 width=0) (actual time=0.060..0.060 rows=0 loops=1)
         Index Cond: (lower(c1) = 'xxx'::text)
 Planning Time: 0.406 ms
 Execution Time: 0.095 ms
(6 rows)

postgres=# explain analyze select * from test where c1 = 'xxx';
                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Seq Scan on test  (cost=0.00..2084.00 rows=1 width=37) (actual time=19.016..19.016 rows=0 loops=1)
   Filter: (c1 = 'xxx'::text)
   Rows Removed by Filter: 100000
 Planning Time: 0.121 ms
 Execution Time: 19.048 ms
(5 rows)

此時(shí)如果直接使用c1字段作為查詢條件是無法走索引的，同理如果創(chuàng)建的是普通索引，在查詢時(shí)對(duì)字段加上了函數(shù)或者表達(dá)式，都不會(huì)走索引，我們應(yīng)始終避免出現(xiàn)這樣的問題

排序索引

在涉及order by操作的sql時(shí)，b-tree索引返回的結(jié)果是有序的，可以直接返回，而其他索引類型，需要對(duì)索引返回結(jié)果再進(jìn)行一次排序。b-tree索引的默認(rèn)排序?yàn)樯颍罩捣旁谧詈?，?chuàng)建索引時(shí)可以指定排序方式，如按倒序排序時(shí)，空值默認(rèn)是放在最前的，但往往我們的查詢并不想展示空值的結(jié)果，此時(shí)可以在創(chuàng)建索引時(shí)指定排序desc nulls last以達(dá)到和查詢sql切合的目的。

索引非銀彈

索引需要占用額外的物理空間，如果表中的數(shù)據(jù)變化，也需要同步維護(hù)索引中的數(shù)據(jù)，對(duì)數(shù)據(jù)庫的性能會(huì)有一定影響。考慮到索引的維護(hù)代價(jià)、空間占用和查詢時(shí)回表的代價(jià)，不能認(rèn)為索引越多越好。索引一定是按需創(chuàng)建的，并且要盡可能確保足夠輕量。一旦創(chuàng)建了多字段的聯(lián)合索引，我們要考慮盡可能利用索引本身完成數(shù)據(jù)查詢，減少回表的成本。不能認(rèn)為建了索引就一定有效，對(duì)于后綴的匹配查詢、查詢中不包含聯(lián)合索引的第一列、查詢條件涉及函數(shù)計(jì)算等情況無法使用索引。此外，即使SQL本身符合索引的使用條件，MySQL也會(huì)通過評(píng)估各種查詢方式的代價(jià)，來決定是否走索引，以及走哪個(gè)索引。

數(shù)據(jù)庫基于成本決定是否走索引

查詢數(shù)據(jù)可以直接在聚簇索引上進(jìn)行全表掃描，也可以走二級(jí)索引掃描后到聚簇索引回表。那么PostgreSQL/MySQL到底是怎么確定走哪種方案的呢。在滿足能走索引的條件下，最終是否走索引由計(jì)劃器生成的執(zhí)行計(jì)劃決定，PostgreSQL/MySQL中執(zhí)行計(jì)劃是完全基于代價(jià)估計(jì)的，如果估算的代價(jià)為全表掃描最優(yōu)，則不會(huì)使用索引掃描

這里的代價(jià)，包括IO成本和CPU成本：

IO成本，是從磁盤把數(shù)據(jù)加載到內(nèi)存的成本。默認(rèn)情況下，讀取數(shù)據(jù)頁的IO成本常數(shù)是1（也就是讀取1個(gè)頁成本是1）。

CPU成本，是檢測數(shù)據(jù)是否滿足條件和排序等CPU操作的成本。默認(rèn)情況下，檢測記錄的成本是0.2。基于此，我們分析下全表掃描的成本。

全表掃描，就是把聚簇索引中的記錄依次和給定的搜索條件做比較，把符合搜索條件的記錄加入結(jié)果集的過程。要計(jì)算全表掃描的代價(jià)需要兩個(gè)信息：

1.聚簇索引占用的頁面數(shù)，用來計(jì)算讀取數(shù)據(jù)的IO成本；

2.表中的記錄數(shù)，用來計(jì)算搜索的CPU成本。

有時(shí)會(huì)因?yàn)榻y(tǒng)計(jì)信息的不準(zhǔn)確或成本估算的問題，實(shí)際開銷會(huì)和MySQL統(tǒng)計(jì)出來的差距較大，導(dǎo)致MySQL選擇錯(cuò)誤的索引或是直接選擇走全表掃描，這個(gè)時(shí)候就需要人工干預(yù)，使用強(qiáng)制索引了。

索引失效

• 對(duì)于 Hash 索引實(shí)現(xiàn)的列，如果使用到范圍查詢，那么該索引將無法被優(yōu)化器使用到。Hash 索引只有在“=”的查詢條件下，索引才會(huì)生效。如果涉及范圍查詢則應(yīng)建立b-tree索引
• 以 % 開頭的 LIKE 查詢將無法利用節(jié)點(diǎn)查詢數(shù)據(jù)，這種情況下需要考慮gin索引或者es這種全文檢索的方式
• 使用復(fù)合索引時(shí)，需要使用索引中的最左邊的列進(jìn)行查詢，才能使用到復(fù)合索引。

例如我們?cè)?order 表中建立一個(gè)復(fù)合索引 idx_user_order_status(order_no, status, user_id)，如果我們使用 order_no、order_no+status、order_no+status+user_id 以及 order_no+user_id 組合查詢，則能利用到索引；而如果我們用 status、status+user_id 查詢，將無法使用到索引，這也是我們經(jīng)常聽過的最左匹配原則。

• 如果查詢條件中使用 or，且 or 的前后條件中有一個(gè)列沒有索引，那么涉及的索引都不會(huì)被使用到。

常見慢sql情況

• 沒有創(chuàng)建索引，建表的時(shí)候一定不要忘記建立可能的索引，創(chuàng)建索引需要按照ESR原則進(jìn)行
• 索引失效的情況，如查詢字段上使用表達(dá)式導(dǎo)致索引失效比如在c1字段上存在一個(gè)b-tree索引，where c1+1 > 10000這個(gè)查詢條件不會(huì)走索引，而where c1 > 10000-1可以走索引。
• 查詢列表數(shù)據(jù)不分頁，對(duì)于列表展現(xiàn)數(shù)據(jù)，在數(shù)據(jù)量特別大的情況，一次性返回所有數(shù)據(jù)一般不具有實(shí)際的業(yè)務(wù)意義，此時(shí)應(yīng)通過limit offset進(jìn)行分頁，這樣有機(jī)會(huì)利用到索引掃描和排序，降低全表掃描的影響，同時(shí)也能減小返回?cái)?shù)據(jù)包過大的負(fù)擔(dān)。
• count (*) 時(shí)order by做無用排序由于列表展現(xiàn)與列表查數(shù)經(jīng)常成對(duì)兒出現(xiàn)，有可能在復(fù)用列表展現(xiàn)的sql時(shí)在查數(shù)時(shí)也加入了排序操作，此時(shí)無論是否加上排序操作，得到的最終結(jié)果是一致的，但加上排序時(shí)大大增加了得到目標(biāo)結(jié)果的代價(jià)。
• 跨表進(jìn)行分組、排序，當(dāng)涉及到跨表分組、排序時(shí)，需要把兩個(gè)表的結(jié)果集匯總到一起進(jìn)行排序、分組，這里的消耗是非常大的，此時(shí)可以考慮去冗余部分字段，使分組、排序操作在一個(gè)表中完成，這樣能夠利用到索引，起到優(yōu)化效果。
• 慢sql對(duì)數(shù)據(jù)庫cpu消耗極大，嚴(yán)重時(shí)甚至?xí)礄C(jī)
  

  

  
  

索引優(yōu)化

子查詢優(yōu)化

實(shí)際的業(yè)務(wù)sql中，往往要涉及多個(gè)表進(jìn)行關(guān)聯(lián)查詢，這里既可以使用子查詢，也可以使用表連接，一般我們認(rèn)為子查詢方式的查詢層次較多，且關(guān)聯(lián)時(shí)的結(jié)果集較大，所以性能會(huì)差一些，執(zhí)行計(jì)劃器會(huì)對(duì)子查詢進(jìn)行邏輯優(yōu)化，將子查詢上提到父查詢中，與父查詢合并，過濾出較小的結(jié)果集再進(jìn)行關(guān)聯(lián)

子查詢類型是否支持優(yōu)化

any，some，exists，not exists基本支持,in部分情況支持,all,not in不支持.

寫法優(yōu)化

• 連接優(yōu)化裁剪 利用left join消除無用的連接，當(dāng)連表查詢時(shí)，只輸出左表字段，且連接條件的右表字段具有唯一性，那么可以使用left join消除部分連接

• union all 代替 unionunion all不會(huì)進(jìn)行去重，union會(huì)去重，如果在明確查詢結(jié)果不存在重復(fù)數(shù)據(jù)時(shí)，union all的效率會(huì)高很多

• 避免使用select * 首先，如果select的字段被索引字段覆蓋，那么可能就會(huì)使用僅索引掃描，這種掃描性能會(huì)更高一些。其次，select字段的多少直接影響著結(jié)果集數(shù)據(jù)包的大小，對(duì)于前臺(tái)來說數(shù)據(jù)包越大，返回就越慢。還有對(duì)于一些復(fù)雜的查詢，比如涉及子查詢、連接、分組、聚合、排序等，過程中如果select字段過多，那么大概率會(huì)影響sql整體使用的work_mem，超出work_mem時(shí)則需使用磁盤，性能更低。

創(chuàng)建合適的索引

單表索引不應(yīng)該超過5個(gè)。復(fù)合索引字段數(shù)量一定不可超過4個(gè)。復(fù)合索引字段數(shù)量多主要有以下2個(gè)影響：1.字段數(shù)量越多，對(duì)查詢的要求越苛刻。查詢必須按照索引的命中規(guī)則來安排。2.字段數(shù)量越多，索引的體積越大。數(shù)據(jù)的扇出度（單次IO能得到的數(shù)據(jù)條數(shù)）越低，IO效率也越低，而且索引被更新的概率越大，由于二級(jí)索引大部分情況下是隨機(jī)更新，所以會(huì)引起B(yǎng)+樹的平衡維護(hù)操作。

• ESR原則

E  即Equal。查詢中等于條件的字段優(yōu)先考慮。S 即Sort,排序字段其次考慮。R 即Range,范圍查詢字段最后考慮 在經(jīng)常用于查詢的字段上創(chuàng)建索引,在經(jīng)常用于連接的字段上創(chuàng)建索引,在經(jīng)常用于排序的字段上創(chuàng)建索引

• 在選擇性好的字段上創(chuàng)建索引

低基數(shù)字段不應(yīng)該建立單獨(dú)的索引。（該字段的不重復(fù)值個(gè)數(shù)低于總行數(shù)的 10%的稱為低基數(shù)字段）。比如性別字段，只有男、女兩種取值，認(rèn)為選擇性不好，不建議創(chuàng)建索引分布不均勻的字段不應(yīng)該建立索引。如果一定需要，應(yīng)該避免使用分布較高的值作為查詢條件。分布不均勻指不同的列值占總體的比例差異很大（通常超過50%），即某一個(gè)列值或者某幾個(gè)列值在整個(gè)數(shù)據(jù)集合中占比非常大。例如幼兒園學(xué)生年齡分段：年齡段占比3~5：95% ，6~8：3%， 9~12：1%，12~20：1%，20以上0%

• 適當(dāng)創(chuàng)建聯(lián)合索引，并將選擇性好的字段作為第一個(gè)字段
• 對(duì)于頻繁更新的表避免創(chuàng)建過多索引

高頻更新字段不應(yīng)該建立索引,高頻更新字段，會(huì)以更新頻率同步去更新索引。這會(huì)引起索引的刪除、插入操作。頻繁地刪除索引上的數(shù)據(jù)，索引頁會(huì)造成大量的空洞，進(jìn)而引發(fā)樹的平衡維護(hù)。

• 不建議在小表上創(chuàng)建索引
• 一定不可存在冗余索引。

例如 同時(shí)存在  idx_A_B(A,B)  ,idx_A(A) 兩個(gè)索引

• 索引單行長度不應(yīng)該 超過200字節(jié)

按數(shù)據(jù)頁16K計(jì)算，我們期望單個(gè)索引頁至少應(yīng)該存納70個(gè)索引。默認(rèn)的innodb的頁上會(huì)留有1/16的空閑區(qū)域。這個(gè)空閑區(qū)域的主要作用是減少樹的平衡操作。

InnoDB是如何存儲(chǔ)和查詢數(shù)據(jù)的

MySQL把數(shù)據(jù)存儲(chǔ)和查詢操作抽象成了存儲(chǔ)引擎，不同的存儲(chǔ)引擎，對(duì)數(shù)據(jù)的存儲(chǔ)和讀取方式各不相同。MySQL支持多種存儲(chǔ)引擎，并且可以以表為粒度設(shè)置存儲(chǔ)引擎。因?yàn)橹С质聞?wù)，我們最常使用的是InnoDB。

• 雖然數(shù)據(jù)保存在磁盤中，但其處理是在內(nèi)存中進(jìn)行的。為了減少磁盤隨機(jī)讀取次數(shù)，InnoDB采用頁而不是行的粒度來保存數(shù)據(jù)，即數(shù)據(jù)被分成若干頁，以頁為單位保存在磁盤中。InnoDB的頁大小，一般是16KB。
• 各個(gè)數(shù)據(jù)頁組成一個(gè)雙向鏈表

每個(gè)數(shù)據(jù)頁中的記錄按照主鍵順序組成單向鏈表；每一個(gè)數(shù)據(jù)頁中有一個(gè)頁目錄，方便按照主鍵查詢記錄。

• 數(shù)據(jù)頁的結(jié)構(gòu)如下：

頁目錄通過槽把記錄分成不同的小組，每個(gè)小組有若干條記錄。如圖所示，記錄中最前面的小方塊中的數(shù)字，代表的是當(dāng)前分組的記錄條數(shù)，最小和最大的槽指向2個(gè)特殊的偽記錄。有了槽之后，我們按照主鍵搜索頁中記錄時(shí)，就可以采用二分法快速搜索，無需從最小記錄開始遍歷整個(gè)頁中的記錄鏈表。

如果要搜索主鍵（PK）=15的記錄：先二分得出槽中間位是(0+6)/2=3，看到其指向的記錄是12＜15，所以需要從#3槽后繼續(xù)搜索記錄；再使用二分搜索出#3槽和#6槽的中間位是(3+6)/2=4.5取整4，#4槽對(duì)應(yīng)的記錄是16＞15，所以記錄一定在#4槽中；再從#3槽指向的12號(hào)記錄開始向下搜索3次，定位到15號(hào)記錄。

• B+樹

  
  

• 

B+樹的特點(diǎn)包括：1.最底層的節(jié)點(diǎn)叫做葉子節(jié)點(diǎn)，用來存放數(shù)據(jù)；2.其他上層節(jié)點(diǎn)叫作非葉子節(jié)點(diǎn)，僅用來存放目錄項(xiàng)，作為索引；3.非葉子節(jié)點(diǎn)分為不同層次，通過分層來降低每一層的搜索量；4.所有節(jié)點(diǎn)按照索引鍵大小排序，構(gòu)成一個(gè)雙向鏈表，加速范圍查找。因此，InnoDB使用B+樹，既可以保存實(shí)際數(shù)據(jù)，也可以加速數(shù)據(jù)搜索，這就是聚簇索引。如果把上圖葉子節(jié)點(diǎn)下面方塊中的省略號(hào)看作實(shí)際數(shù)據(jù)的話，那么它就是聚簇索引的示意圖。由于數(shù)據(jù)在物理上只會(huì)保存一份，所以包含實(shí)際數(shù)據(jù)的聚簇索引只能有一個(gè),這也就是為什么主鍵只能有一個(gè)的原因。

• InnoDB會(huì)自動(dòng)使用主鍵

（唯一定義一條記錄的單個(gè)或多個(gè)字段）作為聚簇索引的索引鍵（如果沒有主鍵，就選擇第一個(gè)不包含NULL值的唯一列）。上圖方框中的數(shù)字代表了索引鍵的值，對(duì)聚簇索引而言一般就是主鍵。

• 我們?cè)倏纯碆+樹如何實(shí)現(xiàn)快速查找主鍵。

比如，我們要搜索PK=4的數(shù)據(jù)，通過根節(jié)點(diǎn)中的索引可以知道數(shù)據(jù)在第一個(gè)記錄指向的2號(hào)頁中，通過2號(hào)頁的索引又可以知道數(shù)據(jù)在5號(hào)頁，5號(hào)頁就是實(shí)際的數(shù)據(jù)頁，然后再通過二分法查找頁目錄馬上可以找到記錄的指針。

• 為了實(shí)現(xiàn)非主鍵字段的快速搜索，就引出了二級(jí)索引，也叫作非聚簇索引、輔助索引。

二級(jí)索引，也是利用的B+樹的數(shù)據(jù)結(jié)構(gòu)，如下圖所示：

這次二級(jí)索引的葉子節(jié)點(diǎn)中保存的不是實(shí)際數(shù)據(jù)，而是主鍵，獲得主鍵值后去聚簇索引中獲得數(shù)據(jù)行。這個(gè)過程就叫作回表。比如有個(gè)索引是針對(duì)用戶名字段創(chuàng)建的，索引記錄上面方塊中的字母是用戶名，按照順序形成鏈表。如果我們要搜索用戶名為b的數(shù)據(jù)，經(jīng)過兩次定位可以得出在#5數(shù)據(jù)頁中，查出所有的主鍵為7和6，再拿著這兩個(gè)主鍵繼續(xù)使用聚簇索引進(jìn)行兩次回表得到完整數(shù)據(jù)。

?? 總結(jié)

以上就是索引的創(chuàng)建及使用時(shí)注意事項(xiàng)，最后匯總了一些索引優(yōu)化方式，并分析InnoDB是如何存儲(chǔ)和查詢數(shù)據(jù)的。下一期將用2個(gè)真實(shí)案例分析索引在實(shí)際生產(chǎn)中的注意事項(xiàng)。

——End——