什么是索引所森？

數(shù)據(jù)庫表內的數(shù)據(jù)是無規(guī)則放在heap上的尖坤，所以每次進行有特定條件的查詢時稳懒，需要掃描全表找出符合條件的數(shù)據(jù)返回÷叮“索引”就是為了這種場景誕生的场梆，如果將你經(jīng)常用來做過濾條件的列建好索引墅冷，在此之上用索引查詢數(shù)據(jù)就會非常快或油。比如where name = 'John'這個條件寞忿，如果你對name建了索引，那其中就會存儲所有名字是John的數(shù)據(jù)在heap上的位置装哆，這個查詢就不需要全表掃描罐脊，可以直接拿到數(shù)據(jù)定嗓。

Postgres內部提供了很多種索引的方式蜕琴，滿足不同的索引需求。

傳統(tǒng)索引方式（B-Tree）

B-Tree

說到傳統(tǒng)宵溅，B-Tree索引當仁不讓凌简，它也是postgres里的默認索引方式。B-Tree的中文名字是二叉平衡樹恃逻，每個葉子結點的深度都是一樣的雏搂，特點是允許在O(log n)的時間內對所存儲的內容進行搜索、順序訪問寇损、插入及刪除凸郑。

B-Tree索引對于唯一值的索引來說是相當之理想的（比如id序號這類數(shù)據(jù)），它存儲的是一對對的鍵值和指針矛市，指針指向被索引數(shù)據(jù)所在的heap上的位置芙沥。

這里說下什么是heap。Heap（或者叫heap文件浊吏，用來區(qū)分同名不同義的數(shù)據(jù)結構heap）存儲著postgres表里的所有數(shù)據(jù)（外部表除外）而昨。heap里邊的數(shù)據(jù)是無序的，這讓數(shù)據(jù)庫在向里面添加數(shù)據(jù)的時候不必考慮排序的問題找田。

目前postgres支持的索引中歌憨，只有B-Tree索引能夠提供有序的查詢結果（也就是支持Order by和Limit），支持高并發(fā)場景（并行scan）墩衙，支持merge join和包含index scan的nested loop操作务嫡。

B-Tree是非常基本且古老的索引漆改，但不代表它功能單一心铃。

有時我們需要更多的功能，比如：表達式籽懦。

看下這個例子：


CREATE TABLE customer (name) AS SELECT 'cust' || i

FROM generate_series(1, 1000) AS g(i);

CREATE INDEX i_customer_name ON customer (name);

/*看一下直接對B-Tree索引列做fitler的plan*/

EXPLAIN SELECT * FROM customer WHERE name = 'cust999';


             QUERY PLAN

------------------------------------------------------

Index Only Scan using i_customer_name on customer ...

   Index Cond: (name = 'cust999'::text)

/* 沒問題于个！使用了Index！另外暮顺，Index Only Scan的意思是厅篓，所有想要的column都在index里已經(jīng)有了*/

/* 如果對B-Tree索引列在查詢時增加一個表達式操作呢秀存？*/

EXPLAIN SELECT * FROM customer WHERE lower(name) = 'cust999';

          QUERY PLAN

---------------------------------------------------------

Seq Scan on customer (cost=0.00..20.00 rows=5 width=7)

   Filter: (lower(name) = 'cust999'::text)

/* 又變回Seq Scan了！?? */

Postgres提供了表達式索引羽氮，你可以用表的一列或者多列組成的表達式泉褐，創(chuàng)建一個索引赘那。

CREATE INDEX i_customer_lower ON customer (lower(name));

EXPLAIN SELECT * FROM customer WHERE lower(name) = 'cust999';

             QUERY PLAN

---------------------------------------------------------------

Bitmap Heap Scan on customer (cost=4.32..9.66 rows=5 width=7)

   Recheck Cond: (lower(name) = 'cust999'::text)

   -> Bitmap Index Scan on i_customer_lower ...

          Index Cond: (lower(name) = 'cust999'::text)

