談數(shù)據(jù)庫(kù)索引和Sqlite中索引的使用

很久沒寫博客了，也不是沒時(shí)間，總覺得缺少積累。開了個(gè)獨(dú)立博客 foocoder.com，用octopress搭在github上的。以后可能就只在這上面更新博客。（cnblog，csdn，51cto每個(gè)都去寫很累。。。）。

?

要使用索引對(duì)數(shù)據(jù)庫(kù)的數(shù)據(jù)操作進(jìn)行優(yōu)化，那必須明確幾個(gè)問題：
1.什么是索引
2.索引的原理
3.索引的優(yōu)缺點(diǎn)
4.什么時(shí)候需要使用索引，如何使用
圍繞這幾個(gè)問題，來探究索引在數(shù)據(jù)庫(kù)操作中所起到的作用。

1.數(shù)據(jù)庫(kù)索引簡(jiǎn)介

回憶一下小時(shí)候查字典的步驟，索引和字典目錄的概念是一致的。字典目錄可以讓我們不用翻整本字典就找到我們需要的內(nèi)容頁(yè)數(shù)，然后翻到那一頁(yè)就可以。索引也是一樣，索引是對(duì)記錄按照多個(gè)字段進(jìn)行排序的一種展現(xiàn)。對(duì)表中的某個(gè)字段建立索引會(huì)創(chuàng)建另一種數(shù)據(jù)結(jié)構(gòu)，其中保存著字段的值，每個(gè)值還包括指向與它相關(guān)記錄的指針。這樣，就不必要查詢整個(gè)數(shù)據(jù)庫(kù)，自然提升了查詢效率。同時(shí)，索引的數(shù)據(jù)結(jié)構(gòu)是經(jīng)過排序的，因而可以對(duì)其執(zhí)行二分查找，那就更快了。

?

2. B-樹與索引
大多數(shù)的數(shù)據(jù)庫(kù)都是以B-樹或者B+樹作為存儲(chǔ)結(jié)構(gòu)的，B樹索引也是最常見的索引。先簡(jiǎn)單介紹下B-樹，可以增強(qiáng)對(duì)索引的理解。
B-樹是為磁盤設(shè)計(jì)的一種多叉平衡樹，B樹的真正最準(zhǔn)確的定義為：一棵含有t（t>=2）個(gè)關(guān)鍵字的平衡多路查找樹。一棵M階的B樹滿足以下條件：
1）每個(gè)結(jié)點(diǎn)至多有M個(gè)孩子；
2）除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有M/2個(gè)孩子；
3）根結(jié)點(diǎn)至少有兩個(gè)孩子（除非該樹僅包含一個(gè)結(jié)點(diǎn)）；
4）所有葉結(jié)點(diǎn)在同一層，葉結(jié)點(diǎn)不包含任何關(guān)鍵字信息，可以看作一種外部節(jié)點(diǎn)；
5）有K個(gè)關(guān)鍵字的非葉結(jié)點(diǎn)恰好包含K+1個(gè)孩子；
?B樹中的每個(gè)結(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支(當(dāng)然是不能超過磁盤塊的大小，根據(jù)磁盤驅(qū)動(dòng)(disk drives)的不同，一般塊的大小在1k~4k左右)；這樣樹的深度降低了，這就意味著查找一個(gè)元素只要很少結(jié)點(diǎn)從外存磁盤中讀入內(nèi)存，很快訪問到要查找的數(shù)據(jù)。B-樹上操作的時(shí)間通常由存取磁盤的時(shí)間和CPU計(jì)算時(shí)間這兩部分構(gòu)成。而相對(duì)于磁盤的io速度，cpu的計(jì)算時(shí)間可以忽略不計(jì)，所以B樹的意義就顯現(xiàn)出來了，樹的深度降低，而深度決定了io的讀寫次數(shù)。
B樹索引是一個(gè)典型的樹結(jié)構(gòu)，其包含的組件主要是：
1）葉子節(jié)點(diǎn)（Leaf node）：包含條目直接指向表里的數(shù)據(jù)行。
2）分支節(jié)點(diǎn)（Branch node）：包含的條目指向索引里其他的分支節(jié)點(diǎn)或者是葉子節(jié)點(diǎn)。
3) ?根節(jié)點(diǎn)（Root node）：一個(gè)B樹索引只有一個(gè)根節(jié)點(diǎn)，它實(shí)際就是位于樹的最頂端的分支節(jié)點(diǎn)。
如下圖所示：

