海量数据处理专题(九)——外排序

【引言】

在数据结构的课程上,我们学习了不少的排序算法,冒泡,堆,快排,归并等。但是这些排序方法有着共同的特点,那就是所有的操作都是在内存中完成的,算法过程中不需要IO,这就使得这样的算法总体上速度比较快,但是也随之出现了一个问题:当需要排序的数据量异常的大的时候,以上的算法就显得力不从心了。这时候,你需要一种另外的排序算法,它的名字叫“外排序”。

通常的,设备的内存读取速度要比外存读取速度快得多(RAM的访问速度大约是磁盘的25万倍),但是内存的容量却要比外存小很多,当所有的数据不能在内存中完全放下的时候,就需要使用到外排序。这是外排序的一个显著特征。 继续阅读

海量数据处理专题(八)——倒排索引(搜索引擎之基石)

引言:

在信息大爆炸的今天,有了搜索引擎的帮助,使得我们能够快速,便捷的找到所求。提到搜索引擎,就不得不说VSM模型,说到VSM,就不得不聊倒排索引。可以毫不夸张的讲,倒排索引是搜索引擎的基石。

VSM检索模型

VSM全称是Vector Space Model(向量空间模型),是IR(Information Retrieval信息检索)模型中的一种,由于其简单,直观,高效,所以被广泛的应用到搜索引擎的架构中。98年的Google就是凭借这样的一个模型,开始了它的疯狂扩张之路。废话不多说,让我们来看看到底VSM是一个什么东东。 继续阅读

海量数据处理专题(七)——数据库索引及优化

索引是对数据库表中一列或多列的值进行排序的一种结构,使用索引可快速访问数据库表中的特定信息。

数据库索引

什么是索引

数据库索引好比是一本书前面的目录,能加快数据库的查询速度。

例如这样一个查询:select * from table1 where id=44。如果没有索引,必须遍历整个表,直到ID等于44的这一行被找到为止;有了索引之后(必须是在ID这一列上建立的索引),直接在索引里面找44(也就是在ID这一列找),就可以得知这一行的位置,也就是找到了这一行。可见,索引是用来定位的。 继续阅读

海量数据处理专题(六)——双层桶划分

【什么是双层桶】
事实上,与其说双层桶划分是一种数据结构,不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候,我们可以将其分成一个个小的单元,然后根据一定的策略来处理这些小单元,从而达到目的。

【适用范围】
第k大,中位数,不重复或重复的数字

【基本原理及要点】
因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子,分治才是其根本(只是“只分不治”)。 继续阅读

海量数据处理专题(五)——堆

【什么是堆】
概念:堆是一种特殊的二叉树,具备以下两种性质
1)每个节点的值都大于(或者都小于,称为最小堆)其子节点的值
2)树是完全平衡的,并且最后一层的树叶都在最左边
这样就定义了一个最大堆。如下图用一个数组来表示堆:

继续阅读

海量数据处理专题(四)——Bit-map

【什么是Bit-map】

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0(如下图:)

继续阅读

海量数据处理专题(三)——Hash

【什么是Hash】

Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。 继续阅读

海量数据处理专题(二)——Bloom Filter

【什么是Bloom Filter】

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,采用Bloom Filter的数据结构,可以通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍,不太懂的博友可以看看。

【适用范围】

可以用来实现数据字典,进行数据的判重,或者集合求交集 继续阅读

海量数据处理专题(一)——开篇

大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论。

本贴从解决这类问题的方法入手,开辟一系列专题来解决海量数据问题。拟包含 以下几个方面。

  1. Bloom Filter
  2. Hash
  3. Bit-Map
  4. 堆(Heap)
  5. 双层桶划分
  6. 数据库索引
  7. 倒排索引(Inverted Index)
  8. 外排序
  9. Trie树
  10. MapReduce

在这些解决方案之上,再借助一定的例子来剖析海量数据处理问题的解决方案。欢迎大家关注。