7月24日，Greenplum原廠核心研發馬洪旭和大家直播分享了《深入淺出Greenplum核心》系列直播的第四期《Greenplum核心揭秘之B樹索引》。相關視訊已上傳至Greenplum中文社群B站頻道，點選文章底部“閱讀原文”即可觀看。本文概括了文章的精華内容，歡迎大家給我們留言交流。
索引是資料庫中的重要元件，而B樹則是最常見的索引資料結構，同時它也是Greenplum中的預設索引類型。今天我将給大家詳細介紹B樹索引。本文将涵蓋B樹的基礎知識、B樹的存儲結構、操作算法、并發控制，相關系統表等知識。
B樹的基本知識
首先和大家介紹一下B樹的基礎知識。大家一般在大學的資料結構課程中都學過B樹，如今回憶起來，很多人都會問，為什麼資料庫索引經常會選用b樹來實作資料庫索引呢？Greenplum的B樹索引和我們大學課程中介紹的是否完全一樣呢？它的資料結構和算法是不是和課程中介紹的完全一樣呢？大家可以思考一下這幾個問題，看完這篇文章就能知曉答案。
01
索引
在開始介紹B樹索引之前，先給大家簡單介紹一下索引。大家在網上看到的定義往往太過複雜，我自己給他下了一個簡單的定義：索引就是能加速一個正常操作的資料結構。為了友善大家的了解，這裡我給大家舉了一個簡單的例子，在用字典時，當我們想查某個詞的時候，我們可以選擇從這字典從頭到尾逐頁翻查，可想而知，這樣的查詢速度非常慢，如果我們使用這本字典附錄中的索引，查詢速度就會大幅提高。
索引包括本文即将詳細介紹的B樹索引，另外還有哈希索引和反向索引。其中哈希索引比較常見，比如一個很簡單的程式，裡邊會執行一個資料查詢，查詢到的結果都存儲到哈希表裡，下次再通路的時候，會先到哈希表裡，判斷資料是否已經存在，如果已經存在，就沒有必要再運作這個查詢，這就是哈希索引。
反向索引往往用于全文檢索中，大家平時在用百度或者谷歌搜尋的時候，就會用到全文檢索，其背後的索引是反向索引。
02
B樹
介紹完索引，我們再來了解一下B樹。大家需要注意的是，B樹實際上是一個很大的家族，是以大家在技術文章或者部落格的時候，需要留意他所提及的B樹具體是哪種B樹。B樹可以細分多個子類别，對比我們大學的資料結構課程，課裡提及的一個結構容易與B樹混淆。即二叉樹。二叉樹和B樹都是平衡樹，但二叉樹它的每個節點裡隻能存儲一個鍵值，而B樹中的每個節點都存儲了大量鍵值，是以樹不會太高。
具體大家看上圖這個典型的B樹，它的節點裡存儲了很多鍵值，這些鍵值也是有序排列，比如圖中的1，2，5，7，9，12，16，18，21。每個鍵值都會指向目标資料。
B+樹是B樹最常見的一個子類别，下圖就是一個典型的B+樹。B+樹的特點是葉子層節點存儲了全部鍵值，這些鍵值再指向目标資料，比如圖中的1，2，5，9，12，18，21。内部節點中重複存儲部分鍵值，但不含資料指針。葉子節點層有一個正向的周遊清單。
這裡我們就會解答開始時讓大家思考的第一個問題：為什麼經常使用B樹來作為資料庫的索引結構？實際上是B+樹。B+樹非常适用于資料庫中的索引結構，它的最主要的目的就是減少磁盤lO，每個節點對應磁盤中的一個頁，通路節點對應一次磁盤IO。是以我們會希望樹非常扁，即樹的高度非常少，因為樹的高度就是通路磁盤IO的次數。
為什麼使用B+樹？因為B+樹在節點不用存儲資料或資料指針，是以每個節點裡能存儲的鍵值要比B樹多，存儲的鍵值多，B樹就會變得非常扁，高度會非常低，磁盤lO就更少。是以我們選用的經常是B+樹。
還有一個原因是我們經常需要範圍查找，比如上圖中如果要找到有2~9的資料，我們把2的資料找到後，沿着右側方向就能把5和9也找到，因為在頁的節點層有右上指針，是以我們不再需要從根出發，而是直接向右移動就能找到。
B+樹也是Greenplum中的預設索引類型。Greenplum是基于Postgresql并在其之上做了很多改進。因為Postgresql也是個傳統資料庫，是以它選用的也是B+樹。比如下面的例子中，我們在一個大表中查找了一個ID等于1萬資料，共花了20秒的時間。接着我們建立了一個索引，需要留意的是，這裡并沒有指明索引的類型，這樣的話，預設就是B樹的。然後我們再查一次，這次花了200毫秒，提升了100倍。大家可以看到，使用索引可以很好地提升查詢的性能。
demo=# select * from big where id=10000;
…
Time: 19490.566 ms
demo=# create index on big(id);
CREATE INDEX
demo=# analyze big;
ANALYZE
demo=# select * from big where id=10000;
…
Time: 210.594 ms 03
Blink樹
在了解完B樹和B+樹後，大家現在可能會有一個疑問：Greenplum中用的到底是不是B+樹呢？答案是既是也不是。Greenplum中用的B+樹叫Blink樹。
在具體介紹Blink樹之前，先補充一點，我們在大學課程中講的B樹或者B+樹 ，有兩個方面基本沒有提及。第一個方面就是B樹需要支援故障恢複，當資料庫當機了，大家肯定不希望所有資料在當機之後就無法恢複了。如果資料庫突然重新開機了，重新開機之後發現索引壞了，大家肯定會非常頭疼。實際上WAL（重做日志）中會記錄節點頁面和樹結構（如頁面分裂）的變化，是以我們通過重做WAL日志就可以恢複。關于恢複的相關内容，大家可以關注我們核心直播系列 的後續課程。
第二個方面是B樹需要提供一個高性能的并發控制，因為生産環境中的資料庫，同時要為大量并發通路所服務，是以就需要提供高性能的并發控制。
出于這兩點考慮，Greenplum采用的是Blink樹。Blink樹來自于Lehman和Yao于1981年的論文《Efficient locking for concurrent operations on B-trees》。Greenplum中的實作就參考了該論文并進行了稍許改進，該論文中在B+樹的基礎上，在結構中引入了右兄弟指針和高鍵。右兄弟指針使得内部節點同層間可以向右移動。除了葉子節點層，在中間節點層也有右兄弟指針的存在，比如下圖的中間層。而高鍵是指目前節點和以目前節點為根的子數中的最大鍵值。
現在我們已經了解了B樹的基礎知識，在接下來的内容裡，我們稱呼上不再細分B樹的類型，提到的B樹特指Greenplum中的B樹，也就是Blink樹。接下來讓我們看看B樹的存儲結構。
存儲結構
01
實體存儲
在這裡，我們先介紹一下就是粗粒度的索引存儲，Greenplum中的索引都是二級索引，簡單來說就是在實體存儲上是獨立的檔案，獨立于表中的資料檔案。索引是按分片存在在每個segment上其索引内容對應segment上的資料配置設定。
大家如果想看索引檔案在哪，可以通過下面這個SQL查詢，先找到檔案名。在我的電腦上，通過檔案名16524，在Greenplum資料目錄中執行一下find指令，就可以找到這兩個檔案。這裡有兩個檔案，是因為我的測試環境是2個segment，大家如果感興趣可以執行一下看看。
demo=# select relname, relfilenode, gp_segment_id from gp_dist_random('pg_class') where relname = 'student_id_idx’;
relname | relfilenode | gp_segment_id
----------------+-------------+---------------
student_id_idx | 16524 | 1
student_id_idx | 16524 | 0
(2 rows)
$ find . -name 16524 | xargs ls -l
-rw------- 1 interma staff 1212416 Mar 17 10:44 ./gpseg0/base/16384/16524
-rw------- 1 interma staff 1179648 Mar 17 10:44 ./gpseg1/base/16384/16524 02
邏輯結構
接下來給大家介紹一下索引的邏輯結構。大家可以看一下下面這張圖。從右向左看，下面是堆表中的資料部分，我們着重看一下上面的索引資料。
大家從上到下看，Meta頁存儲的是整個樹的元資訊。root節點大家應該都了解，但這裡還有個Fast Root，我們來簡單介紹一下什麼是Fast Root？B樹随着增删資料，有可能從最上層，每層的節點到下層都隻有一條指針。這樣的話，每次查找都需要從根上往下走，但是每層到下層隻有一個指針，是以就沒必要再從第一層進第二層再進第三層，直接從fast root層進入即可，這樣就起到一個加速的作用。每個節點中标注粉色的就是高鍵。
此外，論文中提到Blink樹隻要是右向指針就可以，但Greenplum中用的是雙向的，是以在反向周遊的時候也很友善。
這是樹的整體情況，接着我們來看看單個節點，即左下這個圖。單個節點裡邊是N-1個鍵值和N的指針，即指針會比鍵值多1，再配上一個高鍵，即High Key。
有些讀者可能會問，索引裡邊有沒有版本資訊呢？答案是沒有。也就是說實際上Greenplum的每個版本的資料元組，都會有對應的索引元組。為了減少索引空間開銷，Greenplum引用了 HOT （Heap Only Turple）技術。這裡就不做進一步介紹，大家感興趣可以去網上搜尋了解一下。
03
索引節點實體結構
每個索引節點實際上都對應一個實體頁面。頁面結構和堆表（Heap）的頁面結構基本一緻，但還存在一些差別。由于資料元組，即堆表裡的頁面存儲的是資料元組，而這個索引的頁面，是以裡面存儲的肯定不是資料，而索引元組，它邏輯上的内容就是鍵值和指針。
這裡大家需要留意的是，Line pointer0指向的，即第一個索引元組是高鍵，它後邊的才是普通的索引元組。而Special 頁面存儲了頁面級元資訊，包括兄弟指針、頁面類型等。
04
Pageinspect示例
介紹完邏輯結構和實體結構，讀者可能有疑問，怎麼能比較直覺的看到這些内容呢？可以通過Greenplum或者Postgresql中的一個擴充來檢視，它叫Pageinspecthttps://www.postgresql.org/docs/9.5/pageinspect.html，通過它可以檢視頁面中的内容。除了可以檢視資料元組的内容，即堆表的内容，它還提供了很多函數檢視索引的内容。檢視B樹索引，最常使用的是下面這三個函數。
- bt_metap returns information about a B-tree index's metapage
- bt_page_stats returns summary information about single pages of B-tree indexes
- bt_page_items returns detailed information about all of the items on a B-tree index page
第一個是bt_metap，是用來看B樹的meta頁。bt_ page_stats是用來檢視頁面的special 中繼資料，而bt_page_items會傳回索引元組的資訊。
下面的例子中建立了一張測試表，表裡有兩個字段，第一個字段是ID，是遞增的1到1萬，第二個字段随機插入了一個字元，然後建立了索引。因為Greenplum是MPP資料庫的，它的Master上是沒有資料的，是以如果大家運作這個SQL時，需要通過工具模式直接連接配接到segment上。
# 建立測試表
demo=# create table test_index (a integer, b text) distributed by (a);
demo=# insert into test_index(a,b) select s.id, chr((32+random()*94)::integer) from generate_series(1,10000) as s(id) order by random();
demo=# create index on test_index(a);
demo=# create extension pageinspect;
PGOPTIONS=‘-c gp_session_role=utility’ psql -p 6000 demo #通過工具模式直接連接配接到segment上 我們先看meta頁面，從查詢中資料可以看出：
- 這個索引的根層級是1（葉子節點層級是0），即樹的高度為2。
- 快速根節點和根節點是同一個節點（塊号相同，均為3）
如果大家看過Greenplum代碼，就會發現這裡的這些資訊，和代碼裡的BTMetapageData結構體是一一對應的。
接下來，我們來看看内部節點長的是什麼樣的。Stats對應頁面中的special結構：對應代碼中的BTPageOpaqueData結構體。各字段的含義如名字，其中btpo表示層号：root節點的層号是1。Items對應頁面中的索引元組：其中内部節點的第一個索引元組的鍵值為空。剛剛我們提過，節點裡的鍵值是n減一個，指針是n個，由于鍵值少1，是以按照慣例，我們會把第一個鍵值留白。
接着我們再來看看葉子節點。葉子節點type都等于l，表明leaf頁；btpo都等于0，表示第0層。live_items總共：1473*3+597=5016個索引元組，而另一個segment上有4984個索引元組，這與表中共10000個記錄吻合。前3個leaf頁面已經填滿，填充率約為(1-3264/32768)=90%，這也是B-Tree的葉子節點的預設填充因子（内部節點的填充因子是70%），如果頁面完全填滿，會導緻這個頁面非常容易分裂，是以我們特地留了一點點空間，讓頁面不那麼容易分裂來提升性能。btpo_prev和btpo_next頁面表明leaf頁的順序是（由左到右）：1 <-> 2 <-> 4 <-> 5。
前面介紹的是頁面元資訊，我們再來介紹一下頁面的索引元組葉子節點items。葉子節點items的第一個條目是ctid=(1,628)，如前邊B-Tree邏輯示例圖中所述，每個頁面記憶體儲的第一個鍵值是HighKey，而從第二個元素開始，才是真正葉子節點存儲的鍵值。同時這也是第二頁的第一個普通鍵值（這裡不是巧合，B-Tree建構的細節将在後邊詳述）。而第一頁的第2個鍵值為2，它也是這個B-Tree索引的最小值。
操作算法
介紹完B樹結構，接下來我們來看看B樹的操作算法。這裡的操作算法我們将不從代碼層面來進行介紹，而是着重介紹一下增删改查的算法。然後在這裡大家不用考慮并發控制，因為并發控制是在我們下一節來介紹的。
01
建構
建構一棵B樹是由create index觸發的，從表中現有資料建立出一顆B樹索引，算法可以分2大階段。第一個階段是排序，将表中資料元組有序化。排序對比插入方案，插入方案在每次插入時，都需要由根到樹葉部分做一次下降過程，消耗較大，是以我們會采用排序來提升效率。先排序還可以提前處理唯一索引。
第二步是周遊有序的資料元組，由下向上來建構整個B樹。當節點頁面已滿（實際上還有部分空閑空間）時，生成目前節點高鍵；再生成右兄弟節點，插入鍵值到父節點中。最後由下向上補全B樹，并填充meta資訊。
02
插入
插入算法是由insert語句觸發：首先插入資料元組，然後插入索引元組，算法如下：
首先從根節點開始向下查找，目标是定位要插入索引元組的葉子節點。記錄從根節點到葉子節點的這條路徑，供後續反向插入父節點使用。随後在葉子節點中定位要插入的具體偏移位置，并插入索引元組到這個葉子節點中。如果葉子節點已滿，則需要分裂節點并插入一個新鍵值到父節點中，此過程會沿着查找路徑遞歸向上執行（有可能導緻父節點繼續分裂）。
03
查找和删除
我們再來給大家講一講查找、删除算法。最常見的使用索引的方法是普通索引掃描，它和我們插入算法特别相似，就是一條下降路徑下降到葉子節點，然後在葉子節點中找到一個偏移，就可以找到。
索引掃描最終是找到一個指針，通過這個指針就可以通路到資料。但指針就意味着這是一個随機IO，也就是說它是随機通路的。是以盡管通過索引查找速度很快，但相對于順序IO，性能較差。如果有大量的随機IO，性能将很難提高。于是引入了位圖索引掃描，它會把找到的位址進行一個排序，然後會随機IO盡量轉化成順序IO。位圖索引掃描可以檢視這篇文章詳細了解。
關于删除算法，大家可能會想是不是在删除一個資料源組的時候，會把索引給删了，答案是不會的。删除不是由delete語句觸發，而是索引掃描時發現死亡的資料元組後，對相應的索引元組進行”标記删除”。vacuum時進行最終删除，也是二階段算法：首先删除已标記的索引元組，然後删除空頁面并調整樹結構（由下向上調整）。
并發控制
在現實生活中應用的資料庫系統裡，并發控制是必須要考慮的，因為資料庫不可能隻由一個人使用，這也是Greenplum選擇Blink樹的原因。在介紹并發控制算法之前，我們先看看一個樸素算法會遇到什麼問題，來幫助大家了解Greenplum中為什麼要使用Blink樹。
這種樸素的并發控制算法的思想非常簡單，在讀節點時加讀鎖，寫節點時加寫鎖，唯一需要特殊處理的就是節點分裂。大家可以看一下下面的代碼。每次其實隻有一個節點會被加鎖，往下走的時候，會把下面的節點加鎖，再把上面的節點的鎖釋放。
插入節點會複雜一些。每次加的鎖是寫鎖。這裡要給大家介紹一個新的概念，當在某個節點上插入一個新索引元組後，不會觸發它的分裂，那麼這個節點就叫做安全節點。也就是說還沒滿的節點，每次插入一個鍵值的時候，就把這條路徑上的所有節點都會加寫鎖。那麼為什麼要加寫鎖呢？前文的插入算法裡提過，我們有可能會反向向父結點中插鍵值，是以必須要鎖住。
在大多數情況下，在葉子節點中插完鍵值後，才把葉子節點釋放掉，然後再把父節點的鎖釋放掉。這裡的安全節點就是一個特殊的優化情況，有些節點因為還沒滿，可能往裡插鍵值也不會分裂，也就是它上層的樹的結構是不會變化的。是以說上層這兩個父節點的鎖都可以先釋放掉，這是一個簡單的優化。但是在極端情況下，這條路徑都加了鎖。這就會帶來兩個問題，首先由于每次路徑下降都需要鎖操作，是以在靠近樹根的位置上的鎖沖突率較高。另外在路徑下降時加的這些鎖，大機率都會被馬上釋放掉。
接下來我們來看看Greenplum中是如何解決的。Greenplum中的Blink樹并發控制算法，引入了一個moveright操作，利用到了HighKey和右兄弟指針，用于及時發現節點已經被分裂：如果分裂，所查找的鍵值一定在右兄弟節點上。也就是說每通路一個節點，先看看查找的鍵值是否大于高鍵。如果是，就移到右邊的節點上，然後再進行通路。
那麼為什麼要用這個操作呢？下圖的示例來自Blink論文，是以也很有年代感了。通過moveright操作，可以處理下圖這種分裂問題。Insert操作的下降過程中也加讀鎖，可以放松下降過程中的鎖操作。
Blink樹并發控制算法具體如下：
Blink樹并發控制算法- Search
- 從根節點開始逐層下降，加讀鎖
- 每次下移一層後，都調用moveright操作，檢查節點是否分裂
- 在下移或者右移操作時，都是先釋放鎖，然後再去申請新鎖，即申請新讀鎖操作時并不持有鎖，是以可以避免死鎖（和Insert操作并發時）
- 最後到達葉子節點，加讀鎖，并讀取内容
Blink樹并發控制算法 – Insert
- 開始階段同Search操作一樣，逐層下降加讀鎖并配合moveright，是以并行佳
- 逐層下降到達葉子節點後，需要将讀鎖更新為寫鎖
- 如果需要節點分裂
- 建立右兄弟頁面，加寫鎖，随後将它挂入到B-Tree中
- 随後遞歸向上插入鍵值：由下向上為父節點申請寫鎖，随後插入到父節點的操作，然後再釋放下層節點的寫鎖
Blink樹解決了樸素算法的2個問題
- 樹根的位置上的鎖沖突率較高 => 讀寫均加讀鎖
- 另外在路徑下降時加的這些鎖，大機率都會被馬上釋放掉 => 下降時加讀鎖，寫鎖由下向上申請
我們再來看下是否會産生死鎖：
- Insert操作中寫鎖的申請順序都是由下向上，由左到右，不會發生死鎖
- Search操作是可能和Insert操作出現不同申請順序（前者由上向下；後者由下向上），但是Search操作每次都是先釋放再申請，是以也不會發生死鎖
索引相關系統表
最後會給大家介紹一下索引相關系統表。大家在用索引的時候，經常會和系統表打交道，這裡簡單介紹它是什麼作用，了解索引相關系統表也更好的了解其作用。這裡給大家提了一個問題，Greenplum中的類型系統是可以自定義和擴充的，同一套B樹算法如何支援不同的資料類型呢？
相信大家都已經有了答案，這裡遇到的問題和C++中的泛型算法非常類似。相當于在B樹算法裡，留出了擴充點或接口。對于B樹來說，就是7個接口，它們本質上都是自定義函數。
- 政策操作符，5個
- 支援函數，2個
索引表的最終目的就是為自定義類型添加索引的支援。如果把系統表都展開，大家可以看到下圖中，有很多個系統表，這裡就不做贅述。這裡就給大家解釋兩個容易混淆的概念，Operator class和Operator family：
- Operator class，同類型上的函數接口
- Operator family，跨相近類型上的函數接口
總結
B樹的基本實作并不複雜，但是各種優化非常博大精深，涉及到系統優化的方方面面。Greenplum中的B樹索引實作主要參考了Blink論文，這篇論文雖然已經年代久遠，但非常經典，對後續B樹的并發控制設計仍然具有深遠的影響。讀者如果有興趣，非常建議繼續閱讀Greenplum的B樹實作源碼（位于src/backend/access/nbtree），進而可以了解到一個實用的資料庫系統是如何處理各個細節的。