求知 文章 文库 Lib 视频 iPerson 课程 认证 咨询 工具 讲座 Modeler   Code  
会员   
 
  
 
 
 
公交车路线查询系统后台数据库设计—换乘算法改进与优化
 

2010-07-22 来源:book.csdn.net

 

在《查询算法》一文中已经实现了换乘算法,但是,使用存储过程InquiryT2查询从“东圃镇”到“车陂路口”的乘车路线时,发现居然用了5分钟才查找出结果,这样的效率显然不适合实际应用。因此,有必要对原有的换乘算法进行优化和改进。在本文中,将给出一种改进的换乘算法,相比原有的算法,改进后的算法功能更强,效率更优。

1. “压缩”RouteT0

假设RouteT0有以下几行

如下图所示,当查询S1到S4的二次换乘路线时,将会产生3×2×4=24个结果

从图中可以看出,第1段路线中的3条线路的起点和站点都相同(第2、3段路线也是如此),事实上,换乘查询中关心的是两个站点之间有无线路可通,而不关心是乘坐什么路线,因此,可以将RouteT0压缩为:

如下图所示,压缩后,查询结果有原来的24条合并1组

查询结果为:

那么,为什么要对视图RouteT0进行压缩呢,原因如下:

(1)RouteT0是原有换乘算法频繁使用的视图,因此,RouteT0的数据量直接影响到查询的效率,压缩RouteT0可以减少RouteT0的数据量,加速查询效率。

(2)压缩RouteT0后,将中转站点相同的路线合并为1组,加速了对结果集排序的速度。

2.视图GRouteT0

在数据库中,将使用GRouteT0来描述压缩的RouteT0,由于本文使用的数据库的关系图与《查询算法》中有所不同,在给出GRouteT0的代码前,先说明一下:

主要的改变是Stop_Route使用了整数型的RouteKey和StopKey引用Route和Stop,而不是用路线名和站点名。

GRouteT0定义如下: 

create view GRouteT0
as
select 
    StartStopKey,
    EndStopKey,
    
min(StopCount) as MinStopCount,
    
max(StopCount) as MaxStopCount
from RouteT0
group by StartStopKey,EndStopKey

注意,视图GRouteT0不仅有StartStopKey和EndStopKey列,还有MinStopCount列,MinStopCount是指从StartStop到EndStop的最短线路的站点数。例如:上述RouteT0对应的GRouteT0为:

3.二次查询算法

以下是二次换乘查询的存储过程GInquiryT2的代码,该存储过程使用了临时表来提高查询效率: 


/*
查询站点@StartStops到站点@EndStops之间的二次换乘乘车路线,多个站点用'/'分开,结果以分组方式给出,如:
exec InquiryT2 '站点1/站点2','站点3/站点4'
*/

CREATE     proc GInquiryT2(
    
@StartStops varchar(2048),
    
@EndStops varchar(2048)
)
as
begin
    
declare @ss_tab table(StopKey int)
    
d


MySQL索引背后的数据结构
MySQL性能调优与架构设计
SQL Server数据库备份与恢复
让数据库飞起来 10大DB2优化
oracle的临时表空间写满磁盘
数据库的跨平台设计
更多...   


并发、大容量、高性能数据库
高级数据库架构设计师
Hadoop原理与实践
Oracle 数据仓库
数据仓库和数据挖掘
Oracle数据库开发与管理


GE 区块链技术与实现培训
航天科工某子公司 Nodejs高级应用开发
中盛益华 卓越管理者必须具备的五项能力
某信息技术公司 Python培训
某博彩IT系统厂商 易用性测试与评估
中国邮储银行 测试成熟度模型集成(TMMI)
中物院 产品经理与产品管理
更多...