levelDB使用skiplist作为索引,实现其实不难,但在levelDB中为了减少浪费空间,使用了variant32类型,具体细节可以参考这里。
这里是KV的内部结构:
因此,我们需要首先从key的指针位置找到internal key size,然后找到对应的user key,之后再用同样的方法找到value
使用GetVarint32Ptr
函数可以方便的帮助我们偏移指针和找到key size,构造print函数为:
template<typename Key, class Comparator>
void SkipList<Key,Comparator>::PrintTable() {
uint32_t* value;
for(int i = GetMaxHeight()-1; i >= 0;i--)
{
Node* tmp = head_->Next(i);
printf("\n-------------PRINT-------------\n");
while(tmp!=NULL)
{
uint32_t keylen = 1;
uint32_t valuelen = 1;
const char* keyPtr = GetVarint32Ptr(tmp->key,tmp->key+5,&keylen);
const char* valuePtr = GetVarint32Ptr(keyPtr+keylen,keyPtr+keylen+5,&valuelen);
char key[keylen] = {""};
char value[valuelen] = {""};
strncpy(key, keyPtr, keylen-8);
strncpy(value, valuePtr, valuelen+1);
key[keylen-8] = '\0';
if (key[keylen-7] == '0')
continue;
// value[valuelen] = '\0';
printf("%s:%s \t",key,value);
tmp = tmp->Next(i);
}
}
}
因此,当每次插入一个kv时,我们都打印当前skiplist 的结构。