原文：How Database B-tree Indexing Works
什麼是 B-tree？
B-tree 是一種樹狀的資料結構，他將資料存在節點中且樹中的節點是排序好的，下圖展示了 B-tree 的結構：
B-tree 中每個節點會儲存一組從小到大的順序的資料，節點中的每個資料會有另外兩個子節點，左邊的資料會小於目前的資料 (i.e 中間的資料)，右邊的資料則會大於目前的資料，如果一個節點有 n 個資料，那麼這個節點將會有 n + 1 個子節點。
為何 索引 被用在資料庫中？
想像你要儲存一組數據列於檔案中，並從這組數據列收尋特定的數字，最簡單的方法就是將資料儲存於陣列，當有新資料時就加到陣列的最後端，但當你需要找某個特定數字是否存在時，必須從最前端的數字一個一個往後尋找，在最糟的情況下，該數字可能在陣列的末端，這個程序將花 O(n) 的時間複雜度，這代表當你的陣列總長度為 “n” 時，最糟時你必須做 “n” 次比對才能找到解答。
我們該如何降低這個時間呢？最簡單的方式是，在一個已排好序的陣列中使用二元收尋法，不論何時新增數字，該陣列都必須是已排序的。二元收尋法起初會從陣列中間的值開始比對，並比較欲找的數字，如果中間數字大於欲找的數字，那麼我們就捨棄左半部陣列，已同樣的方式從右半部開始收尋比對，反之亦然。
在上面的圖，我們嘗試從已排序的陣列中找出 15，如果你使用一般的收尋法，他將會花五次的比較，並發現他在第五個數字，若使用二元收尋，他就只用花三次比較。
如果我們用二元收尋法收尋所有數字，過程會像下面的圖：
有熟悉的感覺嗎？他就是二元樹，也就是簡單的 B-tree (i.e 每個節點只有一個資料)，只不過在二元樹的實做中，我們可以使用指標來指向資料，而不用將資料儲存在排序好的陣列中。透過數學，我們可以證明在最糟的情況下，二元樹的搜尋時間為 O(log(n))，二元樹的概念可被延伸到更廣的結構，也就是 B-tree，有別於每個節點只儲存一個資料，B-tree 的節點使用陣列儲存多個資料，而每個節點有同樣用陣列儲存資料的子節點。
下列是不同操作的時間複雜度在先前介紹方法之間的比較。
B+tree 是另一種用來儲存資料的結構，他幾乎跟 B-tree 一樣，唯一的不同是 B+tree 將資料儲存在葉節點 (e.g 沒有子節點的節點)，也就是說在 B+tree 中，所有非葉節點中的值都是從葉節點中複製的，下面為 B+tree 的結構：
從上圖可以發現，13, 30, 9, 11, 16, 38 等非葉節點的直接與葉節點的值重複，如此以來，你是否發現了葉節點在 B+tree 中的特色？
沒錯，葉節點代表了所有的資料並且是已排序的狀態，有了這個特色，就可以像 B-tree 那樣收尋資料，此外如果我們使用指標串連所有葉節點 (如下圖)，我們就可以輕易地遊歷所有的資料。
索引 如何被用於資料庫中？
當 B-tree 被應用於資料庫的索引中時，資料結構會變得有點複雜，原因不僅是需要有個鍵值，這個鍵值還需要有相關的數值，且這個數值必須與資料庫中實際的資料相關，而鍵值與對應的數值合起來被稱為酬載(payload)。
假設下面的表格必須被儲存於資料庫中：
首先，資料庫會先給每一筆資料建立一個唯一的亂數值(或主鍵)，並將資料一欄一欄地轉換成字節流(byte stream)，然後將每組鍵值(e.g 亂數值) 跟資料的字節流儲存在 B+tree 中，此時，亂數值被用於 索引 的鍵值，此鍵值與字節流合在一起就作為酬載(payload)，B+tree 的結果如下圖：
從上圖你可看出資料表中的資料和索引的鍵值皆儲存在葉節點，而非資料表中的資料則儲存非葉節點，每個葉節點都能參照到樹中的下一個葉節點，因此，資料庫能夠使用索引進行二元搜尋法，或者藉由走訪所有葉節點來進行線性收尋。
如果索引沒被使用的話，資料庫必須讀取所有資料來找到對應的資料，但當索引被使用，資料庫會建立 B-tree 來儲存資料表的欄位(如下圖)，在圖中，鍵值代表被使用於索引的資料欄位，而索引則是用於參照到在 B+tree 中的完整資料。
起初當索引被使用時，資料庫會在 B-tree 中透過特定的鍵值(e.g 某欄位) 來找到索引，此步驟花 O(log(n))，隨後資料庫在 B+tree 中使用找到的索引再進行收尋，最後找到完整的資料，此步驟也花 O(log(n))。
B-tree 和 B+tree 中的所有節點皆儲存在 Pages 中，且 Pages 為固定的大小。Pages 有從一開始的唯一值，此唯一值可讓 Page 被其他 Page 參照。資料庫中主要有兩種 Pages。
- Pages for indexing：這些 Pages 儲存索引、被視為索引的資料欄位以及參照的其他 Page。
- Pages to store records：這些 Pages 儲存完整的資料且 Page 必須為葉節點。
結論
資料庫應該要有效地去儲存、讀取及修改資料，而 B-tree 提供了一個效率的方法來插入查詢資料，在真實的資料庫實做中，資料庫會同時使用 B-tree 和 B+tree 來儲存資料，B-tree 用於儲存索引，B+tree 用於儲存完整的資料，B+tree 除了二元收尋外也提供線性的收尋，有了 B+tree，資料庫就能控制非指標資料在資料庫中的收尋。
