goleveldb memdb实现

goleveldb [https://github.com/syndtr/goleveldb] 中的memdb是一个跳表, 跳表的原理参看： http://blog.sina.com.cn/s/blog_72995dcc01017w1t.html

跳表高度

memdb采用常数const tMaxHeight = 12,每个插入的key-value的高度是随即确定的。

const tMaxHeight = 12
func (p *DB) randHeight() (h int) {
    const branching = 4
    h = 1
    for h < tMaxHeight && p.rnd.Int()%branching == 0 {
        h++
    }
    return
}

在插入2000万key的情况下:

func TestRandHeight(t *testing.T) {
    db := New(comparer.DefaultComparer, 0)
    fmt.Println("begin")
    m := make(map[int]int)
    for i := 0; i < 20000000; i++ {
        h := db.randHeight()
        m[h] = m[h] + 1

    }
    for k, v := range m {
        fmt.Printf("%d: %d\n", k, v)
    }
}

key高度的分布如下：

1   14998891 
2   3750488
3   938399
4   233846
5   58845
6   14742
7   3565
8   928
9   224
10  54
11  14
12  4

表明在第一级的key的个数约1500万个， 占75%*2000万
表明在第二级的key的个数约375万个， 占25%*75%*2000万
表明在第三级的key的个数约93.75万个， 占25%*25%*75%*2000万
也就是说，高一个级别的key个数是上一级的25%

数据存储

type DB struct {
    kvData []byte  -> 存储key，value值的地方，默认4m大小
    nodeData  []int -> 存放key关系的地方：后一个key的位置
    prevNode  [tMaxHeight]int  -> put/delete过程中临时保存变量的地方
    maxHeight int -> 当前跳表最高高度，默认是 1
    n         int  -> key个数
    kvSize    int -> 有效key，value占的空间
}

kvSize 不等于 len(db.kvData),因为kvData是append模式的。原因是降低gc压力。
nodeData[4:4+12]: 代表跳表高度h指向的第一个key的位置。
每一个key-value在nodeData中是由多个int来表示，假设("a9","v") 位于h1=6跳表高度（1=<h1<=12)
那么在nodeData有 10个数字表示

nodeData:   [index]  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19 
nodeData:  [content] 00 00 00 0c 10 10 10 10 10 10 00 00 00 00 00 00 00 02 01 06 00 00 00 00 00 00

kvData: len: 3,     [index]  00 01 02 
kvData: len: 3,  [content]  61 39 76

上图表示插入("a9","v") 数据后，其中nodeData,kvData对应的实际数据。
nodeData 位置从0x10～0x19的10个数据表示("a9","v")
nodeData[0x10] = 00,表示 从kvData[0]开始存储数据。
nodeData[0x11] = 02,表示 key的长度。
nodeData[0x12] = 01,表示 value的长度。
nodeData[0x13] = 06,表示 本key所在的跳表高度。
nodeData[0x14] = 00,表示 本key在的跳表高度1对应的下一个key的位置。
nodeData[0x15] = 00,表示 本key在的跳表高度2对应的下一个key的位置。
nodeData[0x16] = 00,表示 本key在的跳表高度3对应的下一个key的位置。
nodeData[0x17] = 00,表示 本key在的跳表高度4对应的下一个key的位置。
nodeData[0x18] = 00,表示 本key在的跳表高度5对应的下一个key的位置。
nodeData[0x19] = 00,表示 本key在的跳表高度6对应的下一个key的位置。

再插入一个跳表高度6的("a8","v")，后，数据如下：

nodeData:    [index]  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 20 21 22 23 
nodeData:   [content] 00 00 00 0c 1a 1a 1a 1a 1a 1a 00 00 00 00 00 00 00 02 01 06 00 00 00 00 00 00 03 02 01 06 10 10 10 10 10 10
kvData: len: 6,    [index]  00 01 02 03 04 05 
kvData: len: 6,  [content]  61 39 76 61 38 76

nodeData[0x04] = 1a,表示 跳表高度1对应的第一个key的位置。
nodeData[0x05] = 1a,表示 跳表高度2对应的第一个key的位置。
nodeData[0x06] = 1a,表示 跳表高度3对应的第一个key的位置。
nodeData[0x07] = 1a,表示 跳表高度4对应的第一个key的位置。
nodeData[0x08] = 1a,表示 跳表高度5对应的第一个key的位置。
nodeData[0x09] = 1a,表示 跳表高度6对应的第一个key的位置。

数据更新

put ("a9","v12345")会导致数据更新：

nodeData:    [index]  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 20 21 22 23 
nodeData:   [content] 00 00 00 0c 1a 1a 1a 1a 1a 1a 00 00 00 00 00 00 06 02 06 06 00 00 00 00 00 00 03 02 01 06 10 10 10 10 10 10

kvData: len: 14,    [index]  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 
kvData: len: 14,  [content]  61 39 76 61 38 76 61 39 76 31 32 33 34 35

发现nodeData的长度没有变化。但是nodeData[0x10] key的位置，nodeData[0x12] value的长度发生变化了。
发现kvData内容增加，原来的key，value（kvData[0:3] ）没有删除。

数据删除

delete ("a9")会导致数据更新：

nodeData:    [index]  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f 20 21 22 23 
nodeData:   [content] 00 00 00 0c 1a 1a 1a 1a 1a 1a 00 00 00 00 00 00 06 02 06 06 00 00 00 00 00 00 03 02 01 06 00 00 00 00 00 00

kvData: len: 14,    [index]  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 
kvData: len: 14,  [content]  61 39 76 61 38 76 61 39 76 31 32 33 34 35

发现“a9”这个key，value还是存在的，只有没有节点引用“a9”这个节点了。

数据查询

查询是从跳表高度最高级别开始，找到一个大于等于当前key的节点，然后进入下一个级别查找。