數據庫table的index是建立在一個或多個column上的一個數據結構, 選定的一個或若干個column稱作index的key, 用來加快相應key所對應的record(tuple)的定位.

從數據結構的角度來看, 索引是一個map, 將key映射到對應的record的指針. 索引能提供更好的查找性能, 關鍵之處在于, 一個block可以存儲的(key, pointer_to_record)是可以很多的, 要遠大于一個block存儲的record的個數, 這意味著查找過程中磁盤io可以大大減少.索引可以分為dense index和sparse index, 前者對于每個record都建立索引, 后者只對一個block上存儲的多個record中的某一個(如第一個)建立索引.

最直接的構建索引想法就是將key所在的column提取出來, 排序之后存儲起來即可. 之后, 查找過程就可以二分來進行. 如果索引本身也比較大, 那進一步可以對索引再做索引, 沿著這個思路走下去, 就得到了B樹了, 下圖是一棵B+樹.

Non-clustered Index : record本身不按照該index排序(當然, index內的key是排序的), 只不過index內的指針指向了不同的record位置.

Clustered Index : record按照該index的key來排序, 即存儲在data block里面的record是按照這個index排序的. 換句話說,這個index的key決定了record是如何存儲的.

實例分析

Microsoft SQL Server 2000

1, 如何創建index, 參見 http://msdn.microsoft.com/en-us/library/aa258260(v=SQL.80).aspx

2, SQL Server 2000中(后續版本未確認), 如果沒有創建 clustered index, 創建primary key的時候會自動創建clustered index. 更多關于clustered index, 參見

3, clustered index與non-clustered index都是用B-tree實現的, 參見 http://msdn.microsoft.com/en-us/library/aa174523(v=SQL.80).aspx

與 http://msdn.microsoft.com/en-us/library/aa174537(v=SQL.80).aspx

4, Non-clustered index中, 如果這張表有clustered index, non-clustered index的pointer存儲的是clustered index key (因此clustered index key應該盡量小).

MySQL InnoDB & MyISAM

InnoDB 的做法和上面提到的SQL Server的做法差不多:索引都是B樹, 用primary key當clustered index, secondary-index中的record locator是clustered index key等. 稍有不同的是, InnoDB在沒有合適的column充當cluster key的時候, 會自動創建一個column來作為cluster index key column, 參見 http://dev.mysql.com/doc/refman/5.5/en/innodb-index-types.html

MySQL的另一個存儲引擎, MyISAM , 做法就土了. MyISAM中, 沒有clustered index, 所有的record locator都直接指向record的位置. InnoDB與MyISAM在index上的對比參見 http://www.xaprb.com/blog/2006/07/04/how-to-exploit-mysql-index-optimizations/

Clustered Index 與record的插入

Clustered Index要求record按照cluster index key的值來排序, 因此, 插入過程首先是一個查找的過程, 找到對應的位置以后, 除了在data block中插入這個record(可能要引起block split, 因為這個block快滿了), 還要在index里也插入這個key, 同樣也可能引起block split.

同理, 刪除的時候也會有這樣的問題.

也正是這個原因, SQL Server和InnoDB的secondary index的record locator存儲的都是clustered index key, 這樣, secondary index就獨立出去了, 不用每次更新都要更新所有的index. 代價是secondary index查完以后, 還要再拿得到的key再走一遍clustered index, 不過clustered index基本上都在內存里面了, 而且就是用來做快速訪問的(良好優化過了), 所以仍然是值得的.

Database Indices