結(jié)構(gòu)
B-tree索引適合用于存儲(chǔ)排序的數(shù)據(jù)橙喘。對(duì)于這種數(shù)據(jù)類型需要定義大于粤咪、大于等于、小于渴杆、小于等于操作符寥枝。
通常情況下，B-tree的索引記錄存儲(chǔ)在數(shù)據(jù)頁(yè)中磁奖。葉子頁(yè)中的記錄包含索引數(shù)據(jù)（keys）以及指向heap tuple記錄（即表的行記錄TIDs）的指針囊拜。內(nèi)部頁(yè)中的記錄包含指向索引子頁(yè)的指針和子頁(yè)中最小值。
B-tree有幾點(diǎn)重要的特性：
1比搭、B-tree是平衡樹(shù)冠跷，即每個(gè)葉子頁(yè)到root頁(yè)中間有相同個(gè)數(shù)的內(nèi)部頁(yè)。因此查詢?nèi)魏我粋€(gè)值的時(shí)間是相同的。
2蜜托、B-tree中一個(gè)節(jié)點(diǎn)有多個(gè)分支抄囚，即每頁(yè)（通常8KB）具有許多TIDs。因此B-tree的高度比較低橄务，通常4到5層就可以存儲(chǔ)大量行記錄幔托。
3、索引中的數(shù)據(jù)以非遞減的順序存儲(chǔ)（頁(yè)之間以及頁(yè)內(nèi)都是這種順序）蜂挪，同級(jí)的數(shù)據(jù)頁(yè)由雙向鏈表連接重挑。因此不需要每次都返回root，通過(guò)遍歷鏈表就可以獲取一個(gè)有序的數(shù)據(jù)集棠涮。
下面是一個(gè)索引的簡(jiǎn)單例子谬哀，該索引存儲(chǔ)的記錄為整型并只有一個(gè)字段：
該索引最頂層的頁(yè)是元數(shù)據(jù)頁(yè)，該數(shù)據(jù)頁(yè)存儲(chǔ)索引root頁(yè)的相關(guān)信息严肪。內(nèi)部節(jié)點(diǎn)位于root下面史煎，葉子頁(yè)位于最下面一層。向下的箭頭表示由葉子節(jié)點(diǎn)指向表記錄（TIDs）驳糯。
例如通過(guò)"indexed-field?=?expression"形式的條件查詢49這個(gè)值篇梭。
root節(jié)點(diǎn)有三個(gè)記錄：(4,32,64)。從root節(jié)點(diǎn)開(kāi)始進(jìn)行搜索结窘，由于32≤ 49 < 64很洋，所以選擇32這個(gè)值進(jìn)入其子節(jié)點(diǎn)。通過(guò)同樣的方法繼續(xù)向下進(jìn)行搜索一直到葉子節(jié)點(diǎn)隧枫，最后查詢到49這個(gè)值喉磁。
實(shí)際上，查詢算法遠(yuǎn)不止看上去的這么簡(jiǎn)單官脓。比如协怒，該索引是非唯一索引時(shí)，允許存在許多相同值的記錄卑笨，并且這些相同的記錄不止存放在一個(gè)頁(yè)中孕暇。此時(shí)該如何查詢？我們返回到上面的的例子赤兴，定位到第二層節(jié)點(diǎn)(32,43,49)妖滔。如果選擇49這個(gè)值并向下進(jìn)入其子節(jié)點(diǎn)搜索，就會(huì)跳過(guò)前一個(gè)葉子頁(yè)中的49這個(gè)值桶良。因此座舍，在內(nèi)部節(jié)點(diǎn)進(jìn)行等值查詢49時(shí)，定位到49這個(gè)值陨帆，然后選擇49的前一個(gè)值43曲秉，向下進(jìn)入其子節(jié)點(diǎn)進(jìn)行搜索采蚀。最后，在底層節(jié)點(diǎn)中從左到右進(jìn)行搜索承二。
(另外一個(gè)復(fù)雜的地方是榆鼠，查詢的過(guò)程中樹(shù)結(jié)構(gòu)可能會(huì)改變，比如分裂)
通過(guò)"indexed-field ≤ expression" (or "indexed-field ≥ expression")查詢時(shí)亥鸠，首先通過(guò)"indexed-field?=?expression"形式進(jìn)行等值（如果存在該值）查詢妆够，定位到葉子節(jié)點(diǎn)后，再向左或向右進(jìn)行遍歷檢索读虏。
下圖是查詢 n ≤ 35的示意圖：
大于和小于可以通過(guò)同樣的方法進(jìn)行查詢责静。查詢時(shí)需要排除等值查詢出的值袁滥。
?范圍查詢"expression1 ≤ indexed-field ≤ expression2"時(shí)盖桥，需要通過(guò) "expression1 ≤ indexed-field =expression2"找到一匹配值，然后在葉子節(jié)點(diǎn)從左到右進(jìn)行檢索题翻，一直到不滿足"indexed-field ≤ expression2" 的條件為止揩徊；或者反過(guò)來(lái)，首先通過(guò)第二個(gè)表達(dá)式進(jìn)行檢索嵌赠，在葉子節(jié)點(diǎn)定位到該值后塑荒，再?gòu)挠蚁蜃筮M(jìn)行檢索，一直到不滿足第一個(gè)表達(dá)式的條件為止姜挺。
下圖是23 ≤ n ≤ 64的查詢示意圖:
下面是一個(gè)查詢計(jì)劃的實(shí)例齿税。通過(guò)demo database中的aircraft表進(jìn)行介紹。該表有9行數(shù)據(jù)炊豪，由于整個(gè)表只有一個(gè)數(shù)據(jù)頁(yè)凌箕，所以執(zhí)行計(jì)劃不會(huì)使用索引。為了解釋說(shuō)明問(wèn)題词渤，我們使用整個(gè)表進(jìn)行說(shuō)明牵舱。
demo=#select*fromaircrafts;
?aircraft_code | ???????model ???????| range
---------------+---------------------+-------
?773 ??????????| Boeing 777-300 ?????| 11100
?763 ??????????| Boeing 767-300 ?????| ?7900
?SU9 ??????????| Sukhoi SuperJet-100 | ?3000
?320 ??????????| Airbus A320-200 ????| ?5700
?321 ??????????| Airbus A321-200 ????| ?5600
?319 ??????????| Airbus A319-100 ????| ?6700
?733 ??????????| Boeing 737-300 ?????| ?4200
?CN1 ??????????| Cessna 208 Caravan ?| ?1200
?CR2 ??????????| Bombardier CRJ-200 ?| ?2700
(9 rows)
demo=#createindexonaircrafts(range);
demo=#setenable_seqscan =off;
（更準(zhǔn)確的方式：create index on aircrafts using btree(range)，創(chuàng)建索引時(shí)默認(rèn)構(gòu)建B-tree索引缺虐。）
等值查詢的執(zhí)行計(jì)劃：
demo=#explain(costsoff)select*fromaircraftswhererange=3000;
????????????????????QUERY PLAN ????????????????????
---------------------------------------------------
?Index Scan using aircrafts_range_idx on aircrafts
???Index Cond: (range = 3000)
(2 rows)
非等值查詢的執(zhí)行計(jì)劃：
demo=#explain(costsoff)select*fromaircraftswhererange<3000;
????????????????????QUERY PLAN ???????????????????
---------------------------------------------------
?Index Scan using aircrafts_range_idx on aircrafts
???Index Cond: (range < 3000)
(2 rows)
范圍查詢的執(zhí)行計(jì)劃：
demo=#explain(costsoff)select*fromaircrafts
whererangebetween3000and5000;
?????????????????????QUERY PLAN ?????????????????????
-----------------------------------------------------
?Index Scan using aircrafts_range_idx on aircrafts
???Index Cond: ((range >= 3000) AND (range <= 5000))
(2 rows)
再次強(qiáng)調(diào)芜壁，通過(guò)index、index-only或bitmap掃描高氮，btree訪問(wèn)方法可以返回有序的數(shù)據(jù)慧妄。因此如果表的排序條件上有索引，優(yōu)化器會(huì)考慮以下方式：表的索引掃描剪芍；表的順序掃描然后對(duì)結(jié)果集進(jìn)行排序塞淹。
當(dāng)創(chuàng)建索引時(shí)可以明確指定排序順序。如下所示紊浩，在range列上建立一個(gè)索引窖铡，并且排序順序?yàn)榻敌颍?/p>
demo=#createindexonaircrafts(rangedesc);
本案例中疗锐，大值會(huì)出現(xiàn)在樹(shù)的左邊，小值出現(xiàn)在右邊费彼。為什么有這樣的需求滑臊？這樣做是為了多列索引。創(chuàng)建aircraft的一個(gè)視圖箍铲，通過(guò)range分成3部分：
demo=#createviewaircrafts_vas
selectmodel,
case
whenrange<4000then1
whenrange<10000then2
else3
endasclass
fromaircrafts;
demo=#select*fromaircrafts_v;
????????model ???????| class
---------------------+-------
?Boeing 777-300 ?????| ????3
?Boeing 767-300 ?????| ????2
?Sukhoi SuperJet-100 | ????1
?Airbus A320-200 ????| ????2
?Airbus A321-200 ????| ????2
?Airbus A319-100 ????| ????2
?Boeing 737-300 ?????| ????2
?Cessna 208 Caravan ?| ????1
?Bombardier CRJ-200 ?| ????1
(9 rows)
然后創(chuàng)建一個(gè)索引（使用下面表達(dá)式）：
demo=#createindexonaircrafts(
(casewhenrange<4000then1whenrange<10000then2else3end),
model);
現(xiàn)在雇卷，可以通過(guò)索引以升序的方式獲取排序的數(shù)據(jù)：
demo=#selectclass,modelfromaircrafts_vorderbyclass,model;
?class | ???????model ???????
-------+---------------------
?????1 | Bombardier CRJ-200
?????1 | Cessna 208 Caravan
?????1 | Sukhoi SuperJet-100
?????2 | Airbus A319-100
?????2 | Airbus A320-200
?????2 | Airbus A321-200
?????2 | Boeing 737-300
?????2 | Boeing 767-300
?????3 | Boeing 777-300
(9 rows)
demo=#explain(costsoff)
selectclass,modelfromaircrafts_vorderbyclass,model;
???????????????????????QUERY PLAN ??????????????????????
--------------------------------------------------------
?Index Scan using aircrafts_case_model_idx on aircrafts
(1 row)
同樣，可以以降序的方式獲取排序的數(shù)據(jù)：
demo=#selectclass,modelfromaircrafts_vorderbyclassdesc,modeldesc;
?class | ???????model ???????
-------+---------------------
?????3 | Boeing 777-300
?????2 | Boeing 767-300
?????2 | Boeing 737-300
?????2 | Airbus A321-200
?????2 | Airbus A320-200
?????2 | Airbus A319-100
?????1 | Sukhoi SuperJet-100
?????1 | Cessna 208 Caravan
?????1 | Bombardier CRJ-200
(9 rows)
demo=#explain(costsoff)
selectclass,modelfromaircrafts_vorderbyclassdesc,modeldesc;
???????????????????????????QUERY PLAN ???????????????????????????
-----------------------------------------------------------------
?Index Scan BACKWARD using aircrafts_case_model_idx on aircrafts
(1 row)
然而颠猴，如果一列以升序一列以降序的方式獲取排序的數(shù)據(jù)的話关划，就不能使用索引，只能單獨(dú)排序：
demo=#explain(costsoff)
selectclass,modelfromaircrafts_vorderbyclassASC,modelDESC;
???????????????????QUERY PLAN ???????????????????
-------------------------------------------------
?Sort
Sort Key: (CASE ...END), aircrafts.modelDESC
-> ?SeqScanonaircrafts
(3rows)
（注意翘瓮，最終執(zhí)行計(jì)劃會(huì)選擇順序掃描贮折，忽略之前設(shè)置的enable_seqscan = off。因?yàn)檫@個(gè)設(shè)置并不會(huì)放棄表掃描资盅，只是設(shè)置他的成本----查看costs on的執(zhí)行計(jì)劃）
若有使用索引调榄，創(chuàng)建索引時(shí)指定排序的方向：
demo=#createindexaircrafts_case_asc_model_desc_idxonaircrafts(
(case
whenrange<4000then1
whenrange<10000then2
else3
end)ASC,
modelDESC);
demo=#explain(costsoff)
selectclass,modelfromaircrafts_vorderbyclassASC,modelDESC;
???????????????????????????QUERY PLAN ???????????????????????????
-----------------------------------------------------------------
?Index Scan using aircrafts_case_asc_model_desc_idx on aircrafts
(1 row)
當(dāng)使用多列索引時(shí)與列的順序有關(guān)的問(wèn)題會(huì)顯示出來(lái)。對(duì)于B-tree呵扛，這個(gè)順序非常重要：頁(yè)中的數(shù)據(jù)先以第一個(gè)字段進(jìn)行排序每庆，然后再第二個(gè)字段，以此類推今穿。
下圖是在range和model列上構(gòu)建的索引：
當(dāng)然缤灵，上圖這么小的索引在一個(gè)root頁(yè)足以存放。但是為了清晰起見(jiàn)蓝晒，特意將其分成幾頁(yè)腮出。
從圖中可見(jiàn)，通過(guò)類似的謂詞class = 3（僅按第一個(gè)字段進(jìn)行搜索）或者class = 3 and model = 'Boeing 777-300'（按兩個(gè)字段進(jìn)行搜索）將非常高效拔创。
然而利诺，通過(guò)謂詞model = 'Boeing 777-300'進(jìn)行搜索的效率將大大降低：從root開(kāi)始，判斷不出選擇哪個(gè)子節(jié)點(diǎn)進(jìn)行向下搜索剩燥，因此會(huì)遍歷所有子節(jié)點(diǎn)向下進(jìn)行搜索慢逾。這并不意味著永遠(yuǎn)無(wú)法使用這樣的索引----它的效率有問(wèn)題。例如灭红，如果aircraft有3個(gè)classes值侣滩，每個(gè)class類中有許多model值，此時(shí)不得不掃描索引1/3的數(shù)據(jù)变擒，這可能比全表掃描更有效君珠。
但是，當(dāng)創(chuàng)建如下索引時(shí)：
demo=#createindexonaircrafts(
model,
(casewhenrange<4000then1whenrange<10000then2else3end));
索引字段的順序會(huì)改變：
通過(guò)這個(gè)索引娇斑，model = 'Boeing 777-300'將會(huì)很有效策添，但class = 3則沒(méi)這么高效材部。
PostgreSQL的B-tree支持在NULLs上創(chuàng)建索引，可以通過(guò)IS NULL或者IS NOT NULL的條件進(jìn)行查詢唯竹。
考慮flights表乐导，允許NULLs：
demo=#createindexonflights(actual_arrival);
demo=#explain(costsoff)select*fromflightswhereactual_arrivalisnull;
??????????????????????QUERY PLAN ??????????????????????
-------------------------------------------------------
?Bitmap Heap Scan on flights
???Recheck Cond: (actual_arrival IS NULL)
???-> ?Bitmap Index Scan on flights_actual_arrival_idx
?????????Index Cond: (actual_arrival IS NULL)
(4 rows)
NULLs位于葉子節(jié)點(diǎn)的一端或另一端，這依賴于索引的創(chuàng)建方式（NULLS FIRST或NULLS LAST）浸颓。如果查詢中包含排序物臂，這就顯得很重要了：如果SELECT語(yǔ)句在ORDER BY子句中指定NULLs的順序索引構(gòu)建的順序一樣（NULLS FIRST或NULLS LAST），就可以使用整個(gè)索引产上。
下面的例子中棵磷，他們的順序相同，因此可以使用索引：
demo=#explain(costsoff)
select*fromflightsorderbyactual_arrivalNULLSLAST;
???????????????????????QUERY PLAN ?????????????????????
--------------------------------------------------------
?Index Scan using flights_actual_arrival_idx on flights
(1 row)
下面的例子晋涣，順序不同仪媒，優(yōu)化器選擇順序掃描然后進(jìn)行排序：
demo=#explain(costsoff)
select*fromflightsorderbyactual_arrivalNULLSFIRST;
???????????????QUERY PLAN ?????????????
----------------------------------------
?Sort
???Sort Key: actual_arrival NULLS FIRST
???-> ?Seq Scan on flights
(3 rows)
NULLs必須位于開(kāi)頭才能使用索引：
demo=#createindexflights_nulls_first_idxonflights(actual_arrivalNULLSFIRST);
demo=#explain(costsoff)
select*fromflightsorderbyactual_arrivalNULLSFIRST;
?????????????????????QUERY PLAN ?????????????????????
-----------------------------------------------------
?Index Scan using flights_nulls_first_idx on flights
(1 row)
像這樣的問(wèn)題是由NULLs引起的而不是無(wú)法排序，也就是說(shuō)NULL和其他這比較的結(jié)果無(wú)法預(yù)知：
demo=# \pset null NULL
demo=#selectnull<42;
??column?
----------
?NULL
(1 row)
這和B-tree的概念背道而馳并且不符合一般的模式姻僧。然而NULLs在數(shù)據(jù)庫(kù)中扮演者很重要的角色规丽，因此不得不為NULL做特殊設(shè)置蒲牧。
由于NULLs可以被索引撇贺，因此即使表上沒(méi)有任何標(biāo)記也可以使用索引。（因?yàn)檫@個(gè)索引包含表航記錄的所有信息）冰抢。如果查詢需要排序的數(shù)據(jù)松嘶，而且索引確保了所需的順序，那么這可能是由意義的挎扰。這種情況下翠订，查詢計(jì)劃更傾向于通過(guò)索引獲取數(shù)據(jù)。
下面介紹btree訪問(wèn)方法的特性遵倦。
?amname | ????name ?????| pg_indexam_has_property
--------+---------------+-------------------------
?btree ?| can_order ????| t
?btree ?| can_unique ???| t
?btree ?| can_multi_col | t
?btree ?| can_exclude ??| t
可以看到尽超，B-tree能夠排序數(shù)據(jù)并且支持唯一性。同時(shí)還支持多列索引梧躺，但是其他訪問(wèn)方法也支持這種索引似谁。我們將在下次討論EXCLUDE條件。
?????name ?????| pg_index_has_property
---------------+-----------------------
?clusterable ??| t
?index_scan ???| t
?bitmap_scan ??| t
?backward_scan | t
Btree訪問(wèn)方法可以通過(guò)以下兩種方式獲取數(shù)據(jù)：index scan以及bitmap scan掠哥」ぃ可以看到，通過(guò)tree可以向前和向后進(jìn)行遍歷续搀。
??????name ???????? | pg_index_column_has_property
--------------------+------------------------------
?asc ???????????????| t
?desc ??????????????| f
?nulls_first ???????| f
?nulls_last ????????| t
?orderable ?????????| t
?distance_orderable | f
?returnable ????????| t
?search_array ??????| t
?search_nulls ??????| t
前四種特性指定了特定列如何精確的排序塞琼。本案例中，值以升序（asc）進(jìn)行排序并且NULLs在后面（nulls_last）禁舷。也可以有其他組合彪杉。
search_array的特性支持向這樣的表達(dá)式：
demo=#explain(costsoff)
select*fromaircraftswhereaircraft_codein('733','763','773');
???????????????????????????QUERY PLAN ???????????????????????????
-----------------------------------------------------------------
?Index Scan using aircrafts_pkey on aircrafts
???Index Cond: (aircraft_code = ANY ('{733,763,773}'::bpchar[]))
(2 rows)
returnable屬性支持index-only scan毅往，由于索引本身也存儲(chǔ)索引值所以這是合理的。下面簡(jiǎn)單介紹基于B-tree的覆蓋索引派近。
前面討論了：覆蓋索引包含查詢所需的所有值煞抬，需不要再回表。唯一索引可以成為覆蓋索引构哺。
假設(shè)我們查詢所需要的列添加到唯一索引革答，新的組合唯一鍵可能不再唯一，同一列上將需要2個(gè)索引：一個(gè)唯一曙强，支持完整性約束残拐；另一個(gè)是非唯一，為了覆蓋索引碟嘴。這當(dāng)然是低效的溪食。
在我們公司 Anastasiya Lubennikova @ lubennikovaav 改進(jìn)了btree，額外的非唯一列可以包含在唯一索引中娜扇。我們希望這個(gè)補(bǔ)丁可以被社區(qū)采納错沃。實(shí)際上PostgreSQL11已經(jīng)合了該補(bǔ)丁。
考慮表bookings：d
demo=# \d bookings
??????????????Table "bookings.bookings"
????Column ???| ??????????Type ??????????| Modifiers
--------------+--------------------------+-----------
?book_ref ????| character(6) ????????????| not null
?book_date ???| timestamp with time zone | not null
?total_amount | numeric(10,2) ???????????| not null
Indexes:
????"bookings_pkey" PRIMARY KEY, btree (book_ref)
Referenced by:
TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)
這個(gè)表中雀瓢，主鍵（book_ref,booking code）通過(guò)常規(guī)的btree索引提供枢析，下面創(chuàng)建一個(gè)由額外列的唯一索引：
demo=#createuniqueindexbookings_pkey2onbookings(book_ref)INCLUDE(book_date);
然后使用新索引替代現(xiàn)有索引：
demo=#begin;
demo=#altertablebookingsdropconstraintbookings_pkeycascade;
demo=#altertablebookingsaddprimarykeyusingindexbookings_pkey2;
demo=#altertableticketsaddforeignkey(book_ref)referencesbookings (book_ref);
demo=#commit;
然后表結(jié)構(gòu)：
demo=# \d bookings
??????????????Table "bookings.bookings"
????Column ???| ??????????Type ??????????| Modifiers
--------------+--------------------------+-----------
?book_ref ????| character(6) ????????????| not null
?book_date ???| timestamp with time zone | not null
?total_amount | numeric(10,2) ???????????| not null
Indexes:
????"bookings_pkey2" PRIMARY KEY, btree (book_ref) INCLUDE (book_date)
Referenced by:
TABLE "tickets" CONSTRAINT "tickets_book_ref_fkey" FOREIGN KEY (book_ref) REFERENCES bookings(book_ref)
此時(shí)，這個(gè)索引可以作為唯一索引工作也可以作為覆蓋索引：
demo=#explain(costsoff)
selectbook_ref, book_datefrombookingswherebook_ref ='059FC4';
????????????????????QUERY PLAN ???????????????????
--------------------------------------------------
?Index Only Scan using bookings_pkey2 on bookings
???Index Cond: (book_ref = '059FC4'::bpchar)
(2 rows)
眾所周知刃麸，對(duì)于大表醒叁，加載數(shù)據(jù)時(shí)最好不要帶索引；加載完成后再創(chuàng)建索引泊业。這樣做不僅提升效率還能節(jié)省空間把沼。
創(chuàng)建B-tree索引比向索引中插入數(shù)據(jù)更高效。所有的數(shù)據(jù)大致上都已排序吁伺，并且數(shù)據(jù)的葉子頁(yè)已創(chuàng)建好饮睬，然后只需構(gòu)建內(nèi)部頁(yè)直到root頁(yè)構(gòu)建成一個(gè)完整的B-tree。
這種方法的速度依賴于RAM的大小篮奄，受限于參數(shù)maintenance_work_mem捆愁。因此增大該參數(shù)值可以提升速度。對(duì)于唯一索引宦搬，除了分配maintenance_work_mem的內(nèi)存外牙瓢，還分配了work_mem的大小的內(nèi)存。
前面间校，提到PG需要知道對(duì)于不同類型的值調(diào)用哪個(gè)函數(shù)矾克，并且這個(gè)關(guān)聯(lián)方法存儲(chǔ)在哈希訪問(wèn)方法中。同樣憔足，系統(tǒng)必須找出如何排序胁附。這在排序酒繁、分組（有時(shí)）、merge join中會(huì)涉及控妻。PG不會(huì)將自身綁定到操作符名稱州袒，因?yàn)橛脩艨梢宰远x他們的數(shù)據(jù)類型并給出對(duì)應(yīng)不同的操作符名稱。
例如bool_ops操作符集中的比較操作符：
postgres=#selectamop.amopopr::regoperatorasopfamily_operator,
?????????amop.amopstrategy
frompg_am am,
???????? pg_opfamily opf,
?????????pg_amop amop
whereopf.opfmethod = am.oid
andamop.amopfamily = opf.oid
andam.amname ='btree'
andopf.opfname ='bool_ops'
orderbyamopstrategy;
??opfamily_operator ?| amopstrategy
---------------------+--------------
?<(boolean,boolean) ?| ???????????1
?<=(boolean,boolean) | ???????????2
?=(boolean,boolean) ?| ???????????3
?>=(boolean,boolean) | ???????????4
?>(boolean,boolean) ?| ???????????5
(5 rows)
這里可以看到有5種操作符，但是不應(yīng)該依賴于他們的名字。為了指定哪種操作符做什么操作哟冬，引入策略的概念鹦牛。為了描述操作符語(yǔ)義习柠，定義了5種策略：
? ? ? ? 1 — less
? ? ? ? 2 — less or equal
? ? ? ? 3 — equal
? ? ? ? 4 — greater or equal
? ? ? ? 5?— greater
postgres=#selectamop.amopopr::regoperatorasopfamily_operator
frompg_am am,
?????????pg_opfamily opf,
?????????pg_amop amop
whereopf.opfmethod = am.oid
andamop.amopfamily = opf.oid
andam.amname ='btree'
andopf.opfname ='integer_ops'
andamop.amopstrategy =1
orderbyopfamily_operator;
??pfamily_operator ?
----------------------
?<(integer,bigint)
?<(smallint,smallint)
?<(integer,integer)
?<(bigint,bigint)
?<(bigint,integer)
?<(smallint,integer)
?<(integer,smallint)
?<(smallint,bigint)
?<(bigint,smallint)
(9 rows)
一些操作符族可以包含幾種操作符，例如integer_ops包含策略1的幾種操作符：
正因如此，當(dāng)比較類型在一個(gè)操作符族中時(shí)，不同類型值的比較亥至，優(yōu)化器可以避免類型轉(zhuǎn)換。
文檔中提供了一個(gè)創(chuàng)建符合數(shù)值的新數(shù)據(jù)類型贱迟，以及對(duì)這種類型數(shù)據(jù)進(jìn)行排序的操作符類姐扮。該案例使用C語(yǔ)言完成。但不妨礙我們使用純SQL進(jìn)行對(duì)比試驗(yàn)衣吠。
創(chuàng)建一個(gè)新的組合類型：包含real和imaginary兩個(gè)字段
postgres=#createtypecomplexas(refloat, imfloat);
創(chuàng)建一個(gè)包含該新組合類型字段的表：
postgres=#createtablenumbers(x complex);
postgres=#insertintonumbersvalues((0.0,10.0)), ((1.0,3.0)), ((1.0,1.0));
現(xiàn)在有個(gè)疑問(wèn)茶敏，如果在數(shù)學(xué)上沒(méi)有為他們定義順序關(guān)系，如何進(jìn)行排序蒸播？
已經(jīng)定義好了比較運(yùn)算符：
postgres=#select*fromnumbersorderbyx;
???x ???
--------
?(0,10)
?(1,1)
?(1,3)
(3 rows)
默認(rèn)情況下睡榆，對(duì)于組合類型排序是分開(kāi)的：首先比較第一個(gè)字段然后第二個(gè)字段，與文本字符串比較方法大致相同袍榆。但是我們也可以定義其他的排序方式，例如組合數(shù)字可以當(dāng)做一個(gè)向量塘揣，通過(guò)模值進(jìn)行排序包雀。為了定義這樣的順序，我們需要?jiǎng)?chuàng)建一個(gè)函數(shù)：
postgres=#createfunctionmodulus(a complex)returnsfloatas$$
selectsqrt(a.re*a.re + a.im*a.im);
$$ immutable language sql;
//此時(shí)亲铡，使用整個(gè)函數(shù)系統(tǒng)的定義5種操作符：
postgres=#createfunctioncomplex_lt(a complex, b complex)returnsbooleanas$$
selectmodulus(a) < modulus(b);
$$ immutable language sql;
postgres=#createfunctioncomplex_le(a complex, b complex)returnsbooleanas$$
selectmodulus(a) <= modulus(b);
$$ immutable language sql;
postgres=#createfunctioncomplex_eq(a complex, b complex)returnsbooleanas$$
selectmodulus(a) = modulus(b);
$$ immutable language sql;
postgres=#createfunctioncomplex_ge(a complex, b complex)returnsbooleanas$$
selectmodulus(a) >= modulus(b);
$$ immutable language sql;
postgres=#createfunctioncomplex_gt(a complex, b complex)returnsbooleanas$$
selectmodulus(a) > modulus(b);
$$ immutable language sql;
然后創(chuàng)建對(duì)應(yīng)的操作符：
postgres=#createoperator#<#(leftarg=complex, rightarg=complex,procedure=complex_lt);
postgres=#createoperator#<=#(leftarg=complex, rightarg=complex,procedure=complex_le);
postgres=#createoperator#=#(leftarg=complex, rightarg=complex,procedure=complex_eq);
postgres=#createoperator#>=#(leftarg=complex, rightarg=complex,procedure=complex_ge);
postgres=#createoperator#>#(leftarg=complex, rightarg=complex,procedure=complex_gt);
此時(shí)才写，可以比較數(shù)字：
postgres=#select(1.0,1.0)::complex #<# (1.0,3.0)::complex;
??column?
----------
?t
(1 row)
除了整個(gè)5個(gè)操作符，還需要定義函數(shù)：小于返回-1奖蔓；等于返回0赞草；大于返回1。其他訪問(wèn)方法可能需要定義其他函數(shù)：
postgres=#createfunctioncomplex_cmp(a complex, b complex)returnsintegeras$$
selectcasewhenmodulus(a) < modulus(b)then-1
whenmodulus(a) > modulus(b)then1
else0
end;
$$ language sql;
創(chuàng)建一個(gè)操作符類：
postgres=# createoperatorclass complex_ops
defaultfortypecomplex
usingbtree as
operator1#<#,
operator2#<=#,
operator3#=#,
operator4#>=#,
operator5#>#,
function1complex_cmp(complex,complex);
//排序結(jié)果：
postgres=# select * from numbers order by x;
???x ???
--------
(1,1)
(1,3)
(0,10)
(3rows)
//可以使用此查詢獲取支持的函數(shù)：
postgres=# select amp.amprocnum,
???????amp.amproc,
???????amp.amproclefttype::regtype,
???????amp.amprocrighttype::regtype
from ??pg_opfamily opf,
???????pg_am am,
???????pg_amproc amp
where ?opf.opfname ='complex_ops'
andopf.opfmethod = am.oid
andam.amname ='btree'
andamp.amprocfamily = opf.oid;
?amprocnum | ??amproc ???| amproclefttype | amprocrighttype
-----------+-------------+----------------+-----------------
1| complex_cmp |complex|complex
(1row)
使用pageinspect插件觀察B-tree結(jié)構(gòu)：
demo=# create extension pageinspect;
索引的元數(shù)據(jù)頁(yè)：
demo=#select*frombt_metap('ticket_flights_pkey');
?magic ?| version | root | level | fastroot | fastlevel
--------+---------+------+-------+----------+-----------
?340322 | ??????2 | ?164 | ????2 | ?????164 | ????????2
(1 row)
值得關(guān)注的是索引level：不包括root吆鹤，有一百萬(wàn)行記錄的表其索引只需要2層就可以了厨疙。
Root頁(yè)，即164號(hào)頁(yè)面的統(tǒng)計(jì)信息：
demo=#selecttype, live_items, dead_items, avg_item_size, page_size, free_size
frombt_page_stats('ticket_flights_pkey',164);
?type | live_items | dead_items | avg_item_size | page_size | free_size
------+------------+------------+---------------+-----------+-----------
?r ???| ????????33 | ?????????0 | ???????????31 | ?????8192 | ?????6984
(1 row)
該頁(yè)中數(shù)據(jù)：
demo=#selectitemoffset, ctid, itemlen,left(data,56)asdata
frombt_page_items('ticket_flights_pkey',164)limit5;
?itemoffset | ?ctid ??| itemlen | ??????????????????????????data ??????????????????????????
------------+---------+---------+----------------------------------------------------------
??????????1 | (3,1) ??| ??????8 |
??????????2 | (163,1) | ?????32 | 1d 30 30 30 35 34 33 32 33 30 35 37 37 31 00 00 ff 5f 00
??????????3 | (323,1) | ?????32 | 1d 30 30 30 35 34 33 32 34 32 33 36 36 32 00 00 4f 78 00
??????????4 | (482,1) | ?????32 | 1d 30 30 30 35 34 33 32 35 33 30 38 39 33 00 00 4d 1e 00
??????????5 | (641,1) | ?????32 | 1d 30 30 30 35 34 33 32 36 35 35 37 38 35 00 00 2b 09 00
(5 rows)
第一個(gè)tuple指定該頁(yè)的最大值疑务，真正的數(shù)據(jù)從第二個(gè)tuple開(kāi)始沾凄。很明顯最左邊子節(jié)點(diǎn)的頁(yè)號(hào)是163梗醇，然后是323。反過(guò)來(lái)撒蟀，可以使用相同的函數(shù)搜索叙谨。
PG10版本提供了"amcheck"插件，該插件可以檢測(cè)B-tree數(shù)據(jù)的邏輯一致性保屯，使我們提前探知故障手负。
https://habr.com/en/company/postgrespro/blog/443284/
