索引( Index )

為什麼我們需要索引?

因為如果沒有索引,我們在一個資料庫裡要搜尋資料的時候就需要把全部資料都看過一遍。效率很差。

所以索引是用來提升我們的 Query 的效率。

索引常見的模型

既然我們知道索引是用來幫助我們可以更快速地取得我們想要的資料,讓我們來看看幾個常見實現索引功能的方式

  1. HashTable
  2. List
  3. Binary Tree 系列

這裡我們簡單的說明一下各自的優缺點

HashTable

HashTable 可以提供很棒的寫入讀取速度,但它面對範圍查詢的效率非常的差。

因為 HashTable 的特性是透過將資料放入 Hash Function 後取得 Hash Value 進行儲存,他沒有原始資料的值,所以無法有效利用原始資料來做範圍的搜尋。

List

List 可以有效的解決範圍搜尋,但因為 List 的特性,讓 List 無法做有效的插入新的資料。

一旦 List 需要插入新的資料便需要移動所有後方的資料。

Binary Tree

Binary Tree 是目前最為廣泛使用在資料庫上的資料結構,他能夠在上述提到的問題上做一個平衡。既能夠快速的搜尋到所需的資料,也可方便加入新的資料。

InnoDB 的索引模型

讓我們來了解一下我們很常使用到的 InnoDB 內的索引模型是什麼吧。

在 InnoDB 中,使用 B+ Tree 作為索引模型。B+ Tree 能夠降低讀取硬碟的次數(因為 B+ Tree 階層相較於 Binary Tree 更少)

每個表在 InnoDB 內都是以 B+ Tree 形式出現。

mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

以上面的 SQL 來說,這張表會有兩個 B+ Tree ,一個是以 primary key 為索引,另一個則是以 k 。

資料來源: MySQL 實戰 45 講

從上圖就可以看到,primary key 的 B+ Tree 儲存的內容是該 Row 的資料,k 的 B+ Tree 儲存的資料是 primary key(以這個例子來看就是 ID ).

如果我們了解上面的解釋後,讓我們來想想以下的兩個 Query 會形成什麼不同的效果。

// 1.
select * from T where ID = 500
// 2.
select * from T where k = 5

讓我們想想看第二個情況會發生什麼事?

因為我們有為 k 做一個 index ,所以他會從 k 這個 B+ Tree 上去做搜尋,但我所要的結果是 * (所有項目)。所以你會發現他會先從 k 這個 B+ Tree 上找到 id 後,再回到 id 這個 B-Tree 上找到所需要的資料。

索引的維護

B+ Tree 雖然用起來相當的方便,但因為 B+ Tree 的特性,在資料新增或刪除的時候,都有機率會引起 B+ Tree 的分裂與合併。所以索引並不是越多越好,也要思考到索引的維護成本。

一般使用的時候都會建議讓 primary key auto increment ,因為 InnoDB 針對 primary key 有做優化,比較不容易觸發 B+ Tree 的分裂與合併。

一般針對 Primary key 有以下幾點使用建議:

  1. 盡可能使用 int 作為 primary key :因為我們可以看到其他的 index 會儲存 primary key ,如果使用字串或是其他佔用空間大的資料結構,會造成資源的浪費。
  2. 盡量使用 auto_increment :InnoDB 有針對 primary key 做優化,可以減少 B+ Tree 的分裂或合併

索引的運用原則


mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

假設我們要從這個表上做 Query select * from T where k between 3 and 5,請問我們需要搜尋幾次 B+ Tree

  1. 在 k B+Tree 上找到 k=3, 找到 value 是 300
  2. 回到 ID B+Tree 找到 ID = 300,取得 value
  3. 再回到 k B+Tree ……

從這個例子可以看到,隨著我們找越多的資料,他就需要跑到另外一張表去查到真正需要的資料。這就是回表,回表會降低搜尋的效率,讓我們來看看有什麼使用原則可以減少回表的次數。

覆蓋索引

依照上面的例子繼續,如果我們這次的 Query 是 select id from T between 3 and 5

這樣你會發現,因為我們所需要的資料是 ID ,這個值在 K B+ Tree 裡面就有了,它不用再去找其他表。

再讓我們看看另外一個例子。

CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB

我們可以看到一個聯合索引 name_age ,如果我們的 Query 是 select age from tuser where name=lester ,它也會達到覆蓋索引的效果。

最左前綴原則

接續上面的範例我們已經有了一個 (name, age) 的聯合索引,我們還需要一個 name 的索引嗎?

索引的維護也是需要成本的,所以我們有一個最左前綴原則,在這個原則下,如果我們沒有其他需求,只要是你 Query 與 name 相關的資料,它都會使用到這個聯合索引。

當我們在設計索引的時候,就可以將需求與最左前綴原則,以及該索引的佔用空間大小去做考量,設計出好用又不佔空間的索引。

索引下推

此功能為 MySQL 5.6 後才出現的功能。

接續上面的範例,我們今天的 Query 是 select * from tuser where name like '張%' and age = 10 and ismale=1;

透過索引下推加上聯合索引的功能,當我們在 name_age B+ Tree 做搜尋的時候我們會自動過濾掉 age != 10 的數據,減少回表的次數,提升效率。

小結

資料庫真的是一門很深的學問。以上是我在 MySQL 實戰 45 講中索引的心得感想,如果有任何理解錯誤或是筆誤的地方歡迎留言來信。