百度笔试题

昨天做了一下百度实习生笔试的题。有一道是这样的：
说有一个监控系统，会监控访问的url和ip还有时间。需求是可以存储1000亿条信息。
1.可以按照url查询某个时间段内的访问量。
2.可以按照ip查询某个时间段内的访问量。
请设计一个系统？
请问大牛们，这样的题何解？上回淘宝的题也差不多，都是大访问量的题。上课没有学过这样的内容 。
我现在的思路就是用缓存，存储每条信息的id值(如url表的id值)，然后value是url对象。但是还是比较费内存吧？还有一个想法就是key为url值，然后value为访问对象的map。不知道回答的靠不靠边。最近郁闷啊 昨天买个笔记本还让人骗了1000多555

写log文件吧！
记录url，ip，date；
按天做备份，类似access.log

不懂
按我的想法 分时间段存数据 每个时间段的数据按树状组织 叶子上记录次数
要是用哈希的话 很难统计范围数据吧

如果要设计一个系统那真的是难为你了

但要是让你设计查询的思路还是可以的

假设就一张表，表里3个字段

url, ip, date

存上1000亿条数据，你需要在这3个字段上都建立索引，利用分词

如果里面有一条数据
url:http://www.iteye.com/topic/1037635

分解这个url的词源可以为http，www.iteye.com，topic/1037635

ip:192.168.1.3
分解这个ip的词源可以为192，168，1，3

date:2011-05-10 21:56:37
分解这次date的词源可以为2011-05-10, 21, 56, 37

每个词源都可以建立索引

比如说你查的就是这条url，由于你本条url已经被分词，并且建立了索引，

也许符合http索引里有900亿，在这900亿里符合www.iteye.com的有10亿，10亿里符合topic/1037635的有103191条，那么这个就是此url的总访问量，如果加上时间的判断就是某段时间段的访问量

在1000亿条的数据表上对每一个字段，进行分词和建立索引，是一个需要精密排序算法，和也许需要多CPU分布计算处理的过程，建立索引再优化的算法也需要一定的时间，但一旦索引建立好，通过索引的归类排序查询起来就非常的快。



我不知道楼主是不是深刻理解，索引的真正目的

在数据上建立索引就是把数据进行归类排序的过程

比如我公司有100人，我为了快速在员工手册上找到这个人
我首先要知道这个员工的一些最基本属性，比如姓名，性别，年龄（当然大多就知道个姓名就够了）

那么我的员工手册的目录就要有几种讲究

如果 按，性别分为男和女，男员工从第1页到第200页，女员工从第201页到400页
然后在性别男的结果集中分，20到30岁之间的几页到几页，30到40岁之间的几页到几页
然后如果我想看一下30到40岁之间的就可以翻到拿一页开始看。

这里的排版只是个比喻，一般企业都是按职位和部门分排，这样看到那个部门就知道下面有那些员工

如果我设计了一个索引算法

有一个人叫张峰，那么把张和峰分开建立索引，那么就会把姓张的或是名字里有张这个字的人全部归类到张这个索引下（当然算法是自己定了，定的时候只要求名字开头第一个字为张的才归类，名字里有张的不算也是可以的），然后名字里有峰的人归到一类。这样就很容易快速找到

如果归类的数据集比较大，那么在归类的数据集上在归类。这个就是索引上再建立索引，

所以说为什么索引的建立和修改是需要花大量的计算和时间的

但最好还是只建立一层索引，多种索引，看到新华字典的编排就是一个典型的例子

就2种索引，一种按拼音，一种按偏旁，而按偏旁的索引又是一个层次索引，因为找到某个偏旁后，翻到那页还要有一个数笔画确认字的索引。最后你才能确认这个字在具体哪一页。


总结：索引的目的就是为了最大限度减少查询的次数。

那么百度这个1000亿数据的题目，其实应该考查你对建立索引和查询索引的一个思路，如果让你写算法，那真不是一朝一夕就马上出来的事。

采用缓存，然后写进日志文件里面，然后采用分布式比如hadoop来分析日志。不知道有没有道理？

chinaagan 写道
采用缓存，然后写进日志文件里面，然后采用分布式比如hadoop来分析日志。不知道有没有道理？

估计这个最符合百度的心意，呵呵。

这种数据如果用nosql应该很费劲吧，还是用传统的数据库方便，因为是分段的，当然是分表了，例如每个月一张表，表四个字段，主键，url，ip，日期

感谢大家的回答，学到不少知识

学习了.


kanny87929 写道
如果要设计一个系统那真的是难为你了

但要是让你设计查询的思路还是可以的

假设就一张表，表里3个字段

url, ip, date

存上1000亿条数据，你需要在这3个字段上都建立索引，利用分词

如果里面有一条数据
url:http://www.iteye.com/topic/1037635

分解这个url的词源可以为http，www.iteye.com，topic/1037635

ip:192.168.1.3
分解这个ip的词源可以为192，168，1，3

date:2011-05-10 21:56:37
分解这次date的词源可以为2011-05-10, 21, 56, 37

每个词源都可以建立索引

比如说你查的就是这条url，由于你本条url已经被分词，并且建立了索引，