等一下，這個Bitmap Index Scan又是什么意思？

Postgres做涉及到索引的掃描的時候议惰，會先在索引上掃描一遍，得出符合條件的row/block的list寇荧，再拿著這個list到表上做真正的取數(shù)據(jù)操作最易。但如果一張表上的查詢涉及多個索引呢？每個索引都這么來一次豈不是很浪費時間粒没？

Bitmap Index Scan就能很好解決這個問題筛婉。多個索引都掃描完畢后，符合每個索引過濾條件的row/block會用同一個bitmap來記錄癞松，然后只需要用這個bitmap一次性去heap表上取出數(shù)據(jù)就好爽撒。值得一提的是，Postgres優(yōu)化器會自動做出是否要使用Bitmap Index Scan的判斷响蓉，不需要任何人工干預硕勿。

下圖是bitmap index的示意圖：

bitmap索引

部分索引

當一個表很大的時候，為每一行都建索引是很耗存儲空間的枫甲。如果常用的數(shù)據(jù)只有一小部分的話源武，完全可以只為這部分數(shù)據(jù)建立索引，省時省力省空間言秸。

省時：當做Insert和Update操作的時候软能，額外開銷更小举畸！
省力：熱數(shù)據(jù)索引掃描更快查排！
省空間：索引再也不用耗費大量磁盤了！

讓我們看下怎么建立一個部分索引

ALTER TABLE customer ADD COLUMN state CHAR(2);

UPDATE customer SET state = 'AZ' WHERE name LIKE 'cust9__';

CREATE INDEX i_customer_state_az ON customer (state) WHERE state = 'AZ';

/* 一個WHERE語句抄沮，只對state = AZ的行進行索引 */

EXPLAIN SELECT * FROM customer WHERE state = 'PA';

               QUERY PLAN

----------------------------------------------------------

Seq Scan on customer (cost=0.00..17.50 rows=5 width=19)

   Filter: (state = 'PA'::bpchar)

/* 當要查詢的數(shù)據(jù)不在部分索引的范圍內時跋核，仍然使用Seq Scan */

EXPLAIN SELECT * FROM customer WHERE state = 'AZ';

   QUERY PLAN

----------------------------------------------------------------------------

Bitmap Heap Scan on customer (cost=4.18..9.51 rows=5 width=19)

   Recheck Cond: (state = 'AZ'::bpchar)

   -> Bitmap Index Scan on i_customer_state_az ...

   Index Cond: (state = 'AZ':bpchar)

/* 當要查詢的數(shù)據(jù)和部分索引一致時，索引就可以被用上了叛买！ */

Postgres這種帶條件部分的索引砂代，在mysql里仍不支持[ref]。如果想在mysql中創(chuàng)建一個類似上面例子的索引率挣，你需要依據(jù)原表創(chuàng)建一個輔助表刻伊，并增加3個triggers（update/insert/delete)，當對原表有滿足“條件”的數(shù)據(jù)變動時，相應操作也會由trigger在輔助表上觸發(fā)捶箱。然后智什，對輔助表創(chuàng)建索引。相比postgres丁屎，mysql的方式不僅耗時耗空間荠锭，對用戶來說操作也非常不友好。

非傳統(tǒng)索引方式

除了被作為默認索引的B-Tree晨川，Postgres還以插件的方式提供了好幾種“新型索引”证九，用于滿足各式各樣的應用場景。下面我們逐個認識一下共虑。

BRIN (Block-Range Index)

名字里有個range愧怜，顧名思義，這種索引存儲的是heap表內每個block中數(shù)據(jù)的最大值和最小值看蚜。

BRIN索引有什么作用和特點呢叫搁？