?
每個(gè)索引都包含兩部分內(nèi)容，一部分是索引本身的值，第二部分即指向數(shù)據(jù)頁(yè)或者另一個(gè)索引也的指針。每個(gè)節(jié)點(diǎn)即為一個(gè)索引頁(yè)，包含了多個(gè)索引。
當(dāng)你為一個(gè)空表建立一個(gè)索引，數(shù)據(jù)庫(kù)會(huì)分配一個(gè)空的索引頁(yè)，這個(gè)索引頁(yè)即代表根節(jié)點(diǎn)，在你插入數(shù)據(jù)之前，這個(gè)索引頁(yè)都是空的。每當(dāng)你插入數(shù)據(jù)，數(shù)據(jù)庫(kù)就會(huì)在根節(jié)點(diǎn)創(chuàng)建索引條目，。當(dāng)根節(jié)點(diǎn)插滿的時(shí)候，再插入數(shù)據(jù)時(shí)，根節(jié)點(diǎn)就會(huì)分裂。舉個(gè)例子，根節(jié)點(diǎn)插入了如圖所示的數(shù)據(jù)。（超過4個(gè)就分裂），這時(shí)候插入H，就會(huì)分裂成2個(gè)節(jié)點(diǎn)，移動(dòng)G到新的根節(jié)點(diǎn)，把H和N放在新的右孩子節(jié)點(diǎn)中。如圖所示：
? ??
　　　　根節(jié)點(diǎn)插滿4個(gè)節(jié)點(diǎn)
? ??
　　　　　　插入H，進(jìn)行分裂。

大致的分裂步驟如下：
1）創(chuàng)建兩個(gè)兒子節(jié)點(diǎn)
2）將原節(jié)點(diǎn)中的數(shù)據(jù)近似分為兩半，寫入兩個(gè)新的孩子節(jié)點(diǎn)中。
3）在跟節(jié)點(diǎn)中放置指向頁(yè)節(jié)點(diǎn)的指針

當(dāng)你不斷向表中插入數(shù)據(jù)，根節(jié)點(diǎn)中指向葉節(jié)點(diǎn)的指針也被插滿，當(dāng)葉子還需要分裂的時(shí)候，根節(jié)點(diǎn)沒有空間再創(chuàng)建指向新的葉節(jié)點(diǎn)的指針。那么數(shù)據(jù)庫(kù)就會(huì)創(chuàng)建分支節(jié)點(diǎn)。隨著葉子節(jié)點(diǎn)的分裂，根節(jié)點(diǎn)中的指針都指向了這些分支節(jié)點(diǎn)。隨著數(shù)據(jù)的不斷插入，索引會(huì)增加更多的分支節(jié)點(diǎn)，使樹結(jié)構(gòu)變成這樣的一個(gè)多級(jí)結(jié)構(gòu)。

?

3. 索引的種類

1）聚集索引：表中行的物理順序與鍵值的邏輯（索引）順序相同。因?yàn)閿?shù)據(jù)的物理順序只能有一種，所以一張表只能有一個(gè)聚集索引。如果一張表沒有聚集索引，那么這張表就沒有順序的概念，所有的新行都會(huì)插入到表的末尾。對(duì)于聚集索引，葉節(jié)點(diǎn)即存儲(chǔ)了數(shù)據(jù)行，不再有單獨(dú)的數(shù)據(jù)頁(yè)。就比如說我小時(shí)候查字典從來不看目錄，我覺得字典本身就是一個(gè)目錄，比如查裴字，只需要翻到p字母開頭的，再按順序找到e。通過這個(gè)方法我每次都能最快的查到老師說的那個(gè)字，得到老師的表?yè)P(yáng)。

?

