很多朋友对于高效海量数据查询：探索常见数据结构应用和不太懂，今天就由小编来为大家分享，希望可以帮助到大家，下面一起来看看吧！
如果要判断某个元素是否在集合中，一般的思路就是保存所有元素，然后通过比较来判断。链表、树等数据结构都是基于这个思想。然而，随着集合中元素的增加，所需的存储空间越来越大，检索速度也越来越慢。上述三种结构的检索时间复杂度分别为O(n),O(log n),O(n/k)。
这时候就可以利用哈希表的数据结构（可以通过哈希函数将一个元素映射成位数组（Bit array）中的一个点）。这样我们只要看该点是否为1就可以知道它是否包含在集合中。这就是布隆过滤器的基本思想。
但此时，哈希冲突就会成为一个问题：假设哈希函数很好，如果我们的位数组有m 点长，那么如果我们想将冲突率降低到，比如1%，这个哈希表只能容纳m/100 元素。显然这不叫节省空间。解决办法也很简单，就是使用多个Hash。如果其中之一说该元素不在集合中，那么它肯定不存在。如果他们都说是，那么就有一定的可能他们都在说谎，但直观上这种事情的概率是比较低的。这种由多个Hash组成的数据结构称为Bloom Filter。
查找示例
布隆过滤器基于一个m位的位向量(b1,bm)，这些位向量的初始值为0。此外，还有一系列哈希函数(h1,bm) .hk），这些哈希函数的取值范围属于1~m。下图是布隆过滤器插入x,y,z并判断某个值w是否在数据集中的示意图：
找到上图中的w例子，m=18，k=3；插入x时，三个哈希函数分别得到蓝线对应的三个值，并将对应的位向量更改为1。插入y和z时，类似，将红线对应的位向量更改和紫色线分别为1。查找的时候，查找x的时候，三个哈希值对应的位向量都是1，所以判断x在这个数据集中。 y 和z 也是如此。但在查找w时，w的位向量对应的哈希值为0，因此可以判断其不在这个集合中。但如果w的最后一个哈希值比上图中的大1，就会认为w在这个集合中。事实上，w可能不在这个集合中，因此可能会出现误报。显然，插入的数据越多，1的位数就越多，误报的概率就越大。
Bitmap
Bit-map用一个bit来标记一个元素对应的Value，Key就是该元素。由于数据以Bit为单位存储，可以大大节省存储空间。可进行数据的快速查找，判重，删除。
应用示例
假设我们要对0-7范围内的5个元素（4,7,2,5,3）进行排序（这里假设这些元素不重复）。那么我们就可以使用Bit-map的方法来达到排序的目的。要表示8 个数字，我们只需要8 位（1 个字节）。首先，我们开辟1Byte空间，并将这些空间中的所有Bit设置为0。
然后遍历这5个元素。首先第一个元素是4，然后将4对应的位置设置为1（可以这样操作：p+(i/8)|(001(i%8)) 当然这里的操作来的时候到Big-ending和Little-ending，这里默认是Big-ending）。因为它是从零开始的，所以第五位应该设置为1。
然后处理第二个元素7，将第八个位置设置为1，然后处理第三个元素，直到最后所有元素处理完毕，将相应位置设置为1。
那么我们现在遍历Bit区域，输出为1的位的个数（2,3,4,5,7），这样就达到了排序的目的。
其实就是将用于计数排序的统计数组的各个单元缩减为位级布尔数组。
Trie树
Trie树，字典树，也称为词搜索树或键树，是一种树结构。典型应用为用于统计和排序大量的字符串（但不仅限于字符串），因此常被搜索引擎系统用来进行文本词频统计。其优点是最大限度地减少不必要的字符串比较，实现较高的查询效率。
Trie的核心思想是空间换时间。使用字符串的公共前缀可以减少查询时间开销，提高效率。同时，可以使用trie树和键字段来存储查询字符串出现的次数。
性质它有3个基本属性：
根节点不包含任何字符，除根节点外的每个节点仅包含一个字符。从根节点到某个节点，将路径上传递的字符连接起来，形成该节点对应的字符串。每个节点的所有子节点都包含不同的字符。
实例
构建Trie 的基本算法也非常简单。无非就是将每个单词的每个字母一一插入到Trie中。插入前检查前缀是否存在。如果存在则共享，否则创建对应的节点和边。例如，插入单词add，有以下步骤：
检查前缀“a”，我们发现边a 已经存在。因此沿着边a到达节点a。检查剩余字符串“dd”的前缀“d”，我们发现从节点a 开始，边d 已经存在。所以我们沿着边d 走到节点ad 来检查最后一个字符“d”。现在从节点ad开始没有边d，所以我们创建了节点ad的子节点add，并将边ad-add标记为d（可以将子节点ad标记为d）。节点的值加1来存储“add”出现的次数）。
倒排索引
倒排索引是全文检索时用于存储某个词在一个文档或一组文档中的存储位置映射的索引方法。常用于搜索引擎和关键词查询问题。
实例
以英文为例，需要索引的文本如下：
T0="就是这样"
T1="这是什么"
T2="这是香蕉" 我们可以得到以下反向文件索引：
“a”: {2}
"香蕉": {2}
"是": {0, 1, 2}
“它”: {0, 1, 2}
由"what": {0, 1} 检索的条件"what"、"is" 和"it" 将对应于集合的交集。
开发前向索引是为了存储每个文档的单词列表。正向索引查询往往满足每个文档的有序、频繁的全文查询以及验证文档中每个单词的验证。在正向索引中，文档占据中心位置，每个文档都指向它包含的一系列索引条目。也就是说，文档指向它包含的单词，以及反向索引则是单词指向了包含它的文档，很容易看出这种反向关系。
外排序
所谓外部排序，顾名思义就是在内存外面的排序，因为当要处理的数据量很大，无法一次性加载到内存中时，只能放在外部读写速度较慢的内存（通常是硬盘）。 ）优越的。
外部排序通常采用“排序-归并”策略。
在排序阶段，首先读入内存中可放入的数据量，排序后输出到临时文件，并据此将待排序的数据组织成多个有序的临时文件；
然后这些临时文件在合并阶段合并成一个大的有序文件，这就是排序后的结果。
假设现在文件A有20条数据：{5 11 0 18 4 14 9 7 6 8 12 17 16 13 19 10 2 1 3 15}，但是一次只能使用4条数据的内容，所以我们可以每遍排序4条数据，即5路合并。具体方法如下：
我们首先将“大”文件A分为a1、a2、a3、a4、a5等5个小文件，每个小文件有4个数据
a1文件为：5 11 0 18
a2文件为：4 14 9 7
a3文件为：6 8 12 17
a4文件为：16 13 19 10
a5文件为：2 1 3 15 然后将这5个小文件按顺序排序。
a1文件排序后：0 5 11 18
a2文件排序后：4 7 9 14
a3文件排序后：6 8 12 17
a4文件排序后：10 13 16 19
a5文件排序后：1 2 3 15最终通过多种方式合并完成整个排序
整个大文件A排序后： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
hadoop/Mapreduce
MapReduce是一种计算模型。简单来说，就是将一大批工作（数据）分解（MAP）执行，然后将结果合并成最终结果（REDUCE）。这样做的好处是，任务分解后，可以在大量机器上进行并行计算，减少整个运算的时间。说白了，Mapreduce的原理就是归并排序。
适用范围：数据量大，但小数据类型可以放在内存中
基本原理和要点：将数据交给不同的机器处理，划分数据，归约结果。
理解：
MapReduce 是一种模式。
Hadoop 是一个框架。
【高效海量数据查询：探索常见数据结构应用】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
看来很多时候要用到数据结构来处理海量的资料
有11位网友表示赞同！
学习一下海量数据查询常用数据结构挺有必要的
有5位网友表示赞同！
哪个数据结构效率最高呢？
有16位网友表示赞同！
这篇文章肯定能让我更了解数据结构的应用场景
有6位网友表示赞同！
想明白不同数据结构的特点，才能更好地选用啊
有19位网友表示赞同！
海量的查询真的让人头疼，希望这篇文章有解决方法
有15位网友表示赞同！
最近在研究类似问题，文章能不能讲解一些案例呢?
有12位网友表示赞同！
数据结构学习永远都不会过时
有10位网友表示赞同！
学习一下这些数据结构可以提升编程水平吧
有9位网友表示赞同！
感觉海量数据处理是个技术难题，这篇文章能带给我启发吗？
有16位网友表示赞同！
对海量数据查询真的不太了解，希望能有详细的说明
有18位网友表示赞同！
希望文章能介绍多种常见的数据结构类型
有8位网友表示赞同！
学习数据结构是提高效率的一大途径
有16位网友表示赞同！
这篇文章一定很有用，收藏一下先！
有5位网友表示赞同！
数据查询速度很重要，选对数据结构就十分关键
有13位网友表示赞同！
我一直想深入了解海量数据的处理方式
有6位网友表示赞同！
学习了这些数据结构，可以更好地应对数据挑战
有11位网友表示赞同！
这篇文章是我最近在想要寻找的答案！
有19位网友表示赞同！
我希望能从这篇文章中获得很多实用的知识
有20位网友表示赞同！