也许符合http索引里有900亿，在这900亿里符合www.iteye.com的有10亿，10亿里符合topic/1037635的有103191条，那么这个就是此url的总访问量，如果加上时间的判断就是某段时间段的访问量

在1000亿条的数据表上对每一个字段，进行分词和建立索引，是一个需要精密排序算法，和也许需要多CPU分布计算处理的过程，建立索引再优化的算法也需要一定的时间，但一旦索引建立好，通过索引的归类排序查询起来就非常的快。



我不知道楼主是不是深刻理解，索引的真正目的

在数据上建立索引就是把数据进行归类排序的过程

比如我公司有100人，我为了快速在员工手册上找到这个人
我首先要知道这个员工的一些最基本属性，比如姓名，性别，年龄（当然大多就知道个姓名就够了）

那么我的员工手册的目录就要有几种讲究

如果 按，性别分为男和女，男员工从第1页到第200页，女员工从第201页到400页
然后在性别男的结果集中分，20到30岁之间的几页到几页，30到40岁之间的几页到几页
然后如果我想看一下30到40岁之间的就可以翻到拿一页开始看。

这里的排版只是个比喻，一般企业都是按职位和部门分排，这样看到那个部门就知道下面有那些员工

如果我设计了一个索引算法

有一个人叫张峰，那么把张和峰分开建立索引，那么就会把姓张的或是名字里有张这个字的人全部归类到张这个索引下（当然算法是自己定了，定的时候只要求名字开头第一个字为张的才归类，名字里有张的不算也是可以的），然后名字里有峰的人归到一类。这样就很容易快速找到

如果归类的数据集比较大，那么在归类的数据集上在归类。这个就是索引上再建立索引，

所以说为什么索引的建立和修改是需要花大量的计算和时间的

但最好还是只建立一层索引，多种索引，看到新华字典的编排就是一个典型的例子

就2种索引，一种按拼音，一种按偏旁，而按偏旁的索引又是一个层次索引，因为找到某个偏旁后，翻到那页还要有一个数笔画确认字的索引。最后你才能确认这个字在具体哪一页。


总结：索引的目的就是为了最大限度减少查询的次数。

那么百度这个1000亿数据的题目，其实应该考查你对建立索引和查询索引的一个思路，如果让你写算法，那真不是一朝一夕就马上出来的事。

kanny87929 写道
如果要设计一个系统那真的是难为你了

但要是让你设计查询的思路还是可以的

假设就一张表，表里3个字段

url, ip, date

存上1000亿条数据，你需要在这3个字段上都建立索引，利用分词

如果里面有一条数据
url:http://www.iteye.com/topic/1037635

分解这个url的词源可以为http，www.iteye.com，topic/1037635

ip:192.168.1.3
分解这个ip的词源可以为192，168，1，3

date:2011-05-10 21:56:37
分解这次date的词源可以为2011-05-10, 21, 56, 37

每个词源都可以建立索引

比如说你查的就是这条url，由于你本条url已经被分词，并且建立了索引，

也许符合http索引里有900亿，在这900亿里符合www.iteye.com的有10亿，10亿里符合topic/1037635的有103191条，那么这个就是此url的总访问量，如果加上时间的判断就是某段时间段的访问量

在1000亿条的数据表上对每一个字段，进行分词和建立索引，是一个需要精密排序算法，和也许需要多CPU分布计算处理的过程，建立索引再优化的算法也需要一定的时间，但一旦索引建立好，通过索引的归类排序查询起来就非常的快。



我不知道楼主是不是深刻理解，索引的真正目的

在数据上建立索引就是把数据进行归类排序的过程

比如我公司有100人，我为了快速在员工手册上找到这个人
我首先要知道这个员工的一些最基本属性，比如姓名，性别，年龄（当然大多就知道个姓名就够了）

那么我的员工手册的目录就要有几种讲究

如果 按，性别分为男和女，男员工从第1页到第200页，女员工从第201页到400页
然后在性别男的结果集中分，20到30岁之间的几页到几页，30到40岁之间的几页到几页
然后如果我想看一下30到40岁之间的就可以翻到拿一页开始看。

这里的排版只是个比喻，一般企业都是按职位和部门分排，这样看到那个部门就知道下面有那些员工

如果我设计了一个索引算法

有一个人叫张峰，那么把张和峰分开建立索引，那么就会把姓张的或是名字里有张这个字的人全部归类到张这个索引下（当然算法是自己定了，定的时候只要求名字开头第一个字为张的才归类，名字里有张的不算也是可以的），然后名字里有峰的人归到一类。这样就很容易快速找到

如果归类的数据集比较大，那么在归类的数据集上在归类。这个就是索引上再建立索引，

所以说为什么索引的建立和修改是需要花大量的计算和时间的

但最好还是只建立一层索引，多种索引，看到新华字典的编排就是一个典型的例子

就2种索引，一种按拼音，一种按偏旁，而按偏旁的索引又是一个层次索引，因为找到某个偏旁后，翻到那页还要有一个数笔画确认字的索引。最后你才能确认这个字在具体哪一页。


总结：索引的目的就是为了最大限度减少查询的次数。

那么百度这个1000亿数据的题目，其实应该考查你对建立索引和查询索引的一个思路，如果让你写算法，那真不是一朝一夕就马上出来的事。



学习了