什么是索引？

數(shù)據(jù)庫(kù)表內(nèi)的數(shù)據(jù)是無(wú)規(guī)則放在heap上的，所以每次進(jìn)行有特定條件的查詢時(shí)，需要掃描全表找出符合條件的數(shù)據(jù)返回。“索引”就是為了這種場(chǎng)景誕生的，如果將你經(jīng)常用來(lái)做過(guò)濾條件的列建好索引，在此之上用索引查詢數(shù)據(jù)就會(huì)非?？?。比如where name = 'John'這個(gè)條件，如果你對(duì)name建了索引，那其中就會(huì)存儲(chǔ)所有名字是John的數(shù)據(jù)在heap上的位置，這個(gè)查詢就不需要全表掃描，可以直接拿到數(shù)據(jù)。

Postgres內(nèi)部提供了很多種索引的方式，滿足不同的索引需求。

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

B-Tree

說(shuō)到傳統(tǒng)，B-Tree索引當(dāng)仁不讓，它也是postgres里的默認(rèn)索引方式。B-Tree的中文名字是二叉平衡樹(shù)，每個(gè)葉子結(jié)點(diǎn)的深度都是一樣的，特點(diǎn)是允許在O(log n)的時(shí)間內(nèi)對(duì)所存儲(chǔ)的內(nèi)容進(jìn)行搜索、順序訪問(wèn)、插入及刪除。

B-Tree索引對(duì)于唯一值的索引來(lái)說(shuō)是相當(dāng)之理想的（比如id序號(hào)這類數(shù)據(jù)），它存儲(chǔ)的是一對(duì)對(duì)的鍵值和指針，指針指向被索引數(shù)據(jù)所在的heap上的位置。

這里說(shuō)下什么是heap。Heap（或者叫heap文件，用來(lái)區(qū)分同名不同義的數(shù)據(jù)結(jié)構(gòu)heap）存儲(chǔ)著postgres表里的所有數(shù)據(jù)（外部表除外）。heap里邊的數(shù)據(jù)是無(wú)序的，這讓數(shù)據(jù)庫(kù)在向里面添加數(shù)據(jù)的時(shí)候不必考慮排序的問(wèn)題。

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

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

有時(shí)我們需要更多的功能，比如：表達(dá)式。

看下這個(gè)例子：

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

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

CREATE INDEX i_customer_name ON customer (name);

/*看一下直接對(duì)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)

/* 沒(méi)問(wèn)題！使用了Index！另外，Index Only Scan的意思是，所有想要的column都在index里已經(jīng)有了*/

/* 如果對(duì)B-Tree索引列在查詢時(shí)增加一個(gè)表達(dá)式操作呢？*/

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提供了表達(dá)式索引，你可以用表的一列或者多列組成的表達(dá)式，創(chuàng)建一個(gè)索引。

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)

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

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

Bitmap Index Scan就能很好解決這個(gè)問(wèn)題。多個(gè)索引都掃描完畢后，符合每個(gè)索引過(guò)濾條件的row/block會(huì)用同一個(gè)bitmap來(lái)記錄，然后只需要用這個(gè)bitmap一次性去heap表上取出數(shù)據(jù)就好。值得一提的是，Postgres優(yōu)化器會(huì)自動(dòng)做出是否要使用Bitmap Index Scan的判斷，不需要任何人工干預(yù)。

下圖是bitmap index的示意圖：

bitmap索引

部分索引

當(dāng)一個(gè)表很大的時(shí)候，為每一行都建索引是很耗存儲(chǔ)空間的。如果常用的數(shù)據(jù)只有一小部分的話，完全可以只為這部分?jǐn)?shù)據(jù)建立索引，省時(shí)省力省空間。

• 省時(shí)：當(dāng)做Insert和Update操作的時(shí)候，額外開(kāi)銷更??！
• 省力：熱數(shù)據(jù)索引掃描更快！
• 省空間：索引再也不用耗費(fèi)大量磁盤了！

讓我們看下怎么建立一個(gè)部分索引

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';

/* 一個(gè)WHERE語(yǔ)句，只對(duì)state = AZ的行進(jìn)行索引 */

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)

