白話文解說 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 裡指向的資料位置，最後去取出相對應的資料。

但這種索引對於 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, 相當有效率！

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 的介紹。