布隆过滤器（bloom filter，BF）：
二进制向量数据结构，时空效率很好，尤其是空间效率极高。作用：检测某个元素在某个巨量集合中存在。
构造：
查询：
不会发生漏判（false negative），但误判（false positive）存在，因此BF适合允许少量误判的场景。
计数布隆过滤器（counting bloom filter，CBF）：
BF基础上支持删除元素操作。数组每个位置1bit扩展为n bits。
另外需要考虑计数溢出问题。
BF应用：
Chrome浏览器判断恶意url；爬虫对爬过的url判重；数据库领域用BF加速join过程等。
BigTable中BF用作提升读效率：在SSTable中查找key。额外增加一次读实际文件操作避免误判。Cassandra也借鉴此法。Google流式系统MillWheel保证记录“恰好送达一次”语义时检测重复记录使用此法。
SkipList：
增删改查时间复杂度O(log(n))
LSM树（Log-Structured Merge tree）：
将大量的随机写换成批量顺序写，极大提升磁盘数据写入速度。代价是降低读效率，可用BF补偿。
以LevelDB实现为例。
log文件用于系统崩溃恢复：
MemTable满时转换为Immutable MemTable，经Compaction导出为SSTable：
manifest文件：
Current文件：
Compation操作：
minor Compaction：
major Compaction：
选择Level：某Level下的SSTable文件数超过设定后，合并此Level和Level+1的SSTable
选择待合并文件：
合并过程：
Merkle Hash树（Merkle Hash Tree）
用于定位数据变化（损毁、篡改、正常修改）
Snappy与LZSS算法：
应用：BigTable，MapReduce，RPC，Hadoop，HBase，Cassandra，Avro等
压缩/解压缩：用时间换空间；Snappy追求高压缩/解压缩速度
LZ77优化得到LZSS，Snappy基于LZSS
LZSS改进LZ77：字符串小于最小匹配长度不压缩
Snappy改进LZSS：设定最小匹配长度=4，hash表内字符串片段固定长度=4，数据切割成32KB的块，滑动窗口每次后移4
Cuckoo Hashing：
解决hash冲突（collisions）问题，O(1)时间删、查，O(c)时间增。空间利用率50%。
Cuckoo Hashing应用：SILT存储系统（Partial Key Cuckoo Hashing，SILT hashing）
内存建立外存数据的索引。
疑问地方应该是：读出h_1(x)的内容并用其值（即b）替换掉哈希空间位置b的内容，即用b替换掉位置b原先的内容。
| BigTable | MillWheel | LevelDB | Redis | Lucene | SILT | RAMCloud | Cassandra | BitTorrent | Git | Dynamo | Riak | Cassandra | |
| 介绍 | flash memory | Amazon,NoSQL | 模仿Dynamo | NoSQL | |||||||||
| 算法 | bloom filter | bloom filter | SkipList | SkipList | SkipList | LSM tree | LSM tree | LSM tree | Merkle tree | Merkle tree | Merkle tree | Merkle tree | Merkle tree |
| LSM tree | LSM tree | partial key cuckoo hashing | Gossip |