iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 11
3
Software Development

30天之從 0 至 1 盡可能的建立一個好的系統 (性能基礎篇)系列 第 11

30-11 之資料庫層的核心 - 索引結構演化論 B+樹

黑色好看版 - 傳送門


https://ithelp.ithome.com.tw/upload/images/20190926/20089358ZPcBZlbJcf.png

正文開始


接下來咱們要來理解資料庫系統中最核心的問題 :

要如何儲放資料,才能更快速的找到資料呢 ?

而這個東西的技術就是所謂的 :

索引

而在 mysql 中決定如何儲放的是資料庫儲存引擎來決定,而這裡咱們將要從 mysql 預設引擎 innodb 來深入的理解一下。

在 InnoDB 中預設是使用『 B+樹 』來當資料儲放格式,而為什麼要選擇它呢 ?

這就是我們這篇文章的重點。

InnoDB 為什麼選擇 B+ 樹 ?

本篇文章分為以下幾個章節,這也就是 B+ 樹的誕生原由。

  • 二分搜尋 Binary Search
  • 二元搜尋樹 Binary Search Tree
  • 平衡二元搜尋樹 Balanced Binary Search Tree
  • B 樹
  • B+樹 ( InnoDB 的選擇 )

二分搜尋 Binary Search


首先我們都知道,資料庫誕生出來的本質就是為了讓我們找東西更快速。

那是和什麼比呢 ? 就是所謂的『 線性搜尋 』,也就是說有 1000 筆資料,你要找到你想要的值,需要一筆一筆的慢慢查,而這種線性搜尋的時間複雜就是 O(n),其中 n 就是你所有的資料量。如下圖 1 所示。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358Ae8XEecWxI.png
圖 1 : 線性搜尋

那要如何加快呢 ? 基本上就是將它整理成固定的規律與特性,讓我們可以根據這個規律進行一些更快速的搜尋,這就是所謂的資料結構。

而最初在設計時,所選擇的規律概念就是所謂的『 二分搜尋 』。

要使用二分搜尋的前提條件為 :

  • 必須是排序好的資料

它的思路為 :

將資料砍成兩半,每一次砍時,判斷你要的資料在左還右 ( 因為是排序,所以可判斷 ),然後再從那段重複一樣的事情。

範例圖如下 :

https://ithelp.ithome.com.tw/upload/images/20190926/200893587uYn9KtGNM.png
圖 2 : 二分搜尋概念

那要選那個資料結構來實現二元搜尋呢 ?

資料結構只是一種概念,比較關鍵的重點在於記憶體的連續性,而這個連續性就可以導出兩個資料結構,那就是『 array 』與『 list 』。

Array ( X )

不行。主要有以下兩個原因。

  • 它的記憶體是連續區塊,需先事先分配大小,大量資料新增、刪除時會很浪費資源。
  • 新增、刪除操作有時會執行很快,有時會很慢,資料庫應該儘可能的操作都是平均。

為什麼 array 在新增或刪除時可能會很慢或很快呢 ?

主要的原因在於,它的記憶體區塊是連續的,所以假設一開始分 5 個位置,然後你新增資料 5 次,這 5 次都是會很快,但是問題出在第 6 次,因為沒有空間了,所以它會進行以下的流程來將 array 變大。

  1. 建立原本陣列兩倍大的記憶體空間。
  2. 將原本的陣列資料拷貝過去。
  3. 在寫入第 6 次資料。

所以基於以上原因,不會選擇這種資料結構。

List ( X )

list 呢 ? 它的記憶體是分散的。不行,因為以下原因如下圖 3 所示,它無法進行二元搜尋,因為它的記憶體是分散的,也就是說如果要至 5,那你要先知道 3 的記憶體位置,它那裡才有記錄 5 在那個位置上。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358i8dWwVsfv1.png
圖 3 : list 進行二元搜尋問題

二元搜尋樹 ( BST Binary Search Tree )


上述說明的兩個資料結構事實上都有某些優點 :

  • Array 可以使用 Binary Search。
  • List 可以解決 Array 的新增效率問題。

