levelDB使用skiplist作为索引,实现其实不难,但在levelDB中为了减少浪费空间,使用了variant32类型,具体细节可以参考这里

这里是KV的内部结构:

skiplist1

因此,我们需要首先从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 的结构。

skiplist2

results matching ""

    No results matching ""