IndexType： GIN

前言

今天要來介紹 GIN index，
我們先重新回想一下我們小時候查字典時是如何查詢的。

上圖是使用注音來做查詢，步驟可以會如下

1. 查找到想要招的注音
2. 在該注音後面會有我們想要查找的字
   像是我想要找一級棒的棒字，我們大概會這樣找
3. 掀翻到ㄅ這個注音下找ㄅㄤ，然後在往下找生符找到ㄅㄤˋ，這是一系列的注音查找
4. 在ㄅㄤˋ下面就會記錄一堆相同音的國字。
   而聰明的工程師們就利用這個動作發展出了GIN index。

GIN 資料結構

GIN index，他也是B+Tree的變形，
我們知道B+Tree的leaf node就是我們要尋找的數值。
而GIN在leaf node部分仍是相同的，但他又在leaf node上再加上一顆B+Tree，
這leaf node的B+Tree就是我們可以拿來做搜尋優化的地方。
所個結構大致上可以分層兩層
Layer1: 第一層Key的搜尋，我們通常稱為entry tree
Layer2: 與該Layer1 Key相關的搜尋，我們稱為posting tree
間單來說可以說GIN是兩個層B+Tree的結合

可以看到這張圖，layer1是拿來做搜尋單字，layer2是拿來紀錄該單字會出現在那些位置上
剛好可以對應上我們查字典一樣的效果
entry tree:拿來查注音。
posting tree:拿來查國字。
相同的原理，我們可以利用這個GIN結構來做無限的推廣。

GIN使用場景

1. 任何需要兩層式搜尋的情境
2. 搜尋陣列、jsonb 和 tsvector等非單一數值的結構

實際使用

加上Index

使用GIN index要先加入EXTENSION
CREATE EXTENSION IF NOT EXISTS pg_trgm;
加上index
CREATE INDEX gin_xxx ON TABLE_A USING gin (colA gin_trgm_ops);

結語

這篇先講解GIN結構與原理，
其實這個結構也是非常簡單，
但在應用在可以說是幫了很大的忙，因為它結合了兩個B+Tree。

下一篇我將介紹FullTextSearch這個應用，來好好的利用GIN這個結構。
並且模擬沒有GIN時可能會如何處理，
經過GIN的幫忙節省了許多麻煩，
來更細細的品味GIN帶來的美妙滋味。

參考資料

1. PostgreSQL's indexes - GIN
2. Understanding Postgres GIN Indexes: The Good and the Bad
3. PostgreSQL GIN 索引實戰（一）
4. Indexes in PostgreSQL — 7 (GIN)