那有沒有什麼資料結構是有這兩個優點呢 ?

那就是『 二元搜尋樹 』,簡稱 BST。

BST 基本上長的如下圖 4 所示,基本特性就是左子樹值一定小於根節點,而右子樹值一定都大於根節點。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358BHJSdMArgE.png
圖 4 : 二元搜尋樹

然後資料庫的操作基本上為新增、刪除、搜尋。接下來我們來說說它們每一個操作的時間。

  • 搜尋 : 平均時間複雜度 log(n),因為只要往其中一邊走。
  • 新增 : 平均時間複雜度 log(n),因為它要找到適當的插入位置
  • 刪除 : 平均時間複雜度 log(n),因為它要找到適當的移除位置

基本上資料庫這三個基本操作平均而言都有 log(n) 指數級的操作時間,正常來說應該是可以選擇它。

平衡二元搜尋樹 ( Balanced BST )


BST 平均來看基本操作都有指數級的時間複雜度,但為什麼還是沒選他呢 ?

主要的原因在於,它最壞變成 O(n) 的時間複雜度操作,如下圖 5 所示,它的確也是一個 BST,這樣如果我們要搜尋某個值,仍然是一個一個慢慢找。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358izAJOp15xM.png
圖 5 : 有問題的 BST

因為後來就誕生一種『 平衡二元搜尋樹 』,如下圖 6 所示,事實和上面二元樹相同,只是差在每當插入節點時,會進行平衡。

它的特點如下 :

  • 葉節點的高度差的絕對值不能超過 1。
  • 左右子樹都為平衡二元搜尋樹。
  • 它的最好、最壞、平均的新增、刪除、搜尋的時間複雜度都是 O (logn)。
  • AVL 樹、紅黑樹都是屬於平衡二元搜尋樹,它們都會自動的進行平衡操作。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358ezitNTP40j.png
圖 6 : 平衡二元樹

平衡二元搜尋樹,正常來說,已經是在搜尋中最有效率的資料結構了,但是為什麼它是沒選它呢 ?

因為它是以『 記憶體 』來說,操作最有效率,但是以『 硬碟 』來說則否。

在資料庫的世界,通常資料量都有點兒大,不太可能全部都塞在記憶體中操作,通常會放在硬碟中。

那為什麼平衡二元搜尋樹在硬碟中操作沒有什麼效率呢 ?

因為 I/O 的問題

然後你想想如果一個很深的平衡二元搜尋樹,那如果要找的值是在最小面,以下圖 7 為例,那它就至少要進行 100 次 i/o 操作。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358H3yqPtnDLU.png
圖 7 : 平衡二元樹在節點多時的問題

B 樹


根據上述 i/o 的原因,因此又誕生出叫『 B 樹 』的東東,它想解決的東西為 :

解決高度太高的所產生的問題 ( ex. 資料庫索引的 i/o 問題 )。

一顆 m 階的 b 樹基本上有以下特點 :

  • 每個節點內最多有 m - 1 個內部節點。
  • 每個節點最多有 m 個子樹。
  • 每個內部節點都有儲放完整資料。
  • 每個節點內的內部節點,都是依順序排序。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358SNSR9D86Gz.png
圖 8 : b 樹

基本上它的概念就是在一個節點內,多塞些東西,為了減少 i/o 讀取次數,如上圖 8 所示。

為什麼可以減少 I/O 次數呢 ? 節點不是還是一樣多 ?

主要原因在於,平衡二元搜尋樹,每一個節點都是儲放在一個硬碟區塊中,而這個區塊大小為 4 kb,在讀取資料時都是以一個區塊為最小單位,也可以想成說,不管你節點資料是 2 byte 還是 1 kb,讀取次數都是和 4 kb 的一樣。

所以 b 樹處理的想法,就是儘可能將每個節點都塞滿 4 KB 的資料,並且內部在使用節點來區分,這樣每一次 i/o 讀取就可以讀到多個節點,這樣就可以減少 i/o 次數了。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358tAZeFzlMxu.png
圖 9 : b 樹與平衡樹的 i/o 比較

