第三章 大数据常用的算法与数据结构
布隆过滤器(BF)
普通布隆过滤器
布隆过滤器用于判断某个元素是否存在集合中，计算过程如下
设置一个长度为m的比特数组，设计k个相互独立的Hash函数，对于集合中的每个值，依次执行这k个函数，得到k个值(0<=K<m)，把数组中对应位置的值设置为1。当要判断某个值是否存在于该集合中时，只需要将这个值依次经过这k个函数，只要对应值的位置出现至少1个0，那么可以判读该值不存在。
对于存在集合中的元素，布隆过滤器可以准确地判断出来，但是对于不存在集合中的元素，布隆过滤器可能会出现误判。在实际应用中可以通过调整Hash函数的个数来调整误判率
改进：计数布隆过滤器
普通的BF有一个明显的缺陷就是：只能一直增加数据而无法删除数据
针对这种缺陷，可以修改BF的基本单元，原先的BF的一个基本单元是一个比特，可以修改成3，4个比特，通过增加计数和删除计数的方式来添加和删除数据。缺点就是存在计数溢出的可能
应用
由于布隆过滤器对空间的利用率极高，因此适用于BigTable中，我们都知道BigTable的数据是以key-value的形式存储在磁盘中的，多次进行磁盘的读取操作对性能的影响极大。通过把key以BF的形式存储到内存中，能够极大地提高读取效率。这种情况下即使出现了误判，也不会造成严重的影响，因为就算出现了误判，在查询BigTable的时候查询不到数据，顶多多一次查询而已，但是如果是真正存在于BF中的，就一定能够准确地命中数据。
跳表(SkipList)
跳表的内容比较简单，普通链表查找数据的平均查找次数是(n+1)/2，跳表就是在链表的基础上，增加链表的层数，加快链表指针的移动。详细的可以看下面
LSM树
LSM树用于许多数据库的存储引擎，在说LSM树之前，先说下其他的引擎
哈希存储引擎：使用的是hash，支持增删改以及随机读取，但是不支持顺序扫描
B+树存储引擎：B树、B+树、红黑树、AVL树
LSM树：和B+树存储引擎一样，支持增删改以及随机读取，且能够顺序扫描。通过批量存储技术规避了磁盘随机写入问题，但是牺牲了读性能
LSM对于数据的修改先是在内存中进行，达到一定量之后，再把这些修改操作批量写入磁盘，但是读取的时候，需要结合磁盘中的历史数据和内存中的修改操作。只适用于写多读少且key值有序的场景，很多BigTable使用了LSM树，如HBase、LevelDB、Google BigTable
LSM存储模型
WAL(Write-ahead logging)：预写入日志。由于LSM中对于数据的操作先是保存在内存当中的，如果发生了断电问题，数据将会发生丢失，因此在写入内存之前，会先把操作写入到日志文件中，即使程序挂掉，也能通过日志进行回复。由于是顺序写入，因此速度很快。当成功写入日志后，才把数据的操作写入到内存。
MemTable：MemTable是数据在内存中的存储结构，一般使用skipList实现，内部根据key进行排序。
Immutable Memtable：当MemTable中的数据量达到一定阈值的时候，首先会把MemTable转换成Immutable Memtable，再生成新的MemTable提供写入操作。Immutable Memtable和Memtable的区别是前者是只读的，后者是可读可写的。设计Immutable Memtable的目的是为了避免在将MemTable的数据写入磁盘时阻塞写操作。
SSTable：SSTable是MemTable在磁盘中的存储形式，内部也是根据key进行排序的，通常为了加快查询速度，也会加入索引。SSTable一般采用分层的方式，MemTable中数据达到阈值后，会在Level 0层创建一个新的SSTable，当某一层的SSTable文件也达到也阈值时，会用多路归并排序的方式和更高一级的SSTable文件进行合并。
LSM操作流程
写操作、更新操作：从前面的存储模型中可以看到，对数据的各种操作都是先写入到日志，再写入到内存中。
删除操作：删除操作时并不会立刻删除数据，而是插入一条标记数据，标记该数据已被删除，在后面合并SSTable文件时，数据才会被真正删除
Compaction：该过程就是对SSTable文件进行合并。由于对数据的更新、删除、插入操作都是写入到内存中，再保存到磁盘上，因此存在同一个key有许多条记录，Compaction可以节省磁盘空间。合并过程一般采用分级合并的方法，合并后的文件有以下特点：
1、每一层的SSTable文件的key值范围不会出现交叉，这样每次查询速度只需查询一个文件即可(第一层不适用于该特点，因为key值会落在多个文件中)
2、当一层的文件数据达到指定数量后，其中的一个文件会被合并进入上一层的文件中
读取操作：前面讲到LSM的读取效率比较低，结合上面的各种操作的流程也可以得知读取数据的流程效率低下的原因。读取数据时依次查询Memtable，Immutable Memtable，各层的SSTable。
对于读取操作的优化：在一些数据库中会对读操作进行优化，如LevelDB中的Mainfest文件，该文件记录了SSTable文件的一些关键信息，如Level层数，每一层的最大key和最小key等。一般这种文件会保存在内存中，方便查询。
此外，还能够利用上面说到了BF，可以快速判断key是否存在于数据中。
