![\"SkipList\u793a\u610f\u56fe\"](\"http:\/\/www.myway5.com\/wp-content\/uploads\/2017\/07\/SkipList1-1024x146.png\")
<\/p>\n\u5728\u4e4b\u524d\u7684\u6587\u7ae0\u4e2d\u63d0\u5230\uff0cleveldb\u6240\u6709\u7684\u8bb0\u5f55\u90fd\u662f\u7531\u4e00\u4e2a\u4e2alog\u6587\u4ef6\u9010\u6e10\u8f6c\u53d8\u6765\u7684\uff0c\u4e0e\u5b58\u50a8\u5728\u78c1\u76d8\u4e0a\u7684log\u6587\u4ef6\u5bf9\u5e94\u7684\u5c31\u662f\u5185\u5b58\u4e2d\u7684memtable\u3002memtable\u548clog\u6587\u4ef6\u5b58\u50a8\u7684\u5185\u5bb9\u662f\u4e00\u81f4\u7684\u3002<\/p>\n
memtable\u4e2d\u7684\u952e\u503c\u5bf9\u662f\u901a\u8fc7SkipList\u8fd9\u79cd\u6570\u636e\u7ed3\u6784\u5b58\u50a8\u7684\uff0cSkipList\u76f8\u5bf9\u4e8e\u666e\u901a\u7684List\u6765\u8bf4,\u666e\u901a\u7684List\u67e5\u627e\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n)\uff0c\u800cSkipList\u53ef\u4ee5\u8fbe\u5230O(log(n)),\u540c\u65f6\uff0cSkipList\u76f8\u5bf9\u4e0e\u7ea2\u9ed1\u6811\uff0c\u5728\u591a\u7ebf\u7a0b\u4e0a\uff0c\u9700\u8981\u9501\u4f4f\u7684\u6570\u636e\u91cf\u66f4\u5c0f\uff0c\u6027\u80fd\u66f4\u4f18\u3002<\/p>\n
<\/p>\n
\u6bd4\u5982\u4e0a\u56fe\u5c31\u662f\u4e00\u4e2aSkipList\u7ed3\u6784\uff0c\u5982\u679c\u6211\u4eec\u9700\u8981\u641c\u7d2245\u8fd9\u4e2a\u70b9\uff0c\u6211\u4eec\u9996\u5148\u5728\u6700\u9ad8\u5c42(\u7b2c\u4e8c\u5c42)\u627e\u523030,\u7136\u540e\u53d1\u73b0\u4e0b\u4e00\u4e2a\u70b9\u662f57\uff0c\u5df2\u7ecf\u5927\u4e8e45\u4e86\uff0c\u4e8e\u662f\u6765\u5230\u4e0b\u4e00\u5c42(\u7b2c\u4e00\u5c42)\u4ece30\u5f00\u59cb,\u5411\u540e\u627e\uff0c\u5c31\u80fd\u627e\u523045\u4e86\uff0c\u5728\u8fd9\u4e2a\u8fc7\u7a0b\u4e2d\uff0c\u6211\u4eec\u8df3\u8fc7\u4e86\u5f88\u591a\u4e2a\u70b9\u3002\u56e0\u6b64\u8fd9\u79cd\u6570\u636e\u7ed3\u6784\u5f97\u540dSkipList\u3002<\/p>\n
SkipList\u662fmemtable\u4e2d\u7528\u5230\u7684\u6700\u4e3b\u8981\u7684\u6570\u636e\u7ed3\u6784\u3002
\nSkipList\u7684\u7ebf\u7a0b\u5b89\u5168\u7279\u70b9\uff1a\u5199\u64cd\u4f5c\u9700\u8981\u5916\u90e8\u7684\u540c\u6b65\uff0c\u6bd4\u5982\u4fe1\u53f7\u91cf\u8fd9\u79cd\u3002\u8bfb\u64cd\u4f5c\u9700\u8981\u4fdd\u8bc1\u5728\u8bfb\u7684\u65f6\u5019SkipList\u4e0d\u4f1a\u88ab\u9500\u6bc1\u3002\u9664\u6b64\u4e4b\u5916\uff0c\u8bfb\u64cd\u4f5c\u6ca1\u6709\u4efb\u4f55\u7684\u5185\u90e8\u9501\u6216\u8005\u540c\u6b65\u3002
\nSkipList\u7684\u57fa\u672c\u539f\u5219\uff1a
\n\uff081\uff09\u5206\u914d\u8282\u70b9\u5728SkipList\u9500\u6bc1\u4e4b\u524d\u4e0d\u4f1a\u88ab\u5220\u9664\u3002\u56e0\u4e3a\u5728\u4ee3\u7801\u4e2d\u6211\u4eec\u6ca1\u6709\u4efb\u4f55\u7684\u5220\u9664\u8282\u70b9\u7684\u64cd\u4f5c\u3002
\n\uff082\uff09\u4e00\u4e2a\u8282\u70b9\u7684\u5185\u5bb9\uff0c\u9664\u4e86next\/prev\u6307\u9488,\u5728\u8fd9\u4e2a\u8282\u70b9\u88ab\u5b58\u50a8\u5230SkipList\u4e4b\u540e\u5176\u4ed6\u6570\u636e\u90fd\u662f\u4e0d\u53d8\u7684\u3002\u53ea\u6709Insert()\u4f1a\u4fee\u6539list\u7684\u5185\u5bb9\uff0c\u521d\u59cb\u5316\u4e00\u4e2a\u8282\u70b9\u5e76\u4f7f\u7528release-stores\u53bb\u5c06\u8fd9\u4e2a\u8282\u70b9\u5b58\u653e\u5230\u4e00\u4e2a\u6216\u591a\u4e2alist\u4e2d\u9700\u8981\u8c28\u614e\u5bf9\u5f85\u3002<\/p>\n
SkipList\u4e2d\uff0c\u516c\u5171\u7684\u6210\u5458\u51fd\u6570\u53ea\u6709\u4e24\u4e2a
\nvoid Insert(const Key& key);
\nbool Contains(const Key& key) const;<\/p>\n
\u987e\u540d\u601d\u4e49\uff0cInsert\u7528\u6765\u5411SkipList\u4e2d\u63d2\u5165key\uff0cContains\u7528\u6765\u68c0\u67e5SkipList\u4e2d\u662f\u5426\u5305\u542b\u67d0\u4e2akey\u3002<\/p>\n
\u79c1\u6709\u7684\u6210\u5458\u51fd\u6570\u5982\u4e0b:<\/p>\n
Node* NewNode(const Key& key, int height);\n int RandomHeight();\n bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }\n\n \/\/ Return true if key is greater than the data stored in \"n\"\n bool KeyIsAfterNode(const Key& key, Node* n) const;\n\n \/\/ Return the earliest node that comes at or after key.\n \/\/ Return NULL if there is no such node.\n \/\/\n \/\/ If prev is non-NULL, fills prev[level] with pointer to previous\n \/\/ node at \"level\" for every level in [0..max_height_-1].\n Node* FindGreaterOrEqual(const Key& key, Node** prev) const;\n\n \/\/ Return the latest node with a key < key.\n \/\/ Return head_ if there is no such node.\n Node* FindLessThan(const Key& key) const;\n\n \/\/ Return the last node in the list.\n \/\/ Return head_ if list is empty.\n Node* FindLast() const;\n<\/code><\/pre>\n2.3 SkipList\u7684\u8282\u70b9Node\u5b9e\u73b0<\/h2>\n\/\/ Implementation details follow\ntemplate<typename Key, class Comparator>\nstruct SkipList<Key,Comparator>::Node {\n explicit Node(const Key& k) : key(k) { }\n\n Key const key;\n\n \/\/ Accessors\/mutators for links. Wrapped in methods so we can\n \/\/ add the appropriate barriers as necessary.\n Node* Next(int n) {\n assert(n >= 0);\n \/\/ Use an 'acquire load' so that we observe a fully initialized\n \/\/ version of the returned Node.\n return reinterpret_cast<Node*>(next_[n].Acquire_Load());\n }\n void SetNext(int n, Node* x) {\n assert(n >= 0);\n \/\/ Use a 'release store' so that anybody who reads through this\n \/\/ pointer observes a fully initialized version of the inserted node.\n next_[n].Release_Store(x);\n }\n\n \/\/ No-barrier variants that can be safely used in a few locations.\n Node* NoBarrier_Next(int n) {\n assert(n >= 0);\n return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());\n }\n void NoBarrier_SetNext(int n, Node* x) {\n assert(n >= 0);\n next_[n].NoBarrier_Store(x);\n }\n\n private:\n \/\/ Array of length equal to the node height. next_[0] is lowest level link.\n port::AtomicPointer next_[1];\n};\n<\/code><\/pre>\n\u6ce8\u610f\u5230Node\u5b9e\u73b0\u4e86\u4e24\u4e2a\u7248\u672c\u7684Next\u548cSetNext\uff0c\u5e26\u6709NoBarrier_\u7684\u662f\u591a\u8fdb\u7a0b\u4e0d\u5b89\u5168\u7684\uff0c\u56e0\u4e3a\u5728\u5c11\u6570\u60c5\u51b5\u4e0b\u4f1a\u7528\u5230\uff0c\u56e0\u6b64\u505a\u4e86\u989d\u5916\u7684\u5b9e\u73b0\u3002\u53e6\u5916\uff0c\u53ef\u4ee5\u6ce8\u610f\u8fd9\u91cc\u53ea\u5b9e\u73b0\u4e86Next()\u65b9\u6cd5\uff0c\u5e76\u6ca1\u6709Prev()\u6307\u5411\u4e0a\u4e00\u4e2a\u8282\u70b9\uff0c\u53ef\u4ee5\u77e5\u9053SkipList\u5e76\u4e0d\u662f\u4e00\u4e2a\u53cc\u5411\u94fe\u8868<\/code>\uff0c\u4f46\u662fSkipList\u7684\u8fed\u4ee3\u5668\u662f\u652f\u6301Prev()\u65b9\u6cd5\u7684\uff0c\u6240\u4ee5\u8fd9\u662f\u4e00\u4e2a\u503c\u5f97\u6ce8\u610f\u7684\u5730\u65b9\u3002<\/p>\nNode\u8282\u70b9\u7684\u521b\u5efa\u662f\u901a\u8fc7NewNode()\u65b9\u6cd5<\/p>\n
template<typename Key, class Comparator>\ntypename SkipList<Key,Comparator>::Node*\nSkipList<Key,Comparator>::NewNode(const Key& key, int height) {\n char* mem = arena_->AllocateAligned(\n sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));\n return new (mem) Node(key);\n}\n<\/code><\/pre>\nNewNode\u4e2d\u4f7f\u7528\u4e86arena\u6765\u5206\u914d\u5bf9\u9f50\u7684\u5185\u5b58\uff0c\u5206\u914d\u7684\u5185\u5b58\u5927\u5c0f\u662fsizeof(Node)+sizeof(port::AtomicPointer) * (height - 1)<\/code>\u3002\u8fd9\u91cc\u53ef\u4ee5\u6ce8\u610f\u5230\u7533\u8bf7\u7684\u7a7a\u95f4\u4e0d\u4ec5\u4ec5\u662f\u4e00\u4e2aNode\u7684\u5927\u5c0f\uff0c\u8fd8\u5305\u62ecsizeof(port::AtomicPointer) * (height – 1)\uff0c\u8fd9\u662f\u56e0\u4e3aSkipList\u662f\u4e00\u4e2a\u591a\u5c42\u7684\u7ed3\u6784\uff0c\u6240\u4ee5\u5982\u679c\u5f53\u524dNode\u662f3\u5c42\uff0c\u90a3\u4e48\u5c31\u9700\u89813\u4e2aNext\u6307\u9488\uff0c\u5728Node\u7684\u4ee3\u7801\u4e2d\uff0c\u9ed8\u8ba4\u53ea\u7533\u8bf7\u4e86\u4e00\u4e2aNext\u6307\u9488\u7a7a\u95f4\uff0c\u6240\u4ee5\u9700\u8981\u989d\u5916\u7684\u591a\u7533\u8bf7(height – 1)\u4e2aAtomicPointer\u7684\u7a7a\u95f4\u3002<\/p>\n2.4 SkipList\u7684\u8fed\u4ee3\u5668(Iterator)<\/h3>\n
SkipList\u5b9e\u73b0\u4e86\u81ea\u5df1\u7684\u8fed\u4ee3\u5668\uff0c\u8fed\u4ee3\u5668\u7684\u58f0\u660e\u5982\u4e0b\uff1a<\/p>\n
class Iterator {\n public:\n \/\/ Initialize an iterator over the specified list.\n \/\/ The returned iterator is not valid.\n explicit Iterator(const SkipList* list);\n\n \/\/ \u5982\u679c\u8fed\u4ee3\u5668\u4f4d\u4e8e\u4e00\u4e2a\u6709\u6548\u7684\u8282\u70b9\u4e0a\uff0c\u5c31\u4f1a\u8fd4\u56detrue.\n bool Valid() const;\n\n \/\/ \u8fd4\u56de\u5f53\u524d\u4f4d\u7f6e\u7684key.\n \/\/ REQUIRES: Valid()\n const Key& key() const;\n\n \/\/ \u524d\u8fdb\u5230\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\n \/\/ REQUIRES: Valid()\n void Next();\n\n \/\/ \u540e\u9000\u5230\u4e0a\u4e00\u4e2a\u4f4d\u7f6e\n \/\/ REQUIRES: Valid()\n void Prev();\n\n \/\/ \u79fb\u5230\u7b2c\u4e00\u4e2akey >= target\u7684entry\n void Seek(const Key& target);\n\n \/\/ \u79fb\u5230\u8fd9\u4e2alist\u7684\u7b2c\u4e00\u4e2aentry\n \/\/ \u5982\u679clist\u975e\u7a7a\uff0c\u8fed\u4ee3\u5668\u7684\u6700\u7ec8\u72b6\u6001\u662fValid()\n void SeekToFirst();\n\n \/\/ \u79fb\u5230\u8fd9\u4e2alist\u7684\u6700\u540e\u4e00\u4e2aentry\n \/\/ \u5982\u679clist\u975e\u7a7a\uff0c\u8fed\u4ee3\u5668\u7684\u6700\u7ec8\u72b6\u6001\u662fValid()\n void SeekToLast();\n\n private:\n const SkipList* list_; \n Node* node_;\n \/\/ Intentionally copyable\n };\n<\/code><\/pre>\n\u5176\u4e2dPrev()\u7684\u5b9e\u73b0\u5e76\u4e0d\u662f\u901a\u8fc7prev\u6307\u9488\uff0c\u56e0\u4e3a\u4e0a\u6587\u4e2d\u5df2\u7ecf\u4ecb\u7ecd\u4e86Node\u53ea\u6709next\u6307\u9488\u3002Prev()\u662f\u901a\u8fc7FindLessThan\u6765\u5b9e\u73b0\uff0c\u627e\u5230\u5c0f\u4e8e\u6307\u5b9aNode\u7684\u6700\u540e\u4e00\u4e2a\u503c\u3002\u8fd9\u91cc\u6709\u4e00\u4e2a\u95ee\u9898\uff0c\u4e3a\u4ec0\u4e48\u4e0d\u4f7f\u7528prev\u6307\u9488\uff0c\u96be\u9053\u4e0d\u4f1a\u5927\u5927\u7684\u964d\u4f4e\u65f6\u95f4\u590d\u6742\u5ea6\u5417\uff1f<\/code>\u770b\u4e00\u4e0bFindLessThan\u7684\u5177\u4f53\u5b9e\u73b0\u3002<\/p>\ntemplate<typename Key, class Comparator>\ntypename SkipList<Key,Comparator>::Node*\nSkipList<Key,Comparator>::FindLessThan(const Key& key) const {\n Node* x = head_;\n int level = GetMaxHeight() - 1;\n while (true) {\n assert(x == head_ || compare_(x->key, key) < 0);\n Node* next = x->Next(level);\n if (next == NULL || compare_(next->key, key) >= 0) {\n if (level == 0) {\n return x;\n } else {\n \/\/ Switch to next list\n level--;\n }\n } else {\n x = next;\n }\n }\n}\n<\/code><\/pre>\n\u5176\u5b9e\u5c31\u662fSkipList\u67e5\u627e\u8fc7\u7a0b\u7684\u5b9e\u73b0\u3002\u65f6\u95f4\u590d\u6742\u5ea6\u5e94\u8be5\u662fO(log(n)).\u76f8\u6bd4\u4e8eprev\u6307\u9488\u7684\u8bdd\uff0c\u5728\u7a7a\u95f4\u5360\u7528\u4e0a\u662f\u5c11\u4e00\u70b9\u7684\u3002\u5177\u4f53\u4e3a\u4ec0\u4e48\u8fd9\u6837\u5b9e\u73b0\u8fd8\u5f97\u7ee7\u7eed\u5f80\u4e0b\u770b\u3002<\/p>\n
SkipList\u8fd8\u4ee5\u540c\u6837\u7684\u65b9\u5f0f\u5b9e\u73b0\u4e86FindGreaterOrEqual<\/code>\u548cFindLast<\/code>\u3002<\/p>\ntemplate<typename Key, class Comparator>\ntypename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)\n const {\n Node* x = head_;\n int level = GetMaxHeight() - 1;\n while (true) {\n Node* next = x->Next(level);\n if (KeyIsAfterNode(key, next)) {\n \/\/ Keep searching in this list\n x = next;\n } else {\n if (prev != NULL) prev[level] = x;\n if (level == 0) {\n return next;\n } else {\n \/\/ Switch to next list\n level--;\n }\n }\n }\n}\n<\/code><\/pre>\nFindGreaterOrEqual<\/code>\u7684\u5b9e\u73b0\u8fd8\u662f\u6bd4\u8f83\u6709\u610f\u601d\u7684\uff0c\u5728\u8fd4\u56de\u6bd4\u6307\u5b9akey\u5927\u4e8e\u6216\u7b49\u4e8e\u7684\u8282\u70b9\u7684\u540c\u65f6\uff0c\u8fd8\u53ef\u4ee5\u9009\u62e9\u6027\u7684\u5c06\u8be5\u8282\u70b9\u7684prev\u6307\u9488\u4fdd\u5b58\u5230Node** prev\u4e2d\uff0c\u8fd4\u56de\u7ed9\u7528\u6237\u3002\u5176\u5b9e\u8fd9\u4e5f\u662fIterator\u4e2dPrev()\u7684\u5b9e\u73b0\u4e0d\u91c7\u7528prev\u6307\u9488\u7684\u539f\u56e0\uff0c\u56e0\u4e3a\u6709\u4e86FindGreaterOrEqual\u8fd9\u6837\u7684\u5b9e\u73b0\uff0cSkipList\u7684\u5185\u90e8\u5b9e\u73b0\u4e2d\u6839\u672c\u4e0d\u9700\u8981Prev()\u6765\u5c06\u6307\u9488\u5411\u524d\u79fb\u52a8\uff0c\u540c\u65f6\u53c8\u5927\u5927\u7684\u8282\u7ea6\u4e86\u5185\u5b58\u3002<\/p>\n\u4e0b\u9762\u770b\u4e00\u4e0bSkipList\u7684Insert\u7684\u5b9e\u73b0\u3002<\/p>\n
void SkipList<Key,Comparator>::Insert(const Key& key) {\n \/\/ TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()\n \/\/ here since Insert() is externally synchronized.\n Node* prev[kMaxHeight];\n Node* x = FindGreaterOrEqual(key, prev);\n\n \/\/ Our data structure does not allow duplicate insertion\n assert(x == NULL || !Equal(key, x->key));\n\n int height = RandomHeight();\n if (height > GetMaxHeight()) {\n for (int i = GetMaxHeight(); i < height; i++) {\n prev[i] = head_;\n }\n \/\/fprintf(stderr, \"Change height from %d to %d\\n\", max_height_, height);\n\n \/\/ It is ok to mutate max_height_ without any synchronization\n \/\/ with concurrent readers. A concurrent reader that observes\n \/\/ the new value of max_height_ will see either the old value of\n \/\/ new level pointers from head_ (NULL), or a new value set in\n \/\/ the loop below. In the former case the reader will\n \/\/ immediately drop to the next level since NULL sorts after all\n \/\/ keys. In the latter case the reader will use the new node.\n max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));\n }\n\n x = NewNode(key, height);\n for (int i = 0; i < height; i++) {\n \/\/ NoBarrier_SetNext() suffices since we will add a barrier when\n \/\/ we publish a pointer to \"x\" in prev[i].\n x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));\n prev[i]->SetNext(i, x);\n }\n}\n<\/code><\/pre>\n\u9996\u5148\uff0cInsert\u65b9\u6cd5\u4e2d\u6ca1\u6709\u505a\u4efb\u4f55\u7684\u591a\u7ebf\u7a0b\u540c\u6b65\uff0c\u6240\u4ee5\u9700\u8981\u8c03\u7528\u8005\u5728\u5916\u90e8\u8fdb\u884c\u5199\u5165\u540c\u6b65(\u9632\u6b62\u591a\u4e2a\u7ebf\u7a0b\u540c\u6b65\u5199\u5165)\u3002<\/p>\n
\u63d2\u5165\u7684\u8fc7\u7a0b\u662f\u5148\u627e\u5230\u9700\u8981\u63d2\u5165\u7684\u4f4d\u7f6e\uff0c\u7136\u540e\u8c03\u7528RandomHeight()\u6765\u968f\u673a\u5f97\u5230\u5f53\u524d\u8282\u70b9\u7684\u9ad8\u5ea6\uff0c\u4e4b\u540e\u5411\u666e\u901a\u94fe\u8868\u4e00\u6837\u6267\u884c\u63d2\u5165\u64cd\u4f5c\u3002<\/p>\n
\u6ce8\u610f\u5230\u8fd9\u91cc\u6709\u4e00\u4e2a\u591a\u7ebf\u7a0b\u8bfb\u5199\u7684\u95ee\u9898\u3002\u4e5f\u5c31\u662f\u5f53\u6211\u4eec\u6539\u53d8max_height_\u7684\u503c\u7684\u65f6\u5019\uff0c\u5e76\u6ca1\u6709\u6539\u53d8head_\u6307\u9488\u3002\u8fd9\u79cd\u60c5\u51b5\u4e0b\u6709\u4e24\u79cd\u53ef\u80fd,\u4e00\u662f\u8bfb\u5230\u4e86\u65b0\u7684max_height_\uff0c\u4f46\u662fhead_\u6307\u9488\u8fd8\u6ca1\u6709\u66f4\u6539,\u8fd9\u65f6\u5019\u6307\u9488\u4f1a\u7acb\u523b\u4e0b\u964d\u5230\u4e0b\u4e00\u7ea7\uff0cSkipList\u7684\u591a\u7ea7\u53ea\u662f\u4e3a\u4e86\u63d0\u9ad8\u67e5\u627e\u901f\u5ea6\uff0c\u6240\u4ee5\u5728\u8fd9\u91cc\u5e76\u6ca1\u6709\u5176\u4ed6\u7684\u526f\u4f5c\u7528\uff1b\u4e8c\u662f\u6b63\u5e38\u7684\u60c5\u51b5\uff0c\u4e0d\u4f5c\u8ba8\u8bba\u3002<\/p>\n
2.Memtable<\/h2>\n
Memtable\u7684\u5b9e\u73b0\u4e3b\u8981\u5c31\u662f\u4f9d\u8d56\u4e8eSkipList\uff0c\u5206\u6790\u4e86SKipList\u4e4b\u540e\uff0cMemtable\u7684\u63d2\u5165\uff0c\u67e5\u627e\u64cd\u4f5c\u90fd\u662fSkipList\u7684\u63d2\u5165\u548c\u67e5\u627e\u3002<\/p>\n
\/\/ Increase reference count.\n void Ref() { ++refs_; }\n\n \/\/ Drop reference count. Delete if no more references exist.\n void Unref() {\n --refs_;\n assert(refs_ >= 0);\n if (refs_ <= 0) {\n delete this;\n }\n }\n<\/code><\/pre>\nMemtable\u7684\u5b9e\u73b0\u4f7f\u7528\u4e86\u7c7b\u4f3c\u4e8e\u8ba1\u6570\u5668\u5f15\u7528\u7684\u673a\u5236\uff0c\u4e0d\u8fc7\u8fd9\u662f\u624b\u52a8\u5b9e\u73b0\u7684\uff0c\u6240\u4ee5\u9700\u8981\u7528\u6237\u5728\u4f7f\u7528Memtable\u65f6\u8c03\u7528Ref()\u6765\u589e\u52a0\u5f15\u7528\u8ba1\u6570\uff0c\u5f15\u7528\u7ed3\u675f\u540e\u8c03\u7528Unref\u6765\u51cf\u5c11\u5f15\u7528\u8ba1\u6570\uff0c\u5f53\u5f15\u7528\u8ba1\u6570\u4e3a0\u65f6\u5219\u9500\u6bc1\u81ea\u5df1\u3002<\/p>\n
\u603b\u7ed3<\/h2>\n
Memtable\u7684\u8bbe\u8ba1\u8fd8\u662f\u5f88\u8ba9\u4eba\u4f69\u670d\u7684\uff0c\u81f3\u5c11\u5bf9\u6211\u6765\u8bf4\u662f\u8fd9\u6837\u3002\u4e86\u89e3\u5230\u4e86SkipList\u8fd9\u6837\u7684\u6570\u636e\u7ed3\u6784\uff0c\u4e5f\u4e86\u89e3\u5230\u5185\u5b58\u5c4f\u969c\u8fd9\u79cd\u591a\u8fdb\u7a0b\u60c5\u51b5\u4e0b\u4ee3\u7801\u6267\u884c\u4e71\u5e8f\u7684\u95ee\u9898\uff0c\u8fd8\u6709\u5185\u5b58\u5bf9\u9f50\u7684\u5fc5\u8981\u3001\u5185\u5b58\u5bf9\u9f50\u7684\u5b9e\u73b0\u3002\u540c\u65f6\u4e5f\u4e86\u89e3\u4e86\u4e00\u4e9bC++\u7f16\u5199\u7a0b\u5e8f\u7684\u72ec\u7279\u98ce\u683c\uff08\u6211\u5199\u7684C++\u4e00\u76f4\u50cfJava\uff0c\u53cd\u800c\u5c11\u4e86\u4e00\u70b9C++\u7684\u7f8e\uff09<\/p>\n","protected":false},"excerpt":{"rendered":"