白話文解說 Clustered Indexes

B-tree 資料結構是談 database 索引(index)不可或缺的重要角色,透過 B-tree 資料結構,我們能用走訪樹狀結構的方式迅速找到資料,當我們執行 CREATE INDEX idx_field ON table(field) 時,其實是建立 1 種稱為 non-clustered 的索引,這種索引的葉節點(leaf node)一般只會存 key (欄位值)與 record identifier (可以直接想像是 primary key),所以找資料的順序會是先找到索引裡的 key ,然後再取出 record identifier 裡指向的資料位置,最後去取出相對應的資料。

fig-1.png

但這種索引對於 range query (例如 WHERE field BETWEEN 1 AND 10 )效能比較不好,原因是 non-clustered 裡的 record identifier 不保證是有序的,只有 key 才是有序的,所以取出範圍型的資料時,就很可能會在資料表跳來跳去讀取各個所需要的資料。

為了克服 range query 效率不好的問題, clustered indexes 就出現了!

簡單來說,就是把資料也像 B-tree 索引結構儲存就好,以下稱之為「資料索引」,所以資料索引也會像 B-tree 索引同樣有序,而且樹狀結構長得跟 B-tree 索引相同,因此在做 range query 時,只要知道資料位於 B-tree 索引的哪幾個 nodes (或稱 pages),只要載入相同位置的資料索引 nodes 就可以進一步拿到所有的資料。 後來更演化成直接把資料存在葉節點,也就是 B+ tree ,而且有序保證這些 nodes 一定鄰近彼此,所以還可以連起來,之後就能夠先找到 1 個節點,循序走訪即可載入多個 nodes, 相當有效率!

fig-2.png

p.s. 實際上不同資料庫的實際做法會不太一樣,要注意一下

雖然 clustered indexes 相當有效率,但是使用 clustered indexes 有限制,也就是每個資料表僅能有 1 組 clustered indexes, 這是因為如果要有多組 clustered indexes 的話,就代表資料索引也要建立多組,等於複製多組重複的資料,不僅浪費儲存空間,也增加資料庫的複雜度與降低資料庫效能。

MySQL 的 InnoDB 的 Primary Key 用的就是 B+ tree 的 clustered indexes, 所以對 table 的 primary key 欄位做 query 會相當有效率,也由於 clustered indexes 已經被 Primary Key 用掉了,所以其他的索引都是屬於 non-clustered index, non-clustered index 預設的演算法為 B-tree 。

噢對,也由於 Primary Key 使用 B+ tree 做 index, 所以 Primary Key 是隨機字串或者 UUID 時,在資料量大時會對寫入效能有影響,就是因為 B+ tree 為了要保持葉節點有序,會修改原有樹狀結構,造成多個節點(或稱 pages)需要更新的影響。

以上,就是關於 clustered indexes 的介紹。

Facebook Threads X

對抗久坐職業傷害

研究指出每天增加 2 小時坐著的時間,會增加大腸癌、心臟疾病、肺癌的風險,也造成肩頸、腰背疼痛等常見問題。

然而對抗這些問題,卻只需要工作時定期休息跟伸展身體即可!

你想輕鬆改變現狀嗎?試試看我們的 PomodoRoll 番茄鐘吧! PomodoRoll 番茄鐘會根據你所設定的專注時間,定期建議你 1 項辦公族適用的伸展運動,幫助你打敗久坐所帶來的傷害!

贊助我們的創作

看完這篇文章了嗎? 休息一下,喝杯咖啡吧!

如果你覺得 MyApollo 有讓你獲得實用的資訊,希望能看到更多的技術分享,邀請你贊助我們一杯咖啡,讓我們有更多的動力與精力繼續提供高品質的文章,感謝你的支持!