LevelDB阅读笔记 之 SkipList

在leveldb中,插入与查找操作是高频操作、无删除操作。因此使用物理上线性的有序结构是不现实的,那么就是经典的二叉有序树及其变种,如AVL、红黑树甚至B\B+树,但这类数据结构都会牵扯到一个问题:随着节点的插入,需要频繁地进行平衡调节。而且为了保证线程安全,在平衡调节时需要锁住大面积地子树。而有一种以随机概率思想实现的类似平衡树的线性表结构:跳表,具体见论文

较为直观地理解跳表,可以从二分查找的思路来理解其原理。对于有序链表,由于其物理结构限制无法实现类似有序线性表的直接”二分达到“,但如果我们通过添加辅助跳转指针完成其”二分达到“,岂不是既可以实现有序链表插入\删除快的优点,又可以获得二分查找lgn时间复杂度的性能优势。但如何添加辅助跳转指针呢?模仿有序线性表设置递归中间指针,这样在随着节点插入,指针的高度就需要不停地变化,显然过于复杂。其实查找的本质就是缩小问题空间,如果限制辅助指针的高度在一个区间,为各个节点分配一个辅助指针数组,并采用随机思想(类似快排中随机选取pivot)完成数组大小指定,节点指针跳转数组相同高度的指针形成一个有序链表,这样就可以在有序链表上形成一个又一个的查找子空间,如下图所示。

4da58564-8335-4608-b97e-2e184a9e1c61

 

跳表实现有几个技术点:

  1. 插入新节点时,如何收集新节点每层跳转指针的前向节点。如对于上图21这个节点,其在插入前的从上到下的跳转指针的前向节点依次为head、9、17、19。下面的实现中FindGreaterOrEqual函数通过在遍历前向节点时,通过prev完成该信息的收集;
  2. 删除节点时,如何更新 新的最大高度。下面的实现中,通过_height_memory跳转指针高度计数,完成最大高度的更新。

以leveldb的跳表接口的一个简单实现(增加了删除节点功能):

  1. struct Node {
  2. explicit Node(int key) : _key(key) { }
  3. int _key;
  4. struct Node* Next(int n) {
  5. return _next[n];
  6. }
  7. void SetNext(int n, struct Node* x) {
  8. _next[n] = x;
  9. }
  10. private:
  11. struct Node* _next[1];
  12. };
  13.  
  14. class SkipList {
  15. public:
  16. SkipList();
  17. ~SkipList();
  18. bool Insert(int key);
  19. bool Contains(int key);
  20. void Remove(int key);
  21. private:
  22. enum { kMaxHeight = 12 };
  23. Node* _head;
  24. int _max_height;
  25. int _height_memory[kMaxHeight + 1];
  26.  
  27. int RandomHeight() { return random() % kMaxHeight; }
  28.  
  29. // Node Operations
  30. Node* NewNode(int key, int height);
  31. void DeleteNode(Node* node);
  32. bool KeyIsAfterNode(int key, Node* node) const;
  33. Node* FindGreaterOrEqual(int key, Node** prev) const;
  34.  
  35. SkipList(const SkipList&);
  36. void operator=(const SkipList&);
  37. };
  38.  
  39. SkipList::SkipList() :
  40. _head(NewNode(0, kMaxHeight)),
  41. _max_height(1) {
  42. for (int i = 0; i < kMaxHeight; i++) {
  43. _height_memory[i] = 0;
  44. }
  45. _height_memory[_max_height] ++;
  46. }
  47.  
  48. SkipList::~SkipList() {
  49. Node* x = _head;
  50. while(x) {
  51. Node* next = x->Next(0);
  52. DeleteNode(x);
  53. x = next;
  54. }
  55. }
  56.  
  57. bool SkipList::Contains(int key) {
  58. Node* node = FindGreaterOrEqual(key, NULL);
  59. return (node != NULL) && (node->_key == key);
  60. }
  61.  
  62.  
  63. void SkipList::Remove(int key) {
  64. Node* prev[kMaxHeight];
  65. while(true) {
  66. Node* node = FindGreaterOrEqual(key, prev);
  67. if (node == NULL) {
  68. break;
  69. }
  70. if (node->_key != key) {
  71. break;
  72. }
  73. int i = 0;
  74. for (; i < kMaxHeight; ++i) {
  75. if (prev[i] && prev[i]->Next(i) == node) {
  76. prev[i]->SetNext(i, node->Next(i));
  77. } else {
  78. break;
  79. }
  80. }
  81. // 高度更新
  82. _height_memory[i] --;
  83. if (_height_memory[i] == 0 && _max_height == i) {
  84. for (int j = i; j > 0; --j) {
  85. if (_height_memory[j] != 0) {
  86. _max_height = _height_memory[j];
  87. }
  88. }
  89. }
  90. DeleteNode(node);
  91. }
  92. }
  93.  
  94. Node* SkipList::NewNode(int key, int height) {
  95. int size = sizeof(Node) + sizeof(Node*) * (height -1);
  96. char* mem = (char*)malloc(size);
  97. memset(mem, 0, size);
  98.  
  99. return new (mem) Node(key);
  100. }
  101.  
  102. void SkipList::DeleteNode(Node* node) {
  103. char* mem = (char*)node;
  104. delete mem;
  105. }
  106.  
  107. bool SkipList::KeyIsAfterNode(int key, Node* node) const {
  108. return (node != NULL) && (key > node->_key);
  109. }
  110.  
  111. Node* SkipList::FindGreaterOrEqual(int key, Node** prev) const {
  112. Node* x = _head;
  113. int i = _max_height - 1;
  114. while (true) {
  115. Node* next = x->Next(i);
  116. if (KeyIsAfterNode(key, next)) { // next->_key 小于 key
  117. x = next;
  118. } else { // next->_key 大于或等于 key
  119. if (prev != NULL) {
  120. prev[i] = x;
  121. }
  122. if (i == 0) {
  123. return next;
  124. } else {
  125. --i;
  126. }
  127. }
  128. }
  129. }
  130.  
  131. bool SkipList::Insert(int key) {
  132. Node* prev[kMaxHeight];
  133. int height = RandomHeight();
  134. Node* new_node = NewNode(key, height);
  135. if (new_node == NULL) {
  136. return false;
  137. }
  138.  
  139. _height_memory[height] ++;
  140. if (height > _max_height) {
  141. _max_height = height;
  142. // 其随机高度比原最高节点还高
  143. for (int i = _max_height; i < height; i++) {
  144. prev[i] = _head;
  145. }
  146. }
  147.  
  148. Node* prev_node = FindGreaterOrEqual(key, prev);
  149. for (int i = 0; i < height; ++i) {
  150. new_node->SetNext(i, prev[i]->Next(i));
  151. prev[i]->SetNext(i, new_node);
  152. }
  153.  
  154. return true;
  155. }
  156.  
  157. int main(void) {
  158. SkipList skip_list;
  159. srandom(time(NULL));
  160.  
  161. for (int i = 0; i < 10000; i++) {
  162. skip_list.Insert(random() % 100);
  163. }
  164. for (int i = 0; i < 10000; i++) {
  165. skip_list.Insert(random() % 100);
  166. skip_list.Remove(random() % 100);
  167. }
  168. return 0;
  169. }

 

发表评论