結(jié)構(gòu)

B-tree索引適合用于存儲(chǔ)排序的數(shù)據(jù)。對(duì)于這種數(shù)據(jù)類(lèi)型需要定義大于、大于等于、小于、小于等于操作符。

通常情況下，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è)。因此查詢(xún)?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）。

等值查詢(xún)

例如通過(guò)”indexed-field = expression”形式的條件查詢(xún)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)，最后查詢(xún)到49這個(gè)值。

實(shí)際上，查詢(xún)算法遠(yuǎn)不止看上去的這么簡(jiǎn)單。比如，該索引是非唯一索引時(shí)，允許存在許多相同值的記錄，并且這些相同的記錄不止存放在一個(gè)頁(yè)中。此時(shí)該如何查詢(xún)？我們返回到上面的的例子，定位到第二層節(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)行等值查詢(xún)49時(shí)，定位到49這個(gè)值，然后選擇49的前一個(gè)值43，向下進(jìn)入其子節(jié)點(diǎn)進(jìn)行搜索。最后，在底層節(jié)點(diǎn)中從左到右進(jìn)行搜索。

(另外一個(gè)復(fù)雜的地方是，查詢(xún)的過(guò)程中樹(shù)結(jié)構(gòu)可能會(huì)改變，比如分裂)

非等值查詢(xún)

通過(guò)”indexed-field ≤ expression” (or “indexed-field ≥ expression”)查詢(xún)時(shí)，首先通過(guò)”indexed-field = expression”形式進(jìn)行等值（如果存在該值）查詢(xún)，定位到葉子節(jié)點(diǎn)后，再向左或向右進(jìn)行遍歷檢索。

下圖是查詢(xún) n ≤ 35的示意圖：

大于和小于可以通過(guò)同樣的方法進(jìn)行查詢(xún)。查詢(xún)時(shí)需要排除等值查詢(xún)出的值。

范圍查詢(xún)

范圍查詢(xún)”expression1 ≤ indexed-field ≤ expression2″時(shí)，需要通過(guò) “expression1 ≤ indexed-field =expression2″找到一匹配值，然后在葉子節(jié)點(diǎn)從左到右進(jìn)行檢索，一直到不滿(mǎn)足”indexed-field ≤ expression2” 的條件為止；或者反過(guò)來(lái)，首先通過(guò)第二個(gè)表達(dá)式進(jìn)行檢索，在葉子節(jié)點(diǎn)定位到該值后，再?gòu)挠蚁蜃筮M(jìn)行檢索，一直到不滿(mǎn)足第一個(gè)表達(dá)式的條件為止。

下圖是23 ≤ n ≤ 64的查詢(xún)示意圖:

案例

下面是一個(gè)查詢(xún)計(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 * from aircrafts;
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=# create index on aircrafts(range);
demo=# set enable_seqscan = off;