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

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

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

2)采用Dijkstra或者Floyd算法或者改進的Dijkstra算法；

3)基于矩陣的運算；

由于在做這個系統(tǒng)之前就想過這個問題，是采用Dijkstra算法、矩陣運算還是基于數(shù)據(jù)庫的查詢。仔細分析之后還是選擇了基于數(shù)據(jù)庫的查詢，因為對于大中型城市的公交網(wǎng)絡(luò)，Dijkstra算法和矩陣運算根本不適用，尤其還是基于Android系統(tǒng)的公交查詢系統(tǒng)(離線查詢系統(tǒng))，舉個例子，像成都市的公交網(wǎng)絡(luò)系統(tǒng)有將近500條公交線路，5000個公交站點，如果采用矩陣運算或者Dijkstra算法的話，就只是直達矩陣就得有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)在進行一次換乘查詢的時候需要直達站點信息，因此添加了一個視圖direct

direct的字段：

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

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

1)直達方案的話，直接在direct中進行查詢：

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

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

?? 查詢耗時：119.05ms

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

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

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

在創(chuàng)建索引之后，重新將上面的一次換乘查詢語句執(zhí)行了一次，耗時：5.59ms，查詢速度提升了將近80倍，然后又將直達查詢語句執(zhí)行了一次，耗時0.49ms，也明顯提升了不少。然后按照一次換乘的思路寫出了二次換乘的sql語句進行執(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ū)別簡直是天壤之別，適當?shù)亟⑺饕軌蚴共樵兯俣忍嵘艽?，關(guān)于索引的相關(guān)問題準備在后面進行進一步學習和研究。

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

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

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

廣告

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