B 樹的問題

有了 B 樹後,為什麼還需要 InnoDB 仍然沒有選擇它呢 ?

因為有以下幾個問題 :

  • 查詢時不穩定。
  • 範圍搜尋時沒什麼效率。
  • 節點太多會導致 i/o 問題。

查詢時不穩定

假設我們有一個以 b 樹的來儲放的資料,接下來我們要進行兩次搜尋,然後結果如下圖 10 所示 :

  • 尋找 10 : 只要 1 次 i/o 就可以找到資料。
  • 尋找 1 : 要 3 次 i/o 才可以找到資料。

這就是 b 樹不穩定的範例,最好的情況是根節點就可以找到,而最壞是最底下的節點才找到。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358Os9GMWwVNe.png
圖 10 : b 樹查詢不穩定問題

範圍搜尋時沒什麼效率

下圖 11 所示,假設咱們要找大於 2 的資料,那基本上就是所有的節點都會走一次,你可以算算幾次 i/o,下圖綠色線就是走的路。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358I3NqN8Pa3U.png
圖 11 : b-樹範圍搜尋時問題

節點太多 I/O 的問題

下圖 12 所示,如果咱們每個節點變大的話,那你覺得原本可以放兩個的,真的還可以放兩個嗎 ?

https://ithelp.ithome.com.tw/upload/images/20190926/20089358zrL1epSRs5.png
圖 12 : 資料變大問題

B+ 樹 ( Innodb 的選擇 )


b+ 樹是為了解決 b 樹的以下問題 :

查詢時不穩定、範圍搜尋時沒什麼效率、節點太多 I/O 的問題

假設我們有一顆 m 階的 b+ 樹,它和 b 樹相比,有以下幾個特點 :

  • 每個節點,最多只能有 M 個子樹。
  • 每個節點中的內部節點,最多只能有 M - 1 個。
  • 每個非葉子節點(就是非最底層的節點),只儲放索引用。
  • 每個葉子節點(就是最底層的節點),儲放了實際資料。
  • 每個葉子節點(就是最底層的節點),會包含一個指針,指向右邊的葉子即點。

根據以上的變化,b+ 樹大至上長的如下圖,有個小重點記一下 :

只有最下面的節點有資料,其它上面的節點只存索引

https://ithelp.ithome.com.tw/upload/images/20190926/20089358gVvqssFgqR.png
圖 13 : b+ 樹

B+ 樹的搜尋與範例搜尋流程

所以如果它要取得 5 的資料,那基本流程如下圖 14 所示,會 3 次 i/o,而如果你要找 6 實際上也是 3 次 i/o,這也代表所有節點搜尋的速度是平均的,而不會有快有慢。

而如果要找 5 的,也只要找到 5 以後,在一直往右抓資料就夠囉。

https://ithelp.ithome.com.tw/upload/images/20190926/20089358dQNaCa8rXa.png
圖 14 : b+ 樹的搜尋範例

它與 B 樹的比較

  • b+ 樹層級更少 : 主要的原因在於,非葉子節點 4 kb 的空間全部用來只儲指針,這也代表它有更多的空間來儲放。
  • b+ 樹查詢更穩定 : 因為一定都要至葉子節點才能取得資料。
  • b+ 樹自帶排序 : 因為它有用個鏈表,來依順序的葉子節點串起來。

結論與心得


本篇文章咱們從 0 至 1 的理解為什麼 innodb 要選擇使用 b+ 樹的原理,而這也是我們學習資料庫核心索引的第一步,當你理解以下,你就可以知道為什麼之後索引要這樣使用囉。

參考資料



上一篇
30-10 之資料庫層架構與優化方向
下一篇
30-12 之資料庫層的核心 - MySQL 的索引實現
系列文
30天之從 0 至 1 盡可能的建立一個好的系統 (性能基礎篇)30

尚未有邦友留言

立即登入留言