首先，如果一整個block里的數(shù)據(jù)都非常大或者非常小供炎，不在我們查詢的條件范圍內，就可以將整個block排除出掃描范圍疾党。這種索引對那些分布是有序的數(shù)據(jù)非常有用音诫，比如insert-only table的id或timestamp列。
其次雪位，因為只存儲最大值和最小值竭钝，BRIN帶來的空間消耗極小。另外雹洗，更新數(shù)據(jù)的時候香罐，索引帶來的額外操作只有比較操作，也是相當高效的时肿。
BRIN對于含有多個列的索引是比較合適的選擇庇茫。

但是，因為索引里存儲的信息非常少螃成，查找數(shù)據(jù)的時候消耗的時間也會很長旦签，當查詢的數(shù)據(jù)范圍和一個block的范圍值有重疊時，就需要對這個block進行scan寸宏，如果有重疊的block很多宁炫，其實跟全表掃描的差別也不大了。

GIN (Generalized Inverted Index)

尤其適用于有很多key或value的數(shù)據(jù)的索引氮凝，比如說文檔羔巢、JSON、整型數(shù)組等等。
尤其適用于重復數(shù)據(jù)很多的場景竿秆，這點和B-Tree正好相反炭臭。
支持一條索引里存在多個key。而B-Tree每條索引里只能有一個key袍辞。比如新插入一條數(shù)據(jù)“foo bar”鞋仍，GIN會拆分出兩個key：“foo” 和 “bar”。

GIN索引內部數(shù)據(jù)結構整體上類似于B-Tree搅吁。不同的是威创，葉子結點上存儲的不是一個TID，而是很多TID的集合谎懦，這是GIN為了存儲重復數(shù)據(jù)做的優(yōu)化肚豺。GIN的葉子結點的數(shù)據(jù)有三種可能：

當只有一個TID的時候，和B-Tree一樣界拦。
當有很多TID的時候吸申，那么存儲的是一個列表（posting list）。
當有非常非常多的TID的時候享甸，葉子結點存儲的是一個指針截碴，這個指針指向另一棵樹（Posting Tree）的根結點。而Posting Tree里面存儲了所有符合這一個entry的TIDs（以page為存儲單元）蛉威。

GIN樹結構示意圖

GIN索引的Fast Updates特性

GIN額外維護著一個列表日丹，當有新的數(shù)據(jù)進入索引，不會直接進入索引樹蚯嫌，而是會先暫存在這個列表里哲虾。當然，每個對索引的搜索也都會額外的對這個列表進行掃描择示。

當做vacuum操作的時候束凑，會把這個列表里的數(shù)據(jù)插入到索引樹上。不過栅盲，如果這個列表已經(jīng)太大了汪诉，postgres不會傻傻等待用戶進行vacuum，會果斷地將它里面的內容插入GIN索引樹剪菱。

但有意思的是摩瞎，雖然它叫Fast Updates，但這個特性會讓搜索變慢孝常，因為每次搜索都要增加一次額外的列表掃描操作旗们，所以很多用戶會把這個特性關掉。

GIN索引的gin_fuzzy_search_limit

GIN索引適用于有大量重復關鍵字的全文索引构灸，但是上渴，當一個關鍵字出現(xiàn)次數(shù)太多時岸梨，返回結果也會很大，太大的結果集對用戶是沒有實際意義的稠氮，而且讀取并排序這么多的數(shù)據(jù)會耗費很長時間曹阔。

GIN提供了一個配置項gin_fuzzy_search_limit來控制這種情況下返回結果集的上限。如果這個值非0隔披，那么查詢只會返回不超過設置值的一個子結果集赃份，而且是隨機的。根據(jù)經(jīng)驗奢米，這個值設定為5000-20000比較好抓韩。

GIST (Generalized Search Tree)

GIST的數(shù)據(jù)結構仍然是樹，但不再是B-Tree了鬓长。

支持的數(shù)據(jù)類型有地理坐標谒拴、range類型（比如ip范圍）、hstore（key/value對）涉波、整型數(shù)組英上、pg_trgm。

