对于海量数据的处理，手工方式早已不能满足需求，必须通过工具进行处理。当数据量达到TB级别时，用计算机处理时也会对软、硬件的要求加倍提升。当遇到的海量数据无法全部存入内存时，那么如何处理这些重复格式不正确的数据也是数据处理人员需要去解决的问题。

1、布隆过滤器及散列法

布隆过滤器（Bloom Filter）是1970年由Bloom提出，最初广泛用于拼写检查和数据库系统中。

布隆过滤器的基本原理:当一个元素被加入集合时，通过k个散列函数将这个元素映射为一个元素中的k个点，把它们置为1。检索时，我们只要看这些点是否是1就知道集合中是否有它了。如果这些点有任何一个0，则被检元素一定不在；如果都是l，被检元素很可能在，查找结果并不能保证100%正确。所以简单的改进就是Counting Bloom Filler，用counter数组代替位数组，就可以支持删除了插人的关键字了。

原始的Bloom Filter不支持删除已经插人的关键宇，因为该关键字对应的位会牵动到其他关键宇。所以简单的改进就是Counting Bloom Filter，用counter数组代替位数组，就可以支持删除了插入的关键字了。布隆过滤器可以用来实现数据字典，进行数据的判重（重复数据判断），或者集合求交集。

散列法（Hashing）是计算机科学中一种对数据的处理方法，通过某种特定的函数/算法，将要检索的项与用来检索的索引关联起来，生成一种便于搜索的数据结构。它常用作一种信息安全的方法，如果一串数据中经过散列算法计算出来的数据指纹，经常用来识别档案与数据是否被篡改过，以保证档案与数据确实是由原创者所提供的。

Hash 函数选择在针对宇符串、整数.排列时具有相应的Hash方法。一种是Open Hashing，也称为拉链法；另一种就是Closed Hashing ，也称开放地址法，即Opened Addressing。目前主要有除法散列法，平方散列法，斐波那契（Fibonacci）散列法。

2、堆排序及双层桶划分

堆排序（Heapsort）是利用一种叫堆积树的数据结构所设计出来的一种排序算法，它是选择排序的一种，可以利用数组的特点快速定位指定索引的元素。堆分为大顶堆和小顶堆，是完全二叉树.大顶堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大顶堆，因为根据大顶堆的要求可知，最大值一定在堆顶。

利用大顶堆（小顶堆）项记录的是最大关键字（最小关键字）这一特性，使得每次从无序数组中选择最大记录（最小记录）变得简单了。对于堆排序，最重要的两个操作就是构造初始堆和调整堆，事实上构造初始堆就是调整堆的过程，但构造初始堆是对所有非叶节点都进行调整。

堆排序适合处理海量数据，并且是可以放入内存的数据。双层桶划分是一种数据结构，也可以看作一种算法设计思想.面对一堆大量的数据无法处理的时候，可以将其分为一个个小的单元，然后根据一定的策略来处理这些小单元。从而达到目的。

因为元素范围很大，不能利用直接寻址表，所以可通过多次划分，逐步确定范围，然后可以在一个可以接受的范围内进行。可以通过多次划分来缩小范围，双层只是一个例子，分治才是其根本。

双层桶划分适用于数据库范围查询，用来寻找第k大.中位数、不重复（或重复）的数字。

3、索引

根据数据库的功能，可在数据库中创建3种索引:

（1）唯一索引

唯一索引是不允许其中任何两行具有相同索引值的索引。当现有数据中存在重复的键值时，大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复值得新数据。

（2）主键索引

主键索引是唯一索引的特殊类型，主键索引要求主键中的每个值都唯一，当在查询中使用主键索引时，还允许对数据的快速访问。

（3）聚集索引

聚集索引中表中的物理顺序与键值的逻辑索引顺序是一样的，一张表只能包含一个聚集索引，如果某索引不是聚集索引，那么表中行的物理顺序与键值的逻辑顺序是不匹配的，聚集索引比非聚集索引将提供更快的数据访问速度。

数据库索引是数据库管理系统中一个排序的数据结构，可以提高数据库表的数据访问速度，能实现大数据量的增加﹑删除.修改.查询等操作，还可以实现快速查询.更新数据库表中的数据。

倒排序索引在实际应用中主要是根据属性的值来查找数据，是根据属性来确定记录的位置，而不是由记录来确定属性值。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址，带有倒排序索引的文件称为倒排索引文件，也称倒排文件。

倒排序索引是文档检索系统中最常用的数据结构，主要用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。倒排序索引可以根据单词快速获取包含这个单词的文档列表，是实现单词到文档映射关系的最佳实现方式和最有效地索引结构，主要适用于搜索引擎、关键字查询等。

4、外排序及TRIE树

外排序指的是对大文件的排序，当文件太大而无法将整个文件所有记录调入内存中进行排序时，只能将文件放在外存储器中，通过数据的内.外存交换和”内部归并"两者结合起来实现。外排序在排序期间由于文件太大对象个数太多，不能同时全部存入内存，因此必须根据排序过程的要求，在内.外存之间不断地进行移动排序，适用于大部分大数据的排序.去重。

单词查找树Trie是一种哈希树的变种，也是一种树形结构。

TRIE树在信息检索，字符串匹配等领域有广泛的应用，是一种非常重要的数据结构，它也是后缀树、AC自动机等复杂算法和数据结构的基础。