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的节点，然后进入下一个级别查找。
