數(shù)據(jù)庫查詢性能優(yōu)化之利器—索引（一）

最近在做基于Android的公交查詢系統(tǒng)的過程中，遇到一個很棘手的問題：換乘算法效率低。在直達(dá)查詢和一次換乘查詢的時候，問題體現(xiàn)的還不是很明顯，能夠在1s之內(nèi)查詢出乘車方案，而當(dāng)進(jìn)行二次查詢的時候，基本要等一兩分鐘才能查詢出換乘方案，這對于公交查詢系統(tǒng)是絕對無法容忍的。于是找了大量的關(guān)于公交換乘算法方面的論文和資料進(jìn)行研究，發(fā)現(xiàn)大多治標(biāo)不治本，沒有從根本上解決公交換乘算法效率低下的問題。公交換乘算法主要有以下三種思路：

　　1)基于數(shù)據(jù)庫的查詢；

　　2)采用Dijkstra或者Floyd算法或者改進(jìn)的Dijkstra算法；

　　3)基于矩陣的運算；

　　由于在做這個系統(tǒng)之前就想過這個問題，是采用Dijkstra算法、矩陣運算還是基于數(shù)據(jù)庫的查詢。仔細(xì)分析之后還是選擇了基于數(shù)據(jù)庫的查詢，因為對于大中型城市的公交網(wǎng)絡(luò)，Dijkstra算法和矩陣運算根本不適用，尤其還是基于Android系統(tǒng)的公交查詢系統(tǒng)(離線查詢系統(tǒng))，舉個例子，像成都市的公交網(wǎng)絡(luò)系統(tǒng)有將近500條公交線路，5000個公交站點，如果采用矩陣運算或者Dijkstra算法的話，就只是直達(dá)矩陣就得有5000*5000=25000000個數(shù)據(jù)，若數(shù)據(jù)采用int類型保存，則該矩陣得占用25000000*4/(1024*1024*8)=12M的內(nèi)存空間，這個數(shù)據(jù)對于移動設(shè)備來說想而知，是不可取的辦法。因此最后采用了基于數(shù)據(jù)庫查詢的方案。

　　在我的數(shù)據(jù)庫中有兩張表：cnbusw(線路表),cnbus(站點線路表)

???? cnbusw的字段：

???? id：線路編號，busw：線路名稱，shijian：起始站和起始時間描述；

???? cnbus的字段：

　　zhan:站點名，xid：對應(yīng)的線路編號，pm：在該線路中的位置，kind：線路類型(去程or返程or環(huán)形路線)

　　后來發(fā)現(xiàn)在進(jìn)行一次換乘查詢的時候需要直達(dá)站點信息，因此添加了一個視圖direct

　　direct的字段：

　　start：起始站，end：終點站，route：對應(yīng)的線路編號，stopcount：兩站之間的站點數(shù)

　　在數(shù)據(jù)庫中進(jìn)行測試了一下：

　　1)直達(dá)方案的話，直接在direct中進(jìn)行查詢：

　　　比如下面一條sql查詢語句:

select?*?from?direct?where?start='磨子橋'?and?end='春熙路南口'

　　?? 查詢耗時：119.05ms

　　2)一次換乘查詢方案，通過direct的自連接進(jìn)行查詢：

　　?? 比如下面一條sql查詢語句：

select?s1.start?as?start,s1.route?as?route1,s1.end?as?zhuan,s2.route?as?route2,
s2.end?as?end,s1.stopcount?as?count1,s2.stopcount?as?count2,(s1.stopcount+s2.stopcount)?
as?stopcount?from?direct?s1,direct?s2?where?s1.start='崔家店'?and?s2.end='磨子橋'?and?s1.end=s2.start?and?s1.route!=s2.route?order?by?(s1.stopcount+s2.stopcount)

　　?? 查詢耗時：415.32ms

　　上述查詢時間都在能夠接受的范圍之內(nèi)，然后我很自然地按照上面的思路寫出了三次換乘的sql查詢語句，結(jié)果在查詢時發(fā)現(xiàn)等了一分鐘還沒等出結(jié)果，并且sqlite可視化管理工具界面卡死了，這個很明顯地告訴我二次換乘直接使用這樣的sql語句是絕對不可行的，于是我想了一些辦法，比如：兩次換乘相當(dāng)于是A->B->C->D，那么先查詢經(jīng)過站點D的線路中站點序號比D小的站點集合U，然后就相當(dāng)于查詢A到U集合中所有站點的一次換乘查詢，這樣就方便了，但是用sql語句查詢了一下，一般U集合的大小都在400左右，然后要進(jìn)行400次一次換乘查詢，耗時400ms*400=160000ms=160s，怎么也得2分多鐘，顯然不可取。在陷入了這樣的僵局之后，想了很久沒想到辦法，因為數(shù)據(jù)庫里面的數(shù)據(jù)量很大，簡單地對sql語句進(jìn)行改進(jìn)無法解決根本性問題。只有從數(shù)據(jù)庫本身著手，于是想到了索引，以前上數(shù)據(jù)庫課程的時候，老師提到過索引對于大量數(shù)據(jù)查詢的時候效率提升的很明顯，于是就嘗試了一下，發(fā)現(xiàn)查詢耗時一下減少了很多。在建立索引的過程中，原本想在視圖上建立索引，發(fā)現(xiàn)似乎sqlite不支持在視圖上創(chuàng)建索引，于是刪除了direct視圖，建立了direct直達(dá)表，在建立索引的時候，考慮是建立多列索引還是單列索引，分析一次換乘查詢發(fā)現(xiàn)要將start，end，route這三列同時作為查詢條件，并且要對stopcount進(jìn)行排序，因此選擇創(chuàng)建多列索引：

create?index?directindex?on?direct(start,end,route,stopcount)

　　在創(chuàng)建索引之后，重新將上面的一次換乘查詢語句執(zhí)行了一次，耗時：5.59ms，查詢速度提升了將近80倍，然后又將直達(dá)查詢語句執(zhí)行了一次，耗時0.49ms，也明顯提升了不少。然后按照一次換乘的思路寫出了二次換乘的sql語句進(jìn)行執(zhí)行，

select?s1.start?as?start,s1.xid?as?route1,s1.end?as?zhuan1,s2.xid?as?route2?,
s2.end?as?zhuan2,s3.xid?as?route3,s3.end?as?end,s1.stopcount,s2.stopcount,s3.stopcount,
(s1.stopcount+s2.stopcount+s3.stopcount)?from?direct?s1,direct?s2,direct?s3?where?s1.start='川大路黃河路口'?and?s3.end='春熙路南口'?and?s1.end=s2.start?and?s2.end=s3.start?
and?s1.xid!=s2.xid?and?s2.xid!=s3.xid?order?by?s1.stopcount+s2.stopcount+s3.stopcount

　　耗時411.15ms，很好地解決查詢效率低下的問題，從這里可以看出，在數(shù)據(jù)量很大的情況，建立索引和沒有索引的區(qū)別簡直是天壤之別，適當(dāng)?shù)亟⑺饕軌蚴共樵兯俣忍嵘艽?，關(guān)于索引的相關(guān)問題準(zhǔn)備在后面進(jìn)行進(jìn)一步學(xué)習(xí)和研究。

?