索引是什麼 ? 為什麼加了索引查詢會變快|| What is indexing ? How the indexing makes SELECT queries faster?

索引是什麼(What is indexing?)

索引是一種資料結構(通常是樹的類型)儲存著按順序排列的資料，因為有序

B樹即為加快樹狀結構存取速度而設計的資料結構，常被應用在資料庫和檔案系統上

延伸閱讀 樹是什麼?樹是資料結構的一種

索引的功能

用於協助快速查詢、更新資料庫表中資料

想像以下為情況

你需要在資料庫中查到朋友名子為 Zack的資料

無索引的情況下

你需要一條一條找往下找，查看每一行，直到找到為止。如果您要查找的數據接近尾聲，則此查詢將需要很長時間才能運行。本次查詢進行了8次的比對找到Zack

有索引的情況下

表按照字母排序，搜索名稱會更快，因為我​​們可以跳過在某些行中查找數據。如果我們想搜索“Zack”並且我們知道是按字母順序排列的，我們可以跳到數據的一半，看看 Zack 是在該行之前還是之後。然後我們可以將剩餘的行減半並進行相同的比較。本次花了3次的比對找到Zack。

以上展示了索引的威力 8次vs3次速度。

索引如何做到的

前面提到資料庫索引是一種樹狀的資料結構，儲存指向存儲在表的指定列中的數據值的指針，並且因為是有序排序所以查詢速度更快。

舉個例子: 我們可以看到透過Index它是如何映射回原始 Friends 表的

我們可以在這裡看到索引的名稱按字母順序(A-Z)存儲。表中存儲的數據是根據添加數據的順序按遞增的 id 排序的。

索引使用稱為Binary_search 最佳搜索方法，原理是不斷地將數據切成兩半，並檢查您要搜索的條目是在當前數據部分中間的條目之前還是之後。

關於Binary_search如下圖

套用到我們的DB在做索引時的邏輯如下圖

使用Binary_search 1,000,000 調資料的 20次可以找到該資料

索引類型

可分為兩種資料庫索引

1. 叢集(Cluster)
2. 非叢集索引(Non-clustered)

聚集索引和非聚集索引都以 B 樹的形式存儲和搜索，樹狀結構對對數據進行排序以便快速搜索差別在於

叢集索引：索引的葉節點就是數據節點

非叢集索引的葉節點仍然是索引節點，只不過有一個指針指向對應的數據塊

叢集索引

叢集索引是每個表的唯一索引，它使用主鍵來組織表中的數據。叢集索引確保主鍵按遞增順序存儲，這也是表在記憶體中保存的順序。

聚集索引像書籍的目錄，每本書只能有一個目錄，整本書會依照這個目錄排序。

創建叢集索引

定義主鍵時會自動創建叢集索引：

CREATE TABLE friends (id INT PRIMARY KEY, name VARCHAR, city VARCHAR);

創建的表“friends”將自動創建一個聚集索引，名為“friends_pkey”的主鍵“id”

當使用Id搜索時

當按“id”搜索表時，列的升序允許執行最佳搜索。由於數字是有序的，因此搜索可以導航 B 樹，從而允許搜索以對數時間進行(因樹型的「有序」特性，依然能夠保持O(log(n)) 的高效率)

但是，為了在表中搜索“名稱”或“城市”，我們必須查看每個條目，因為這些列沒有索引。

叢集索引的數據的物理存放順序與索引順序是一致的

1. 每個表只能有一個聚集索引，因為目錄只能按照一種方法進行排序
2. 叢集索引對於那些經常要搜索範圍值的列特別有效。使用叢集索引找到包含第一個值的行後，便可以確保包含後續索引值的行在物理相鄰聚簇索引的數據的物理存放順序與索引順序是一致的(見下圖)

非聚集索引

非聚集索引是對特定字段的排序引用，來自主表，它保存指向表的原始條目的指針。上面例子按照名子搜尋的索引就是一種非聚集索引

非叢集索引像書本後面的索引目錄，每本書可以有很多種索引目錄，例如依照字母排序

依照字母排序

套用在DB 建立非叢集索引(案名稱)邏輯如下圖

先找到名稱對應的id指向原本Table資料

非叢集索引不是新Table。非聚集索引包含它們負責排序的字段，每個索引鍵值項目都有一個指標，指向包含索引鍵值的資料列。

創建非集群數據庫（PostgreSQL）

創建一個索引來按字母順序對名子做排序

CREATE INDEX friends_name_asc ON friends(name ASC);

創建出“friends_name_asc”的索引如下，該索引存儲的“Friends”表中的name (按字母升序)

這邊可以注意到friends_name_asc 裡面沒有city欄位，這是因為索引不會儲存原來的table的所有欄位，只會儲存”id”欄位將指向原始的table如下圖

透過id mapper到原始表

非聚集索引指向記憶體地址，而不是自己存儲數據。這使得它們的查詢速度比聚集索引慢，但通常比非索引列快得多。

非叢集索引-葉節點仍然是索引節點，只不過有一個指針指向對應的數據塊

該索引中索引的邏輯順序與磁盤上行的物理存儲順序不同

Q:如果沒有id怎麼辦?

A:NonClustered Index(index page)上所有分葉節點存放指標，如果資料表已存在Clustered Index(KeyID)，那麼該指標將會指Clustered Index，如不存在將指向資料真實存放位置(RID)

何時使用索引?

1. 想加快資料的檢索速度，這也是建立索引的最主要的原因
2. 對資料進行order by , group by 進行檢索時可以減少排序和分組時間
3. 唯一性索引，可以保證資料庫表中每一行資料的唯一性

索引問題?

前面提到索引是一種樹狀的結構

• 每個索引都會建立一顆 b+樹。(mysql為例)
• 每次新增、更新資料時都會改變 b+ 樹。(mysql為例)

所以索引越多時，需要的記憶體與維護索引的 cpu 運算就需要越多

因為當資料寫入資料庫時，更新原始表的聚集索引（the clustered index），然後更新該表的所有索引

常用資料庫索引實現

mongoDB oracle 索引採用B tree結構

Mysql 採用B+ tree 樹

B tree vs B+ tree

B樹中每個節點（包括葉節點和非葉節點）都存儲真實的數據，B+樹中只有葉子節點存儲真實的數據，非葉節點只存儲鍵

總結

• 索引可以大大減少查詢時間
• 每個具有主鍵的表都有一個叢集索引
• 每個表都可以有許多非叢集索引來幫助查詢
• 非叢集索引保留指向主表的指針
• 並非每個索引都會提高資料庫的查詢速度

參考

Indexing