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

目前成都創(chuàng)新互聯(lián)已為上千余家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、網(wǎng)站托管、服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、懷遠(yuǎn)網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

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

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

3)基于矩陣的運(yùn)算；

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

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

cnbusw的字段：

id：線路編號(hào)，busw：線路名稱，shijian：起始站和起始時(shí)間描述；

cnbus的字段：

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

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

direct的字段：

start：起始站，end：終點(diǎn)站，route：對(duì)應(yīng)的線路編號(hào)，stopcount：兩站之間的站點(diǎn)數(shù)

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

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

比如下面一條sql查詢語(yǔ)句:

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

?? 查詢耗時(shí)：119.05ms

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

?? 比如下面一條sql查詢語(yǔ)句：

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)

?? 查詢耗時(shí)：415.32ms

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

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

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

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

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

網(wǎng)頁(yè)標(biāo)題：數(shù)據(jù)庫(kù)查詢性能優(yōu)化之利器—索引（一）-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://www.rwnh.cn/article46/ddcceg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、微信小程序、商城網(wǎng)站、虛擬主機(jī)、App開發(fā)、網(wǎng)頁(yè)設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)