Background Knowledge
一. Bloom Filter
1. 什么是Bloom Filter
Bloom Filter是一种空间效率很高的随机数据结构.它利用位数组很简洁地表示一个集合, 并能判断一个元素是否属于这个集合.
基本原理
当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位阵列（Bit array）中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检索元素一定不在；如果都是1，则被检索元素很可能在(也有可能是false positive)。
特点
在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，采用Bloom Filter的数据结构，可以通过极少的错误换取了存储空间的极大节省。虽然有可能把不属于这个集合的元素误认为属于这个集合（False Positive），但不会把属于这个集合的元素误认为不属于这个集合（False Negative）
集合表示和元素查询
面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。
为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1 (1≤ i ≤ k).注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。
在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1 (1≤ i ≤k),那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有2处指向了“0”位）。y2或者属于这个集合，或者刚好是一个false positive。
有几个关键数据我们需要了解: 错误率，最优的Hash函数的个数, Bit Array 数组大小
几个数值之间的关系:
这块应该很容易理解, 几个数值的变化对Bloom Filter 影响非常大, 比如 k 个hash, k 很大， 那么hash 之后要落在array中很多位, 多弄几次，检测一个不在集合中的元素，会有一定概率 false positive, 因为很多位已经是1了(极端情况都是1了，那么任何一个数检测都是false positive). 不过因为k个检测条件多了，也可能会使错误率降低，这些都要综合来看.
我们如何根据输入元素个数n，确定位数组m的大小及hash函数个数？
当hash函数个数k=(ln2)*(m/n)时错误率最小。
在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。
注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
算法简单分析
我们假设kn<m且各个哈希函数是完全随机的。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是：
False Positive的概率是：
p’表示1的概率,k次方表示8次hash都为1的概率。
当 k = ln 2 * m/n 时，右边的等式值最小，此时等式转变成:
Details:
2. 概念，原理 要点总结:
对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。(因为可能 s1, s2 都映射到这一位，如果对于s1, 删掉1bit，那么s2 下次检测就不存在). 所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除
还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。
注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
3. 扩展
Bloom filter将集合中的元素映射到位数组中，用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。
Counting bloom filter (CBF)将位数组中的每一位扩展为一个counter, 将基本Bloom Filter每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了. 删除时候 -1 不影响其他.
Spectral Bloom Filter (SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
Bloom Filter跟单哈希函数Bit-Map不同之处: Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率. 单一Hash函数的冲突率太高.
但从存储效率来讲，Bloom Filter应该是不如BitMap的吧？BitMap 1bit就可以代表一条数据, Bloom Filter 需要更大空间.
二. Hash
1. Hash 算法
HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系. 具体的算法我这不提了，一般就是MD5 - 128, SHA1 - 160等，下面题目我们普遍认为是MD5, 不管输入多么长，输出 128 Bit
大数据题目用Hash算法处理的非常多. 主要目的在于两点
1. 节省空间. 建立和key的映射，这样用hash(key) 同样可以代表key, 同时缩小key的体积，比如一个url, maxLength = 50 Bytes. 我们MD5 Hash 一下就只有128 Bit = 16 Bytes了. 省了将近3倍.
2. 平均分布
很多题目需要分治，会对内容做处理，一般都是hash(content) % size. 因为直接根据内容不好分布，但是根据 hash value 取模的话，相同的content内容一定会分在一个区间内，比如url. 这点特性非常重要
2. 常用散列法
我们可以用MD5算法来算，但是如何均匀分布, 也要看散列法，如何设计散列, 比如String 的hashCode() 方法，如果让我们自己弄一个Class 比如Person, 属性是name，age，我们怎么override这个方法确保Hash后分布均匀少碰撞？ 我这是不是混了。。有点乱
2.1 除法散列法
最直观的一种，上图使用的就是这种散列法，公式：
index = value % 16
学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。
2.2 平方散列法
求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：
index = (value * value) >> 28
如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。
2.3 斐波那契（Fibonacci）散列法
平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。
1. 对于16位整数而言，这个乘数是40503
2. 对于32位整数而言，这个乘数是2654435769
3. 对于64位整数而言，这个乘数是11400714819323198485
这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，如果你还有兴趣，就到网上查找一下“斐波那契数列”等关键字，我数学水平有限，不知道怎么描述清楚为什么，另外斐波那契数列的值居然和太阳系八大行星的轨道半径的比例出奇吻合，很神奇，对么？
对我们常见的32位整数而言，公式：
index = (value * 2654435769) >> 28
如果用这种斐波那契散列法的话，那我上面的图就变成这样了：
很明显，用斐波那契散列法调整之后要比原来的取摸散列法好很多
3. 概念，原理 要点总结:
hash函数要根据情况选择，针对字符串，整数，排列，具体相应的hash方法。
碰撞处理，一种是open hashing，也称为拉链法(建议用)；另一种就是closed hashing，也称开地址法，opened addressing(小数据量高效)
关于碰撞处理算是Hash的数据结构内容，这块不说.http://blog.csdn.net/wangwh485/article/details/6415299
4. 扩展
d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个 位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。 (这块只做了解就好)
三. Bit-Map
1. 什么是Bit-Map
Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
我们来考虑具体的例子深入理解, 假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit (1Bytes)，首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0
然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置1
然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：
然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。
2. 概念，原理 要点总结:
Bit-Map的映射一开始确实有点不太好理解，尤其应用上, 主要就是根据数据结构来映射一定另一种内容.
Leetcode 上有道题目 Single Number II. 将一个int(32 bit) 映射到 int[32] 的数组中, 用来计算每一位的sum, 算是Bit-Map 很典型的题目.
CC150 上又道找String 中最高频char的题目，char(8 bit) 256 种可能, int[256] 数字来表示每位出现次数比如 int[‘a’]
第一个题目和第二个有点区别，第一个其实是把int解析成 32 bit. 每位对应到数组中，不是我们这里说的Bit-Map(我们这里是每一位代表一个数), 如果按我们这个说的，bit 需要的数量是 要代表的content的可能性，比如要代表一个char, 255中可能，需要255的空间. 代表一个int, 2^32中可能，需要4G bit 来代表所有的int
别蒙: 一个int的空间(32bit) 和他能表示的所有int的空间(4G bit )别弄混了！
3. 扩展
其实Bloom - Filter 就是Bit-Map 的一种扩展，使得 Hash冲突率降低, 感觉一道题目如果可以用Bit-Map做的话，再不考虑出错率的情况下，用Bloom - Filter也没问题，另外就是 Bloom - Filter 需要Hash, Bit-Map 可以不用
看完一些题目以后发现，这就是一种节省空间mapping的思想，看之前leetcode cc150的实际题目，也不太可能用bit去标记，当然这不是海量数据问题，但是2.5亿整数中找不重复，实际上需要2bit来标记 -> 2Bit-Map，所以说，我们可以根据不同情况进行扩展
四. Heap
1. 什么是Heap
Head 在Java中是得自己实现的，或者直接用PriorityQueue. 有一些特性要记住
堆是一种特殊的二叉树，具备以下两种性质
1) 每个节点的值都大于（或者都小于，称为最小堆）其子节点的值
2) 是一颗完全二叉树, 树是完全平衡的，并且最后一层的树叶都在最左边.
最重要的是...Heap只是在逻辑中是Tree，再存储结构中因为他的特性，用Array.
parent i， left child 2i+1, right child 2i+2, parent (i-1)/2
2. Heap 的添加, 删除操作
假设要在这个二叉堆里入队一个单元，键值为2，那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复杂度为Ο(logn)的操作，二叉堆还是二叉堆。
那如何出队呢？也不难，看图：
出队一定是出数组的第一个元素，这么来第一个元素以前的位置就成了空位，我们需要把这个空位挪至叶子节点，然后把数组最后一个元素插入这个空位，把这个“空位”尽量往上挪。这种操作的复杂度也是Ο(logn)
3. 概念，原理 要点总结:
最大堆就是大根堆， root最大，同理最小堆反之亦然.
最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。
这里别蒙，Heap在空间饱和的情况，add会先弹出root，然后再插入. 求最小的话，选最大堆，这样，大值都会弹出. Java中Priority Queue是默认按element natural ordering, 一般就是最小堆
4. 扩展
双堆，一个最大堆和一个最小堆向结合，可以用来维护中位数.
这个我不知道有什么具体的例子，我理解的就是一起pop，然后等pop值相同的时候，肯定是median了
五. 双层桶
1. 什么是双层桶
搜了下网上的材料，没有介绍这个的...好捉急，那就按引用文章的定义 ，事实上，与其说双层桶划分是一种数据结构，不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候，我们可以将其分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的。
2. 概念，原理 要点总结:
因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子，分治才是其根本（只是“只分不治”）
3. 扩展
当有时候需要用一个小范围的数据来构造一个大数据，也是可以利用这种思想，相比之下不同的，只是其中的逆过程。
六. External Sort(Merge Sort)
1. 什么是External Sort
在数据结构的课程上，我们学习了不少的排序算法，冒泡，堆，快排，归并等。但是这些排序方法有着共同的特点，那就是所有的操作都是在内存中完成的，算法过程中不需要IO，这就使得这样的算法总体上速度比较快，但是也随之出现了一个问题：当需要排序的数据量异常的大的时候，以上的算法就显得力不从心了。这时候，需要一种另外的排序算法，它的名字叫“外排序”
外部排序就是内存太小，数据太大，没有办法一次性装载入内存，我们平时用的sort全是内部排序，必须装入内存才可以，外部排序不能这么操作，只能利用merge sort的思想, 先分割成小文件，然后逐步merge.
通常的，设备的内存读取速度要比外存读取速度快得多（RAM的访问速度大约是磁盘的25万倍），但是内存的容量却要比外存小很多，当所有的数据不能在内存中完全放下的时候，就需要使用到外排序。这是外排序的一个显著特征。
2. 算法分析
外排序其实是采用一种分治（Divide and conquer algorithm）的算法设计思想，将一个大问题划分成相对独立的若干个小问题，解决小问题，得到小问题的答案，然后合并小问题的答案，最终得到原始大问题的答案。
在这里，我们举一个外排的典型例子，二路外部归并排序，假设我们有一个大文件，里面是待排序的数据，一共N个，这些数据在内存中放不下。排序过程如下：
- 将该大文件分割成大小为m的文件（m小于可用内存大小）
- 将这些小文件依次读入内存，在内存中采用任一种排序算法排序并输出文件F1，F2….Fn。（其实可以和第一步合并，可以省一次IO）
- 分块快读取两个已经排完序的文件Fi和Fi+1，由于两个文件已经排完序，这里可以用归并排序，将两个文件排序完毕，并写入文件。（这个过程就好比有两队人马将其合并为一对一样）
- 重复过程3，直到剩余文件数为1。
以上就是二路外部归并排序的基本思路，毫无疑问，这种排序算法需要读取外存（IO）次数为log(2,N/m)，这时候算法的性能瓶颈已经不在内存中排序的时间复杂度上，而是内外村交换数据IO的次数了。这里我补充一句，各种操作的性能差别：
读取网络 > 磁盘文件IO > 读取数据库 > 内存读取
这个可谓是程序性能的黄金法则，各位在写对性能要求比较高的程序时一定要考虑。
好，言归正传，二路归并排序这个算法的性能时比较低的。因此就有了多路归并排序算法，其IO的次数为log(b, N/m)，其中b为几路归并。这个可以参考以下地址：
http://zh.wikipedia.org/wiki/%E5%A4%96%E6%8E%92%E5%BA%8F
2. 概念，原理 要点总结:
外排序的归并方法，置换选择败者树原理，最优归并树(关于树这块还不理解)
merge的部分一定要理解，假设分块数据 size = memory size = 100M. merge 时候,
不是一次性的将 f1, f2 load 进来，这样不就超了么，2路归并的花，输入缓冲区只有 memory size / 2 = 50 M. 然后输出buffer 是50M，输出buffer一空，从对应的文件里面，读取50M出来. 所以merge部分有流控制，绝对没有问题.
4. 扩展
K路归并，还有2路归并时候的空间效率是可以优化的，这部分有空再看
七. Map Reduce Framework
1. 什么是Map-Reduce
Map-Reduce 是一套实现并行计算的编程模式. 如果要弄，这节会很多内容，简单说下，之后会单独拉一篇文章总结Hadoop 和 Map-Reduce等内容
2. Map Reduce 工作模型
MapReduce 借鉴了函数式程序设计语言的设计思想，其软件实现是指定一个Map 函数，把键值对(key/value)映射成新的键值对(key/value)，形成一系列中间结果形式的key/value 对，然后把它们传给Reduce(规约)函数，把具有相同中间形式key 的value 合并在一起。Map 和Reduce 函数具有一定的关联性。函数描述如表1 所示：
MapReduce致力于解决大规模数据处理的问题，因此在设计之初就考虑了数据的局部性原理，利用局部性原理将整个问题分而治之。MapReduce集群由普通PC机构成，为无共享式架构。在处理之前，将数据集分布至各个节点。处理时，每个节点就近读取本地存储的数据处理（map），将处理后的数据进行合并（combine）、排序（shuffle and sort）后再分发（至reduce节点），避免了大量数据的传输，提高了处理效率。无共享式架构的另一个好处是配合复制（replication）策略，集群可以具有良好的容错性，一部分节点的down机对集群的正常工作不会造成影响。
ok，你可以再简单看看下副图，整幅图是有关hadoop的作业调优参数及原理，图的左边是MapTask运行示意图，右边是ReduceTask运行示意图：
如上图所示，其中map阶段，当map task开始运算，并产生中间数据后并非直接而简单的写入磁盘，它首先利用内存buffer来对已经产生的buffer进行缓存，并在内存buffer中进行一些预排序来优化整个map的性能。而上图右边的reduce阶段则经历了三个阶段，分别
Copy->Sort->reduce。我们能明显的看出，其中的Sort是采用的归并排序，即merge sort。
3. 概念，原理 要点总结:
Map-Reduce 只适用于对实时性要求不高的数据，一般都是处理离线数据, 作业要求难度不大，主要是统计类的题目.
对于Map-Reduce计算框架的理解，从我目前的角度来看，也远没有这么简单，很多过程我们不关心，但是非常重要，比如shuffle，还有其中的子过程是非常重要的，这些子过程设计Map Reduce 的优化，之前看的两篇文章非常好，贴在这里
八. Trie Tree
1. 什么是Trie Tree
前缀树或字典树，是一种有序数，用于保存关联数组，其中键通常是字符串
下面讨论一棵最简单的trie树，基于英文26个字母组成的字符串，讨论插入字符串、判断前缀是否存在、查找字符串等基本操作；至于trie树的删除单个节点实在是少见，故在此不做详解
性质：
好多人说trie的根节点不包含任何字符信息，我所习惯的trie根节点却是包含信息的，而且认为这样也方便，下面说一下它的性质 (基于本文所讨论的简单trie树)
1. 字符的种数决定每个节点的出度，即branch数组(空间换时间思想)
2. branch数组的下标代表字符相对于a的相对位置
3. 采用标记的方法确定是否为字符串。
4. 插入、查找的复杂度均为O(len),len为字符串长度
图示
如图所示，该trie树存有abc、d、da、dda四个字符串，如果是字符串会在节点的尾部进行标记。没有后续字符的branch分支指向NULL
2. 概念，原理 要点总结:
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 要理解它的实现方式，节点孩子的表示方式
3. 扩展
压缩实现
九. Database Index and Optimization
1. Index 相关知识
基本知识都知道了，没什么好说的，这部分除了Index知识，补充一切其他的数据库的优化知识
例如这样一个查询：select * from table1 where id=44。如果没有索引，必须遍历整个表，直到ID等于44的这一行被找到为止；有了索引之后(必须是在ID这一列上建立的索引)，直接在索引里面找44（也就是在ID这一列找），就可以得知这一行的位置，也就是找到了这一行。可见，索引是用来定位的。
索引分为聚簇索引和非聚簇索引两种，聚簇索引 是按照数据存放的物理位置为顺序的，而非聚簇索引就不一样了；聚簇索引能提高多行检索的速度，而非聚簇索引对于单行的检索很快
B-Tree索引sql server 索引方式
优缺点：
创建索引大大提高系统性能，比如唯一性索引，提高select速度，显著减少分组和排序子句进行检索的时间。
缺点就是，需要占用空间，创建和维护索引话费时间，对表操作时候，索引也需要动态维护，费时,
所以索引要建在最优价值的字段上，在哪建立呢？
1). 在经常需要搜索的列上，可以加快搜索的速度；
2). 在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；
3). 在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；
4). 在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；
5). 在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。
哪些字段不该建立索引
1). 对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为，既然这些列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求。
2). 对于那些只有很少数据值的列也不应该增加索引。这是因为，由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。
3). 对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少,不利于使用索引。
4). 当修改性能远远大于检索性能时，不应该创建索引。这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因此，当修改操作远远多于检索操作时，不应该创建索引。
2. 数据库优化
以前学数据库没有认识到终点，根本没考虑过性能问题，其实这是非常重要的..这就是为什么淘宝, Facebook 活下来的原因.
此外，除了数据库索引之外，在LAMP结果如此流行的今天，数据库（尤其是MySQL）性能优化也是海量数据处理的一个热点。说下数据库优化的几个方面, mysql为例
第一，在数据库设计的时候，要能够充分的利用索引带来的性能提升，至于如何建立索引，建立什么样的索引，在哪些字段上建立索引，上面已经讲的很清楚了，这里不在赘述。另外就是设计数据库的原则就是尽可能少的进行数据库写操作（插入，更新，删除等），查询越简单越好。如下
第二，配置缓存是必不可少的，配置缓存可以有效的降低数据库查询读取次数，从而缓解数据库服务器压力，达到优化的目的，一定程度上来讲，这算是一个“围魏救赵”的办法。
可配置的缓存包括
- 索引缓存(key_buffer)
- 排序缓存(sort_buffer)
- 查询缓存(query_buffer)
- 表描述符缓存(table_cache)
第三，切表，切表也是一种比较流行的数据库优化方法。
分表包括两种方式：横向分表和纵向分表，
其中，横向分表比较有使用意义，故名思议，横向切表就是指把记录分到不同的表中，而每条记录仍旧是完整的（纵向切表后每条记录是不完整的），例如原始表中有100条记录，我要切成2个表，那么最简单也是最常用的方法就是ID取摸切表法，本例中，就把ID为1,3,5,7。。。的记录存在一个表中，ID为2,4,6,8,。。。的记录存在另一张表中。虽然横向切表可以减少查询强度，但是它也破坏了原始表的完整性，如果该表的统计操作比较多，那么就不适合横向切表。横向切表有个非常典型的用法，就是用户数据：每个用户的用户数据一般都比较庞大，但是每个用户数据之间的关系不大，因此这里很适合横向切表。最后，要记住一句话就是：分表会造成查询的负担，因此在数据库设计之初，要想好是否真的适合切表的优化：
总结：
纵向: 字段较多时候考虑，一般用处不大
横向: 有效降低表大小，减少由于加锁导致的等待，但是查询会变复杂，尤其需要排序的查询.
第四，日志分析
在数据库运行了较长一段时间以后，会积累大量的LOG日志，其实这里面的蕴涵的有用的信息量还是很大的。通过分析日志，可以找到系统性能的瓶颈，从而进一步寻找优化方案, 比如那些SQL的延迟最大，进一步改进。
查询吞吐量，数据量监控
慢查询分析: 索引，IO 和 CPU
性能分析
以上讲的都是单机MySQL的性能优化的一些经验，但是随着信息大爆炸，单机的数据库服务器已经不能满足我们的需求，于是，多多节点，分布式数据库网络出现了，其一般的结构如下：
分布式数据库结构
这种分布式集群的技术关键就是“同步复制”.. 这个图跟我平时看的不太一样，平时主要考虑master-slave 读写分离，读是多台，写是一台，master向slave 同步复制，但是如果master多台，同步过程中肯定会有问题，这块是需要深入了解的。
3. 概念，原理 要点总结:
利用数据的设计实现方法，对海量数据的增删改查进行处理。
这部分需要重复去复习下数据库index的知识，对谁建立index这个很重要，注意index的tradeoff
另外还有几大块知识，比如说
1). master - slave 读写分离，同步数据库的问题，
2). 数据库分库的问题(User, UGC)
3). 横向纵向分表的问题.
4). Denormalize 加快查询的问题
十. Inverted Index (倒排索引)
1. 什么是 Inverted Index
在信息大爆炸的今天，有了搜索引擎的帮助，使得我们能够快速，便捷的找到所求。提到搜索引擎，就不得不说VSM模型，说到VSM，就不得不聊倒排索引。可以毫不夸张的讲，倒排索引是搜索引擎的基石。
VSM检索模型
VSM全称是Vector Space Model(向量空间模型)，是IR(Information Retrieval信息检索)模型中的一种，由于其简单，直观，高效，所以被广泛的应用到搜索引擎的架构中。98年的Google就是凭借这样的一个模型，开始了它的疯狂扩张之路。废话不多说，让我们来看看到底VSM是一个什么东东。
在开始之前，我默认大家对线性代数里面的向量(Vector)有一定了解的。向量是既有大小又有方向的量，通常用有向线段表示，向量有：加、减、倍数、内积、距离、模、夹角的运算。
文档(Document)：一个完整的信息单元，对应的搜索引擎系统里，就是指一个个的网页。
标引项(Term)：文档的基本构成单位，例如在英文中可以看做是一个单词，在中文中可以看作一个词语。
查询(Query)：一个用户的输入，一般由多个Term构成。
那么用一句话概况搜索引擎所做的事情就是：对于用户输入的Query，找到最相似的Document返回给用户。而这正是IR模型所解决的问题：
信息检索模型是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法。
举个简单的例子：
现在有两篇文章(Document)分别是 “春风来了，春天的脚步近了” 和 “春风不度玉门关”。然后输入的Query是“春风”，从直观上感觉，前者和输入的查询更相关一些，因为它包含有2个春，但这只是我们的直观感觉，如何量化呢，要知道计算机是门严谨的学科^_^。这个时候，我们前面讲的Term和VSM模型就派上用场了。
首先我们要确定向量的维数，这时候就需要一个字典库，字典库的大小，即是向量的维数。在该例中，字典为{春风,来了,春天, 的,脚步,近了,不度,玉门关} ，文档向量，查询向量如下图：
PS:为了简单起见，这里分词的粒度很大。
将Query和Document都量化为向量以后，那么就可以计算用户的查询和哪个文档相似性更大了。简单的计算结果是D1和D2同Query的内积都是1，囧。当然了，如果分词粒度再细一些，查询的结果就是另外一个样子了，因此分词的粒度也是会对查询结果（主要是召回率和准确率）造成影响的。
上述的例子是用一个很简单的例子来说明VSM模型的，计算文档相似度的时候也是采用最原始的内积的方法，并且只考虑了词频(TF)影响因子，而没有考虑反词频(IDF)，而现在比较常用的是cos夹角法，影响因子也非常多，据传Google的影响因子有100+之多。
大名鼎鼎的Lucene项目就是采用VSM模型构建的，VSM的核心公式如下（由cos夹角法演变，此处省去推导过程）
从上面的例子不难看出，如果向量的维度(对汉语来将，这个值一般在30w-45w)变大，而且文档数量(通常都是海量的)变多，那么计算一次相关性，开销是非常大的，如何解决这个问题呢？不要忘记了，我们这节的主题就是 倒排索引，主角终于粉墨登场了！！！
倒排索引
倒排索引非常类似我们前面提到的Hash结构。以下内容来自维基百科：
倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。
有两种不同的反向索引形式：
- 一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。
- 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。
后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。
由上面的定义可以知道，一个倒排索引包含一个字典的索引和所有词的列表。其中字典索引中包含了所有的Term(通俗理解为文档中的词)，索引后面跟的列表则保存该词的信息(出现的文档号，甚至包含在每个文档中的位置信息)。下面我们还采用上面的方法举一个简单的例子来说明倒排索引。
例如现在我们要对三篇文档建立索引(实际应用中，文档的数量是海量的)：
文档1(D1)：中国移动互联网发展迅速
文档2(D2)：移动互联网未来的潜力巨大
文档3(D3)：中华民族是个勤劳的民族
那么文档中的词典集合为：{中国，移动，互联网，发展，迅速，未来，的，潜力，巨大，中华，民族，是，个，勤劳}
建好的索引如下图：
在上面的索引中，存储了两个信息，文档号和出现的次数。建立好索引以后，我们就可以开始查询了。例如现在有一个Query是”中国移动”。首先分词得到Term集合{中国，移动}，查倒排索引，分别计算query和d1,d2,d3的距离。有没有发现，倒排表建立好以后，就不需要在检索整个文档库，而是直接从字典集合中找到“中国”和“移动”，然后遍历后面的列表直接计算。
对倒排索引结构我们已经有了初步的了解，但在实际应用中还有些需要解决的问题(主要是由海量数据引起的)。笔者列举一些问题，并给出相应的解决方案，抛砖以引玉，希望大家可以展开讨论：
1) .左侧的索引表如何建立?怎么做才能最高效？
可能有人不假思索回答：左侧的索引当然要采取hash结构啊，这样可以快速的定位到字典项。但是这样问题又来了，hash函数如何选取呢？而且hash是有碰撞的，但是倒排表似乎又是不允许碰撞的存在的。事实上，虽然倒排表和hash异常的相思，但是两者还是有很大区别的，其实在这里我们可以采用前面提到的Bitmap的思想，每个Term(单词)对应一个位置(当然了，这里不是一个比特位)，而且是一一对应的。如何能够做到呢，一般在文字处理中，有很多的编码，汉字中的GBK编码基本上就可以包含所有用到的汉字，每个汉字的GBK编码是确定的，因此一个Term的”ID”也就确定了，从而可以做到快速定位。注：得到一个汉字的GBK号是非常快的过程，可以理解为O(1)的时间复杂度。
2) .如何快速的添加删除更新索引？
有经验的码农都知道，一般在系统的“做加法”的代价比“做减法”的代价要低很多，在搜索引擎中中也不例外。因此，在倒排表中，遇到要删除一个文档，其实不是真正的删除，而是将其标记删除。这样一个减法操作的代价就比较小了。
3) .那么多的海量文档，如果存储呢？有么有什么备份策略呢？
当然了，一台机器是存储不下的，分布式存储是采取的。一般的备份保存3份就足够了。
2. 概念，原理 要点总结:
倒排主要还是用于搜索引擎，如果不是search 类的职位，一般不会问，这部分结lunence nutch等开源框架的内容等真正碰到了再细看吧.
虽说倒排不重要，但是这是一种重要的思想，涉及search的一些题目肯定会提到
CC 150 上面有道很经典的题目，是 find all documents that contains a list of words.
No comments:
Post a Comment