Postgres内部提供了很多种索引的方式，满足不同的索引需求。
传统索引方式（B-Tree）
说到传统，B-Tree索引当仁不让，它也是postgres里的默认索引方式。B-Tree的中文名字是二叉平衡树，每个叶子结点的深度都是一样的，特点是允许在O(logn)的时间内对所存储的内容进行搜索、顺序访问、插入及删除。
B-Tree索引对于唯一值的索引来说是相当之理想的（比如id序号这类数据），它存储的是一对对的键值和指针，指针指向被索引数据所在的heap上的位置。
这里说下什么是heap。Heap（或者叫heap文件，用来区分同名不同义的数据结构heap）存储着postgres表里的所有数据（外部表除外）。heap里边的数据是无序的，这让数据库在向里面添加数据的时候不必考虑排序的问题。
目前postgres支持的索引中，只有B-Tree索引能够提供有序的查询结果（也就是支持Order by和Limit），支持高并发场景（并行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里已经有了*/
/* 如果对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提供了表达式索引，你可以用表的一列或者多列组成的表达式，创建一个索引。
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到表上做真正的取数据操作。但如果一张表上的查询涉及多个索引呢？每个索引都这么来一次岂不是很浪费时间？
Bitmap Index Scan就能很好解决这个问题。多个索引都扫描完毕后，符合每个索引过滤条件的row/block会用同一个bitmap来记录，然后只需要用这个bitmap一次性去heap表上取出数据就好。值得一提的是，Postgres优化器会自动做出是否要使用Bitmap Index Scan的判断，不需要任何人工干预。
下图是bitmap index的示意图：
部分索引
当一个表很大的时候，为每一行都建索引是很耗存储空间的。如果常用的数据只有一小部分的话，完全可以只为这部分数据建立索引，省时省力省空间。
- 省时：当做Insert和Update操作的时候，额外开销更小！
- 省力：热数据索引扫描更快！
- 省空间：索引再也不用耗费大量磁盘了！
让我们看下怎么建立一个部分索引
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)
/* 当要查询的数据不在部分索引的范围内时，仍然使用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)
/* 当要查询的数据和部分索引一致时，索引就可以被用上了！ */
Postgres这种带条件部分的索引，在mysql里仍不支持[ref]。如果想在mysql中创建一个类似上面例子的索引，你需要依据原表创建一个辅助表，并增加3个triggers（update/insert/delete)，当对原表有满足“条件”的数据变动时，相应操作也会由trigger在辅助表上触发。然后，对辅助表创建索引。相比postgres，mysql的方式不仅耗时耗空间，对用户来说操作也非常不友好。
非传统索引方式
除了被作为默认索引的B-Tree，Postgres还以插件的方式提供了好几种“新型索引”，用于满足各式各样的应用场景。下面我们逐个认识一下。
BRIN (Block-Range Index)
名字里有个range，顾名思义，这种索引存储的是heap表内每个block中数据的最大值和最小值。
BRIN索引有什么作用和特点呢？
- 首先，如果一整个block里的数据都非常大或者非常小，不在我们查询的条件范围内，就可以将整个block排除出扫描范围。这种索引对那些分布是有序的数据非常有用，比如insert-only table的id或timestamp列。
- 其次，因为只存储最大值和最小值，BRIN带来的空间消耗极小。另外，更新数据的时候，索引带来的额外操作只有比较操作，也是相当高效的。
- BRIN对于含有多个列的索引是比较合适的选择。
但是，因为索引里存储的信息非常少，查找数据的时候消耗的时间也会很长，当查询的数据范围和一个block的范围值有重叠时，就需要对这个block进行scan，如果有重叠的block很多，其实跟全表扫描的差别也不大了。
GIN (Generalized Inverted Index)
- 尤其适用于有很多key或value的数据的索引，比如说文档、JSON、整型数组等等。
- 尤其适用于重复数据很多的场景，这点和B-Tree正好相反。
- 支持一条索引里存在多个key。而B-Tree每条索引里只能有一个key。比如新插入一条数据“foo bar”，GIN会拆分出两个key：“foo” 和 “bar”。
GIN索引内部数据结构整体上类似于B-Tree。不同的是，叶子结点上存储的不是一个TID，而是很多TID的集合，这是GIN为了存储重复数据做的优化。GIN的叶子结点的数据有三种可能：
- 当只有一个TID的时候，和B-Tree一样。
- 当有很多TID的时候，那么存储的是一个列表（posting list）。
- 当有非常非常多的TID的时候，叶子结点存储的是一个指针，这个指针指向另一棵树（Posting Tree）的根结点。而Posting Tree里面存储了所有符合这一个entry的TIDs（以page为存储单元）。
GIN树结构示意图：
GIN索引的Fast Updates特性：
GIN额外维护着一个列表，当有新的数据进入索引，不会直接进入索引树，而是会先暂存在这个列表里。当然，每个对索引的搜索也都会额外的对这个列表进行扫描。
当做vacuum操作的时候，会把这个列表里的数据插入到索引树上。不过，如果这个列表已经太大了，postgres不会傻傻等待用户进行vacuum，会果断地将它里面的内容插入GIN索引树。
但有意思的是，虽然它叫Fast Updates，但这个特性会让搜索变慢，因为每次搜索都要增加一次额外的列表扫描操作，所以很多用户会把这个特性关掉。
GIN索引的gin_fuzzy_search_limit
GIN索引适用于有大量重复关键字的全文索引，但是，当一个关键字出现次数太多时，返回结果也会很大，太大的结果集对用户是没有实际意义的，而且读取并排序这么多的数据会耗费很长时间。
GIN提供了一个配置项gin_fuzzy_search_limit来控制这种情况下返回结果集的上限。如果这个值非0，那么查询只会返回不超过设置值的一个子结果集，而且是随机的。根据经验，这个值设定为5000-20000比较好。
GIST (Generalized Search Tree)
GIST的数据结构仍然是树，但不再是B-Tree了。
支持地理坐标、range类型（比如ip范围）、hstore（key/value对）、整型数组、pg_trgm。
GIST和range
问题（见上图示意）：假设表中有一列是range类型的数据，给出一个range范围，找出表中所有和它有重叠部分的数据。
如果是B-Tree，可以按照range的最大值或最小值进行排序，但仍然避免不了每次查询都要做扫描。GIST的做法，是将范围差不多的数据聚集在一起，形成一个个的“clusters”，每个cluster的最大值和最小值都在根结点上记录，这样就可以按照每个cluster的整体范围，排除掉那些根本不可能有重叠的cluster，大大降低了扫描成本。
GIST树的结构：
索引cluster存储在page上，根结点保存了每个page内部的最小值和最大值。给出查询范围后，只需要先扫描根结点，找出所有可能有范围重叠的page，再对这些page进行相应的扫描即可。
GIST对存储的key的顺序没有严格要求，而且每个key都可以在整棵树上任何一个page上存储，只要能把根结点的相应page的最大值最小值相应更新好就ok。但是，如果使用随机存储的话，最后根结点里每个page的范围就会差不多，性能会变得非常差（几乎等同于全表扫描）。所以，如何选择对key分组的函数就至关重要。另外当一个page增长过大之后，需要用picksplit函数来对page分割，这个函数的好坏对性能也有很大影响。
GIST的用途
- GIS (geographic information system)
- 寻找bounding box的顶点
- 找到最近的n个邻居
- 全文检索
- 整型数组
一句话总结：GIST适合上层结点的范围能“包含”下层结点的类型。
SP-GIST (Space-Partitioned Generalized Search Tree)
虽然和GIST名字相似，但却是完全不同的索引类型，不是平衡树，各个叶子节点的深度可以不同。GIST各个cluster之间是可以有范围重叠的，但是SP-GIST不允许重叠。
举个例子：
这是一个网址数据索引的例子，父节点是各个子节点的共有前缀，一个完整的键值在SP-GIST的树上只存一次，每一部分分别存储在从根结点到该键值叶子节点的路径上。
另外一个常见的使用场景是索引坐标点：将空间分割成不重叠的块，每个子节点再将父节点的空间细分。但是如果是空间里的形状，就无法使用SP-GIST来索引了，因为形状可能有重叠。
索引小知识
- 你不能删除索引里的一条数据，只能通过vacuum操作将索引里无用的信息删掉。
- Index Only Scan并不理会每一条数据是否是可见的，它只会如实把找到的一切符合条件的数据信息返回，可见性的控制是上层程序需要做的事。
什么时候你应该建立索引？
当seq_scan耗时很长的时候！
Explain一下你常用的查询，如果seq_scan的cost很高，可以考虑建立索引。但是相应的，如果一个索引的idx scan很少被用到，就要考虑这个索引是不是还应该继续存在了。毕竟，维护一个索引是耗时耗空间的事情。
如何选择使用哪种索引？
当然，数据类型是第一个考虑要素。在此之外，还可以从以下几点考虑：
- 索引建立的时间
- 索引存储空间
- 数据更新时索引带来的额外开销
- 访问速度