GIST和range

GIST與Range

問題（見上圖示意）：假設表中有一列是range類型的數(shù)據(jù)啤覆，給出一個range范圍苍日，找出表中所有和它有重疊部分的數(shù)據(jù)。

如果是B-Tree城侧，我們可以按照range的最大值或最小值進行排序易遣，但仍然避免不了每次查詢都要做掃描。GIST的做法嫌佑，是將范圍差不多的數(shù)據(jù)聚集在一起，形成一個個的“clusters”侨歉，每個cluster的最大值和最小值都在根結點上記錄屋摇，這樣就可以按照每個cluster的整體范圍，排除掉那些根本不可能有重疊的cluster幽邓，大大降低了掃描成本炮温。

GIST樹的結構

索引cluster存儲在page上，根結點保存了每個page內部的最小值和最大值牵舵。給出查詢范圍后柒啤，只需要先掃描根結點，找出所有可能有范圍重疊的page畸颅，再對這些page進行相應的掃描即可担巩。

GIST對存儲的key的順序沒有嚴格要求，而且每個key都可以在整棵樹上任何一個page上存儲没炒，只要能把根結點的相應page的最大值最小值相應更新好就ok涛癌。但是，如果使用隨機存儲的話，最后根結點里每個page的范圍就會差不多拳话，性能會變得非常差（幾乎等同于全表掃描）先匪。所以，如何選擇對key分組的函數(shù)就至關重要弃衍。另外當一個page增長過大之后呀非，需要用picksplit函數(shù)來對page分割，這個函數(shù)的好壞對性能也有很大影響镜盯。

GIST的用途

GIS (geographic information system)
尋找bounding box的頂點
找到最近的n個鄰居
全文檢索
整型數(shù)組

一言蔽之：GIST適合上層結點的范圍能“包含”下層結點的類型岸裙。

SP-GIST (Space-Partitioned Generalized Search Tree)

雖然和GIST名字相似，但卻是完全不同的索引類型形耗，不是平衡樹哥桥，各個葉子節(jié)點的深度可以不同。GIST各個cluster之間是可以有范圍重疊的激涤，但是SP-GIST不允許重疊拟糕。

舉個例子：

GIST示例

這是一個網(wǎng)址數(shù)據(jù)索引的例子，父節(jié)點是各個子節(jié)點的共有前綴倦踢，一個完整的鍵值在SP-GIST的樹上只存一次送滞，每一部分分別存儲在從根結點到該鍵值葉子節(jié)點的路徑上。

另外一個常見的使用場景是索引坐標點：將空間分割成不重疊的塊辱挥，每個子節(jié)點再將父節(jié)點的空間細分犁嗅。但如果是空間里的形狀，就無法使用SP-GIST來索引了晤碘，因為形狀可能有重疊褂微。

索引小知識

你不能刪除索引里的一條數(shù)據(jù)，只能通過vacuum操作將索引里無用的信息刪掉园爷。
Index Only Scan并不理會每一條數(shù)據(jù)是否是可見的宠蚂，它只會如實把找到的一切符合條件的數(shù)據(jù)信息返回，可見性的控制是上層程序需要做的事童社。

什么時候你應該建立索引求厕？

首先，當seq_scan耗時很長的時候扰楼！

Explain一下你常用的查詢呀癣，如果seq_scan的cost很高，可以考慮建立索引弦赖。但是相應的项栏，如果一個索引的idx scan很少被用到，就要考慮這個索引是不是還應該繼續(xù)存在了腾节。畢竟忘嫉，維護一個索引是耗時耗空間的事情荤牍。

如何選擇使用哪種索引？

當然庆冕，數(shù)據(jù)類型是第一個考慮要素康吵。在此之外，還可以從以下幾點考慮：

索引建立的時間
索引存儲空間
數(shù)據(jù)更新時索引帶來的額外開銷
訪問速度

Postgres Index二三事