/* 當(dāng)要查詢的數(shù)據(jù)不在部分索引的范圍內(nèi)時(shí)，仍然使用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)

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

Postgres這種帶條件部分的索引，在mysql里仍不支持[ref]。如果想在mysql中創(chuàng)建一個(gè)類似上面例子的索引，你需要依據(jù)原表創(chuàng)建一個(gè)輔助表，并增加3個(gè)triggers（update/insert/delete)，當(dāng)對(duì)原表有滿足“條件”的數(shù)據(jù)變動(dòng)時(shí)，相應(yīng)操作也會(huì)由trigger在輔助表上觸發(fā)。然后，對(duì)輔助表創(chuàng)建索引。相比postgres，mysql的方式不僅耗時(shí)耗空間，對(duì)用戶來(lái)說(shuō)操作也非常不友好。

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

除了被作為默認(rèn)索引的B-Tree，Postgres還以插件的方式提供了好幾種“新型索引”，用于滿足各式各樣的應(yīng)用場(chǎng)景。下面我們逐個(gè)認(rèn)識(shí)一下。

BRIN (Block-Range Index)

名字里有個(gè)range，顧名思義，這種索引存儲(chǔ)的是heap表內(nèi)每個(gè)block中數(shù)據(jù)的最大值和最小值。

BRIN索引有什么作用和特點(diǎn)呢？

• 首先，如果一整個(gè)block里的數(shù)據(jù)都非常大或者非常小，不在我們查詢的條件范圍內(nèi)，就可以將整個(gè)block排除出掃描范圍。這種索引對(duì)那些分布是有序的數(shù)據(jù)非常有用，比如insert-only table的id或timestamp列。
• 其次，因?yàn)橹淮鎯?chǔ)最大值和最小值，BRIN帶來(lái)的空間消耗極小。另外，更新數(shù)據(jù)的時(shí)候，索引帶來(lái)的額外操作只有比較操作，也是相當(dāng)高效的。
• BRIN對(duì)于含有多個(gè)列的索引是比較合適的選擇。

但是，因?yàn)樗饕锎鎯?chǔ)的信息非常少，查找數(shù)據(jù)的時(shí)候消耗的時(shí)間也會(huì)很長(zhǎng)，當(dāng)查詢的數(shù)據(jù)范圍和一個(gè)block的范圍值有重疊時(shí)，就需要對(duì)這個(gè)block進(jìn)行scan，如果有重疊的block很多，其實(shí)跟全表掃描的差別也不大了。

GIN (Generalized Inverted Index)

• 尤其適用于有很多key或value的數(shù)據(jù)的索引，比如說(shuō)文檔、JSON、整型數(shù)組等等。
• 尤其適用于重復(fù)數(shù)據(jù)很多的場(chǎng)景，這點(diǎn)和B-Tree正好相反。
• 支持一條索引里存在多個(gè)key。而B(niǎo)-Tree每條索引里只能有一個(gè)key。比如新插入一條數(shù)據(jù)“foo bar”，GIN會(huì)拆分出兩個(gè)key：“foo” 和 “bar”。

GIN索引內(nèi)部數(shù)據(jù)結(jié)構(gòu)整體上類似于B-Tree。不同的是，葉子結(jié)點(diǎn)上存儲(chǔ)的不是一個(gè)TID，而是很多TID的集合，這是GIN為了存儲(chǔ)重復(fù)數(shù)據(jù)做的優(yōu)化。GIN的葉子結(jié)點(diǎn)的數(shù)據(jù)有三種可能：

1. 當(dāng)只有一個(gè)TID的時(shí)候，和B-Tree一樣。
2. 當(dāng)有很多TID的時(shí)候，那么存儲(chǔ)的是一個(gè)列表（posting list）。
3. 當(dāng)有非常非常多的TID的時(shí)候，葉子結(jié)點(diǎn)存儲(chǔ)的是一個(gè)指針，這個(gè)指針指向另一棵樹(shù)（Posting Tree）的根結(jié)點(diǎn)。而Posting Tree里面存儲(chǔ)了所有符合這一個(gè)entry的TIDs（以page為存儲(chǔ)單元）。

GIN樹(shù)結(jié)構(gòu)示意圖

GIN索引的Fast Updates特性

GIN額外維護(hù)著一個(gè)列表，當(dāng)有新的數(shù)據(jù)進(jìn)入索引，不會(huì)直接進(jìn)入索引樹(shù)，而是會(huì)先暫存在這個(gè)列表里。當(dāng)然，每個(gè)對(duì)索引的搜索也都會(huì)額外的對(duì)這個(gè)列表進(jìn)行掃描。

當(dāng)做vacuum操作的時(shí)候，會(huì)把這個(gè)列表里的數(shù)據(jù)插入到索引樹(shù)上。不過(guò)，如果這個(gè)列表已經(jīng)太大了，postgres不會(huì)傻傻等待用戶進(jìn)行vacuum，會(huì)果斷地將它里面的內(nèi)容插入GIN索引樹(shù)。

但有意思的是，雖然它叫Fast Updates，但這個(gè)特性會(huì)讓搜索變慢，因?yàn)槊看嗡阉鞫家黾右淮晤~外的列表掃描操作，所以很多用戶會(huì)把這個(gè)特性關(guān)掉。

GIN索引的gin_fuzzy_search_limit

GIN索引適用于有大量重復(fù)關(guān)鍵字的全文索引，但是，當(dāng)一個(gè)關(guān)鍵字出現(xiàn)次數(shù)太多時(shí)，返回結(jié)果也會(huì)很大，太大的結(jié)果集對(duì)用戶是沒(méi)有實(shí)際意義的，而且讀取并排序這么多的數(shù)據(jù)會(huì)耗費(fèi)很長(zhǎng)時(shí)間。

GIN提供了一個(gè)配置項(xiàng)gin_fuzzy_search_limit來(lái)控制這種情況下返回結(jié)果集的上限。如果這個(gè)值非0，那么查詢只會(huì)返回不超過(guò)設(shè)置值的一個(gè)子結(jié)果集，而且是隨機(jī)的。根據(jù)經(jīng)驗(yàn)，這個(gè)值設(shè)定為5000-20000比較好。

GIST (Generalized Search Tree)

GIST的數(shù)據(jù)結(jié)構(gòu)仍然是樹(shù)，但不再是B-Tree了。

支持的數(shù)據(jù)類型有地理坐標(biāo)、range類型（比如ip范圍）、hstore（key/value對(duì)）、整型數(shù)組、pg_trgm。

GIST和range

GIST與Range

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

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

GIST樹(shù)的結(jié)構(gòu)

索引cluster存儲(chǔ)在page上，根結(jié)點(diǎn)保存了每個(gè)page內(nèi)部的最小值和最大值。給出查詢范圍后，只需要先掃描根結(jié)點(diǎn)，找出所有可能有范圍重疊的page，再對(duì)這些page進(jìn)行相應(yīng)的掃描即可。

GIST對(duì)存儲(chǔ)的key的順序沒(méi)有嚴(yán)格要求，而且每個(gè)key都可以在整棵樹(shù)上任何一個(gè)page上存儲(chǔ)，只要能把根結(jié)點(diǎn)的相應(yīng)page的最大值最小值相應(yīng)更新好就ok。但是，如果使用隨機(jī)存儲(chǔ)的話，最后根結(jié)點(diǎn)里每個(gè)page的范圍就會(huì)差不多，性能會(huì)變得非常差（幾乎等同于全表掃描）。所以，如何選擇對(duì)key分組的函數(shù)就至關(guān)重要。另外當(dāng)一個(gè)page增長(zhǎng)過(guò)大之后，需要用picksplit函數(shù)來(lái)對(duì)page分割，這個(gè)函數(shù)的好壞對(duì)性能也有很大影響。

GIST的用途

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

一言蔽之：GIST適合上層結(jié)點(diǎn)的范圍能“包含”下層結(jié)點(diǎn)的類型。

SP-GIST (Space-Partitioned Generalized Search Tree)

雖然和GIST名字相似，但卻是完全不同的索引類型，不是平衡樹(shù)，各個(gè)葉子節(jié)點(diǎn)的深度可以不同。GIST各個(gè)cluster之間是可以有范圍重疊的，但是SP-GIST不允許重疊。

舉個(gè)例子：

GIST示例

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

另外一個(gè)常見(jiàn)的使用場(chǎng)景是索引坐標(biāo)點(diǎn)：將空間分割成不重疊的塊，每個(gè)子節(jié)點(diǎn)再將父節(jié)點(diǎn)的空間細(xì)分。但如果是空間里的形狀，就無(wú)法使用SP-GIST來(lái)索引了，因?yàn)樾螤羁赡苡兄丿B。

索引小知識(shí)

• 你不能刪除索引里的一條數(shù)據(jù)，只能通過(guò)vacuum操作將索引里無(wú)用的信息刪掉。
• Index Only Scan并不理會(huì)每一條數(shù)據(jù)是否是可見(jiàn)的，它只會(huì)如實(shí)把找到的一切符合條件的數(shù)據(jù)信息返回，可見(jiàn)性的控制是上層程序需要做的事。

什么時(shí)候你應(yīng)該建立索引？

首先，當(dāng)seq_scan耗時(shí)很長(zhǎng)的時(shí)候！

Explain一下你常用的查詢，如果seq_scan的cost很高，可以考慮建立索引。但是相應(yīng)的，如果一個(gè)索引的idx scan很少被用到，就要考慮這個(gè)索引是不是還應(yīng)該繼續(xù)存在了。畢竟，維護(hù)一個(gè)索引是耗時(shí)耗空間的事情。

如何選擇使用哪種索引？

當(dāng)然，數(shù)據(jù)類型是第一個(gè)考慮要素。在此之外，還可以從以下幾點(diǎn)考慮：

• 索引建立的時(shí)間
• 索引存儲(chǔ)空間
• 數(shù)據(jù)更新時(shí)索引帶來(lái)的額外開(kāi)銷
• 訪問(wèn)速度