2）非聚集索引：表中行的物理順序與索引順序無關(guān)。對(duì)于非聚集索引，葉節(jié)點(diǎn)存儲(chǔ)了索引字段值以及指向相應(yīng)數(shù)據(jù)頁(yè)的指針。葉節(jié)點(diǎn)緊鄰在數(shù)據(jù)之上，對(duì)數(shù)據(jù)頁(yè)的每一行都有相應(yīng)的索引行與之對(duì)應(yīng)。有時(shí)候查字典，我并不知道這個(gè)字讀什么，那我就不得不通過字典目錄的“部首”來查找了。這時(shí)候我會(huì)發(fā)現(xiàn)，目錄中的排序和實(shí)際正文的排序是不一樣的，這對(duì)我來說很苦惱，因?yàn)槲也荒鼙葎e人快了，我需要先再目錄中找到這個(gè)字，再根據(jù)頁(yè)數(shù)去找到正文中的字。?

?

4．索引與數(shù)據(jù)的查詢，插入與刪除

1）查詢。查詢操作就和查字典是一樣的。當(dāng)我們?nèi)ゲ檎抑付ㄓ涗洉r(shí)，數(shù)據(jù)庫(kù)會(huì)先查找根節(jié)點(diǎn)，將待查數(shù)據(jù)與根節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行比較，再通過根節(jié)點(diǎn)的指針查詢下一個(gè)記錄，直到找到這個(gè)記錄。這是一個(gè)簡(jiǎn)單的平衡樹的二分搜索的過程，我就不贅述了。在聚集索引中，找到頁(yè)節(jié)點(diǎn)即找到了數(shù)據(jù)行，而在非聚集索引中，我們還需要再去讀取數(shù)據(jù)頁(yè)。

?

2）插入。聚集索引的插入操作比較復(fù)雜，最簡(jiǎn)單的情況，插入操作會(huì)找到對(duì)于的數(shù)據(jù)頁(yè)，然后為新數(shù)據(jù)騰出空間，執(zhí)行插入操作。如果該數(shù)據(jù)頁(yè)已經(jīng)沒有空間，那就需要拆分?jǐn)?shù)據(jù)頁(yè)，這是一個(gè)非常耗費(fèi)資源的操作。對(duì)于僅有非聚集索引的表，插入只需在表的末尾插入即可。如果也包含了聚集索引，那么也會(huì)執(zhí)行聚集索引需要的插入操作。

?

3）刪除。刪除行后下方的數(shù)據(jù)會(huì)向上移動(dòng)以填補(bǔ)空缺。如果刪除的數(shù)據(jù)是該數(shù)據(jù)頁(yè)的最后一行，那么這個(gè)數(shù)據(jù)頁(yè)會(huì)被回收，它的前后一頁(yè)的指針會(huì)被改變，被回收的數(shù)據(jù)頁(yè)也會(huì)在特定的情況被重新使用。與此同時(shí)，對(duì)于聚集索引，如果索引頁(yè)只剩一條記錄，那么該記錄可能會(huì)移動(dòng)到鄰近的索引表中，原來的索引頁(yè)也會(huì)被回收。而非聚集索引沒辦法做到這一點(diǎn)，這就會(huì)導(dǎo)致出現(xiàn)多個(gè)數(shù)據(jù)頁(yè)都只有少量數(shù)據(jù)的情況。

?

5. 索引的優(yōu)缺點(diǎn)
其實(shí)通過前面的介紹，索引的優(yōu)缺點(diǎn)已經(jīng)一目了然。
先說優(yōu)點(diǎn)：
? ? 1）大大加快數(shù)據(jù)的檢索速度，這也是創(chuàng)建索引的最主要的原因
? ? 2）加速表和表之間的連接，特別是在實(shí)現(xiàn)數(shù)據(jù)的參考完整性方面特別有意義。

? ? 3）在使用分組和排序子句進(jìn)行數(shù)據(jù)檢索時(shí)，同樣可以顯著減少查詢中分組和排序的時(shí)間。

?

