{"id":28777,"date":"2026-01-15T08:32:41","date_gmt":"2026-01-15T00:32:41","guid":{"rendered":"https:\/\/aif.amtbbs.org\/?p=28777"},"modified":"2026-01-15T08:33:49","modified_gmt":"2026-01-15T00:33:49","slug":"%e5%ad%98%e5%82%a8%e5%bc%95%e6%93%8e%e7%9a%84%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e9%98%b5%e8%90%a5","status":"publish","type":"post","link":"https:\/\/aif.amtbbs.org\/index.php\/2026\/01\/15\/28777\/","title":{"rendered":"\u5b58\u50a8\u5f15\u64ce\u7684\u6570\u636e\u7ed3\u6784\u9635\u8425"},"content":{"rendered":"<div><img data-dominant-color=\"3378a3\" data-has-transparency=\"false\" style=\"--dominant-color: #3378a3;\" loading=\"lazy\" decoding=\"async\" class=\"not-transparent alignnone size-full wp-image-28780\" src=\"https:\/\/aiforumimage.oss-cn-shanghai.aliyuncs.com\/wp-content\/uploads\/2026\/01\/4480a6d243beaadfcff105d3b2868fd696f28e-300x167-1.jpg\" width=\"300\" height=\"167\" alt=\"\" srcset=\"https:\/\/aiforumimage.oss-cn-shanghai.aliyuncs.com\/wp-content\/uploads\/2026\/01\/4480a6d243beaadfcff105d3b2868fd696f28e-300x167-1.jpg 300w, https:\/\/aiforumimage.oss-cn-shanghai.aliyuncs.com\/wp-content\/uploads\/2026\/01\/4480a6d243beaadfcff105d3b2868fd696f28e-300x167-1-150x84.jpg 150w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/div>\n<div><\/div>\n<div class=\"article-desc\">\u4ece\u66f4\u5e7f\u9614\u7684\u89c6\u89d2\u6765\u770b\uff0cB+ Tree \u548c LSM-Tree \u4e0d\u518d\u662f\u5b64\u7acb\u7684\u4e24\u4e2a\u9635\u8425\u548c\u5355\u4e00\u9009\u62e9\uff0c\u800c\u662f\u4f4d\u4e8e\u7531\u591a\u79cd\u8bbe\u8ba1\/\u6743\u8861\u7ef4\u5ea6\u6784\u6210\u7684\u4ea4\u53c9\u533a\u57df\u3002<\/div>\n<div id=\"postspictures\" class=\"article-content\">\n<div id=\"container\" class=\"container am-engine\" data-v-01a18e2f=\"\" data-element=\"root\">\n<h3>\u4e00\u3001\u4e3b\u6d41\u9635\u8425<\/h3>\n<p>\u5728\u4e3b\u6d41\u7684\u3001\u901a\u7528\u7684\u3001\u57fa\u4e8e HDD\/SSD \u7684\u6301\u4e45\u5316\u5b58\u50a8\u5f15\u64ce\u9886\u57df\u4e2d\uff0cLSM-Tree \u548c B+ Tree \u786e\u5b9e\u662f\u4e3b\u6d41\u7684\u4e24\u5927\u4e3b\u5bfc\u9635\u8425\uff0c\u5b83\u4eec\u5206\u522b\u4ee3\u8868\u4e86\u00a0\u4f18\u5316\u5199\u00a0\u548c\u00a0\u4f18\u5316\u8bfb\u00a0\u4e24\u79cd\u6838\u5fc3\u8bbe\u8ba1\u7684\u6743\u8861\u3002<\/p>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/1916ccc1241c86ebe014339f2eb0f9391bffda.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>\u4e24\u79cd\u6570\u636e\u7ed3\u6784\u7684\u8bbe\u8ba1\u90fd\u6e90\u4e8e\u4e00\u4e2a\u57fa\u672c\u7684\u5b58\u50a8\u786c\u4ef6\u7279\u6027\uff1a\u968f\u673a I\/O \u8fdc\u6bd4\u987a\u5e8f I\/O \u6162\u3002\u4e3e\u4f8b\u6765\u8bf4\uff0c\u5bf9\u4e8e\u4e00\u4e2a\u5bfb\u9053\u5ef6\u8fdf\u4e3a 10ms\u3001\u541e\u5410\u91cf\u4e3a 100MB\/s \u7684\u786c\u76d8\uff0c\u8bbf\u95ee\u4e00\u4e2a\u968f\u673a 1KB \u6570\u636e\u6240\u9700\u7684\u5927\u7ea6\u65f6\u95f4\u662f 10ms\uff0c\u800c\u8bbf\u95ee\u4e0b\u4e00\u4e2a\u987a\u5e8f\u5757\u7684\u65f6\u95f4\u5927\u7ea6\u662f 10\u00b5s, \u968f\u673a\u4e0e\u987a\u5e8f\u5ef6\u8fdf\u7684\u6bd4\u7387\u662f\u00a01000:1\u3002<\/p>\n<ul data-id=\"u738a58b-1WcCjPkh\">\n<li data-id=\"ld70c578-DusUwB4w\">\u673a\u68b0\u786c\u76d8 (HDD): \u968f\u673a I\/O \u6d89\u53ca\u78c1\u5934\u5bfb\u9053\u548c\u76d8\u7247\u65cb\u8f6c\uff0c\u5ef6\u8fdf\u5728\u6beb\u79d2 (ms) \u7ea7\u522b\uff0c\u4f46\u662f\u987a\u5e8f I\/O \u8981\u5feb\u5f88\u591a<\/li>\n<li data-id=\"ld70c578-9FHCxvf9\">\u56fa\u6001\u786c\u76d8 (SSD): \u867d\u7136\u6ca1\u6709\u673a\u68b0\u90e8\u4ef6\uff0c\u968f\u673a\u8bfb\u7684\u6027\u80fd\u5927\u5927\u63d0\u5347\uff08\u5fae\u79d2\/\u00b5s, \u7ea7\u522b\uff09\uff0c\u4f46 SSD \u7684\u7269\u7406\u7279\u6027\u51b3\u5b9a\u4e86\u5b83\u4e0d\u80fd\u539f\u5730\u66f4\u65b0\uff0c\u5bf9\u4e00\u4e2a\u6570\u636e\u7684\u5199\u64cd\u4f5c\uff0c\u5fc5\u987b\u5148\u64e6\u9664\uff0c\u7136\u540e\u518d\u5199\u5165\u65b0\u7684\u6570\u636e\u3002\u64e6\u9664\u64cd\u4f5c\u975e\u5e38\u8017\u65f6\uff0c\u4e14 SSD \u6709\u64e6\u5199\u6b21\u6570\u5bff\u547d\u9650\u5236<\/li>\n<\/ul>\n<h4>1. \u653e\u5927\u578b\u95ee\u9898<\/h4>\n<p>\u56e0\u6b64\uff0c\u4e00\u4e2a\u597d\u7684\u5b58\u50a8\u7ed3\u6784\u8bbe\u8ba1\uff0c\u5fc5\u987b\u5c3d\u91cf\u907f\u514d\u968f\u673a\u5199\uff0c\u5e76\u5c06\u5199\u64cd\u4f5c (\u5c3d\u53ef\u80fd) \u8f6c\u5316\u4e3a\u987a\u5e8f\u5199\uff0c\u540c\u65f6\u5c3d\u53ef\u80fd\u907f\u514d\u5199\u653e\u5927\u3001\u8bfb\u653e\u5927\u3001\u7a7a\u95f4\u653e\u5927\u95ee\u9898\u3002<\/p>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/69241064088c07409fb7918cf47cfd3f81eae2.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<ul data-id=\"u738a58b-R8KccPpf\">\n<li data-id=\"ld70c578-oTIj29FT\">\u5199\u653e\u5927\uff1a\u7cfb\u7edf\u5199\u5165\u7684\u6570\u636e\u91cf \/ \u5e94\u7528\u8bf7\u6c42\u5199\u5165\u7684\u903b\u8f91\u6570\u636e\u91cf\uff1b\u5047\u8bbe\u5e94\u7528\u8bf7\u6c42\u5199\u5165 1MB \u6570\u636e\uff0c\u4f46\u5b58\u50a8\u7cfb\u7edf\u6700\u7ec8\u5411\u786c\u76d8\u5199\u5165 10MB \u6570\u636e\uff0c\u5199\u653e\u5927\u5c31\u662f 10<\/li>\n<li data-id=\"ld70c578-B4UwUbaq\">\u8bfb\u653e\u5927\uff1a\u7cfb\u7edf\u8bfb\u53d6\u7684\u6570\u636e\u91cf \/ \u5e94\u7528\u8bf7\u6c42\u8bfb\u53d6\u7684\u903b\u8f91\u6570\u636e\u91cf\uff1b\u5047\u8bbe\u5e94\u7528\u8bf7\u6c42\u8bfb\u53d6 1MB \u6570\u636e\uff0c\u4f46\u5b58\u50a8\u7cfb\u7edf\u6700\u7ec8\u5411\u786c\u76d8\u8bf7\u6c42 50MB \u6570\u636e\uff0c\u8bfb\u653e\u5927\u5c31\u662f 50<\/li>\n<li data-id=\"ld70c578-aFsvle3g\">\u7a7a\u95f4\u653e\u5927\uff1a\u5b58\u50a8\u7cfb\u7edf\u5360\u7528\u7684\u603b\u7a7a\u95f4 \/ \u5e94\u7528\u5b58\u50a8\u7684\u6709\u6548\u903b\u8f91\u6570\u636e\u7a7a\u95f4\uff1b\u5e94\u7528\u5b58\u50a8\u4e86 1GB \u7684\u6570\u636e\uff0c\u4f46\u7cfb\u7edf\u5360\u7528\u4e86 3GB \u7684\u78c1\u76d8\u7a7a\u95f4\uff0c\u90a3\u4e48\u7a7a\u95f4\u653e\u5927\u5c31\u662f 3<\/li>\n<\/ul>\n<p>\u8fd9\u4e09\u4e2a \u201c\u653e\u5927\u578b\u95ee\u9898\u201d \u5e76\u975e\u5b64\u7acb\uff0c\u800c\u662f\u76f8\u4e92\u5236\u7ea6\uff0c\u5f62\u6210\u4e86\u4e00\u4e2a\u7684 \u201c\u8bbe\u8ba1\u6743\u8861\u4e09\u89d2\u201d\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/1499c3329f3645b8e664907b570b957ac063c0.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>(1) \u5199\u653e\u5927\u548c\u7a7a\u95f4\u653e\u5927<\/strong><\/p>\n<p>\u4f8b\u5982 LSM-Tree Compaction \u7b56\u7565\uff0c\u6fc0\u8fdb\u7684 Compaction \u7b56\u7565\uff1a\u9ad8\u9891\u6b21\u7684 Compaction \u8fc7\u7a0b\u4f1a\u964d\u4f4e\u7a7a\u95f4\u653e\u5927\uff0c\u4f46\u4f1a\u5bfc\u81f4\u6781\u9ad8\u7684\u5199\u653e\u5927\uff1b\u4fdd\u5b88\u7684 Compaction \u7b56\u7565\uff1a\u4f4e\u9891\u6b21\u7684 Compaction \u8fc7\u7a0b\u4f1a\u663e\u8457\u964d\u4f4e\u5199\u653e\u5927\uff0c\u4f46\u4f1a\u5bfc\u81f4\u66f4\u9ad8\u7684\u7a7a\u95f4\u653e\u5927\u3002<\/p>\n<p><strong>(2) \u8bfb\u653e\u5927\u548c\u7a7a\u95f4\u653e\u5927<\/strong><\/p>\n<p>\u4f8b\u5982 LSM-Tree \u7684 SSTable \u8bbe\u8ba1\uff0c\u66f4\u5c11\u7684 SSTable \u6587\u4ef6\u7b56\u7565\uff1a\u91c7\u7528\u00a0Level-style compaction\uff0c\u6bcf\u5c42\u53ea\u6709\u4e00\u4e2a\u5927\u6587\u4ef6\uff0c\u53ef\u4ee5\u964d\u4f4e\u8bfb\u653e\u5927\uff0c\u56e0\u4e3a\u67e5\u8be2\u8def\u5f84\u66f4\u77ed\uff1b\u4f46\u4e3a\u4e86\u7ef4\u6301\u8fd9\u79cd\u7ed3\u6784\uff0c\u9700\u8981\u66f4\u6fc0\u8fdb\u7684 Compaction \u7b56\u7565\uff0c\u4ece\u800c\u589e\u52a0\u5199\u653e\u5927\u3002<\/p>\n<p>\u5141\u8bb8\u66f4\u591a\u7684 SSTable \u6587\u4ef6 (\u4f8b\u5982\uff0c\u91c7\u7528 Tiered-style compaction\uff0c\u6bcf\u5c42\u6709\u591a\u4e2a\u6587\u4ef6): \u5199\u64cd\u4f5c\u66f4\u7b80\u5355\uff08\u53ea\u9700\u4e0d\u65ad\u5806\u53e0\u65b0\u6587\u4ef6\uff09\uff0c\u5199\u653e\u5927\u66f4\u4f4e\u3002\u4f46\u8bfb\u64cd\u4f5c\u9700\u8981\u5728\u66f4\u591a\u6587\u4ef6\u4e2d\u67e5\u627e\uff0c\u8bfb\u653e\u5927\u66f4\u9ad8\u3002 B+ Tree vs. LSM-Tree \u7684\u6839\u672c\u6743\u8861:<\/p>\n<p><strong>(3) \u8bfb\u653e\u5927\u548c\u5199\u653e\u5927<\/strong><\/p>\n<p>B+Tree \u7684\u8bfb\u53d6\u653e\u5927\u4f4e\u4e8e LSM-Tree\uff0c\u800c LSM-Tree \u7684\u5199\u653e\u5927\u4f4e\u4e8e B+Tree\u3002<\/p>\n<p>\u8fd9\u4e5f\u662f B+ Tree vs. LSM-Tree \u7684\u6839\u672c\u6743\u8861: B+ Tree \u901a\u8fc7\u8f83\u9ad8\u7684\u5199\u6210\u672c\uff08\u968f\u673a\u5199\uff09\u6362\u53d6\u4e86\u6781\u4f4e\u7684\u8bfb\u653e\u5927\u548c\u7a7a\u95f4\u653e\u5927\uff1b\u800c\u53cd\u8fc7\u6765\uff0cLSM-Tree \u901a\u8fc7\u6781\u4f4e\u7684\u5199\u6210\u672c\uff08\u987a\u5e8f\u5199\uff09\u4e3a\u4ee3\u4ef7\uff0c\u63a5\u53d7\u4e86\u8f83\u9ad8\u7684\u8bfb\u653e\u5927\u3001\u5199\u653e\u5927\u548c\u7a7a\u95f4\u653e\u5927\u7b49 \u201c\u6f5c\u5728\u95ee\u9898\u201d\uff0c\u5e76\u901a\u8fc7\u540e\u53f0 Compaction \u8fdb\u7a0b\u6765\u89e3\u51b3\u8fd9\u4e9b \u201c\u6f5c\u5728\u95ee\u9898\u201d \u3002<\/p>\n<p>\u4e00\u822c\u6765\u8bf4\uff0c\u4e00\u4e2a\u6570\u636e\u7ed3\u6784\u6700\u591a\u53ef\u4ee5\u4f18\u5316\u5199\u653e\u5927\u3001\u8bfb\u653e\u5927\u3001\u7a7a\u95f4\u653e\u5927\u4e09\u4e2a\u95ee\u9898\u4e2d\u7684\u4e24\u4e2a\uff0c\u8fd9\u4e5f\u610f\u5473\u7740\uff0c\u4e00\u79cd\u6570\u636e\u7ed3\u6784\u4e0d\u592a\u53ef\u80fd\u5728\u4e09\u4e2a\u95ee\u9898\u4e0a\u90fd\u5b8c\u5168\u4f18\u4e8e\u53e6\u4e00\u79cd\u6570\u636e\u7ed3\u6784\u3002<\/p>\n<h4>2. B+ Tree<\/h4>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/51a1b848051e7ed3568584af83f674cc42f834.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>B+Tree \u5c5e\u4e8e\u539f\u5730\u66f4\u65b0\u578b\u7684\u6570\u636e\u7ed3\u6784\uff0c\u4e3a\u5feb\u901f\u8bfb\u53d6\u800c\u4f18\u5316\u3002<\/p>\n<p>\u901a\u8fc7\u5728\u5185\u90e8\u8282\u70b9\u4e2d\u4f7f\u7528\u8f83\u5927\u7684\u5ea6\u6570\u6765\u51cf\u5c11\u6811\u7684\u9ad8\u5ea6\uff0c\u5c06\u4f20\u7edf\u7684\u4e8c\u53c9\u6811\u7ed3\u6784 (\u53c8\u7626\u53c8\u9ad8\u578b) \u00a0\u53d8\u4e3a\u4e00\u68f5\u53c8\u77ee\u53c8\u80d6\u7684\u5e73\u8861\u6811\uff0c\u5145\u5206\u5229\u7528\u786c\u4ef6\u548c\u64cd\u4f5c\u7cfb\u7edf\u63d0\u4f9b\u7684\u7f13\u5b58\u5c40\u90e8\u6027\uff08\u9884\u8bfb\uff09\u548c\u78c1\u76d8\u8bf7\u6c42\u53cb\u597d\u987a\u5e8f\uff0c\u6765\u6700\u5c0f\u5316\u5b9a\u4f4d\u6570\u636e\u6240\u9700\u7684\u5bfb\u9053\u6b21\u6570\u3002<\/p>\n<p>B+tree \u80fd\u591f\u63d0\u4f9b\u6700\u4f18\u7684\u8bfb\u6027\u80fd\uff0c\u4e3b\u8981\u4f53\u73b0\u5728\u00a0I\/O \u6b21\u6570\u975e\u5e38\u5c11\u5e76\u4e14\u975e\u5e38\u7a33\u5b9a\uff0c\u8303\u56f4\u67e5\u8be2\u975e\u5e38\u9ad8\u6548\uff0c\u53f6\u5b50\u8282\u70b9\u4e4b\u95f4\u7684\u53cc\u5411\u94fe\u8868\u53ef\u4ee5\u5b9e\u73b0\u987a\u5e8f I\/O\u3002<\/p>\n<p>\u4f46\u662f B+tree \u7684\u5199\u6027\u80fd\u5e76\u4e0d\u597d\uff0c\u6bcf\u6b21\u5199\u64cd\u4f5c\u9700\u8981\u5148\u5b9a\u4f4d\u5230\u53f6\u5b50\u7ed3\u70b9\uff0c\u7136\u540e\u628a\u53f6\u5b50\u8282\u70b9\u7684\u6570\u636e\u8bfb\u51fa\u6765 -&gt; \u4fee\u6539 -&gt; \u518d\u5199\u56de\u53bb\u3002\u8fd9\u79cd\u539f\u5730\u66f4\u65b0\u7684\u65b9\u5f0f\u5f00\u9500\u8f83\u5927\uff0c\u56e0\u4e3a\u6574\u4e2a\u8fc7\u7a0b\u4e0d\u4ec5\u9700\u8981\u591a\u6b21\u5bfb\u9053\uff0c\u800c\u4e14\u5b58\u5728\u8f83\u9ad8\u7684\u5199\u653e\u5927\u3002\u4f8b\u5982\uff0c\u8981\u5728\u4e00\u4e2a 8KB \u7684\u8282\u70b9\u4e2d\u66f4\u65b0\u4e00\u6761 128B \u7684\u6570\u636e\u8bb0\u5f55\uff0c\u5fc5\u987b\u8bfb\u5199\u6574\u4e2a\u8282\u70b9\uff0c\u90a3\u4e48\u8fd9\u5c31\u4f1a\u5e26\u6765 64 \u500d (8KB \/ 128B) \u7684\u5199\u653e\u5927\u3002\u8fd9\u6837\u7684\u8bdd\uff0c\u5bf9\u4e8e\u4e00\u5757 640MB\/s \u5e26\u5bbd\u7684\u78c1\u76d8\u6765\u8bf4\uff0c\u6301\u7eed\u5199\u5165\u7684\u5e26\u5bbd\u6700\u591a\u53ea\u80fd\u8fbe\u5230 10MB\/s\u3002\u6240\u4ee5 B+tree \u5bf9\u4e8e\u5199\u5165\u5bc6\u96c6\u578b\u7684\u5e94\u7528\u5e76\u4e0d\u662f\u4e00\u4e2a\u597d\u7684\u9009\u62e9\uff0c\u5c24\u5176\u662f\u6bcf\u6761\u6570\u636e\u8bb0\u5f55\u6bd4\u8f83\u5c0f\u7684\u60c5\u51b5\u4e0b\u3002<\/p>\n<p>&nbsp;<\/p>\n<p>\u6570\u636e\u8bb0\u5f55\u548c\u5199\u653e\u5927\u6210\u53cd\u6bd4\u4f8b\uff0c\u5355\u6761\u6570\u636e\u8bb0\u5f55\u8d8a\u5c0f\uff0c\u5199\u653e\u5927\u5c31\u8d8a\u5927\u3002<\/p>\n<p>&nbsp;<\/p>\n<p>\u5bf9\u4e8e\u5e76\u53d1\u63a7\u5236\u6765\u8bf4\uff0cB+Tree \u4e2d\u7684\u540c\u4e00\u4e2a Key \u53ea\u6709\u4e00\u4efd\uff0c\u867d\u7136\u6811\u7ed3\u6784\u66f4\u5bb9\u6613\u8fdb\u884c\u52a0\u9501\/\u89e3\u9501\u64cd\u4f5c\uff0c\u4f46\u662f\u5b9e\u73b0\u6bd4\u8f83\u590d\u6742\uff0c\u5bf9\u6811\u7ed3\u6784\u7684\u4fee\u6539\uff08\u5982\u8282\u70b9\u5206\u88c2\/\u5408\u5e76\uff09\u9700\u8981\u4f7f\u7528\u7cbe\u7ec6\u7684\u9501\u6765\u4fdd\u62a4\u4e34\u754c\u533a\uff0c\u5bb9\u6613\u6210\u4e3a\u5e76\u53d1\u74f6\u9888\u3002<\/p>\n<p>\u7efc\u4e0a\uff0cB+Tree \u5bf9 HDD \u548c SSD \u90fd\u9002\u7528\uff0c\u9002\u5408\u8bfb\u591a\u5199\u5c11\u3001\u5bf9\u7a7a\u95f4\u653e\u5927\u975e\u5e38\u654f\u611f\u3001\u9700\u8981\u975e\u5e38\u7a33\u5b9a\u4e14\u4f4e\u5ef6\u8fdf\u7684\u70b9\u67e5\u8be2\u548c\u8303\u56f4\u67e5\u8be2\u7684\u573a\u666f\uff0c\u4f46\u662f\u5176\u968f\u673a\u5199\u7279\u6027\u5728 HDD \u4e0a\u8868\u73b0\u5f97\u66f4\u5dee\uff0c\u5178\u578b\u7684\u5e94\u7528\u573a\u666f\u5728\u4f20\u7edf\u5173\u7cfb\u578b\u6570\u636e\u5e93\uff0c\u4f8b\u5982 MySQL (InnoDB \u5b58\u50a8\u5f15\u64ce), PostgreSQL \u7b49\u3002<\/p>\n<h4>3. LSM-Tree<\/h4>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/79194b32920b5fa47ea745892b0f0c8a5f37d0.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>LSM-Tree \u5c5e\u4e8e\u00a0\u201c\u8ffd\u52a0\u5199\/\u5ef6\u8fdf\u66f4\u65b0\u201d\u00a0\u7684\u6570\u636e\u7ed3\u6784\u3002\u4e3a\u5feb\u901f\u5199\u5165\u800c\u4f18\u5316\u3002<\/p>\n<p>\u901a\u8fc7\u5c06\u6570\u636e\u5148\u5199\u5165\u5185\u5b58\u4e2d\u7684 MemTable\uff0cMemTable \u5199\u6ee1\u4e4b\u540e\uff0c\u53d8\u4e3a\u53ea\u8bfb\u7684 Immutable MemTable\uff0c\u7136\u540e Immutable MemTable \u4f5c\u4e3a\u4e00\u4e2a\u6574\u4f53\uff08SSTable\uff09\u987a\u5e8f\u5237\u5230\u78c1\u76d8\uff0c\u901a\u8fc7\u5199\u5165\u5185\u5b58\u4e2d\u7684 MemTable\uff08\u6781\u5feb\uff09\u5916\u52a0\u5199\u5165 WAL \u6765\u4fdd\u8bc1\u6301\u4e45\u6027\uff08\u4e00\u6b21\u987a\u5e8f\u5199\uff09\uff0c\u6574\u4e2a\u8fc7\u7a0b\u51e0\u4e4e\u90fd\u662f\u5185\u5b58\u64cd\u4f5c\u548c\u987a\u5e8f\u78c1\u76d8\u5199\u64cd\u4f5c\uff0c\u5199\u6027\u80fd\u975e\u5e38\u9ad8\u3002<\/p>\n<p>\u5f53\u7136\uff0cLSM-Tree \u5b9e\u73b0\u9ad8\u6027\u80fd\u5199\u5165\u7684\u540c\u65f6\uff0c\u4e5f\u5e26\u6765\u4e86\u8bfb\u653e\u5927\u548c\u5199\u653e\u5927\u95ee\u9898\uff0c\u5bf9\u4e8e\u8bfb\u64cd\u4f5c\u6765\u8bf4\uff0c\u9700\u8981\u4f9d\u6b21\u67e5\u8be2 MemTable\u3001\u591a\u5c42 SSTable\uff0c\u6700\u574f\u60c5\u51b5\u4e0b\uff0c\u9700\u8981\u67e5\u8be2\u6240\u6709\u5c42\u7ea7\u624d\u80fd\u627e\u5230\u6570\u636e\uff0c\u867d\u7136\u5355\u4e2a SSTable \u5185\u7684\u6570\u636e\u6709\u5e8f\uff0c\u4f46\u8de8\u5c42\u7ea7\u7684 SSTable \u6570\u636e\u65e0\u5e8f\uff0c\u8303\u56f4\u67e5\u8be2\u9700\u8981\u5728\u591a\u5c42 SSTable \u4e0a\u8fdb\u884c\u5f52\u5e76\u67e5\u627e\uff0c\u6bd4 B+ Tree \u590d\u6742\u4e14\u6548\u7387\u7565\u4f4e (\u4e3b\u8981\u53d6\u51b3\u4e8e LSM-Tree \u5c42\u7ea7\u6570\u91cf\u548c B+Tree \u7684\u9ad8\u5ea6)\uff1b\u5bf9\u4e8e\u5199\u64cd\u4f5c\u6765\u8bf4\uff0c\u4e00\u4e2a\u6570\u636e\u5728\u5176\u751f\u547d\u5468\u671f\u5185\u4f1a\u88ab\u591a\u6b21\u91cd\u5199\uff1aMemTable -&gt; L0 SSTable -&gt; L1 SSTable -&gt; &#8230; LN SSTable, \u6bcf\u6b21 Compaction (\u538b\u7f29) \u8fc7\u7a0b\u90fd\u4f1a\u8bfb\u51fa\u65e7\u6570\u636e\u5e76\u5199\u5165\u65b0\u6570\u636e\uff0c\u8fc7\u591a\u7684\u6570\u636e\u64e6\u9664\u6b21\u6570\u5bf9 SSD \u5bff\u547d\u5f88\u4e0d\u53cb\u597d\u3002<\/p>\n<p>\u5bf9\u4e8e\u5e76\u53d1\u63a7\u5236\u6765\u8bf4\uff0cLSM-Tree \u4e2d\u7684\u540c\u4e00\u4e2a Key \u4f1a\u5b58\u5728\u591a\u4efd (\u5177\u4f53\u53d6\u51b3\u4e8e Compaction \u8fdb\u7a0b\u7684\u9891\u6b21\u548c\u901f\u7387)\uff0c\u4e00\u822c\u4f7f\u7528 MVCC \u8fdb\u884c\u63a7\u5236\uff0c\u5b9e\u73b0\u4e5f\u76f8\u5bf9\u7b80\u5355\uff0c\u5199\u64cd\u4f5c\u662f\u65e0\u9501\u7684\uff08\u5199\u5165 MemTable \u53ef\u4ee5\u4f7f\u7528\u65e0\u9501\u6570\u636e\u7ed3\u6784\uff09\uff0c\u8bfb\u64cd\u4f5c\u662f\u65e0\u9501\u7684\uff08SSTable \u662f\u4e0d\u53ef\u53d8\u7684\uff09\uff0c\u4e3b\u8981\u51b2\u7a81\u53ef\u80fd\u53d1\u751f\u5728 Compaction \u8fdb\u7a0b\u3002<\/p>\n<p>\u7efc\u4e0a\uff0cLSM-Tree \u66f4\u9002\u5408 SSD\uff0c\u56e0\u4e3a\u5b83\u5c06\u968f\u673a\u5199\u8f6c\u6362\u6210\u4e3a\u6279\u91cf\u7684\u987a\u5e8f\u5199\uff0c\u7b26\u5408 SSD \u7684\u7269\u7406\u7279\u6027\uff0c\u9002\u5408\u5199\u591a\u8bfb\u5c11\u3001\u6570\u636e\u5199\u5165\u540e\u8f83\u5c11\u66f4\u65b0\u3001\u80fd\u591f\u5bb9\u5fcd\u7a0d\u9ad8\u7684\u8bfb\u5ef6\u8fdf\uff0c\u4f46\u9700\u8981\u6781\u9ad8\u7684\u5199\u5165\u541e\u5410\u91cf\u7684\u573a\u666f\uff0c\u5178\u578b\u7684\u5e94\u7528\u573a\u666f\u5728 NoSQL \u548c\u73b0\u4ee3\u5206\u5e03\u5f0f\u6570\u636e\u5e93\uff0c\u4f8b\u5982 LevelDB, RocksDB, TiDB (\u4f7f\u7528 RocksDB \u4f5c\u4e3a\u5b58\u50a8\u5f15\u64ce) \u7b49\u3002<\/p>\n<h4>4. \u5c0f\u7ed3<\/h4>\n<p>\u6211\u4eec\u53ef\u4ee5\u6839\u636e\u4e00\u4e9b\u5e94\u7528\u573a\u666f (\u56fe\u4e2d\u7684\u6bd4\u4f8b\u503c\u53ef\u4ee5\u6839\u636e\u5177\u4f53\u573a\u666f\u4fee\u6539)\uff0c\u53e0\u52a0\u57fa\u51c6\u6d4b\u8bd5\u7684\u7ed3\u679c\u6765\u9009\u62e9\u4e0d\u540c\u7684\u5b58\u50a8\u5f15\u64ce\u3002<\/p>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/661e3c9316ce4a746ad9998a29f730549f31a1.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<h3>\u4e8c\u3001\u975e\u4e3b\u6d41\u9635\u8425<\/h3>\n<p>B+ Tree \u548c LSM-Tree \u7684\u7ecf\u5178\u8bbe\u8ba1\uff0c\u4e3b\u8981\u4f18\u5316\u76ee\u6807\u662f\u51cf\u5c11 I\/O \u6b21\u6570\u548c\u5c06\u968f\u673a I\/O \u987a\u5e8f\u5316\u3002\u6211\u4eec\u53ef\u4ee5\u8bf4\uff0c\u81f3\u5c11\u5728 HDD \u786c\u4ef6\u4e0a\uff0cB+tree \u548c LSM-tree \u90fd\u5904\u4e8e\u6700\u4f18\u7684\u8bbe\u8ba1\u9886\u57df\u4e2d\u3002<\/p>\n<p>\u5f53\u7136\uff0c\u8fd9\u4e2a\u7248\u56fe\u9635\u8425\u5e76\u975e\u4ec5\u6b64\u4e24\u5bb6\u72ec\u5927\uff0c\u9664\u6b64\u4e4b\u5916\uff0c\u8fd8\u5b58\u5728\u5176\u4ed6\u91cd\u8981\u7684\u6570\u636e\u7ed3\u6784\uff0c\u5b83\u4eec\u5728\u7279\u5b9a\u573a\u666f\u4e0b\u751a\u81f3\u6bd4 LSM-Tree \u548c B+ Tree \u66f4\u4f18\u8d8a\u3002\u5f53\u786c\u4ef6\u7279\u6027\u53d1\u751f\u53d8\u5316\uff0c\u4f8b\u5982\uff0c\u51fa\u73b0\u4e86\u5ec9\u4ef7\u7684\u5927\u5bb9\u91cf\u5185\u5b58\u3001\u901f\u5ea6\u5ab2\u7f8e DRAM \u7684\u6301\u4e45\u5185\u5b58 (PMem, \u65ad\u7535\u540e\u4e0d\u4e22\u6570\u636e)\uff0c\u6216\u662f I\/O \u672c\u8eab\u5df2\u7ecf\u975e\u5e38\u5feb\u65f6 (\u4f8b\u5982 Nvme)\uff0c\u8fd9\u65f6\uff0c\u65b0\u7684\u4f18\u5316\u673a\u4f1a\u548c\u8bbe\u8ba1\u8303\u5f0f\u4fbf\u4f1a\u5e94\u8fd0\u800c\u751f\u3002<\/p>\n<p>\u4f8b\u5982\uff0c\u4ee5\u00a0Bitcask \u4e3a\u4ee3\u8868\u7684\u3001\u8ffd\u6c42\u6781\u81f4\u70b9\u67e5\u6027\u80fd\u7684\u00a0\u54c8\u5e0c\u7d22\u5f15\u00a0\u9635\u8425\uff0c\u5927\u91cf\u6df7\u5408\u548c\u7279\u5316\u7684\u6570\u636e\u7ed3\u6784\uff08\u4f8b\u5982 WiscKey\u3001\u5206\u5f62\u6811\u3001Trie \u7b49\uff09\u4e5f\u5728\u5404\u81ea\u7684\u7ec6\u5206\u9886\u57df\u5c55\u73b0\u51fa\u5f3a\u5927\u7684\u751f\u547d\u529b\uff0c\u4e0d\u65ad\u4e30\u5bcc\u548c\u6311\u6218\u7740\u5df2\u6709\u7684\u6570\u636e\u5b58\u50a8\u5f15\u64ce\u683c\u5c40\u3002<\/p>\n<h4>1. \u54c8\u5e0c\u7d22\u5f15<\/h4>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/d794439296ae3e3697e614dc7f77809b627184.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>B+ Tree \u548c LSM-Tree \u672c\u8d28\u4e0a\u90fd\u662f\u6709\u5e8f\u7ed3\u6784\uff0c\u5b83\u4eec\u7ef4\u62a4\u4e86 Key\/\u7d22\u5f15 \u7684\u6392\u5e8f\u4fe1\u606f\uff0c\u4ee5\u4fbf\u652f\u6301\u8303\u56f4\u67e5\u8be2\u3002\u4f46\u5982\u679c\u6211\u4eec\u653e\u5f03\u8303\u56f4\u67e5\u8be2\u8fd9\u4e2a\u9700\u6c42\uff0c\u53ea\u5173\u5fc3\u4e00\u4e2a\u6700\u57fa\u672c\u7684 KV \u5b58\u50a8\u95ee\u9898\uff1a\u201c\u67d0\u4e2a Key \u5bf9\u5e94\u7684\u6570\u636e\u5728\u54ea\u91cc\uff1f\u201d \u90a3\u4e48\u663e\u7136\uff0c\u4e00\u79cd\u66f4\u76f4\u63a5\u3001\u66f4\u5feb\u901f\u7684\u65b9\u6848\u5c31\u662f\u4f7f\u7528\u00a0\u54c8\u5e0c\u7d22\u5f15\u3002<\/p>\n<p>\u8fd9\u91cc\u4ee5 Bitcask \u4e3a\u4ee3\u8868\uff0c\u8fd9\u79cd\u54c8\u5e0c\u7d22\u5f15\u6570\u636e\u7ed3\u6784\u7684\u6838\u5fc3\u601d\u60f3\u662f\uff1a\u4f7f\u7528\u54c8\u5e0c\u51fd\u6570\u76f4\u63a5\u5c06 Key \u6620\u5c04\u5230\u6570\u636e\u7684\u4f4d\u7f6e\uff0c\u5b9e\u73b0 O(1) \u590d\u6742\u5ea6\u7684\u67e5\u627e\u3002<\/p>\n<p>Bitcask \u548c LSM-Tree \u7c7b\u4f3c\uff0c\u6240\u6709\u7684\u6570\u636e\uff08KV \u952e\u503c\u5bf9\uff09\u90fd\u4ee5\u8ffd\u52a0\u65b9\u5f0f\u5199\u5165\u4e00\u4e2a\u6216\u591a\u4e2a\u6570\u636e\u6587\u4ef6\u4e2d\uff0c\u53ef\u4ee5\u5c06 Bitcask \u770b\u4f5c LSM-Tree \u7684 \u201c\u7cbe\u7b80\u7248\u672c\u201d\uff0c\u8fd9\u4e2a \u201c\u7cbe\u7b80\u7248\u672c\u201d \u4e24\u4e2a\u4e3b\u8981\u7684\u7ea6\u675f\u6761\u4ef6\u662f\uff1a\u7b2c\u4e00\uff0c\u5168\u90e8 Key \u90fd\u5fc5\u987b\u653e\u5165\u5185\u5b58\uff1b\u7b2c\u4e8c\uff0c\u4e0d\u652f\u6301\u8303\u56f4\u67e5\u627e\u3002<\/p>\n<p>\u5bf9\u4e8e\u5199\u64cd\u4f5c\u6765\u8bf4\uff0c\u56e0\u4e3a\u5199\u5165\u662f\u7eaf\u7cb9\u7684\u987a\u5e8f I\/O\uff0c\u901f\u5ea6\u6781\u5feb\uff0c\u6570\u636e\u6587\u4ef6\u4e2d\u7684\u6761\u76ee\u5305\u542b Key\u3001Value\u3001\u65f6\u95f4\u6233\u7b49\u5143\u4fe1\u606f\uff1b\u5bf9\u4e8e\u8bfb\u64cd\u4f5c\u6765\u8bf4\uff0c\u53ef\u4ee5\u76f4\u63a5\u5728\u5185\u5b58\u7684\u54c8\u5e0c\u8868\u4e2d\u67e5\u627e Key\uff0c\u83b7\u5f97\u5176\u4f4d\u7f6e\u4fe1\u606f\uff08\u4e00\u6b21\u5185\u5b58\u8bbf\u95ee\uff0c\u6781\u5feb\uff09\uff0c\u7136\u540e\u6839\u636e\u4f4d\u7f6e\u4fe1\u606f\uff0c\u5728\u78c1\u76d8\u4e0a\u8fdb\u884c\u4e00\u6b21\u7cbe\u786e\u7684\u968f\u673a I\/O\uff0c\u76f4\u63a5\u8bfb\u51fa Value \u6570\u636e\u3002\u66f4\u591a\u7684\u7ec6\u8282\u53ef\u4ee5\u00a0\u67e5\u770b\u4e4b\u524d\u7684\u6587\u7ae0\u3002<\/p>\n<h4>2. \u9488\u5bf9\u7279\u5b9a\u786c\u4ef6\u6216\u573a\u666f\u7684\u6df7\u5408\u6570\u636e\u7ed3\u6784<\/h4>\n<p>LSM-Tree \u7684 Compaction \u8fc7\u7a0b\u4f1a\u5e26\u6765\u5de8\u5927\u7684\u5199\u653e\u5927\uff0c\u56e0\u4e3a\u6bcf\u6b21\u5408\u5e76\u8fc7\u7a0b\u90fd\u9700\u8981\u91cd\u5199 Key \u548c Value\u3002\u73b0\u5b9e\u7cfb\u7edf\u4e2d\u7684 Value \u901a\u5e38\u6bd4 Key \u5927\u5f97\u591a\uff08\u4f8b\u5982\uff0cKey \u662f\u4e00\u4e2a UUID\uff0cValue \u662f\u4e00\u5f20\u56fe\u7247\u6216\u4e00\u4e2a JSON \u6587\u6863\uff09\uff0c\u5373\u4f7f\u4e00\u4e2a Value \u672c\u8eab\u6ca1\u6709\u53d1\u751f\u4efb\u4f55\u53d8\u5316\uff0c\u4f46\u4ec5\u4ec5\u56e0\u4e3a\u5b83\u6240\u5728\u7684 SSTable \u6587\u4ef6\u9700\u8981\u88ab\u5408\u5e76\uff0c\u8fd9\u4e2a\u5de8\u5927\u7684 Value \u4e5f\u8981\u88ab\u5b8c\u6574\u5730\u4ece\u65e7\u6587\u4ef6\u8bfb\u53d6\u51fa\u6765\uff0c\u518d\u5b8c\u6574\u5730\u5199\u5165\u5230\u65b0\u6587\u4ef6\u4e2d\u3002<\/p>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/c83490360b17bcbd05d7649fb2227c90f0e41b.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>\u7406\u6240\u5f53\u7136\uff0cWiscKey \u7684\u6838\u5fc3\u601d\u60f3\u5c31 Key-Value \u5206\u79bb\u5b58\u50a8\uff0c\u7cbe\u51c6\u5730\u89e3\u51b3\u4e86 LSM-Tree \u5728\u5904\u7406\u5927 Value \u65f6\u7684\u5199\u653e\u5927\u95ee\u9898\uff0c\u63d0\u5347\u6027\u80fd\u548c SSD \u5bff\u547d\uff0c\u66f4\u591a\u7684\u7ec6\u8282\u53ef\u4ee5\u00a0\u67e5\u770b\u4e4b\u524d\u7684\u6587\u7ae0\u3002<\/p>\n<h4>3. \u5206\u5f62\u6811\u7d22\u5f15 (Fractal Tree Index)<\/h4>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/265eaaa46831aba60ab691cb6c1a71fabc8bc8.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>B-Tree (\u5305\u62ec B+Tree) \u7684\u95ee\u9898\u5728\u4e8e\u5199\u64cd\u4f5c\u662f\u540c\u6b65\u7684\u3001\u963b\u585e\u7684\uff0c\u4e00\u6b21\u8282\u70b9\u5206\u88c2\u53ef\u80fd\u4f1a\u5e26\u6765\u4e00\u8fde\u4e32\u7684 I\/O\uff0c\u5bfc\u81f4\u5199\u5ef6\u8fdf\u6296\u52a8\u5f88\u5927\uff0c\u5e76\u53ef\u80fd\u5f15\u53d1\u66f4\u4e25\u91cd\u7684 \u201c\u7ea7\u8054\u5f71\u54cd\u201d\u3002<\/p>\n<p>\u6839\u636e\u64cd\u4f5c\u7cfb\u7edf\u8bbe\u8ba1\u4e2d\u7684 Cache\/Buffer \u7684\u542f\u53d1\uff0c\u6211\u4eec\u53ef\u4ee5\u60f3\u5230\u7684\u4e00\u4e2a\u4f18\u5316\u65b9\u6848\u662f\uff1a\u9488\u5bf9\u5185\u90e8\u8282\u70b9\u8bbe\u7f6e\u5199\u7f13\u51b2\u533a\u3002\u800c\u8fd9\u4e00\u70b9\u6b63\u662f\u5206\u5f62\u6811\u7d22\u5f15\u7684\u6838\u5fc3\u601d\u60f3\uff1a\u5728 B-Tree \u7684\u5185\u90e8\u8282\u70b9\u4e2d\u8bbe\u7f6e\u7f13\u51b2\u533a\uff0c\u5c06\u66f4\u65b0\u64cd\u4f5c\u7f13\u5b58\u5728\u6811\u7684\u4e0a\u5c42\uff0c\u7136\u540e\u5c06\u66f4\u65b0\u64cd\u4f5c\u6279\u91cf\u5411\u4e0b\u4f20\u9012\uff0c\u53ef\u4ee5\u770b\u4f5c\u662f B-Tree \u548c LSM-Tree \u7684\u4e00\u79cd\u6df7\u5408\u4f53\u6570\u636e\u7ed3\u6784\u3002<\/p>\n<p>\u4e00\u4e2a\u77e5\u540d\u7684\u5f00\u6e90\u9879\u76ee\u662f\u00a0TokuDB, \u5176\u6838\u5fc3\u8bbe\u8ba1\u7406\u5ff5\u662f\u5c06 LSM-Tree \u7684\u5ef6\u8fdf\u66f4\u65b0\/\u7f13\u51b2\u8bbe\u8ba1\u5e94\u7528\u5230 B+ Tree \u4e0a\uff0c\u644a\u5e73 B-Tree \u4e2d\u7684\u5199\u64cd\u4f5c\u6210\u672c\u3002<\/p>\n<p>\u4ece\u6570\u636e\u89d2\u5ea6\u6765\u770b\uff0c\u5206\u5f62\u6811\u4ecd\u7136\u662f\u4e00\u68f5 B-Tree\uff0c\u4f46\u5176\u5185\u90e8\u8282\u70b9\u4e0d\u518d\u4ec5\u4ec5\u662f\u7d22\u5f15\uff0c\u8fd8\u9644\u5e26\u4e86\u6d88\u606f\u7f13\u51b2\u533a\u3002\u5bf9\u4e8e\u5199\u64cd\u4f5c\u6765\u8bf4\uff0c\u4e0d\u4f1a\u7acb\u5373\u53bb\u6700\u6df1\u5c42\u7684\u53f6\u5b50\u8282\u70b9\u4fee\u6539\u6570\u636e\uff0c\u800c\u662f\u5c06\u5199\u5165\u64cd\u4f5c\u5f53\u4f5c\u4e00\u4e2a \u201c\u6d88\u606f\u201d\uff08\u4f8b\u5982\uff0c\u63d2\u5165 (K,V)\uff0c \u6216\u5220\u9664 K\uff09\u88ab\u5199\u5165\u5230\u6839\u8282\u70b9\u7684\u7f13\u51b2\u533a\u4e2d\u3002\u5f53\u4e00\u4e2a\u8282\u70b9\u7684\u7f13\u51b2\u533a\u6ee1\u4e86\uff0c\u5c31\u5c06\u7f13\u51b2\u533a\u5185\u7684\u6d88\u606f\u00a0\u5237\u65b0\u5199\u5165\u00a0\u5230\u5176\u6240\u6709\u5b50\u8282\u70b9\u7684\u7f13\u51b2\u533a\u4e2d\uff0c\u8fd9\u4e2a\u8fc7\u7a0b\u5c31\u50cf \u201c\u6c34\u6d41\u201d \u4e00\u6837\u4f1a\u4e00\u76f4 \u201c\u4ece\u9ad8\u5230\u4f4e\u201d \u6301\u7eed\u8fdb\u884c\u4e0b\u53bb\uff0c\u76f4\u5230\u6d88\u606f\u6700\u7ec8\u5230\u8fbe\u53f6\u5b50\u8282\u70b9\uff0c\u5e76\u88ab\u5e94\u7528\u5230\u5b9e\u9645\u7684\u6570\u636e\u4e0a\u3002<\/p>\n<p>\u901a\u8fc7\u7f13\u51b2\u4f18\u5316\u53ef\u4ee5\u4f18\u5316\u4e3a\uff1a\u5927\u91cf\u7684\u968f\u673a\u5199\u88ab\u6279\u91cf\u5730\u3001\u5f02\u6b65\u5730\u5e94\u7528\u5230\u6811\u7684\u6df1\u5c42\u8282\u70b9\uff0c\u8fd9\u6837\u5355\u6b21\u5199\u64cd\u4f5c\u7684\u5ef6\u8fdf\u6781\u4f4e\uff08\u53ea\u9700\u5199\u5165\u6839\u8282\u70b9\u7684\u5185\u5b58\u7f13\u51b2\u533a\uff09\uff0c\u5199\u541e\u5410\u91cf\u5927\u5927\u63d0\u9ad8\u3002<\/p>\n<h4>4. \u524d\u7f00\u6811 (Trie \/ Radix Tree)<\/h4>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/s2.51cto.com\/oss\/202601\/14\/c31f82541f10c1f509e337931ee6f5cfff18e5.webp\" data-type=\"block\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>\u5f53 Key \u662f\u5b57\u7b26\u4e32\u7c7b\u578b\u65f6\uff0cB+ Tree \u7684\u6bd4\u8f83\u5f00\u9500\u4f1a\u53d8\u5927\uff0c\u4e14\u65e0\u6cd5\u5229\u7528\u591a\u4e2a Key \u4e4b\u95f4\u7684\u516c\u5171\u524d\u7f00\u3002<\/p>\n<p>Trie \u6811\uff08\u6216\u79f0\u5b57\u5178\u6811\u3001\u57fa\u6570\u6811\uff09\u6839\u636e Key \u7684\u524d\u7f00\u6765\u7ec4\u7ec7\u6570\u636e\uff0c\u53ef\u4ee5\u9488\u5bf9\u00a0\u5b57\u7b26\u4e32 Key \u548c\u53ef\u53d8\u957f Key\u00a0\u4e13\u95e8\u505a\u4f18\u5316\uff0c\u5bf9\u4e8e\u6709\u516c\u5171\u524d\u7f00\u7684 Key\u975e\u5e38\u9ad8\u6548\uff0c\u652f\u6301\u6309\u524d\u7f00\u7684\u8303\u56f4\u67e5\u8be2\u3002\u4f8b\u5982\uff0c\u00a0apple\u00a0\u548c\u00a0apply\u00a0\u8fd9\u4e24\u4e2a Key \u4f1a\u5171\u4eab\u00a0appl\u00a0\u8fd9\u6bb5\u516c\u5171\u524d\u7f00\u8def\u5f84\uff0c\u6781\u5927\u8282\u7701\u4e86\u7a7a\u95f4\u3002<\/p>\n<p>\u5bf9\u4e8e IP \u8def\u7531\u8868\u3001\u7f16\u7a0b\u8bed\u8a00\u4e2d\u7684\u5b57\u5178\u6570\u636e\u7ed3\u6784\u5b9e\u73b0\u7b49\u573a\u666f\uff0c\u524d\u7f00\u6811\u51e0\u4e4e\u662f\u6700\u4f18\u9009\u62e9\u3002<\/p>\n<h3>\u4e09\u3001\u603b\u7ed3<\/h3>\n<p>\u4ece\u66f4\u5e7f\u9614\u7684\u89c6\u89d2\u6765\u770b\uff0cB+ Tree \u548c LSM-Tree \u4e0d\u518d\u662f\u5b64\u7acb\u7684\u4e24\u4e2a\u9635\u8425\u548c\u5355\u4e00\u9009\u62e9\uff0c\u800c\u662f\u4f4d\u4e8e\u7531\u591a\u79cd\u8bbe\u8ba1\/\u6743\u8861\u7ef4\u5ea6\u6784\u6210\u7684\u4ea4\u53c9\u533a\u57df\u3002<\/p>\n<ul data-id=\"u738a58b-GoLnBEsK\">\n<li data-id=\"ld70c578-Gpb3c5dU\">\u6570\u636e\u6709\u5e8f\u8fd8\u662f\u65e0\u5e8f\uff0c\u51b3\u5b9a\u4e86\u662f\u5426\u652f\u6301\u9ad8\u6548\u7684\u8303\u56f4\u67e5\u8be2<\/li>\n<li data-id=\"ld70c578-rF4lwxLa\">\u6570\u636e\u539f\u5730\u66f4\u65b0\u8fd8\u662f\u8ffd\u52a0\u5199\uff0c\u51b3\u5b9a\u4e86\u8bfb\u5199\u6027\u80fd\u7684\u9009\u62e9\u503e\u5411<\/li>\n<li data-id=\"ld70c578-CX6dnJ06\">Key\/Value \u8026\u5408\u8fd8\u662f\u5206\u79bb\uff0c\u51b3\u5b9a\u4e86\u5199\u653e\u5927\u548c\u5bf9\u5927 Value \u7684\u5408\u5e76\u5904\u7406\u6548\u7387<\/li>\n<li data-id=\"ld70c578-xpVEJVJp\">\u6570\u636e\u540c\u6b65\u66f4\u65b0\u8fd8\u662f\u7f13\u51b2\/\u5f02\u6b65\u66f4\u65b0\uff0c\u51b3\u5b9a\u4e86\u5199\u5165\u64cd\u4f5c\u7684\u5ef6\u8fdf\u548c\u6296\u52a8<\/li>\n<\/ul>\n<p>\u6ca1\u6709\u94f6\u5f39\uff0c\u6839\u636e\u7cfb\u7edf\u573a\u666f\uff0c\u9009\u62e9\u5408\u9002\u7684\u6570\u636e\u7ed3\u6784\u5373\u53ef<\/p>\n<\/div>\n<p>\u6587\u7ae0\u6765\u81ea\uff1a51CTO<\/p>\n<\/div>\n<div class=\"pvc_clear\"><\/div>\n<p id=\"pvc_stats_28777\" class=\"pvc_stats total_only  \" data-element-id=\"28777\" style=\"\"><i class=\"pvc-stats-icon medium\" aria-hidden=\"true\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" version=\"1.0\" viewBox=\"0 0 502 315\" preserveAspectRatio=\"xMidYMid meet\"><g transform=\"translate(0,332) scale(0.1,-0.1)\" fill=\"\" stroke=\"none\"><path d=\"M2394 3279 l-29 -30 -3 -207 c-2 -182 0 -211 15 -242 39 -76 157 -76 196 0 15 31 17 60 15 243 l-3 209 -33 29 c-26 23 -41 29 -80 29 -41 0 -53 -5 -78 -31z\"\/><path d=\"M3085 3251 c-45 -19 -58 -50 -96 -229 -47 -217 -49 -260 -13 -295 52 -53 146 -42 177 20 16 31 87 366 87 410 0 70 -86 122 -155 94z\"\/><path d=\"M1751 3234 c-13 -9 -29 -31 -37 -50 -12 -29 -10 -49 21 -204 19 -94 39 -189 45 -210 14 -50 54 -80 110 -80 34 0 48 6 76 34 21 21 34 44 34 59 0 14 -18 113 -40 219 -37 178 -43 195 -70 221 -36 32 -101 37 -139 11z\"\/><path d=\"M1163 3073 c-36 -7 -73 -59 -73 -102 0 -56 133 -378 171 -413 34 -32 83 -37 129 -13 70 36 67 87 -16 290 -86 209 -89 214 -129 231 -35 14 -42 15 -82 7z\"\/><path d=\"M3689 3066 c-15 -9 -33 -30 -42 -48 -48 -103 -147 -355 -147 -375 0 -98 131 -148 192 -74 13 15 57 108 97 206 80 196 84 226 37 273 -30 30 -99 39 -137 18z\"\/><path d=\"M583 2784 c-38 -19 -67 -74 -58 -113 9 -42 211 -354 242 -373 16 -10 45 -18 66 -18 51 0 107 52 107 100 0 39 -1 41 -124 234 -80 126 -108 162 -133 173 -41 17 -61 16 -100 -3z\"\/><path d=\"M4250 2784 c-14 -9 -74 -91 -133 -183 -95 -150 -107 -173 -107 -213 0 -55 33 -94 87 -104 67 -13 90 8 211 198 130 202 137 225 78 284 -27 27 -42 34 -72 34 -22 0 -50 -8 -64 -16z\"\/><path d=\"M2275 2693 c-553 -48 -1095 -270 -1585 -649 -135 -104 -459 -423 -483 -476 -23 -49 -22 -139 2 -186 73 -142 361 -457 571 -626 285 -228 642 -407 990 -497 242 -63 336 -73 660 -74 310 0 370 5 595 52 535 111 1045 392 1455 803 122 121 250 273 275 326 19 41 19 137 0 174 -41 79 -309 363 -465 492 -447 370 -946 591 -1479 653 -113 14 -422 18 -536 8z m395 -428 c171 -34 330 -124 456 -258 112 -119 167 -219 211 -378 27 -96 24 -300 -5 -401 -72 -255 -236 -447 -474 -557 -132 -62 -201 -76 -368 -76 -167 0 -236 14 -368 76 -213 98 -373 271 -451 485 -162 444 86 934 547 1084 153 49 292 57 452 25z m909 -232 c222 -123 408 -262 593 -441 76 -74 138 -139 138 -144 0 -16 -233 -242 -330 -319 -155 -123 -309 -223 -461 -299 l-81 -41 32 46 c18 26 49 83 70 128 143 306 141 649 -6 957 -25 52 -61 116 -79 142 l-34 47 45 -20 c26 -10 76 -36 113 -56z m-2057 25 c-40 -58 -105 -190 -130 -263 -110 -324 -59 -707 132 -981 25 -35 42 -64 37 -64 -19 0 -241 119 -326 174 -188 122 -406 314 -532 468 l-58 71 108 103 c185 178 428 349 672 473 66 33 121 60 123 61 2 0 -10 -19 -26 -42z\"\/><path d=\"M2375 1950 c-198 -44 -350 -190 -395 -379 -18 -76 -8 -221 19 -290 114 -284 457 -406 731 -260 98 52 188 154 231 260 27 69 37 214 19 290 -38 163 -166 304 -326 360 -67 23 -215 33 -279 19z\"\/><\/g><\/svg><\/i> <img loading=\"lazy\" decoding=\"async\" width=\"16\" height=\"16\" alt=\"Loading\" src=\"https:\/\/aif.amtbbs.org\/wp-content\/plugins\/page-views-count\/ajax-loader-2x.gif\" border=0 \/><\/p>\n<div class=\"pvc_clear\"><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u4ece\u66f4\u5e7f\u9614\u7684\u89c6\u89d2\u6765\u770b\uff0cB+ Tree \u548c LSM-Tree \u4e0d\u518d\u662f\u5b64\u7acb\u7684\u4e24\u4e2a\u9635\u8425\u548c\u5355\u4e00\u9009\u62e9\uff0c\u800c\u662f\u4f4d\u4e8e\u7531\u591a\u79cd\u8bbe\u8ba1\/ [&hellip;]<\/p>\n<div class=\"pvc_clear\"><\/div>\n<p id=\"pvc_stats_28777\" class=\"pvc_stats total_only  \" data-element-id=\"28777\" style=\"\"><i class=\"pvc-stats-icon medium\" aria-hidden=\"true\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" version=\"1.0\" viewBox=\"0 0 502 315\" preserveAspectRatio=\"xMidYMid meet\"><g transform=\"translate(0,332) scale(0.1,-0.1)\" fill=\"\" stroke=\"none\"><path d=\"M2394 3279 l-29 -30 -3 -207 c-2 -182 0 -211 15 -242 39 -76 157 -76 196 0 15 31 17 60 15 243 l-3 209 -33 29 c-26 23 -41 29 -80 29 -41 0 -53 -5 -78 -31z\"\/><path d=\"M3085 3251 c-45 -19 -58 -50 -96 -229 -47 -217 -49 -260 -13 -295 52 -53 146 -42 177 20 16 31 87 366 87 410 0 70 -86 122 -155 94z\"\/><path d=\"M1751 3234 c-13 -9 -29 -31 -37 -50 -12 -29 -10 -49 21 -204 19 -94 39 -189 45 -210 14 -50 54 -80 110 -80 34 0 48 6 76 34 21 21 34 44 34 59 0 14 -18 113 -40 219 -37 178 -43 195 -70 221 -36 32 -101 37 -139 11z\"\/><path d=\"M1163 3073 c-36 -7 -73 -59 -73 -102 0 -56 133 -378 171 -413 34 -32 83 -37 129 -13 70 36 67 87 -16 290 -86 209 -89 214 -129 231 -35 14 -42 15 -82 7z\"\/><path d=\"M3689 3066 c-15 -9 -33 -30 -42 -48 -48 -103 -147 -355 -147 -375 0 -98 131 -148 192 -74 13 15 57 108 97 206 80 196 84 226 37 273 -30 30 -99 39 -137 18z\"\/><path d=\"M583 2784 c-38 -19 -67 -74 -58 -113 9 -42 211 -354 242 -373 16 -10 45 -18 66 -18 51 0 107 52 107 100 0 39 -1 41 -124 234 -80 126 -108 162 -133 173 -41 17 -61 16 -100 -3z\"\/><path d=\"M4250 2784 c-14 -9 -74 -91 -133 -183 -95 -150 -107 -173 -107 -213 0 -55 33 -94 87 -104 67 -13 90 8 211 198 130 202 137 225 78 284 -27 27 -42 34 -72 34 -22 0 -50 -8 -64 -16z\"\/><path d=\"M2275 2693 c-553 -48 -1095 -270 -1585 -649 -135 -104 -459 -423 -483 -476 -23 -49 -22 -139 2 -186 73 -142 361 -457 571 -626 285 -228 642 -407 990 -497 242 -63 336 -73 660 -74 310 0 370 5 595 52 535 111 1045 392 1455 803 122 121 250 273 275 326 19 41 19 137 0 174 -41 79 -309 363 -465 492 -447 370 -946 591 -1479 653 -113 14 -422 18 -536 8z m395 -428 c171 -34 330 -124 456 -258 112 -119 167 -219 211 -378 27 -96 24 -300 -5 -401 -72 -255 -236 -447 -474 -557 -132 -62 -201 -76 -368 -76 -167 0 -236 14 -368 76 -213 98 -373 271 -451 485 -162 444 86 934 547 1084 153 49 292 57 452 25z m909 -232 c222 -123 408 -262 593 -441 76 -74 138 -139 138 -144 0 -16 -233 -242 -330 -319 -155 -123 -309 -223 -461 -299 l-81 -41 32 46 c18 26 49 83 70 128 143 306 141 649 -6 957 -25 52 -61 116 -79 142 l-34 47 45 -20 c26 -10 76 -36 113 -56z m-2057 25 c-40 -58 -105 -190 -130 -263 -110 -324 -59 -707 132 -981 25 -35 42 -64 37 -64 -19 0 -241 119 -326 174 -188 122 -406 314 -532 468 l-58 71 108 103 c185 178 428 349 672 473 66 33 121 60 123 61 2 0 -10 -19 -26 -42z\"\/><path d=\"M2375 1950 c-198 -44 -350 -190 -395 -379 -18 -76 -8 -221 19 -290 114 -284 457 -406 731 -260 98 52 188 154 231 260 27 69 37 214 19 290 -38 163 -166 304 -326 360 -67 23 -215 33 -279 19z\"\/><\/g><\/svg><\/i> <img loading=\"lazy\" decoding=\"async\" width=\"16\" height=\"16\" alt=\"Loading\" src=\"https:\/\/aif.amtbbs.org\/wp-content\/plugins\/page-views-count\/ajax-loader-2x.gif\" border=0 \/><\/p>\n<div class=\"pvc_clear\"><\/div>\n","protected":false},"author":56,"featured_media":28780,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23,20,80],"tags":[2079],"class_list":["post-28777","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-23","category-20","category-80","tag-2079"],"_links":{"self":[{"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/posts\/28777","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/users\/56"}],"replies":[{"embeddable":true,"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/comments?post=28777"}],"version-history":[{"count":2,"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/posts\/28777\/revisions"}],"predecessor-version":[{"id":28781,"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/posts\/28777\/revisions\/28781"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/media\/28780"}],"wp:attachment":[{"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/media?parent=28777"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/categories?post=28777"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aif.amtbbs.org\/index.php\/wp-json\/wp\/v2\/tags?post=28777"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}