海量数据处理

一，海量数据处理的数据规模：

1T = 1024G

1G = 10亿

2G = 2*1000*1000*1000=20亿

2^32=4*2^30 = 4G = 40亿

1M = 1*1000*1000 = 100万

计算机存储单位一般用B，KB，MB，GB，TB，PB，EB，ZB，YB，BB来表示。

1KB (Kilobyte 千字节)=1024B

1MB (Megabyte 兆字节简称“兆”)=1024KB

1GB (Gigabyte 吉字节又称“千兆”)=1024MB

1TB (Trillionbyte 万亿字节太字节)=1024GB，其中1024=2^10 ( 2 的10次方)

1PB（Petabyte 千万亿字节拍字节）=1024TB

1EB（Exabyte 百亿亿字节艾字节）=1024PB

1ZB (Zettabyte 十万亿亿字节泽字节)= 1024 EB

1YB (Yottabyte 一亿亿亿字节尧字节)= 1024 ZB

1BB (Brontobyte 一千亿亿亿字节)= 1024 YB

二，海量数据处理常用算法：

1．Bloom filter

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集合求交集

2．Hashing

适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。

3．bit-map

适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

4．堆

适用范围：海量数据前n大，并且n比较小，堆可以放入内存

5．分区划分

适用范围：第k大，中位数，不重复或重复的数字

6．倒排索引(Inverted index)

适用范围：搜索引擎，关键字查询

7．外排序

适用范围：大数据的排序，去重

8．

适用范围：数据量大，重复多，但是数据种类小可以放入内存

9．分布式处理 mapreduce

适用范围：数据量大，但是数据种类小可以放入内存

基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。

三，海量数据处理实际例子：

1．海量日志数据，提取出某日访问百度次数最多的那个IP

2．搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过

3．有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的

4．有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照

5．给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的

6．在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这

7．给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

8．怎么在海量数据中找出重复次数最多的一个？

9．上千万或上亿数据（有重复），统计其中出现次数最多的钱N个数据。