PostgreSQL中indexing的資料結構：B-Tree

Published in

Practicode

7 min readJun 10, 2017

相信多數 Rails developer 在開發過程中，都會對一些 attributes 進行indexing，好處在於可以加快 query 所需的時間。通常會進行 indexing 的 attributes：

而在 PostgreSQL 中預設的 index type 就是這篇文章介紹的資料結構：B-Tree

B-tree

我們先假設大家都知道 Tree 這個資料結構，而這裡的「B」指的就是「Balanced」的意思，是屬於其中一種「平衡樹」，其基於 Binary Search Tree 再進行改良，使其能自己保持 Balanced 的資料結構。

「平衡（Balanced）」便是指 Tree 的兩邊資料量、深度相差不多，因此可以有較快查找速度、較低的查找複雜度。

「平衡樹（Balanced Tree）」便是指能夠在進行新增、刪除時透過「樹旋轉（rotate）」維持住「平衡（Balanced）」狀態的 Tree 資料結構，而 B-Tree 就是屬於其中一種。

B-Tree 的複雜度如下圖所示：

B-Tree 基本特性：

每一個節點（包含根）所能擁有的鍵值數量範圍是先被定義好的，假設 d 為大於等於 2 的整數，通常定義為 d-1 與 2d-1 之間。換句話說，每一個節點擁有 d-1~2d-1 個值。
因此可以推斷出每個節點擁有的子節點數量為 d~2d 之間（除了葉節點）。
B-Tree 中的所有葉節點深度（depth）皆相同。

以下我們用一個例子來說明：

這個例子中 d=2，因此每個節點最少有 1 個鍵值、最多有 3 個鍵值，而每個節點（除了葉節點）依照鍵值數量分別擁有 2~4 個子節點，而所有葉節點深度皆為 2，符合上述對 B-Tree 的描述。

在 B-Tree 進行搜尋的方式很類似在 Binary Search Tree 中的搜尋方式：搜尋數值 K，則從根開始，若 K 大於該節點值便往右子樹搜尋；反之則往左子樹搜尋，較不一樣的為當該節點有多值時，會從第一個值開始搜尋，直到找到該值或是找到其應該往子樹繼續下去搜尋的範圍。

範例：在上面的Tree中搜尋「15」

在 B-Tree 中的插入操作永遠從葉節點進行，另外必須考慮其每個節點鍵值數量的限制，若超過限制時會用到 split 的技巧。

範例1：插入值「20」

範例2：插入值「16.5」

藉由搜尋的技巧發現 16.5 應該屬於[14, 15, 16]這個節點之中
將 16.5 插入這個節點得到[14, 15, 16, 16.5]超出節點鍵值數量限制
split : 將這個節點中，中間值（15或16）往父節點提升，這裡以16為例
父節點[13, 17]變為[13, 16, 17]，而[14, 15, 16, 16.5]被拆為[14, 15]成為13, 16間的葉節點；[16.5]成為16, 17間的葉節點。插入成功

＊若往上提升後導致父節點也超過鍵值數量限制，則必須再用同樣的 split 方法再向上提升。

刪除操作較為複雜，需分為1. 刪除的值非葉節點 2. 刪除的值為葉節點，又得再分為刪除後是否造成空節點：

刪除後並未造成空節點，則可以直接刪除，例如刪除「1」，便是先找到1在[0, 1]的節點中，直接把1刪除，此節點剩下[0]。
刪除後造成空節點，則必須進行「樹旋轉（rotate）」，例如刪除「3」後，2, 4之間的葉節點為空，便進行 rotate：[0, 1]的 1 提升到父節點，而2往下移填補3的空位。