skiplist.h/filter_policy.h/arena.h/coding.h分析

一、skiplist.h（跳表）分析

用户只需要处理写冲突，leveldb跳表保证没有读写冲突。部分函数功能如下：

• KeyIsAfterNode()：返回值bool，key是否大于n的数据
• FindLessThan()：返回小于key的最新节点
• FindLast()：返回最后一个节点

要求不能插入重复数据，关键点在于：每个节点插于时，如何确定新插了节点的层数，以使跳表满足既率均衡进而提供高效的查性能。

跳表实现专门对多线程读做了优化,但仍需外部加锁

二、filter_policy.h分析

bloom_filter误判率和：哈希函数个数k、位数组长度m、数据集大小n有关，当k=ln2*(m/n)有最优准确率

函数的作用：Leveld中的过滤策略、查找对应的keys的Value时,如果事先知道了所有的key里都找不到这个query,就不需要进一步读取磁盘了.

使用了策略模式，将策略 单独设计为一个类或接口 ，不同的子类对应不同策略。依次计算n个key的K个哈希结果这里使用了Double hash

 三、Arena.h分析

作用：

1. 分配指定大小的字节
2. 按字节对齐的方式分配

四、coding.h分析

函数功能：这个类是用来类型转换和压缩空间的

• EncodeFixed64：将dst转为小端存到buf中

把int---->varint：是为了尽可能的节约存储空间，最高位是一个标记位