LSM-Tree - LevelDb之LRU缓存引言LRU缓存在各种开源组件中都有使用的场景，常常用于做冷热数据和淘汰策略，使用LRU主要有三点。第一点是实现非常简单。第二点是代码量本身也不错。最后涉及数据结构非常经典。LevelDB对于LRU缓存实现算是比较经典的案例，这一节来介绍它是如何使用LRU实现缓存的。LeetCode 中有一道相应LR...

布隆过滤器有点类似哈希表，但是比哈希表的效率要更高，因为使用了位来判断Key是否存在，布隆过滤器在完成高效搜索key是否存在的同时带来一定的副作用-- 不保证Key一定存在，所以它只适用于允许一定容错率的系统。

跳表（SkipList）是由William Pugh提出的。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细地介绍了有关跳表结构、插入删除操作的细节。

在上一篇文章[[LSM-Tree - LevelDb了解和实现]]中介绍了LevelDb相关的数据结构和核心组件，LevelDB的核心读写部分，以及为什么在这个数据库中写入的速度要比读取的速度快上好几倍。

自从[[《数据密集型型系统设计》LSM-Tree VS BTree]]这篇文章完成之后，对于LSM-Tree这种结构非常感兴趣，于是趁热打铁在之后的几天静下心来研究了一下LevelDB的具体实现，最终阅读了一下源代码。