# 一、海量数据处理
海量数据，指的就是数据量过大，导致数据无法一次性装入内存，无法短时间内快速处理的情况。
- 针对时间：可以利用算法 + 数据结构：如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树
- 针对空间：则遵循大而化小，分而治之（hash映射）
而海量数据的处理又分为单机处理和集群处理
单机处理：依次处理小部分数据，只要考虑cpu，内存，硬盘的数据交互。
集群处理：涉及到多台机器，适合分布式处理，并行计算，更多考虑节点和节点间的数据交互，例如Hadoop的MapReduce就是利用到多台机器进行并行处理。
# 二、海量数据处理方法总结
# 2.1 Bloom filter
适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集。
问题实例：
# 2.2 Hashing
适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。
问题实例：
- 海量日志数据，提取出某日访问百度次数最多的那个IP。
IP的数目还是有限的（本质是一个int类型数字被划分成了4段），最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。
# 2.3 bit-map
适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下。
问题实例：
- 已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。
- 2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
通过bit-map存储，用2bitmap存储，或者用两个bitmap模拟，0表示不存在，1表示存在，2以上表示重复
# 2.4 堆
适用范围：海量数据前n大，并且n比较小，堆可以放入内存。
扩展：双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。
问题实例：
- 100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。
# 2.5 双层桶划分（分而治之）
适用范围：第k大，中位数，不重复或重复的数字
基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。
# 2.6 数据库索引
适用范围：大数据量的增删改查
基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。
# 2.7 倒排索引(Inverted index)
适用范围：搜索引擎，关键字查询
基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
# 2.8 外排序
适用范围：大数据的排序，去重
# 2.9 trie树
适用范围：数据量大，重复多，但是数据种类小可以放入内存
# 2.10 分布式处理 mapreduce
适用范围：数据量大，但是数据种类小可以放入内存
基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。