? ?再說缺點(diǎn)：
? 1）創(chuàng)建索引需要耗費(fèi)一定的時(shí)間，但是問題不大，一般索引只要build一次
? 2）索引需要占用物理空間，特別是聚集索引，需要較大的空間

? 3）當(dāng)對(duì)表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時(shí)候，索引也要?jiǎng)討B(tài)的維護(hù)，降低了數(shù)據(jù)的維護(hù)速度，這個(gè)是比較大的問題。

?

6.索引的使用
? ? ? ?根據(jù)上文的分析，我們大致對(duì)什么時(shí)候使用索引有了自己的想法（如果你沒有，回頭再看一遍。。。）。一般我們需要在這些列上建立索引：
1）在經(jīng)常需要搜索的列上，這是毋庸置疑的；?
2）經(jīng)常同時(shí)對(duì)多列進(jìn)行查詢，且每列都含有重復(fù)值可以建立組合索引，組合索引盡量要使常用查詢形成索引覆蓋（查詢中包含的所需字段皆包含于一個(gè)索引中，我們只需要搜索索引頁(yè)即可完成查詢）。 同時(shí)，該組合索引的前導(dǎo)列一定要是使用最頻繁的列。對(duì)于前導(dǎo)列的問題，在后面sqlite的索引使用介紹中還會(huì)做討論。
3）在經(jīng)常用在連接的列上，這些列主要是一些外鍵，可以加快連接的速度，連接條件要充分考慮帶有索引的表。；?

4）在經(jīng)常需要對(duì)范圍進(jìn)行搜索的列上創(chuàng)建索引，因?yàn)樗饕呀?jīng)排序，其指定的范圍是連續(xù)的，同樣，在經(jīng)常需要排序的列上最好也創(chuàng)建索引。

6）在經(jīng)常放到where子句中的列上面創(chuàng)建索引，加快條件的判斷速度。要注意的是where字句中對(duì)列的任何操作（如計(jì)算表達(dá)式，函數(shù)）都需要對(duì)表進(jìn)行整表搜索，而沒有使用該列的索引。所以查詢時(shí)盡量把操作移到等號(hào)右邊。

?

對(duì)于以下的列我們不應(yīng)該創(chuàng)建索引：
1）很少在查詢中使用的列
2）含有很少非重復(fù)數(shù)據(jù)值的列，比如只有0，1，這時(shí)候掃描整表通常會(huì)更有效
3）對(duì)于定義為TEXT，IMAGE的數(shù)據(jù)不應(yīng)該創(chuàng)建索引。這些字段長(zhǎng)度不固定，或許很長(zhǎng)，或許為空。
當(dāng)然，對(duì)于更新操作遠(yuǎn)大于查詢操作時(shí)，不建立索引。也可以考慮在大規(guī)模的更新操作前drop索引，之后重新創(chuàng)建，不過這就需要把創(chuàng)建索引對(duì)資源的消耗考慮在內(nèi)。總之，使用索引需要平衡投入與產(chǎn)出，找到一個(gè)產(chǎn)出最好的點(diǎn)。

7. 在sqlite中使用索引?

1）Sqlite不支持聚集索引，android默認(rèn)需要一個(gè)_id字段，這保證了你插入的數(shù)據(jù)會(huì)按“_id”的整數(shù)順序插入，這個(gè)integer類型的主鍵就會(huì)扮演和聚集索引一樣的角色。所以不要再在對(duì)于聲明為：INTEGER PRIMARY KEY的主鍵上創(chuàng)建索引。

?

2）很多對(duì)索引不熟悉的朋友在表中創(chuàng)建了索引，卻發(fā)現(xiàn)沒有生效，其實(shí)這大多數(shù)和我接下來講的有關(guān)。對(duì)于where子句中出現(xiàn)的列要想索引生效，會(huì)有一些限制，這就和前導(dǎo)列有關(guān)。所謂前導(dǎo)列，就是在創(chuàng)建復(fù)合索引語(yǔ)句的第一列或者連續(xù)的多列。比如通過：CREATE INDEX comp_ind ON table1(x, y, z)創(chuàng)建索引，那么x,xy,xyz都是前導(dǎo)列，而yz，y，z這樣的就不是。下面講的這些，對(duì)于其他數(shù)據(jù)庫(kù)或許會(huì)有一些小的差別，這里以sqlite為標(biāo)準(zhǔn)。在where子句中，前導(dǎo)列必須使用等于或者in操作，最右邊的列可以使用不等式，這樣索引才可以完全生效。同時(shí)，where子句中的列不需要全建立了索引，但是必須保證建立索引的列之間沒有間隙。舉幾個(gè)例子來看吧：

