前言

B+樹，相信在學習資料庫時，多多少少都會聽過，如同二元樹、平衡二元樹等，他就是一種資料結構，定義十分複雜，在這裡只會簡單對B+樹做個簡介。

何謂B+樹

是一種資料結構，在 B+樹中所有紀錄結點都是按照鍵值大小順序放在同一層的葉子結點上(leaf node)，各葉子結點會用 pointer 連結，可以從一個葉子結點到下一個葉子結點，這個好處是找到資料後可以很快再移動到下一個資料就不需要每次都從 root 出發，如圖1：是一顆高度=2 的 B+ 樹。

圖1 參考至書籍-MySQL 技術內幕 InnoDB 存儲引擎
這裡可以看到兩個部分

• Index Page: B+樹中的非葉子結點
• Leaf page: B+樹中的葉子結點

B+樹索引

前面是簡單說一下一顆 B+樹的長相，但是 B+樹在資料庫中的實現就是B+樹索引，又可以分成

• 叢集索引 clustered index
• 輔助索引 secondary index

這兩種索引都是 B+樹。

叢集索引 clustered index

上一篇文章有說過，在 InnoDB 中，每一張表都是索引組織表，可以回去看一下MySQL 系列文 - 索引的相關知識 - 索引組織表，也就是說每張 TABLE 都是依照 PK 順序存放，而這裡說的叢集索引，就是依照每張 TABLE 的 PK 順序建立的一顆 B+樹，葉子結點的部分就是放所有的資料，簡單來說

• 叢集索引上的葉子結點(leaf node)就是放所有的資料，又稱資料頁。
• 由於一張 TABLE 裡的資料只能按照一個 B+樹來排序，因此每張 TABLE 只會有一個叢集索引。

當我們在SELECT 資料時，如果優化器決定使用叢集索引，那麼就可以在叢集索引的葉子結點上直接找到資料。如果查的是範圍資料例如SELECT * FROM table_name WHERE id>10 and id <20 也能快速找到這個範圍，因為資料都已經依照 PK 去排序了。

★ 範例

假設有一張表: tel_tb
PK: id
id|name|phone_num
----|-------------
2|Amy|0912345678
5|Simon|0912876543
8|Terry|0912222222
9|Bob|0912111111

結構如下

圖2

現在有一個語法 SELECT * FROM tel_tb WHERE id = 5 其查找流程如下
找到葉子結點，資料就在葉子結點上。

圖3

輔助索引 secondary index

又稱為非叢集索引，跟叢集索引不同的是，其葉子結點不包含每一筆資料的所有資料。這裡的葉子結點放的是兩個部分

1. 建立此 index 假設是用 name，那麼葉子結點會放 name
2. 另一個是儲存對應的叢集索引，稱作書籤(bookmark)，告訴 InnoDB 要去哪裡可以找到真正的資料
   假設現在要透過輔助索引(secondary index) 來找資料，順序如下

• 透過輔助索引找到對應的葉子結點
• 獲得對應叢集索引的 PK
• 透過叢集索引找到完整的資料

★ 範例

同上面的範例
假設有一張表: tel_tb
PK: id
id|name|phone_num
----|-------------
2|Amy|0912345678
5|Simon|0912876543
8|Terry|0912222222
9|Bob|0912111111
現在另外建立一個輔助索引在 name 欄位
CREATE INDEX index_name ON tel_tb (name)
結構如下

圖4
從圖中可以知道，每建立一個輔助索引，就會在建立一個 B+樹，所以表的空間會占用 Disk 更多，此外注意看輔助索引的葉子結點，並不是真實資料，放的是索引結點，也就是 name 欄位的值，而資料區域放的是對應的PK。

現在有一個語法 SELECT * FROM tel_tb name = 'Bob' 其查找流程如下
先找輔助索引找到對應的PK是 9 ，再到叢集索引去找到 9 所對應的真實資料。

圖5

小結

這篇主要在講叢集索引與輔助索引的差異，以及當我們在下 SELECT 語法時，怎麼在 InnoDB 裡面去查找，其實有一些狀況是不會到叢集索引裡面去拿資料的，這個觀念會在下一篇跟大家說明。

資料庫知識相當廣泛，文中若有不正確的地方，也煩請各位大神不吝指教，謝謝