对Google算法优越性的一点小体会

lose

原帖由 zszyj 于 2008-6-24 16:51 发表

数据库的索引算法是b-tree, 自已拿本数据库原理的书看看吧. 其中一书中也有介绍这个算法. 都是由数据库实现了的, 开发人员根本不需要自已重新实现.
B-tree最大的作用, 就是数据量几何增长的情况下,而查找时间 ...

多谢指点，一眼看到以为是数据结构，再看是数据库原理，好我去看看。

zszyj

原帖由 lose 于 2008-6-24 16:55 发表

多谢指点，一眼看到以为是数据结构，再看是数据库原理，好我去看看。

"数据结构"是很多年前看的书了, 印象中在排序和查找一章中,是有b-tree算法的. 也可能是我记错了, 不妨看看.

system888net

  继续关注大家的讨论!

bbpet

原帖由 可恶的 于 2008-6-24 13:04 发表
期待bbpet的结果。
晚上再来关注。

呵呵，晚上踢球去了，不幸让你等惨了~
这回的结果让我相当的吃惊，居然到了0.1ms的级别去了

由于自己对db不熟，这回干脆让做数据库维护的人测，应该不犯错了
主机z990（长进了，不用s390了），两张表，一张7亿数据，另一张30亿
查找索引，两张表结果一样，联机查5-6ms，批量1ms以下
囧rz，差一个数据级的记录数竟然结果没有啥差别
由批量时间和数据量得出的结果，非主索引，0.001s以下，主索引0.0001s左右
靠，无语了，看来主要还是看索引设置
联机5-6ms的原因，是有很多相对查询比较耗时的操作混在中间
仅就db查询而言，批量那个比较准确，对于查用户名这种，联机的时间似乎更有参考价值~

that is all，期待高人出来讲解，因为这个数据太无敌了，db的强悍超出了我的想象
也可指点下是不是测试方法有不妥或有改进的地方……

wwwsq

用“布隆过滤器”可以瞬间进行判断，这个用户名是否已经被用过。

不用查数据库，也不用查RB-Tree。

过滤器的构建：构造一个巨大的bit array，比如10亿比特（占用约125 M内存），把这个array的所有bit都初始化为零。然后把现有的user name都做hash，再把hash结果对10亿求余。得到的余数作为bit array的偏移量，把这个bit置1

过滤器的使用：把新的用户名求hash再对10亿求余，得到的余数作为array的偏移量，看这个bit是否为零。为零则这个新的用户名肯定没被用过；为1则99%的可能已经被用过了，那么就告诉用户这个用户名已经被用过了。

[ 本帖最后由 wwwsq 于 2008-6-25 00:14 编辑 ]

leotalk

无语，一个字符串匹配，就算法优越了？

省省吧，就搜索算法这玩意，以目前的理论水平，在没有获得重大突破前，google与其它公司不过50步与100步的差别，在某些领域还差些。

瞧你们吹捧的，大汗... ...

评论的诸位，估计连个算法导论都没看个全，话说回来便是看个全也不顶用，在国内，诸位怕是都没有这样的工程实践机会

最后，提醒一下楼主，这么随随便便就给Gmail用户上亿了，当真了不得，

emacsnw

原帖由 leotalk 于 2008-6-24 08:14 发表
无语，一个字符串匹配，就算法优越了？

省省吧，就搜索算法这玩意，以目前的理论水平，在没有获得重大突破前，google与其它公司不过50步与100步的差别，在某些领域还差些。

瞧你们吹捧的，大汗... ...

...

baidu的？

zszyj

原帖由 bbpet 于 2008-6-24 22:16 发表

呵呵，晚上踢球去了，不幸让你等惨了~
这回的结果让我相当的吃惊，居然到了0.1ms的级别去了

由于自己对db不熟，这回干脆让做数据库维护的人测，应该不犯错了
主机z990（长进了，不用s390了），两张表，一 ...

这就是数据库的真实能力, 即使数据量几何级数增长, 查询时间也就是线性增长.
而且说实在, 你做的联机之所以慢, 估计你是没有将服务常驻了, 如果服务常驻的话,性能与批量是一样的.
联机超过1ms的原因, 估计是因为你查询时才建立数据库连接, 而没有使用连接池等技术.
在我们的程序里,不仅使用连接池, 还建立了statment池, 速度还可以提升5倍. 够吓人吧?

zszyj

原帖由 wwwsq 于 2008-6-24 23:55 发表
用“布隆过滤器”可以瞬间进行判断，这个用户名是否已经被用过。

不用查数据库，也不用查RB-Tree。

过滤器的构建：构造一个巨大的bit array，比如10亿比特（占用约125 M内存），把这个array的所有bit都初 ...

省省吧, 用户名匹配, 犯得着什么复杂算法吗? 数据库查询, 即使是10亿以上,也不超过1ms, 前面的已经测试了, 0.1ms, 你这个hash能快到哪去?
再说了, 即使机器内存多,将用户名换成bit都放在内存, 用户详细信息放哪? 增删改用户, 这个hash表维护起来会简单? ACID怎么保证?
另外,都放在一台机器的内存,也就一台机器可用, cluster怎么办? 几千台机器, 并发数据库查询的吞吐量,绝对远高于单机上的所谓hash内存查询的吞吐量.
一看这种唯"算法论", 就是完全无视大型系统整体架构规划,完全无视工程实施可行性的学术派思想.
一

benjiam

原帖由 bbpet 于 2008-6-23 23:31 发表


难道是我不会用？？？
由于在大表中从来没见过ms级别的反馈，所以特意去试了一下
在db2上试的，分part了，24个批次跑，具体多少条不知道，反正没到10亿，等了好几分钟，总之就不是ms……
oracle上 ...

mysql

我插入到87w 条 就没信心等下去了。
1个亿..... 不知道要等多久。



还有把1格亿的用户名放在一个数据库里的想法很烂。 足以成为最大的瓶颈