數(shù)據(jù)庫table的index是建立在一個或多個column上的一個數(shù)據(jù)結(jié)構(gòu), 選定的一個或若干個column稱作index的key, 用來加快相應(yīng)key所對應(yīng)的record(tuple)的定位.

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

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

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

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

實(shí)例分析

Microsoft SQL Server 2000

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

2, SQL Server 2000中(后續(xù)版本未確認(rèn)), 如果沒有創(chuàng)建 clustered index, 創(chuàng)建primary key的時候會自動創(chuàng)建clustered index. 更多關(guān)于clustered index, 參見

3, clustered index與non-clustered index都是用B-tree實(shí)現(xiàn)的, 參見 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應(yīng)該盡量小).

MySQL InnoDB & MyISAM

InnoDB 的做法和上面提到的SQL Server的做法差不多:索引都是B樹, 用primary key當(dāng)clustered index, secondary-index中的record locator是clustered index key等. 稍有不同的是, InnoDB在沒有合適的column充當(dāng)cluster key的時候, 會自動創(chuàng)建一個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的值來排序, 因此, 插入過程首先是一個查找的過程, 找到對應(yīng)的位置以后, 除了在data block中插入這個record(可能要引起block split, 因?yàn)檫@個block快滿了), 還要在index里也插入這個key, 同樣也可能引起block split.

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

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

Database Indices