q*c
发帖数: 9453 | 1 老魏给了模型了，好歹大家能看看咋工作的。你也给个数据库车票模型，大家看看？
说这个是因为昨晚我想上个高端机器看看数据库能到啥程度，结果发现这个不好弄！下
次面试阿三题就这个了：
如何设计一个火车车票数据库模型，支持查询任意给定两站有没有票，有票的话优化座
号多少？ 沿途旅客任意上下车，火车任意增减车厢（所以各点运力不同，，不能换座）
对于数据库锁定交易什么的都是容易， 但是昨晚我想了一会，竟然没法设计出高效的
表来支持这种交易。这个问题很有意思！
这个面试题有意思，有兴趣的都来贡献一下？ |
n*****t
发帖数: 22014 | 2 LOL
【在 q*c 的大作中提到】
: 老魏给了模型了，好歹大家能看看咋工作的。你也给个数据库车票模型，大家看看？
: 说这个是因为昨晚我想上个高端机器看看数据库能到啥程度，结果发现这个不好弄！下
: 次面试阿三题就这个了：
: 如何设计一个火车车票数据库模型，支持查询任意给定两站有没有票，有票的话优化座
: 号多少？ 沿途旅客任意上下车，火车任意增减车厢（所以各点运力不同，，不能换座）
: 对于数据库锁定交易什么的都是容易， 但是昨晚我想了一会，竟然没法设计出高效的
: 表来支持这种交易。这个问题很有意思！
: 这个面试题有意思，有兴趣的都来贡献一下？
|
q*c
发帖数: 9453 | 3 笑啥？给个数据库模型是正经！
【在 n*****t 的大作中提到】
: LOL
|
L*****e
发帖数: 8347 | 4 一个table放车次本身信息，有以下column
车次（primary key），站点，站点顺序，车厢号，车厢种类（硬座，硬卧，软卧），
车厢容量（座位数，卧铺数）
一个辅助table给车厢座位分座号
车次（secondary key），车厢号，座位/卧铺号
另一个table处理和售票有关的信息
车次（secondary key），座位号，20列bool表示该座位在该车次站点的售出情况（假
设20是所有车次最多可有的站点）
★ 发自iPhone App: ChineseWeb 8.2.2
【在 q*c 的大作中提到】
: 老魏给了模型了，好歹大家能看看咋工作的。你也给个数据库车票模型，大家看看？
: 说这个是因为昨晚我想上个高端机器看看数据库能到啥程度，结果发现这个不好弄！下
: 次面试阿三题就这个了：
: 如何设计一个火车车票数据库模型，支持查询任意给定两站有没有票，有票的话优化座
: 号多少？ 沿途旅客任意上下车，火车任意增减车厢（所以各点运力不同，，不能换座）
: 对于数据库锁定交易什么的都是容易， 但是昨晚我想了一会，竟然没法设计出高效的
: 表来支持这种交易。这个问题很有意思！
: 这个面试题有意思，有兴趣的都来贡献一下？
|
n*****t
发帖数: 22014 | 5 你这是强人所难啊，数据库干这活没法高效
【在 q*c 的大作中提到】
: 笑啥？给个数据库模型是正经！
|
w**z
发帖数: 8232 | 6 懂不懂什么叫Shard啊？
【在 n*****t 的大作中提到】
: 你这是强人所难啊，数据库干这活没法高效
|
n*****t
发帖数: 22014 | 7 要快速检索，第三个表不行，必须改成 。。。先不告诉古德八
【在 L*****e 的大作中提到】
: 一个table放车次本身信息，有以下column
: 车次（primary key），站点，站点顺序，车厢号，车厢种类（硬座，硬卧，软卧），
: 车厢容量（座位数，卧铺数）
: 一个辅助table给车厢座位分座号
: 车次（secondary key），车厢号，座位/卧铺号
: 另一个table处理和售票有关的信息
: 车次（secondary key），座位号，20列bool表示该座位在该车次站点的售出情况（假
: 设20是所有车次最多可有的站点）
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
L*****e
发帖数: 8347 | 8 然后看看满足你要求不。
1。给出车次，起点，终点，给出是否有票
第一个table里query，拿到起点，终点的站点顺序
然后车票table里，query有没有一个座位起点号列到终点好列全是true，有这样的row
存在，就有票。
2。座位优化
满足上述条件的rows按座位生存多少排序（true最少的排前面），并检查要求起点站前
一站或者要求终点站后一站是否售出，如果是，优先选择。
3。不同站车厢增减。
更新三个table信息
根据实际运用情况，可以对每个车次生成一个view，方便编程
还有什么其它的，大家补充。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 L*****e 的大作中提到】
: 一个table放车次本身信息，有以下column
: 车次（primary key），站点，站点顺序，车厢号，车厢种类（硬座，硬卧，软卧），
: 车厢容量（座位数，卧铺数）
: 一个辅助table给车厢座位分座号
: 车次（secondary key），车厢号，座位/卧铺号
: 另一个table处理和售票有关的信息
: 车次（secondary key），座位号，20列bool表示该座位在该车次站点的售出情况（假
: 设20是所有车次最多可有的站点）
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
n*****t
发帖数: 22014 | 9 咱俩打个赌，你用 whatever DB，我用草地 C，你的速度能超过我的一半算我输，这个
简单吧
我的算法贴过几次，随便用，不算你抄袭
【在 w**z 的大作中提到】
: 懂不懂什么叫Shard啊？
|
i**i
发帖数: 1500 | 10 RDBMS = no way = Oracle does not have more advantage over TW
If you don't like any sb, use it as the interview question.
座）
【在 q*c 的大作中提到】
: 老魏给了模型了，好歹大家能看看咋工作的。你也给个数据库车票模型，大家看看？
: 说这个是因为昨晚我想上个高端机器看看数据库能到啥程度，结果发现这个不好弄！下
: 次面试阿三题就这个了：
: 如何设计一个火车车票数据库模型，支持查询任意给定两站有没有票，有票的话优化座
: 号多少？ 沿途旅客任意上下车，火车任意增减车厢（所以各点运力不同，，不能换座）
: 对于数据库锁定交易什么的都是容易， 但是昨晚我想了一会，竟然没法设计出高效的
: 表来支持这种交易。这个问题很有意思！
: 这个面试题有意思，有兴趣的都来贡献一下？
|
|
|
L*****e
发帖数: 8347 | 11 当然，真正做系统时，检索这部分恐怕要放到内存数据库中去做，就照你提的算法，然
后把结果更新到硬盘数据库。。。
从另一方面讲，因为检索是可以有延迟的，而且没有写，可以distribute到N个sever上
去做以对付高并发检索。。。
而古德八的出票是异步处理，所以应该也不是大问题，当然，能不能达到他的目标我就
不知道了。应该是还有不小的优化余地。。。我这不是暖暖身，我去面试老q他们组做
做准备么，表太苛求。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 n*****t 的大作中提到】
: 要快速检索，第三个表不行，必须改成 。。。先不告诉古德八
|
t**********1
发帖数: 550 | 12 你太保守了。
可以给wwzz打99折。
他要是持续每秒1万张就算我输。
【在 n*****t 的大作中提到】
: 咱俩打个赌，你用 whatever DB，我用草地 C，你的速度能超过我的一半算我输，这个
: 简单吧
: 我的算法贴过几次，随便用，不算你抄袭
|
n*****t
发帖数: 22014 | 13 不单是这个问题，效率首先不说了，算法首先不对，数据库实现的化，这种结构的表
。。。
我先学习古德八和赵策，晚上给出我的表设计
【在 L*****e 的大作中提到】
: 当然，真正做系统时，检索这部分恐怕要放到内存数据库中去做，就照你提的算法，然
: 后把结果更新到硬盘数据库。。。
: 从另一方面讲，因为检索是可以有延迟的，而且没有写，可以distribute到N个sever上
: 去做以对付高并发检索。。。
: 而古德八的出票是异步处理，所以应该也不是大问题，当然，能不能达到他的目标我就
: 不知道了。应该是还有不小的优化余地。。。我这不是暖暖身，我去面试老q他们组做
: 做准备么，表太苛求。。。
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
n*****t
发帖数: 22014 | 14 俺们这种买卖人都是周扒皮，能不打折尽量不打折，五折其实我已经狠心痛了
【在 t**********1 的大作中提到】
: 你太保守了。
: 可以给wwzz打99折。
: 他要是持续每秒1万张就算我输。
|
t**********1
发帖数: 550 | 15 老姜，你时间好多。
【在 n*****t 的大作中提到】
: 不单是这个问题，效率首先不说了，算法首先不对，数据库实现的化，这种结构的表
: 。。。
: 我先学习古德八和赵策，晚上给出我的表设计
|
w**z
发帖数: 8232 | 16 怎么优化车次？ 上海到北京有很多车，怎么排序？ 需要有个算法。
row
【在 L*****e 的大作中提到】
: 然后看看满足你要求不。
: 1。给出车次，起点，终点，给出是否有票
: 第一个table里query，拿到起点，终点的站点顺序
: 然后车票table里，query有没有一个座位起点号列到终点好列全是true，有这样的row
: 存在，就有票。
: 2。座位优化
: 满足上述条件的rows按座位生存多少排序（true最少的排前面），并检查要求起点站前
: 一站或者要求终点站后一站是否售出，如果是，优先选择。
: 3。不同站车厢增减。
: 更新三个table信息
|
n*****t
发帖数: 22014 | 17 下岗了，穷得只剩时间了
【在 t**********1 的大作中提到】
: 老姜，你时间好多。
|
q*c
发帖数: 9453 | 18 查询给定时间站有没有余票咋整，怎么出优化座位。
【在 L*****e 的大作中提到】
: 一个table放车次本身信息，有以下column
: 车次（primary key），站点，站点顺序，车厢号，车厢种类（硬座，硬卧，软卧），
: 车厢容量（座位数，卧铺数）
: 一个辅助table给车厢座位分座号
: 车次（secondary key），车厢号，座位/卧铺号
: 另一个table处理和售票有关的信息
: 车次（secondary key），座位号，20列bool表示该座位在该车次站点的售出情况（假
: 设20是所有车次最多可有的站点）
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
w**z
发帖数: 8232 | 19 没人和你比单机性能。单机比不过你的计数器，这我承认。只要找到合理的办法和算法
sharding,加机器就行了。
【在 t**********1 的大作中提到】
: 你太保守了。
: 可以给wwzz打99折。
: 他要是持续每秒1万张就算我输。
|
t**********1
发帖数: 550 | 20 咱们这种高端货，打99折wwzz都不敢接。不信你问丫敢接么？
所以zhaoce早就打定主意出来卖一辈子了。啥都不用会，只要抱定卖一辈子的决心就好
了。
【在 n*****t 的大作中提到】
: 俺们这种买卖人都是周扒皮，能不打折尽量不打折，五折其实我已经狠心痛了
|
|
|
w**z
发帖数: 8232 | 21 看，这是问题的关键，怎么shard.
【在 q*c 的大作中提到】
: 查询给定时间站有没有余票咋整，怎么出优化座位。
|
q*c
发帖数: 9453 | 22 你这个查询和座位优化的 sql 还是相当麻烦的， 看下周要出差，可以搞一搞看看能上
多少次。
row
【在 L*****e 的大作中提到】
: 然后看看满足你要求不。
: 1。给出车次，起点，终点，给出是否有票
: 第一个table里query，拿到起点，终点的站点顺序
: 然后车票table里，query有没有一个座位起点号列到终点好列全是true，有这样的row
: 存在，就有票。
: 2。座位优化
: 满足上述条件的rows按座位生存多少排序（true最少的排前面），并检查要求起点站前
: 一站或者要求终点站后一站是否售出，如果是，优先选择。
: 3。不同站车厢增减。
: 更新三个table信息
|
n*****t
发帖数: 22014 | 23 效为先啊，话说我的算法改改不就能建表了摸？
【在 q*c 的大作中提到】
: 你这个查询和座位优化的 sql 还是相当麻烦的， 看下周要出差，可以搞一搞看看能上
: 多少次。
:
: row
|
t**********1
发帖数: 550 | 24 行，用多少台机器随你便，目标10k票每秒。
【在 w**z 的大作中提到】
: 没人和你比单机性能。单机比不过你的计数器，这我承认。只要找到合理的办法和算法
: sharding,加机器就行了。
|
w**z
发帖数: 8232 | 25 说了不和你比无敌计数器。
【在 t**********1 的大作中提到】
: 咱们这种高端货，打99折wwzz都不敢接。不信你问丫敢接么？
: 所以zhaoce早就打定主意出来卖一辈子了。啥都不用会，只要抱定卖一辈子的决心就好
: 了。
|
q*c
发帖数: 9453 | 26 你这有问题。
车次不该包含站点性息。车次站点都是多对多，应该是车次一个表，站点一个表，
车次站点叉一个大表。
车次票另外一个表。
这事情比我想的要复杂。
【在 L*****e 的大作中提到】
: 一个table放车次本身信息，有以下column
: 车次（primary key），站点，站点顺序，车厢号，车厢种类（硬座，硬卧，软卧），
: 车厢容量（座位数，卧铺数）
: 一个辅助table给车厢座位分座号
: 车次（secondary key），车厢号，座位/卧铺号
: 另一个table处理和售票有关的信息
: 车次（secondary key），座位号，20列bool表示该座位在该车次站点的售出情况（假
: 设20是所有车次最多可有的站点）
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
n*****t
发帖数: 22014 | 27 老魏你就是托大，像我这种金算盘随身带的，万年不赔，哈哈
【在 t**********1 的大作中提到】
: 咱们这种高端货，打99折wwzz都不敢接。不信你问丫敢接么？
: 所以zhaoce早就打定主意出来卖一辈子了。啥都不用会，只要抱定卖一辈子的决心就好
: 了。
|
L*****e
发帖数: 8347 | 28 啊？优化车次？又是一个新要求啊。。。车次优劣的比较参数是，出发时间？抵达时间
？经过站数？速度？票价？火车妹妹的漂亮程度？先明确一下嘛。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 w**z 的大作中提到】
: 怎么优化车次？ 上海到北京有很多车，怎么排序？ 需要有个算法。
:
: row
|
q*c
发帖数: 9453 | 29 一半？数据库支持查询index， acid failover 各种操作，有你的c 20分之一就赢了。
【在 n*****t 的大作中提到】
: 咱俩打个赌，你用 whatever DB，我用草地 C，你的速度能超过我的一半算我输，这个
: 简单吧
: 我的算法贴过几次，随便用，不算你抄袭
|
L*****e
发帖数: 8347 | 30 嗯，翘首以待。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 n*****t 的大作中提到】
: 不单是这个问题，效率首先不说了，算法首先不对，数据库实现的化，这种结构的表
: 。。。
: 我先学习古德八和赵策，晚上给出我的表设计
|
|
|
t**********1
发帖数: 550 | 31 wwzz敢接招么。
要支持联票和团体票。
我的单机也支持联票和团体票的transaction。
咱们公平，算的是票数，不是transaction数量。
给你的目标很低，是10k每秒。
我的单机目标很高1mm 每秒。
【在 t**********1 的大作中提到】
: 行，用多少台机器随你便，目标10k票每秒。
|
n*****t
发帖数: 22014 | 32 你们这些家伙，砸我买卖狠好玩吗！
【在 q*c 的大作中提到】
: 一半？数据库支持查询index， acid failover 各种操作，有你的c 20分之一就赢了。
|
q*c
发帖数: 9453 | 33 优化的定义是，出了一张票，导致剩下该列车的连续区间最少（座位碎片最少）
老 bug 给的定义，还是非常准确简单的。
【在 w**z 的大作中提到】
: 怎么优化车次？ 上海到北京有很多车，怎么排序？ 需要有个算法。
:
: row
|
L*****e
发帖数: 8347 | 34 是，这个query效率肯定不高，应该有很大优化余地。。。优化这东西，不具体动手做
个调试很难具体有效。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 q*c 的大作中提到】
: 你这个查询和座位优化的 sql 还是相当麻烦的， 看下周要出差，可以搞一搞看看能上
: 多少次。
:
: row
|
q*c
发帖数: 9453 | 35 你们那几百文，你以为是个人都退休了？有那时间看。
【在 n*****t 的大作中提到】
: 效为先啊，话说我的算法改改不就能建表了摸？
|
w**z
发帖数: 8232 | 36 你的是全国一盘棋。和这不一样。别瞎掺和。我先接孩子。回来再说。
【在 t**********1 的大作中提到】
: wwzz敢接招么。
: 要支持联票和团体票。
: 我的单机也支持联票和团体票的transaction。
: 咱们公平，算的是票数，不是transaction数量。
: 给你的目标很低，是10k每秒。
: 我的单机目标很高1mm 每秒。
|
q*c
发帖数: 9453 | 37 好歹模型设计的时候就不能出发点是线性扫描吧。
【在 L*****e 的大作中提到】
: 是，这个query效率肯定不高，应该有很大优化余地。。。优化这东西，不具体动手做
: 个调试很难具体有效。。。
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
i**i
发帖数: 1500 | 38 1mm is for 1 million ... dollars.
hoho
http://answers.yahoo.com/question/index?qid=20080323155213AAKnv
【在 t**********1 的大作中提到】
: wwzz敢接招么。
: 要支持联票和团体票。
: 我的单机也支持联票和团体票的transaction。
: 咱们公平，算的是票数，不是transaction数量。
: 给你的目标很低，是10k每秒。
: 我的单机目标很高1mm 每秒。
|
q*c
发帖数: 9453 | 39 我觉得 不能 shard. 一 shard 就掉进老魏那难以 transactional 的坑里面去了。
但是可以上多核单机，老 bug 本来也觉得只能单机交易的，问题就是我发现这个模型
不好建。
【在 w**z 的大作中提到】
: 看，这是问题的关键，怎么shard.
|
l*********s
发帖数: 5409 | |
|
|
L*****e
发帖数: 8347 | 41 哦，是有点问题。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 q*c 的大作中提到】
: 你这有问题。
: 车次不该包含站点性息。车次站点都是多对多，应该是车次一个表，站点一个表，
: 车次站点叉一个大表。
: 车次票另外一个表。
: 这事情比我想的要复杂。
|
b*******g
发帖数: 603 | 42 你把问题粒度看得太细，想用数据库锁各段来保证不冲突，就比较麻烦。
外部分好，直接往数据库上写占用结果就很简单。
只要单线程分车次&类型，分票内存只会比数据库多占用，不会错票重票，用数据库向
内存的反向sync保证不丢票。其实是一个特殊情况下可行的分布式交易。
太监成天就要跨DC串糖葫芦，根本没有分析具体问题的能力。
【在 q*c 的大作中提到】
: 我觉得 不能 shard. 一 shard 就掉进老魏那难以 transactional 的坑里面去了。
: 但是可以上多核单机，老 bug 本来也觉得只能单机交易的，问题就是我发现这个模型
: 不好建。
|
