leveldb源码分析（二）leveldb数据结构
1、skiplist
跳跃表是一种O(logN)插入和查找操作的数据结构，和红黑树类似，优点是实现简单，易于理解。levedb使用的跳跃表在一般跳跃表的基础上做了一些改造，特点如下：
- 内部没有同步机制，写操作需要调用者同步，读操作可并发，写不阻塞读，读者可能丢失同时进行的写，但是不会读取不一致数据
- 相同的key只允许插入一次
- 不提供删除操作，数据插入后不允许修改内容
- 支持用户定制比较器用于key的比较
skiplist内存管理
skiplist使用arena管理内存，目的是缩减小内存的申请次数以优化性能。arena内部使用vector管理内存块，内存块默认大小为4096字节，当前块内足够分配时在当前块内分配，否则申请新块。用户类型T插入skiplist时，skiplist在arena中分配内存，在这段内存地址上定位构造T(要求T可以拷贝构造)。由于arena不记录每次T的起始地址，因此无法做析构，要求T析构函数中无处理。skiplist析构时，arena析构释放内存。
源码地址：db/skiplist.h util/arena.h util/arena.cc
2、slice
slice是leveldb使用的字符串表示
源码位置：include/leveldb/slice.h
特点：
- 维护二进制安全的字符串
- slice不管理字符串生命周期
- leveldb中使用字符串的地方多用slice做传递，原因是开销低
- 提供和string、char*之间方便的转换接口
slice结构很简单如下：
slice
| 1 2 3 4 |
|
3、varint
varint是一种紧凑数字表示法，针对小int较多的情况，能有效减少存储占用。
原理是，标准int固定4个字节，对一些小数字，高位bit实际上全是0，也占用全部的4个字节，浪费了空间。varint通过编码到原始数据的方法压缩int的大小，最终形成的变量大小从1字节到5字节不等。方法是，针对每个8bit，高位1个bit用作标记位，7位低bit用作实际数据存储。高位为0表示数据到这个字节终止，高位为1表示下个字节仍然是这个数据的一部分需要继续读取。
例如：
十进制数字10，varint编码后二进制为00000010，即高位的0 + 低位的0000010，只占用一个字节。
十进制数字200，原始二进制为11001000，编码后二进制为
低 高
11001000 00000001
占用两个字节。解码时，读到第一个字节的高位为1表示需要继续读下一个字节，取本字节低7位bit待用。读下个字节高位为0，表示到这里终止了，取出第二个字节的低位7个bit，然后将两个字节中获取到的2个7bit拼接到一起，即00000011001000，还原得到原始的200。
需要注意的是，由于在原始数据中增加了标记位，因此会导致最大增加4个bit，导致占用字节达到5个字节，对于一些超过28位的大int，会多使用一个字节，如果这种大int占比例大，那么会导致varint的压缩效果反而差了。基于对leveldb中使用int情况的观察，使用varint有正收益。
以上是对varint32的描述，leveldb同时支持varint64，原理相同，编码后长度为1至10字节
代码位置：util/coding.h util/coding.cc