?

用如下語(yǔ)句創(chuàng)建索引：
CREATE INDEX idx_ex1 ON ex1(a,b,c,d,e,...,y,z);
這里是一個(gè)查詢語(yǔ)句：
...WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'
這顯然對(duì)于abcd四列都是有效的，因?yàn)橹挥械扔诤蚷n操作，并且是前導(dǎo)列。
再看一個(gè)查詢語(yǔ)句：
... WHERE a=5 AND b IN (1,2,3) AND c>12 AND d='hello'
那這里只有a，b和c的索引會(huì)是有效的，d列的索引會(huì)失效，因?yàn)樗赾列的右邊，而c列使用了不等式，根據(jù)使用不等式的限制，c列已經(jīng)屬于最右邊。
最后再看一條：
... WHERE b IN (1,2,3) AND c NOT NULL AND d='hello'

索引將不會(huì)被使用，因?yàn)闆]有使用前導(dǎo)列，這個(gè)查詢會(huì)是一個(gè)全表查詢。

?

其實(shí)除了索引，對(duì)查詢性能的影響因素還有很多，比如表的連接，是否排序等。影響數(shù)據(jù)庫(kù)操作的整體性能就需要考慮更多因素，使用更對(duì)的技巧，不得不說這是一個(gè)很大的學(xué)問。

?

最后在android上使用sqlite寫一個(gè)簡(jiǎn)單的例子，看下索引對(duì)數(shù)據(jù)庫(kù)操作的影響。
創(chuàng)建如下表和索引：
?? db.execSQL("create table if not exists t1(a,b)"); ? ? ? ?
? ?db.execSQL("create index if not exists ia on t1(a,b)");
插入10萬(wàn)條數(shù)據(jù)，分別對(duì)表進(jìn)行如下操作：
select * from t1 where a='90012'
插入：insert into t1(a,b) values('10008','name1.6982235534984673')
更新：update t1 set b='name1.999999' where a = '887'

刪除：delete from t1 where a = '1010'

?

數(shù)據(jù)如下（5次不同的操作取平均值）：
操作 ??無索引 ? ?有索引
查詢 ??170ms ?5ms
插入 ??65ms ??75ms
更新 ??240ms ?52ms
刪除 ??234ms ?78ms

? ? ? ? 可以看到顯著提升了查詢的速度，稍稍減慢了插入速度，還稍稍提升了更新數(shù)據(jù)和刪除數(shù)據(jù)的速度。如果把更新和刪除中的where子句中的列換成b，速度就和沒有索引一樣了，因?yàn)樗饕АＫ运饕艽蠓忍嵘樵兯俣?，?duì)于刪除和更新操作，如果where子句中的列使用了索引，即使需要重新build索引，有可能速度還是比不使用索引要快的。對(duì)與插入操作，索引顯然是個(gè)負(fù)擔(dān)。同時(shí)，索引讓db的大小增加了2倍多。

?

? ? ? ?還有個(gè)要吐槽的是，android中的rawQurey方法，執(zhí)行完sql語(yǔ)句后返回一個(gè)cursor，其實(shí)并沒有完成一個(gè)查詢操作，我在rawquery之前和之后計(jì)算查詢時(shí)間，永遠(yuǎn)是1ms...這讓我無比苦悶。看了下源碼，在對(duì)cursor調(diào)用moveToNext這些移動(dòng)游標(biāo)方法時(shí)，都會(huì)最終先調(diào)用getCount方法，而getCount方法才會(huì)調(diào)用native方法調(diào)用真正的查詢操作。這種設(shè)計(jì)顯然更加合理。